首页
社区
课程
招聘
[原创]The XOR Secret in Our Computer System--延伸討論
2009-10-21 13:19 8108

[原创]The XOR Secret in Our Computer System--延伸討論

2009-10-21 13:19
8108
接原帖46的讨论:http://bbs.pediy.com/showthread.php?t=87916&page=4

Algorithm : 由我寫的,證明也由我完成。
以下這個是將 Lemma 4 及 Lemma 5 合併寫成一個 mathematical expression/equation.


哦,看这个我明白这段程序是什么意思了,也就说验证下仅有在这个条件满足时才是成立的吧,我试试看。

试了下,发现并不仅仅在上面那个情况下成立。因为没能看到 Lemma 5 中关于偶数相等时的详细定义,我只能根据上面这个条件说说我的理解。
按版主L4和L5合并后的思路,当且仅当【A,B都是奇数】,或【A,B是偶数,且能被4整除但不是8的倍数】这两种情况下成立才有相等吧,但我觉得这个同为偶数时的定义漏掉了很多情况,比如:2 xor 2, 16 xor 16 ...

当然不一定A,B相等时才出现xor相等,其实 2 xor 6 也是和 -2 xor -6 相等的。也许版主用的是Windows计算器确定的结果,我觉得那个算法实际上是经过符号位优化后的,我举个例子吧:
比如 2 xor 6,运行calc.exe,先算 2 xor 6,结果显然是4。然后接着算 -2 xor -6,这时问题就来了,算出的结果是 -4
我们从一个32位寄存器的 xor 操作来看,2,-2 和 6,-6 在寄存器里是这样表示的:
2 = 0x00000002 6 = 0x00000006
-2 = 0xFFFFFFFE -6 = 0xFFFFFFFA

你计算 0xFFFFFFFE xor 0xFFFFFFFA 看看,这个结果是多少?不是 -4 (0xFFFFFFFC) 吧。

所以 2 xor 6 也是满足条件的,但显然不在L4 和 L5合并后那个推论中。这样的例子还能举很多,不知道版主关于A,B同为偶数且xor相等的条件是如何定义?

[培训]内核驱动高级班,冲击BAT一流互联网大厂工 作,每周日13:00-18:00直播授课

收藏
点赞7
打赏
分享
最新回复 (13)
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-21 14:22
2
0
1) 奇數很明顯;至於偶數,就是那個數學式中可以整除4, 但不能整除8的那個判斷式。
,(2) ⊕ (6) = (-2) ⊕ (-6) ===>這剛好是個很棒的例外 exception.
雪    币: 232
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
deryope 1 2009-10-21 17:26
3
0
1. A,B 两数相等应该也算是一种特例,因为 0 没有正负之分
2. 考虑偶数的情况下,发现虽然A,B取8以内只有 2 xor 6 = (-2) xor (-6) 这个特例,但是8以外这样的情况还很多,比如:6 xor 10, 6 xor 14, ..., 86 xor 90, ...
6 xor 10, (00000006 xor 0000000A) = (FFFFFFFA xor FFFFFFF6)
86 xor 90, (00000056 xor 0000005A) = (FFFFFFAA xor FFFFFFA6)


利用之前那个TestXor()函数,写了个程序枚举A, B同为偶数时的例外情况。附件中是100以内的输出结果和源码(源代码没有整理过,随便看看吧)
上传的附件:
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-21 21:06
4
0
觀察  0 到 7 的 two's complement,然後看看結果如下:
0)
       000
Not
-----------
       111
+        1
-----------
      1000

1)
       001
Not
-----------
       110
+        1
-----------
       111

2)
       010
Not
-----------
       101
+        1
-----------
       110

3)
       011
Not
----------
       100
+        1
-----------
       101

4)
       100
Not
-----------
       011
+        1
-----------
       100

5)
       101
Not
-----------
       010
+        1
-----------
       011

6)
       110
Not
-----------
       001
+        1
-----------
       101
      
7)
       111
Not
-----------
       000
+        1
-----------
       001

0) 的結果之 bits 型態為 1000,最後的 3 個 bits 為 0.
4) 的結果之 bits 型態為 100,最後的 3 個 bits 為 0.

以 4) 為例子,轉換前的 bits 型態是 100,轉換後的 bits 型態還是 100,因此轉換前、後的bits 型態都一樣。

以 0)為例子,轉換前的 bits 型態是 000,轉換後的 bits 型態是 1000,取最右邊 3 個 bits 為 000,所以轉換前、後的 bits 型態也都一樣。
可是,若 integer 為 zero ,那意義不大;因此,只能把 3 個 bits length 變成 4 bits length,那就變成 1000 的型態。而最右邊的 bits length 若為 1000 型態者,必與 8 有關。

===== 接著討論 deryope 的例外 sample =====
討論以下 pairs 的關係,例如討論 2 跟 6 關係,我用 (2,6); (6,10); (6,14); (10,14); (86,90) 總共 五個 pairs。
g c d 為 greatest common divisor 之縮寫。
g c d(2,6)=2
g c d(6,10)=2
g c d(6,14)=2
g c d(10,14)=2
g c d(86,90)=2

我所提的證明,保證條件成立,也有規則可循。
deryope 所提的例子,條件也成立,但有沒固定規則可循?我不知道,唯一我能找出這個規則的是 g c d(a,b)=2.

補充1:
將 (2,6) 同乘 3 倍,為 (6,18)
g c d(2,6)=2.
g c d(6,18)=6.
2⊕6=-2⊕-6.
6⊕18=-6⊕-18.
可見g c d(a,b)=2 不是唯一可做為判斷的條件。
雪    币: 377
活跃值: (10)
能力值: ( LV9,RANK:170 )
在线值:
发帖
回帖
粉丝
宙斯 4 2009-10-22 00:23
5
0
楼主是台湾或香港人?
雪    币: 101
活跃值: (10)
能力值: ( LV2,RANK:10 )
在线值:
发帖
回帖
粉丝
carollii 2009-10-22 09:10
6
0
下次用简体中文吧
雪    币: 232
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
deryope 1 2009-10-22 09:37
7
0
先说明这个思路不是我想出来的,昨天吃饭时和几个哥们聊起这个问题,他们倒是从二进制角度解释了这一现象。其实版主的思路已经很接近了,就是看二进制的最后几位来确定xor后结果是否相等。

我们知道『负数 = 正数取反+1』,因为偶数取反+1后会有进位,导致了可能 (A ⊕ B) != (-A ⊕ -B)
总结来说,就是看二进制进位后停在哪一位上。一旦两个数+1操作进位的位数相同,就产生 (A ⊕ B) = (-A ⊕ -B)

举个例子:

我们先看偶数的情况:
2 => 0x2 => (0010)b
6 => 0x6 => (0110)b
14 => 0xE => (1110)b

原始值 取反结果
2 => (... 0000 0010)b => (1111 ... 1111 1101)b
6 => (... 0000 0110)b => (1111 ... 1111 1001)b
+1操作导致进位
取反结果 +1后
2 => (1111 ... 1111 1101)b +1 => (1111 ... 1111 1110)b
6 => (1111 ... 1111 1001)b +1 => (1111 ... 1111 1010)b
| |
注意这个0 进位操作到这个地方为止,进位1次

两个数进位的位数相同,所以XOR后的结果相等。同理可以推出 14 (1110)b 与 2、6 之间异或也是满足 A ⊕ B = -A ⊕ -B 的。

类推这样的数有:

2 (0000 0010)b
6 (0000 0110)b
10 (0000 1010)b
14 (0000 1110)b
18 (0001 0010)b
22 (0001 0110)b
26 (0001 1010)b
.. ...

这还只是进位1次的情况,按照上面说的只要进位位数相同就能满足条件,于是还能推出:

4 (0000 0100)b
12 (0000 1100)b
20 (0001 0100)b
28 (0001 1100)b
.. ...

这是进位两次的数(也就是4的倍数),还能推出进位3次、4次... 总之无穷无尽。


按照这个理论,两个数都是奇数的情况也很容易解释了,奇数取反后末尾为 (...0)b,+1后不会进位(也就是进位0次的情况),所以100%相等。一奇一偶也一样,奇数取反+1不进位,但偶数却进位了(也就是进位的位数不相同),所以异或后结果不相等。
雪    币: 232
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
deryope 1 2009-10-22 09:43
8
0
不是,不过繁体字也能看懂吧,文言文不都是繁体字?
总之随意了,尊重个人习惯,用繁体用简体都不影响交流

忘了,附带一个显示两个数计算结果和16进制的程序,方便验证结果。
  u_int32_t a, b;
  u_int32_t temp;
  do {
    a = 0; b = 0;
    printf("\n请输入两个正整数A,B (以逗号分割): "); scanf("%d,%d", &a, &b);
    // 输出下计算结果
    temp = (-a)^(-b);
    printf("%d xor %d, C1=0x%.8X, C2=0x%.8X\n", a, b, (a^b), temp);
    printf("  (%.8X xor %.8X) = (%.8X xor %.8X)\n", a, b, -a, -b);
  }while ( a || b );


之前那个枚举这些数的程序,删掉了那些没用的代码,具体看附件中的程序
上传的附件:
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-22 11:02
9
0
請問有沒發現 一個跟 4 影關係,另一個跟8有關係,都差,都差8.
雪    币: 2071
活跃值: (77)
能力值: ( LV9,RANK:180 )
在线值:
发帖
回帖
粉丝
sessiondiy 4 2009-10-22 11:47
10
0
看到后面那个, 我就想到Innova问的 是4的倍数, 但不要8的倍数
那不就是 4*奇数
雪    币: 232
活跃值: (10)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
deryope 1 2009-10-22 12:46
11
0
嗯,这两个例子刚好一个是+4,另一个是+8,类推3次进位的就是+16了(8,24,40,...)。
至于间隔多少,是由二进制的尾数决定的:
前三个:
 2  .... ..[COLOR="Red"]1[/COLOR]0    (+ 4) 2,6,10,14...
 4  .... .[COLOR="red"]1[/COLOR]00    (+ 8) 4,12,20...
 8  .... [COLOR="red"]1[/COLOR]000    (+16) 8,24,40...
再往后继续乘2(1继续向前挪动):
16  ...[COLOR="red"]1[/COLOR] 0000    (+32) ...
32  ..[COLOR="red"]1[/COLOR]0 0000
...


二进制的角度很容易理解吧,至于里面的数学规律,我就不继续想了...



为什么不考虑8的倍数?2的倍数呢?
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-30 08:10
12
0

上传的附件:
雪    币: 271
活跃值: (90)
能力值: ( LV4,RANK:50 )
在线值:
发帖
回帖
粉丝
qwert123 1 2009-10-30 09:25
13
0
很感兴趣,但是感觉理论性太强,感觉高深。

不知道哪位可以用简单的应用做例子?

以前我认为软件里的XOR跟没加密一样 - 其实是因为算法可以直接跟踪。

但是,在实际应用里,给你一段XOR之后的密文及部分明文,要求反推算法,就蒙了。
因为,这时候没有程序的算法可以让你跟踪 - 纯粹是部分密文及部分明文,这时候成了文字算法游戏了。
对这种情况,上面对XOR的讨论能给与帮助吗?

现实中,有很多这样脱离程序 - 或者我们无法跟踪内存运行的程序,比如网站上的加密 -我们不可能去调试服务器上的程序。

我希望多举点大家感兴趣的应用实例,因为太理论化,不太好懂,呵呵,谢谢大家的讨论,哪位继续给点指教一并谢谢了。

很希望哪位帮助指点一下:
  在知道部分密文及部分明文的情况下,逆向XOR算法有没有什么简便些的通用方法?
以前尝试过用暴力逆推的方法,就是类似于从0到最大整数逐个推演,但是感觉不通用,有时会误入歧途。

----------------
感谢rockinuk的回复,我想可能我发错地方了,所以转贴调试论坛了,呵呵。
这里不太适合我这种实用主义者讨论的地方,谢谢你的书单,也感叹各位的高深。
雪    币: 2096
活跃值: (100)
能力值: (RANK:420 )
在线值:
发帖
回帖
粉丝
rockinuk 8 2009-10-30 10:30
14
0
游客
登录 | 注册 方可回帖
返回