看看在歷史上我們是如何隱藏私密信息的

凱撒加密

***個(gè)被最廣泛熟知的加密方式就是公元前 58 年的凱撒加密（Caesar cipher）

加密

凱撒加密的加密方式就是，在加解密之初，加解密的雙方需要先確定一個(gè)位移長度。加密的一方通過對(duì)明文中的單詞按照選定的平移長度逐個(gè)的進(jìn)行平移，得到加密后的內(nèi)容；解密的一方通過將密文按照選定的平移長度進(jìn)行逆向的平移，則可以得出明文。

比如，對(duì)于加密條件 明文為 hello，平移長度為 3 的加密過程：

1. 根據(jù) 26 個(gè)英文字母的順序，h 向后推 3 個(gè)的字母為 k
2. 按照***步對(duì)剩余的明文字母依次類推，可以得出密文為 khoor

破解

對(duì)于凱撒加密，其破解的關(guān)鍵有兩點(diǎn)：

1. 明文所采用的語言中的字母出現(xiàn)頻率的統(tǒng)計(jì)圖表（可以通過大量的統(tǒng)計(jì)分析該語言的書籍）
2. 對(duì)密文進(jìn)行大量統(tǒng)計(jì)得出的其中其母出現(xiàn)的頻率圖表
3. 第1步和第2步得出的圖表進(jìn)行簡單的位移就可以得知加密采用的位移

之所以可以這樣去破解凱撒加密，是因?yàn)槿祟惖恼Z言實(shí)際是一個(gè)具有規(guī)律的事物，而語言中的各個(gè)字母出現(xiàn)的頻率也是這個(gè)規(guī)律的一部分（這一點(diǎn)常常容易被忽略）。對(duì)于選定的位移，實(shí)際上只是將原有的字母頻率圖表做了一個(gè)平移 - 因?yàn)槊恳粋€(gè)字母都平移了固定的長度。

多字碼加密

15 世紀(jì)中葉，加密方式進(jìn)步到了多字碼加密（Polyalphabetic Cipher）

加密

多字碼加密的加密方式就是，在加密之初，加解密雙方要先確定一個(gè)平移詞（shift word）。加密的一方首先需要事先將確定的平移詞轉(zhuǎn)變成與其對(duì)應(yīng)的一組數(shù)字（稱為字碼序列），然后對(duì)于給定的明文，不斷地按照轉(zhuǎn)換后的一組字碼序列的長度，循環(huán)的對(duì)其平移。解密的一方首先也需要將平移詞變成其對(duì)應(yīng)的字碼序列，然后對(duì)于給定的密文，不斷地按照轉(zhuǎn)換后的字碼序列的長度，循環(huán)的對(duì)密文字母其進(jìn)行逆平移。

比如，對(duì)于加密條件 明文為 hello，平移詞為 hi 的加密過程：

1. 首先將平移詞 hi 變成一組對(duì)于的數(shù)字，這里按照英文中 26 個(gè)字母的出現(xiàn)順序，平移詞 hi 其中的字母換換后所對(duì)應(yīng)的一組數(shù)字就是 78（從 0 開始）

2. 現(xiàn)在需要根據(jù)轉(zhuǎn)換后的一組平移數(shù)字，逐個(gè)循環(huán)的對(duì)明文進(jìn)行平移。

    h e l l o
    + + + + + （按照明文字母在 26 個(gè)字母中出現(xiàn)的順序進(jìn)行平移）
    7 8 7 8 7
    -----------
    o m s t v

3. 最終，根據(jù)上面的變換，就會(huì)得出密文 omstv

對(duì)于解密的一方，他需要知道平移詞 hi，當(dāng)然這個(gè)雙方在事先就約定好了。解密方式就不冗述了，就是其加密的逆過程。

破解

相對(duì)于凱撒加密的破解過程 - 分析統(tǒng)計(jì)密文中的字母頻率出現(xiàn)的圖表，與明文所采用的語言中字母出現(xiàn)的圖表進(jìn)行簡單的平移對(duì)比之后，就會(huì)得出平移量而言，多字碼加密加大了從密文中得出有效的字母出現(xiàn)的頻率的難度。但是其解密的原理依舊不復(fù)雜。

對(duì)于破解者而言，他們更加關(guān)心的是多字碼加密時(shí)采用的字碼序列的長度，比如上面的例子中 78 這個(gè)字碼序列的長度就是 2。另外，之所以在上文的加密的過程的解釋中，一直強(qiáng)調(diào) “循環(huán)” 這個(gè)概念的目的就是，當(dāng)你理解了 “循環(huán)” 的概念之后，你會(huì)發(fā)現(xiàn)，上面的例子中 h、***個(gè) l、o 都是采用的 7 作為了它們的平移量，那么問題其實(shí)又回到了凱撒加密。

于是，對(duì)于破解者，他們只要不斷地猜測(cè)字碼的長度，因?yàn)槊魑氖前凑兆执a序列的長度循環(huán)平移的，一個(gè)循環(huán)的開頭，和下一個(gè)循環(huán)的開始必定是使用的同樣的平移量，只要按照這個(gè)規(guī)律，將以一個(gè)猜測(cè)的字碼序列的長度為間隔的加密字母挑出來進(jìn)行頻率分析統(tǒng)計(jì)，然后與明文的字母頻率進(jìn)行對(duì)比，就能得出平移量了 - 回到了凱撒加密的破解過程。

一次一密

19世紀(jì)末期，出現(xiàn)了一個(gè)具有相當(dāng)強(qiáng)度的加密方式，稱為一次一密（one-time pad）。

加密

所謂一次一密，其加密的字碼的長度不再像是上文提到的固定長度了，它所采用的是使用隨機(jī)的方式得到一個(gè)與明文字母等長的隨機(jī)字碼序列。

首先要知道的是，對(duì)于英文字母而言，每一個(gè)字母所能進(jìn)行的平移量只有 26 種。因?yàn)閷?duì)于任何一個(gè)具有固定長度的計(jì)數(shù)系統(tǒng)而言（其實(shí)就是一個(gè)模系統(tǒng)），超過了其模的平移將會(huì)從頭開始進(jìn)行移動(dòng)（補(bǔ)數(shù)），這里你可以想象成一個(gè)有 26 個(gè)小時(shí)刻度的時(shí)鐘，從 0 點(diǎn)順時(shí)針的平移量如果是 27 的話，實(shí)際的結(jié)果就是 1 點(diǎn) - 和順時(shí)針直接平移 1 沒有什么區(qū)別。

那么，對(duì)于明文為 hello 的一次一密的加密過程可以是這樣：

1. 隨機(jī)得到一個(gè) 0～25 以內(nèi)的隨機(jī)數(shù)，假設(shè)本次隨機(jī)數(shù)是 3

   1. 記錄這個(gè)隨機(jī)數(shù)
   2. 將明文 h 平移 3 變成 k

2. 隨機(jī)得到一個(gè) 0～25 以內(nèi)的隨機(jī)數(shù)，假設(shè)本次隨機(jī)數(shù)是 5

   1. 記錄這個(gè)隨機(jī)數(shù)
   2. 將明文 e 平移 5 變成 j

3. 依次類推...

那么假設(shè)隨機(jī)的字碼序列是 35685，其對(duì)應(yīng)的密文就是 kjrtt。
如果再次加密的話，需要再次隨機(jī)生成一個(gè)與明文等長的字碼序列。

當(dāng)然，接收方需要同時(shí)知道每一次的隨機(jī)字碼序列和對(duì)應(yīng)密文。

破解

對(duì)于采用一次一密的加密方式等到的密文，破解者需要面對(duì)兩個(gè)問題：

1. 用于加密的字碼序列的長度是和明文等長的，于是也就沒有了 “多字碼加密” 中的 “循環(huán)” 問題了。
2. 密文中的每一個(gè)字母的出現(xiàn)頻率將會(huì)是相同的，因?yàn)槊總€(gè)明文字母都隨機(jī)對(duì)應(yīng)到了 26 個(gè)字母中的一個(gè)，它們出現(xiàn)的概率是相同的。

由于密文沒有規(guī)律可循，破解者只有通過暴力破解的方式去嘗試得出明文。不過，對(duì)于明文 hello 它的密文將會(huì)是 26*26*26*26*26 = 11881376 種組合中的一種，而且這僅僅是只有 5 個(gè)字母的情況。

***保密

理解這樣一個(gè)游戲：Eve 邀請(qǐng) Bob 來到一個(gè)房間，Bob 發(fā)現(xiàn)這個(gè)房間除了有一副牌、幾把鎖（帶鑰匙的鎖和密碼鎖）、一個(gè)空格子之外，什么也沒有。Eve 讓 Bob 選擇一張牌，然后盡他***的能力去將牌藏起來。規(guī)則很簡單，Bob 不能從房間帶走任何物品，所有牌和鑰匙必須留在房間內(nèi)，并且在空格子中最多只可以放一張牌，Eve 保證他沒有動(dòng)過那些鎖。如果 Eve 不能找出 Bob 藏的牌的話，Bob 就贏了。那么 Bob 應(yīng)該怎么做？

首先 Bob 選擇了一張方塊6，并將它扔進(jìn)了空盒子中，然后他開始考慮使用哪一個(gè)鎖將盒子鎖起來。似乎使用密碼鎖是一個(gè)很好的選擇，不過 Bob 很快意識(shí)到一個(gè)問題 - 桌上剩余的牌會(huì)暴露他的選擇。鎖只不過是一個(gè)陷阱，他不能將牌從牌堆里面拿出來，所以他將選擇的牌重新放回牌堆，并將牌堆進(jìn)行重新的洗牌，以此打亂它們?cè)械捻樞颉，F(xiàn)在，Bob 選擇的牌，可能是牌堆中的任意一張了，他可以信心十足的離開房間。

***，Bob 贏得了游戲，因?yàn)?Eve 最多只能靠猜測(cè)才能得知 Bob 選擇的牌 - Bob 沒有留下任何關(guān)于其選擇的牌的信息。即使給了 Eve 一個(gè)沒有性能限制的計(jì)算機(jī)，他也只能靠猜，這就是我們所說的 “***保密” 。

在 1945 年九月一日，29歲的 Claude Shannon 發(fā)布了一個(gè)保密論文，***次從數(shù)學(xué)角度去證明 “一次一密” 如何以及為什么具有***的保密性。Claude Shannon 是按照下面的方式去思考加密方案的：

• 設(shè)想 Alice 給 Bob 寫了一個(gè) 20 個(gè)字母長度的消息。這就好比從消息空間（message space）中抽出一個(gè)特定頁面。對(duì)于消息空間，可以想象成是包含 20 個(gè)字母可以組成的所有組合的一個(gè)集合。

• 接著 Alice 需要在 0～25 之間隨機(jī)的生成 20 個(gè)字母的密匙（字碼）。密匙空間（key space）就是包含所有隨機(jī)組合情況的一個(gè)集合，所以生成一個(gè)密匙就好比從密匙空間中隨機(jī)的抽出一頁。

• 接著 Alice 將密匙的作為一個(gè)個(gè)平移量應(yīng)用到明文消息中，得出了密文。密文空間（ciphertext space）表示了所有可能的加密結(jié)果組合的集合。當(dāng)她選擇并應(yīng)用了某一個(gè)密匙，結(jié)果將會(huì)唯一地對(duì)應(yīng)到密文空間中的一頁。

• 注意這里的消息空間大小、等于密匙空間的大小、等于密文空間的大小，這些就是 “***保密” 的定義。所以當(dāng)只知道密文的情況下，唯一可以得到的信息就是：這段密文唯一對(duì)應(yīng)于消息密文中的一頁。因?yàn)橐平庵荒芸坎聹y(cè)，所以無論功能多強(qiáng)勁的計(jì)算機(jī)，面對(duì)只能靠猜測(cè)的算法，除了可以縮短猜測(cè)的時(shí)間之外，并沒有什么提升。

現(xiàn)在，在使用一次一密的情況下，唯一需要面對(duì)的問題就是，我們?nèi)绾卧谑孪裙蚕砟切╅L的密匙。

偽隨機(jī)數(shù)生成器

當(dāng)我們?cè)谟^察自然界時(shí)，我們到處會(huì)發(fā)現(xiàn)一些隨機(jī)的波動(dòng)。我們可以通過對(duì)熟知的比如噪音的波動(dòng)，去測(cè)量并生成真實(shí)的隨機(jī)數(shù)。當(dāng)我們?cè)趯?duì)噪音進(jìn)行取樣的時(shí)候，我們可以獲得數(shù)字。比如，我們通過測(cè)量一段時(shí)間的電視機(jī)電流，我們就可以生成一個(gè)真的隨機(jī)數(shù)序列。為了將一個(gè)數(shù)的序列可視化，我們可以根據(jù)序列中的每一個(gè)數(shù)去畫出它們的更改路徑，這種方式也叫做隨機(jī)游走（random walk）。根據(jù)可視化后的圖像得出，在真隨機(jī)序列中的任意一點(diǎn)上，都無法預(yù)測(cè)下一點(diǎn)將會(huì)出現(xiàn)在哪里。隨機(jī)的過程按理說應(yīng)該是具有非確定性的，因?yàn)樗鼈儫o法事先就測(cè)定。

另一方面，機(jī)器是具有確定性的，它的操作是可預(yù)測(cè)的以及可重復(fù)的。由于隨機(jī)數(shù)需要被不斷以及快速的得到，加上之前的計(jì)算機(jī)具有有限的存儲(chǔ)大小，所以直接存儲(chǔ)一個(gè)固定長度的隨機(jī)數(shù)是不現(xiàn)實(shí)的。所以，在早期的計(jì)算機(jī)中，科學(xué)家發(fā)明了一個(gè)算法去機(jī)械的模擬隨機(jī)中的亂序現(xiàn)象。這個(gè)算法叫做 平方取中 Middle-square method。

比如，要使用此算法去生成一個(gè) 4 位的偽隨機(jī)數(shù)，就需要先選擇一個(gè)四位數(shù)作為整個(gè)過程的起始值（種子），將這個(gè)四位數(shù)和自身相乘（平方）運(yùn)算后，會(huì)得到一個(gè) 8 位的數(shù)字（如果不足八位，就在前面補(bǔ)上 0，以湊足 8 位）。得到結(jié)果的 8 位數(shù)字之后，取出其中的 4 為數(shù)字作為結(jié)果，或者作為下一次運(yùn)算的種子，再配合重復(fù)上面的過程以獲得更多的 4 位偽隨機(jī)數(shù)。

為此方法提供隨機(jī)性的唯一保障就是最初選擇的隨機(jī)種子。相同的種子，將會(huì)生成相同的序列。那么，隨機(jī)序列和偽隨機(jī)序列之間有什么不同？可以通過上述提到的隨機(jī)游走的方式將偽隨機(jī)序列進(jìn)行可視化，以此具象化地進(jìn)行觀察。結(jié)果就會(huì)發(fā)現(xiàn)，如果中間產(chǎn)生了一個(gè)曾經(jīng)使用過的種子，那么接下來的結(jié)果都將會(huì)和之前出現(xiàn)的中間結(jié)果發(fā)生重復(fù)。在偽隨機(jī)數(shù)序列發(fā)生重復(fù)之前的時(shí)期，就被稱為周期（the period）。這個(gè)周期會(huì)被最初選擇的種子長度嚴(yán)格限制。比如，我們使用了一個(gè) 2 個(gè)數(shù)字的種子，那么在結(jié)果序列發(fā)生重復(fù)前，可以產(chǎn)生 100 個(gè) 2 位數(shù)字組合，一旦其中出現(xiàn)了和最初的 2 個(gè)數(shù)字的種子一樣的中間結(jié)果，那么接下來的中間結(jié)果將會(huì)做周期性的重復(fù)。3 位數(shù)字的種子，就可以產(chǎn)生 1000 個(gè) 3 位數(shù)字的組合。4 位數(shù)字的種子，就可以產(chǎn)生 10000 個(gè) 4 位數(shù)字的組合。如果我們使用了一個(gè)具有非常長長度的種子，那么就可以產(chǎn)生具有非常長周期的偽隨機(jī)的結(jié)果序列。

另外一個(gè)需要面對(duì)的問題就是，一旦我們選擇了偽隨機(jī)的方式生產(chǎn)隨機(jī)數(shù)，那么就會(huì)丟失很多在真隨機(jī)序列中應(yīng)該出現(xiàn)的序列。比如，Alice 需要為 20 個(gè)字母長度的明文生成一個(gè)真隨機(jī) 20 個(gè)字碼的組合，那么這些隨機(jī)字碼的組合就有 26^20 次方的可能性，
這將會(huì)是一個(gè)天文數(shù)字。作為對(duì)比，假設(shè) Alice 使用的是上面提到的偽隨機(jī)方式，并使用了一個(gè) 4 位的種子。也就是說，使用偽隨機(jī)的方式，她只能選擇 10000 種可能的種子，因此只能生成 10000 種不同的數(shù)字序列，我們可以在生成的序列中選擇前 20 個(gè)作為字碼?？梢园l(fā)現(xiàn)，使用了偽隨機(jī)方式的結(jié)果，使得我們的密匙空間被大大的縮小了，密匙空間的太小變成了種子空間（seed space）的大小。

那么作為這種偽隨機(jī)的破解方式，可以通過不斷的猜測(cè)所有的可能的種子。這就將問題帶到了一個(gè)計(jì)算機(jī)中常見的問題，什么是可能的，以及什么是在一定時(shí)間內(nèi)可能的。在我們買一個(gè)自行車密碼鎖時(shí)，其實(shí)采用了相同的邏輯。我們知道所有人都可以對(duì)密碼鎖去嘗試所有可能數(shù)字組合，直到他們找出匹配的那一組并打開了鎖。但是，這個(gè)過程將花費(fèi)他們幾天的時(shí)間，所以對(duì)于 8 個(gè)小時(shí)之內(nèi)的時(shí)間，我們可以認(rèn)為鎖幾乎是安全的。在上述偽隨機(jī)生成方法下，保密程度將隨著種子的長度而提高，如果***勁的計(jì)算機(jī)都需要花幾百年才可以嘗試掉所有的種子的可能性的話，我們就可以認(rèn)為這種方式幾乎是安全的，但不是***保密。隨著計(jì)算機(jī)的不斷發(fā)展，種子的長度也需要相應(yīng)地不斷地增長。

采用上述的偽隨機(jī)方式，使得 Alice 和 Bob 不必事先共享一整個(gè)很長的字碼序列了。他們只要分享一個(gè)對(duì)應(yīng)的隨機(jī)種子，然后使用那個(gè)種子去生成看起來是隨機(jī)的序列作為字碼序列。但是，當(dāng)他們無法面對(duì)面分享那個(gè)隨機(jī)種子時(shí)，將會(huì)發(fā)生什么？