谋定而后动

Just Do It

破解碰到的两两异或问题

昨晚,不想睡觉,就在电脑上随便逛逛。

以前在看雪论坛(很好的论坛)下载过一堆玩意儿,有教程也有工具。那个时候,不知道自己是太浮躁了还是怎么的,没怎么用心研究。

昨晚就认认真真研究了直到早上4点,事实上我这几天都是这么晚睡的。

我开始看一点破解教程,然后试着破解教程里的几个样例程序。前面几个很简单,后面居然碰到一个让我没法下手的,我就去睡了。

今天早上起来继续,发现,原来这个玩意儿挺简单的。

首先,破解之后发现,程序是需要输入一个8位的序列号,这个序列号跟0x32(50)异或后得到一个新的序列号,然后这个新的8位的序列号两两异或得到4位的,4位的两两异或得到2位数,然后再异或得到一个数放在al寄存器里。暂时把这个数命名为al吧。然后将al与那个新的8位序列号异或之后得到一个最终8位序列号,最后将这个最终的结果与程序里存储的8位标准序列号相比较,相同则破解成功,否则序列号不正确。

当然,破解不是我的目的,写个算法给算出来才过瘾。

以python为准的。首先定义一个8位列表,s[0]…s[7] 存储输入的序列号。然后定义一个程序里原来的 8位标准序列号,o[0]…o[7],然后:
s[0] s[1] s[2] s[3] s[4] s[5] s[6] s[7] ^0x32 得到
n[0] n[1] n[2] n[3] n[4] n[5] n[6] n[7] 两两异或得到(第一个和第二异或,第三个和第四个异或,类推)
mid1[0] mid1[1] mid1[2] mid1[3] 再两两异或得到
mid2[0] mid2[1] 再两两异或得到
al 然后 将al 与 n[0]..n[7] 8个异或就得到最终的序列号。
当然这8个要跟 程序里定义好的8个o[0]…o[7]相同,这样就算序列号正确了。
这样看来,就是根据程序里的8个标准的序列号反推就能得到输入的序列号了。那怎么反推呢?
这个问题让我纠结了好久,最后,还是找到了规律。规律最后再说。首先给出自己写的算法,python版的。

1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
#反汇编时得到的标准序列号
o=[0x71,0x18,0x59,0x1b,0x79,0x42,0x45,0x4c]
#求al,过程很有趣
al=0
for i in o:
	al^=i
#初始化输入所需的序列号,并求之
s=[0]*8
for i in range(8):
	s[i]=al^o[i]^0x32
	print chr(s[i])

接下来是C语言版的程序,来自看雪论坛,源地址。

虽然我的得出的结论与此无关,但是还是给了我灵感的。

首先楼主给了一个他找来的代码,他说不懂其中的原理。很囧,其实看他接下来的程序,如果他分析一下就知道了,不过他没有。

首先是他找来的代码。注意,虽然代码不同,但是,这篇文章里所有的代码都是一个原理,最后我会说明。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
void main()
{
 char middle_1[4];
 char middle_2[2];
 char b[8]={0x71,0x18,0x59,0x1B,0x79,0x42,0x45,0x4C} ;
 middle_1[0]=b[0]^b[1];
 middle_1[1]=b[2]^b[3];
 middle_1[2]=b[4]^b[5];
 middle_1[3]=b[6]^b[7];
 cout<<middle_1[0]<<middle_1[1]<<middle_1[2]<<middle_1[3]<<endl;
 middle_2[0]=middle_1[0]^middle_1[1];
 middle_2[1]=middle_1[2]^middle_1[3];
 char al=middle_2[0]^middle_2[1];
 cout<<al<<endl;
 for(int i=0;i<=8;i++)
 {
  b[i]=b[i]^al;
  b[i]=b[i]^0x32;
  cout<<b[i]<<' ';
 }
}</stdio.h>

这个是正确的代码,但是还是没有我的那个简便。其实我那个python版的跟这个是一个原理。这个代码几乎和加密是反过来的,把程序里的标准8位序列两两异或,再运算,然后得到了al,最后通过al得到需要输入的8位序列;而我的是将标准8位序列全异或一遍,然后得到al。得到al了就能解决其他的问题了。

原理就在这里。这里面有个巧妙的地方,那就是异或的运算法则有交换律,分配律,和结合律。其中分配律和普通运算有点不同,要注意一下。但是只要交换律和结合律就能搞定了。

首先,假设输入的序列号是正确的。那么我们得到最终序列号就会跟程序里的标准的一样了。那就假设我们得到的最终序列号就是o[0]…o[7]。

那o[0]…o[7]这8个是怎么得到的呢,前面讲了是 al 与 n[0]…n[7]异或得到的。得到式子:
n[0]^al=o[0]
n[1]^al=o[1]

n[7]^al=o[7]

不难发现规律 o[0]^o[1] =(n[0] ^al)^(n[1]^al),根据结合律,o[0]^o[1] =n[0]^n[1]。哈哈,规律发现了,能得到 o[0]^o[1]^…o[7]=n[0]^n[1]…n[7]。

那怎么得到al呢,这就好办了,知道了结合律,那8个两两异或最后得到一个,还不是等价于8个相互异或得到一个么?

从这里可以看出,我的python版的程序和C语言版的是一个原理。

不过还有一种算法。这得追溯到看雪论坛的那位老大了,很有意思的人。他知道了异或的运算法则,但是走了弯路,居然在反推的时候,将8位输入序列和al设成9个未知数,而此时又有9个方程,那他就能推出这9个未知数了。虽然这个方法很笨,但是,我当时一筹莫展的时候可想不到这样的方法。所以,对于这位老大的研究精神我还是有点佩服的。贴出他最后的得出的程序,跟上面两个原理一样。再贴一下他的网址吧,http://bbs.pediy.com//showthread.php?t=66222&referrerid=207614那里有很有意思的推导过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
#include <conio.h>
void main()
{
	int i;
	char c[8]={0x71,0x18,0x59,0x1B,0x79,0x42,0x45,0x4C};
	char a[8];
	char b=0;
	for(i=0;i<8;i++)
		b^=c[i];
	for(i=0;i<8;i++)
		{
			a[i]=c[i]^b^0x32;
		printf("%c",a[i]);
	}
	getch();
}</conio.h></stdio.h>

Comments