XOR

注意，本文禁止轉載！

今天畫油畫時，心血來潮，將衣帶上的花紋線水平地作 XOR 運算，
一條接一條的畫著，柔柔軟軟，效果不錯。
順便想到在玩電腦的時候，也幾度見到 Xor 的身影。

xor 是 Exclusive OR 的縮寫，
像 MUTEX 的 X 也是 Exclusive (mutual exclusive)
它是雙運算子函數，很多語言都有提供，如：

     X xor Y                 --> by VB
     X ^ Y == (X&Y)^(~X&~Y)  --> by C and C++ and C# and Java
     xor X,Y                 --> by Assembly
     ::operator^(X,Y)        --> by C++

(0). SSI(Small Scale Integration)中，
      常用 XOR+AND或OR gate 做出 universal gate..
   
(1). 由 True table 可看出它是個奇函數， 
     所以它可以驗證是否 binary 變數有奇數個1，比如:

      #define  hasOdd_1(n)  ((n)^0) 

(2). 可用來交換變數，像是:

      #define  swap(a,b)    (a)^=(b); (b)^=(a); (a)^=(b);
      
     或：
      #define  swap(a,b)    (a)^=(b)^=(a)^=(b);

(3). 將變數清成0: 

      #define  cls(n)       (_asm xor (n),(n))


在密碼學中，XOR 出現的次數可說是多到有濫用的嫌疑，隨便想就有:

(4). Vigenere 的 autokey cryptSystem， 
      有 plaintext 與 key 具相同字元頻率分布的問題，
      AT&T 的 Gilbert Vernam 在 1918 年說:
      "令 Ci = Pi^Ki 就行了!"
      Ci = CryptText 的第 i 個 bit
      Pi = PlainText 的第 i 個 bit
      Ki = key  的第 i 個 bit
      (註: 後來大兵 Joseph Mauborgane 將之改良成著名的 one-time pad
       架構, 我私下把它叫做 discard pad: 用完即可丟架構)

(5). 將 Block cipher 轉成 Stream cipher:
      1945 年，偉大的 Claude Shannon 提出 product cipher 
      (乘積加密法) 的兩大建構方式， 
      一個是 confusion (混淆，相con-，融合fusion)
      一個是 diffusion (擴散，非diff-，融合fusion)
      diffusion 就是讓一個明文位元可影響到多個密文位元,
      最簡單的方式為:

           bool C[64], P[64], IV;    //P[i]=第i個明文位元 
           cin >> IV;                //C[i]=第i個密文位元
           while (cin >> C[i]);      //IV=Initial Vector
           C[0] = P[0] ^ IV;
           for( i=1; i<n; i++)                      
                C[i] = C[i-1] ^ P[i];      
      
      ECB(Electronic Codebook Mode) 為應付大流量資料
      而提出的 CBC(Cipher Block Chaining Mode) 就是此類的應用。
      更進一步地, CFB(Cipher FeedBack Mode)，
      可將 Block cipher 轉成 Stream cipher， 
      使得每加密完一個字元後，便可將它立即送出，
      這要如何辦到!? 就像這般：

           char C[64], P[64];        //P[i]=第i個明文字元
           int  IV; 
           cin >> IV;                //C[i]=第i個密文字元
           while (cin >> C[i]);      //IV=Initial Vector
           C[0] = P[0] ^ ((IV & 0xf000)>>24);
           send( C[0] );             //將 C[0] 送出
           IV <<= 8; 
           IV |= C[0]; 
           for( i=1; i< n; i++)
           {                      
                C[i] = P[i] ^ ((IV & 0xf000)>>24);
                send( C[i] );
                IV <<= 8; 
                IV |= C[i];                
           }
     解密時, 反著作就行了.

(6). 對於 DES 等的 Differential Attack (差異破解法):
      令DES明文區 binary block = Mi, 1<i<18
      Ki = key  的第 i 個 bit
      則 Mi+1 = Mi-1 ^ f(Mi,Ki)     ,i=1~16, f=加密函數,為已知
      再取得另一明文訊息 M'，
      令 XOR difference (XOR差距) Xi = Mi ^ M'i
      則 X(i+1) = M(i-1) ^ M'(i+1)
       = [M(i-1) ^ f(Mi,Ki)] ^ f(M'i,Ki)
      
      假設 key 不變，輸入M的XOR difference是 X_in，
      其輸出的XOR difference是 X_out，
      而 X_in 導致 X_out 的機率很高，
      也就是 X(i-1) 與 X(i) 出現機率很高的話，
      則 X(i+1) 出現機率也會很高，
      咱便可比對多組輸入輸出的 XOR difference，求出 key。