標籤：

如何理解「異或（XOR）」運算在計算機科學中的重要性？

12-30

在學邏輯學的時候，基本的邏輯運算是非、與、或，且並沒有得到特別的強調，而且事實上異或可以由這三個邏輯運算符表出。可是在計算機領域，異或似乎處於與非、與、或並列的關係，例如c語言的位運算符中就有專門的異或運算符：「^「。

一直不清楚是什麼原因使異或在計算機領域獲得了這種重要性，是來源於門電路的設計呢還是來源於代數方面的某些性質？

關於XOR加密的應用 @阿里聚安全 裡面的回答了一些，但是並沒有完全說清楚。(知乎公式編輯有毒，經常不顯示，什麼時候可以用markdown啊)

對於任意一個長度（比如為n個二進位位）的密文-明文對 (e,o) ，我們可以考察一下它們的概率關係，由貝葉斯公式很容易得到：P(o|e)P(e)=P(e|o)P(o)

我們注意到，如果有 P(e)=P(e|o)，那麼我們就可以得到 P(o)=P(o|e)，這就是我們所謂的絕對安全：有密文得到的明文概率等於明文的先驗分布，也就是即使你得到密文，對明文的認知也是和瞎猜一樣的，密文不會讓你不會得到任何有用的信息。

對於xor， e=ooplus key， o=eoplus key 。對應於任意一個o，都存在一個key，它們的xor是密文e（這是一個滿射），於是用古典概率的計數原理，我們有P(e)=P(e|o)，於是 P(o)=P(o|e)。

此外，異或加密是高度對稱的，在公式中你可以將明文o和秘鑰key互換，並不會造成數學上的區別。也就是某種意義上你是用明文加密秘鑰。再深入一想，你可能就會發現這種「絕對安全」演算法的平凡性帶來的問題：如果我真的能夠不被泄露地傳輸和明文一樣長的秘鑰，那麼我為什麼不直接傳遞明文？加密的意義又何在？一次一密的異或加密雖然在演算法上絕對安全，但它不能構成一個實際中合格的密碼學系統。因此在目前的（特別是實時的）加密系統中，大家常用的是AES/RSA之流，原因在於它們使用比明文短的多的秘鑰時就能達到極其強的，雖然不是絕對安全的加密效果。

最近若干年一次一密的異或加密因為量子秘鑰分發(QKD)又被用來證明在使用QKD的時候，可以做到密碼系統的絕對安全（端系統部分除外）。原因在於QKD雖然不能用於傳遞明文，但是可以用於實時的絕對安全的秘鑰分發，這樣一來我們（原則上）就可以得到和明文一樣長的秘鑰，一次一密的異或加密就有了用武之地。

異或相比加減乘除這些加密操作額外的好處在於執行效率極高：它不會產生進位，各個部分間可以並行執行。

上面是異或在密碼學上的用途。

XOR 在編碼學上也用的非常多的用途。特別是各類糾錯碼和校驗碼的編碼關鍵過程。

  1. 奇偶校驗是單bit校驗中最常見一種（可能沒有之一），廣泛使用於各種場合。它相當於對一串二進位重複使用異或的結果(reduce with xor)，比如 1oplus0oplus0oplus1oplus1=1
  2. 著名的CRC校驗，它使用兩個位元組數據流採用二進位除法（沒有進位，使用XOR來代替減法）相除所得到的餘數。
  3. Hadamard 編碼某種意義上也可以用一串異或表述。
  4. Gray 碼。如果你希望有一種數字編碼，使得相鄰數字只差一個二進位位，gray碼就符合這個要求。它也是你遍歷一組開關的所有可能開閉組合最快的方式（每次只要撥一個開關） 。假設以二進位為0的值做為格雷碼的0，那麼就有G(N) = (B(n)/2) XOR B(n) 【G：格雷碼 B：二進位碼】
  5. md5/sha1/sha256/des/aes中均大量使用了XOR來「打亂」數據。

XOR 在可逆計算和量子計算中有非常重要的意義

我們定義一類控制門電路：

CIRCUIT-GATE(A, B) = (A, GATE(A, B))

比如 CIRCUIT-AND(A, B) = (A, A B)

CIRCUIT-OR(A, B) = (A, A | B)

CIRCUIT-XOR(A, B) = (A, A ^ B)

其中 CIRCUIT-XOR(A, B) 更常用的稱呼是CNOT（Controlled NOT），原因在於如果A=0，那麼結果是(A, B)；如果A=1，結果是(A, !B)，也就是A控制了B的反相。

CNOT非常重要的一點在於它是可逆的。將CNOT結果反過來輸入就會得到原來的結果(A, A^B^A)=(A, B)，AND和OR等沒有這點功能。

一種運算是可逆的，意味著兩點：

  1. 可逆運算原則上可以不產生熱量。它不會「抹除信息」，基於熱力學可以得出不產生熱量（當然具體實現上產生的熱量是另外一回事）。
  2. 它很可能可以推廣用於量子計算。量子計算中演化的酉算符是可逆的，如果存在對應關係就可以推廣。

在量子計算中，CNOT和一個單量子位的酉變換（都是可逆的）可以構成量子線路的Universal Gate Set，也就是可以組成任意功能的量子線路，就好像經典數字電路中的NAND一樣。這是非常重要的結論。並且由於可逆性，早期研究量子計算的目的很大程度上和可逆計算相關（直到shor, grover等人展示了一些讓人吃驚的量子演算法）。

並且很多和XOR相關的經典特性可以移植到量子計算中，產生新的效應，比如下面的交換演算法（如何在不使用第三個變數的情況下交換兩個變數的值）：

int a, b;
// ...
// Swap
b ^= a; // CNOT(a, b) -&> (a, a ^ b)
a ^= b; // CNOT(a ^ b, a) -&> (a ^ b, a ^ b ^ a) -&> (a ^ b, a)
b ^= a; // CNOT(a, a ^ b) -&> (a, a ^ b ^ a) -&> (a, b)

// therefore, (b, a) -&> (a, b)

這在實際中是個tricky但是基本上useless的東西。

如果仔細觀察會發現這實質上是3個CNOT門，於是我們可以推廣到量子線路中，這時候就完全不一樣了：(結合非局域性質)它可以實現遠程的兩個物體量子狀態的交換，而不用交換物體本身，這就是著名的 Quantum Swapping 實驗。它的各種變種在量子計算中也有非常重要的作用（比如交換一個光子的SAM和另外一個光子的OAM）。

這麼多回答，都沒有說 xor operator 可以讓布爾值形成一個群。

這樣就可以用代數知識來處理布爾值了啊。

這才是為啥它在密碼學裡面用的那麼多。。。

我來說一下計算機圖形學……

有種東西叫做橡皮筋。

說白了就是繪製一個圖形需要動態實時改變的樣子。

簡單而言畫一個圓確定圓心以後要確定半徑，我們通過滑鼠move移動操作的時候其實就是在進行 異或 運算……

繪製上一條線後再"重複繪製"一次這條線就會消失，然後繪製當前位置一條線。

嗯就醬……演算法這麼高深的東西我可不會(?_?)

因為它就是二進位的不進位加法，你說多重要

XOR加密是一種簡單高效、非常安全的加密方法

一、 XOR 運算

邏輯運算之中，除了 AND 和 OR，還有一種 XOR 運算，中文稱為"異或運算"。

它的定義是：兩個值相同時，返回false，否則返回true。也就是說，XOR可以用來判斷兩個值是否不同。

true XOR true // false
false XOR false // false
true XOR false // true
true XOR false // true

JavaScript 語言的二進位運算，有一個專門的 XOR 運算符，寫作^。

1 ^ 1 // 0
0 ^ 0 // 0
1 ^ 0 // 1
0 ^ 1 // 1

上面代碼中，如果兩個二進位位相同，就返回0，表示false；否則返回1，表示true。

二、 XOR 的應用

XOR 運算有一個很奇妙的特點：如果對一個值連續做兩次 XOR，會返回這個值本身。

// 第一次 XOR
1010 ^ 1111 // 0101

// 第二次 XOR
0101 ^ 1111 // 1010

上面代碼中，原始值是1010，再任意選擇一個值（上例是1111），做兩次 XOR，最後總是會得到原始值1010。這在數學上是很容易證明的。

三、加密應用

XOR 的這個特點，使得它可以用於信息的加密。

message XOR key // cipherText
cipherText XOR key // message

上面代碼中，原始信息是message，密鑰是key，第一次 XOR 會得到加密文本cipherText。對方拿到以後，再用key做一次 XOR 運算，就會還原得到message。

四、完美保密性

二戰期間，各國為了電報加密，對密碼學進行了大量的研究和實踐，其中就包括 XOR 加密。

戰後，美國數學家香農（Claude Shannon）將他的研究成果公開發表，證明了只要滿足兩個條件，XOR 加密是無法破解的。

key的長度大於等於message
key必須是一次性的，且每次都要隨機產生

理由很簡單，如果每次的key都是隨機的，那麼產生的CipherText具有所有可能的值，而且是均勻分布，無法從CipherText看出message的任何特徵。也就是說，它具有最大的"信息熵"，因此完全不可能破解。這被稱為 XOR 的amp;quot;完美保密性amp;quot;（perfect secrecy）。

滿足上面兩個條件的key，叫做 one-time pad（縮寫為OTP），意思是"一次性密碼本"，因為以前這樣的key都是印刷成密碼本，每次使用的時候，必須從其中挑選key。

五、實例：哈希加密

下面的例子使用 XOR，對用戶的登陸密碼進行加密。實際運行效果看這裡。

第一步，用戶設置登陸密碼的時候，算出這個密碼的哈希，這裡使用的是 MD5 演算法，也可以採用其他哈希演算法。

const message = md5(password);

第二步，生成一個隨機的 key。

// 生成一個隨機整數，範圍是 [min, max]
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}

// 生成一個隨機的十六進位的值，在 0 ～ f 之間
function getHex() {
let n = 0;
for (let i = 4; i &> 0; i--) {
n = (getRandomInt(0, 1) &<&< (i - 1)) + n; } return n.toString(16); } // 生成一個32位的十六進位值，用作一次性 Key function getOTP() { const arr = []; for (let i = 0; i &< 32; i++) { arr.push(getHex()); } return arr.join(""); }

上面代碼中，生成的key是32位的十六進位值，對應 MD5 產生的128位的二進位哈希。

第三步，進行 XOR 運算，求出加密後的message。

function getXOR(message, key) {
const arr = [];
for (let i = 0; i &< 32; i++) { const m = parseInt(message.substr(i, 1), 16); const k = parseInt(key.substr(i, 1), 16); arr.push((m ^ k).toString(16)); } return arr.join(""); }

使用這種方法保存用戶的登陸密碼，即使加密文本泄露，只要一次性的密鑰（key）沒有泄露，對方也無法破解。

-----------------------------------------------

*本文來源自《 XOR 加密簡介》，作者：阮一峰@螞蟻金服

更多安全類知識分享，請持續關注阿里聚安全的安全專欄及博客

二元布爾函數總共也就十六個，符合交換律的八個，扣掉邏輯恆真恆假六個，引入一元聯詞非以後只剩三個。雖說這三個任何一個都可以被另兩個表示，但實際應用中這麼做才是缺心眼。於是多個三個常用二元聯詞，與或異或。

用它在密碼學中的重要性說明它在計算機科學中的重要性，怎麼說呢……像是拿核彈炸了廣島說明它打蚊子效率很高之類的？舉不出好例子，領會精神……

不僅非，或，與運算可以模擬與非

a xor b = (a or b) and neg (a and b)

非，與運算還可以模擬或

a or b = neg ((neg a) and (neg b))

這些操作在計算機科學相當有用（其他答主說過了），當然可以形成一個單獨概念加以學習。

至於在C實現需要有內置的^和|當然因為cpu有相應的指令，c語言當然要實現影射基本cpu指令這個功能。cpu為什麼要實現這些基本指令呢？因為性能！

藉助至多一次非運算符表示所有對稱布爾操作至少需要xor，and和or三種二元運算符

於是實現任意二元對稱布爾運算至多需要兩個指令，多美。

上句話的討論，在我的博客里

https://lhprojects.github.io/2017/06/08/why-xor-need/

如果只用「與、或、非」三種運算的話，那麼實現兩個布爾變數A和B的「亦或」和「異或非」運算均需要五次操作。

A異或B = (AB) | (~A~B)

A異或非B = (A|B) (~A|~B)

其餘邏輯中最複雜的也只需要三次，~A~B 和 ~A|~B。

從這個角度來看，單拿一個符號出來代替最複雜的兩個操作也很正常吧。

數學中的極值點，放到異或門裡，輸出為真。

運用這個可以做很多事情，說個貼近生活的，咱們手機里的計步器演算法，加速度波形圖中的波峰位置，一邊上升(1)，另一邊下降(0)，輸入到異或門裡，結果就是真(1)，這就是一步。

幾乎所有的加密演算法都會涉及到XOR（邏輯加），和伽羅華域上的加法乘法也有關係。例如現在安全係數很高的基於橢圓曲線的離散對數問題的加密演算法ECC就是基於2^8的伽羅華域，其安全性160位就可高於1024位的RSA加密演算法和ElGamal。

扯遠了，這些演算法是通過計算秘鑰或公鑰，最後一步多多少少都是對明文進行XOR。

像分組密碼DES、AES， 流密碼RC4等，都大量的用到了XOR。

香農大法好，沒有他就沒有今天的現代密碼學。

1，實現模2加法，0+1=1，0+0=0，1+1=0

，輸入的2個信號進行與操作，就是進位。因此一個與門與一個異或門就可以實現帶進位的1位二進位加法

2，清0。c語言i=0，編譯成彙編是xor指令。xor指令比mov 0指令短很多，尤其是64位系統，更加明顯。

3，最簡單高效的加密解密演算法。

拿來做兩個數值的交換，即迅速，又不會佔用第三空間（只要是二進位序列均可以這樣處理）

--------

xor的特點，若a^b=c，則abc中任意兩個以任意順序進行異或，則必然為剩下的那個，這個性質正好可以用於加密：

明文^密鑰=密文

密文^密鑰=明文

明文^密文=密鑰

密文^明文=密鑰

幾乎所有的加密演算法都用到了異或運算

註：MD5等hash（哈希，散列）演算法不是加密，因為他們的本質是取余，只是除數非常大（一般為128比特）的取余。所以必然會存在這種情況：

原文1=散列A，同時有，原文2=散列A

原有信息在散列計算後必然丟失，知道散列也無法得出唯一的原文

所以散列只是比對數據特徵值的一種方法，而不是一種加密演算法

同時，異或門又恰好可用於二進位數字電路中的加法運算，得出兩個一位二進位數相加後的低位數值，所以又稱「半加器」。配合與門計算高位數值，即可成為「全加器」。將數個「全加器」串接再稍加改進，就是二進位加法器了。再配合上補碼形式的負數，就可以做到減法……

回答里居然還有這麼多人答異或是加密。

如果異或算加密，那加法減法也可以算加密了。兩種均為：

給定第二操作數（key），均可以給出唯一輸出，並可逆；

第二操作數未暴露的情況下，第一操作數不會暴露；

得知結果和第一操作數，可以逆推第二操作數。

以後別人問你們加法是什麼，你們就答加密吧。

從數字集成電路設計的角度而言，通過傳輸門傳輸管等結構可以很方便的設計出異或門。另外學過數字電路的人都知道，全加器需要異或門，而全加器是數字集成電路里最基礎的運算單元，所以異或門很常見

另外個人感覺，對於數字ic來說，實際上常用邏輯門應該是 非，與非，或非，異或

最簡單的加密, 利用對同一個數兩次XOR之後回到原來的數的特性

A XOR B = C

C XOR B = A

兩個同類型變數, 交換值:

A 和 B 初始值為:

A = X (常數)

B = Y (常數)

然後開始交換:

A = A XOR B

B = A XOR B

A = A XOR B

現在他們的值就是:

A : Y , B : X

異或的性質使得它用途廣泛

A^B=C

則

C^B=A

A^C=B

還有

A^A=0

A^0=A

可用於編碼、加密等

續一下當年某位用戶的回答...

因為很多基本運算需要用到異或操作，比如說:加法。

暫時不談複雜的程序，我們只看最基本的邏輯電路吧。

電路中，一個「與」加上一個「異或」運算可以形成「一位半加器」，它能夠計算兩個一位數的加法並給出進位。

兩個一位半加器合起來，能夠形成一個「一位全加器」，它可以接收低位的進位，計算加法並給出進位。

多個一位全加器合起來，就能實現最基本的加法運算了。比如我們用八個一位全加器，就能實現255以內的加法運算;用十六個就能實現0-65535以內的加法運算;用三十二個就能實現四十億以內的加法運算啦。

而在這些最基本的加法運算背後，有一半的運算都是用「異或」實現的，它的重要程度應該不言而喻了吧。

(當然，後來人們發明了「超前進位加法器」，可以提前算出進位的結果，大幅提升電路中加法運算的速度……不過那就是另外一個故事啦。)

和同一個key進行模2加，數是不變的。加解密基本上是不停的異或，旋轉，移位。這些操作都是能通過多運行幾次讓數據複位。

沒有這玩意兒，我碩士基本上很難畢業。。。(搞加密方向)

異或這種演算法最早應該是用在無線電通信上面，那時計算機還沒出現呢，電碼原文跟密鑰進行異或得到密文，密文發出去後，接收方用相同密鑰對密文進行異或計算得到原文。

如：

1001 xor 1111=0110 加密得到密文

0110 xor 1111=1001 解密得到原文

最簡單的應用在SPN加密 達到key mixing

推薦閱讀：

※根據哥德爾不完備定理，能否推導出 在固定法律體系下 總有一個案件 既不能證明有罪 也不能證明無罪？
※西方人的圍棋水平如何？
※能否從形式上說明【辯論】活動到底在解決一個什麼樣的問題？
※有哪些比較有趣的，類似「雞生蛋、蛋生雞」的思想怪圈？
※如果兩人對弈，A擁有能看透別人內心的超能力，那麼B應該用什麼策略才能贏？

TAG:計算機 | 計算機科學 | 邏輯學 |