-
-
[原创]The XOR Secret in Our Computer System
-
2009-5-5 02:46
-
|
|
|---|---|
|
|
|
|
|
|
|
|
 我去好好消化啦
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
很易懂，写得不错
(A) ⊕ (B) ＝ (-A) ⊕ (-B) 就是说虽然负数虽然在我们看来前面多了个负号，但是计算机是通过在补码来表示的，导致两个负数都补1后XOR结果相同。 嗯，好像可以减少一半的探测次数，得到 (-A) 也就知道 (A) 了。 |
|
|
|
|
|
写程序下才发现之前我完全没懂
 原来XOR相同只在一定条件下成立。我测试了(整数) -100000 ～ 100000 以内的数xor： 两个数都是奇数时是100%， 直接看代码吧，附上工程和可执行程序： #include <stdio.h>
#include <stdlib.h>
#define u_int32_t unsigned int
void printXORImpact(u_int32_t nSize)
{
int i, j;
u_int32_t temp;
u_int32_t count = 0, sum = 0;
if (nSize == 0) return;
for (i = 0; i < nSize; i++)
{
for (j = 0; j < nSize; j++)
if ((i % 2 != 0) && (j % 2 != 0)) // 奇数
//if ((i % 2 == 0) && (j % 2 == 0)) // 偶数
{
temp = (-1*i)^(-1*j);
if (temp == (i^j)) {
count++;
//printf("Impact at (%d xor %d)\n", i, j);
}
sum++;
}
}
printf("XOR Impact %d/%d times, %.2f%%\n", count, sum, (double)count/sum*100);
return;
}
int main(int argc, char *argv[])
{
printXORImpact(1000);
system("PAUSE");
return 0;
}
|
|
|
|
|
|
看过那篇paper了
以奇数来说，当两两均为奇数时， (A⊕ B) = (-A⊕ -B) 条件永远成立。当两两均为偶数时，要符合特定条件才会成立。由于计算过程，有点复杂，非本文探讨主轴，因此未列其中 两个数都是奇数的概率是100%吧，那篇论文的 Lemma 4 不就是在证明奇数时相等？倒是 Lemma 5 没见着，估计版主是截掉了  另外，为什么两偶数是50%？我用程序穷举了-10000 ～ 10000 之间的数XOR（就是上面程序，把偶数那个if的注释去掉），结果是33.32%。 一奇一偶倒是0%，这样加起来是 100%*0.25 + 33.32%*0.25 = 33.3% |
|
|
1) 我這裏的機率 二分之一，四分之一，不同於你的 機率100%。
2) 當兩數A, B 均為奇數時，必有 (A) ⊕ (B) ＝ (-A) ⊕ (-B) 這樣的現象。 3) 當兩數A, B 為一奇一偶數時，不會有 (A) ⊕ (B) ＝ (-A) ⊕ (-B) 這樣的現象。 4) 當兩數A, B 均為偶數時，在某種條件下存在 (A) ⊕ (B) ＝ (-A) ⊕ (-B) 這樣的現象。 這個機率怎麼算呢? 請看以下這個圖的算法：  想一想 s 不是偶數就是奇數，對不對? 想一想 r 不是偶數就是奇數，對不對? 那，當 r 及 s 均為奇數，機率就是 四分之一。 那，當 r 及 s 為一奇一偶數，機率就是 二分之一。 那，當 r 及 s 均為偶數，機率就是 四分之一。 小結，這個無關乎窮舉法。 Lemma 5 是我漏掉了，改天等 paper 登出來後，再補上。 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
這個 program 是把 38樓 - 40樓 的關鍵內容呈現出來。
之前提到的 Lemma 4 及 Lemma 5，今天用 Language C 來實現。 Algorithm : 由我寫的，證明也由我完成。 以下這個是將 Lemma 4 及 Lemma 5 合併寫成一個 mathematical expression/equation.  Program : 由 nudtsong 完成 coding。 Revised 1: 由副壇主 Ivanov 做第一次改版 ，修正一個小地方。 // test1.c : Design by Rock, Nudtsong and Ivanov in Oct 21 2009.
//
#include "stdio.h"
int main(int argc, char argv[])
{
unsigned int a = 0;
unsigned int b = 0;
unsigned int c1 = 0;
unsigned int c2 = 0;
LABEL_INPUT:
// User input integer
printf("Please input two integers: A, B must be both odd or even numbers\n");
printf("A=");
scanf("%d", &a);
printf("B=");
scanf("%d", &b);
// Does it check A,B one odd and one even number?
if (((0 == (a % 2)) && (0 != (b % 2)))
|| ((0 != (a % 2)) && (0 == (b % 2))))
{
printf("error:A, B must be odd or even numbers\n");
goto LABEL_INPUT;
}
else if ((0 != (a % 2)) && (0 != (b % 2))) // If A,B are odd numbes
{
printf("A, B are odd numbers\n");
c1 = a ^ b;
c2 = (-a) ^ (-b);
printf("C1=%d, C2=%d\n", c1, c2);
}
else // If A, B are even numbers
{
//printf("A, B are even numbers\n");
if ((0 == (a % 4)) && (0 == (b % 4))) {
if ((0 != (a % 8)) && (0 != (b % 8)))
{
// A,B are divisible by 4 rather than 8
printf("A, B be divided 4 and be not divided 8\n");
c1 = a ^ b;
c2 = (-a) ^ (-b);
printf("C1=%d, C2=%d\n", c1, c2);
}
else {
printf("A or B is divisible by 8\n");
goto LABEL_INPUT;
}
}
else {
printf("A or B is not divisible by 4\n");
goto LABEL_INPUT;
}
}
system("pause");
return 0;
}
以上的 code，主要驗證我提出的想法與關點是正確的，並沒有對 code 進行 optimize，請見諒。 這個 code 可以和 【分享+讨论】对 XOR_password 及XOR_cryptanalyiss 等相关论文研讨。(No. 2)相呼應。 |
|
|
|
|
|
|
|
|
|
|
|
|
