前言

前幾天在用wireshark的時(shí)候，突然對(duì)密碼學(xué)來了興趣，所以在看有關(guān)的書籍（說不定以后能夠派的上用處）。然后順帶寫點(diǎn)筆記分享給大家。

一、術(shù)語

括號(hào)里面的中文全部是用google tranlate翻譯過來的。懶得上百度去查中文術(shù)語了

Plaintext（純文本）與Ciphertext（密文）分別是加密之前的文本和加密之后的文本。

Encryption scheme （加密方案）：由3個(gè)部分組成——Key generation algorithm G, Encryption algorithm E, 以及?Decryption algorithm D.

Key generation algorithm （密鑰生成算法）：一個(gè)基于概率分布來生成 key 的算法。

Encryption algorithm （加密算法）：輸入plaintext 和key ，輸出ciphertext ，但算法本身不要求是derministic（即，輸入相同的m和k，可以輸出不同的c）

Decryption algorithm（解密算法）：輸入ciphertext?和key?，輸出plaintext?。從實(shí)際出發(fā)，我們要求算法是derministic（不然，A可以從一個(gè)加密的文本中解密出apple，B可以從相同的文本中解密出banana，就很奇怪）

二、Frequency Analysis（頻率分析）

無論是英文還是中文，都有一個(gè)頻繁出現(xiàn)的字母和單詞。從這個(gè)角度出發(fā)，我們就可以破譯一些用傳統(tǒng)加密方式（比如說caesar cipher）加密的文本。

從Wikipedia給出的數(shù)據(jù)來看（https://en.wikipedia.org/wiki/Letter_frequency），英文中最常用的幾個(gè)字母為a, e, i, o；所以我們?nèi)绻掷锬玫揭粋€(gè)用caesar cipher加密的文本的話（通過字母位移來加密文本的一個(gè)古老的方法），我們可以統(tǒng)計(jì)一下文本里面每個(gè)文字出現(xiàn)的次數(shù)和比率，然后試著和a, e, i, o對(duì)應(yīng)，然后我們就可以順藤摸瓜找到位移量，也就是我們的key，然后我們就能成功解密我們的文本了。

三、Perfect secrecy

Perfect secrecy如它的名字一樣，我們的密碼破譯者如果只有ciphertext c的話，是從我們的c里面獲得任何我們加密算法的信息的。用公式表達(dá)就是

也就是，對(duì)于一個(gè)ciphertext c，任何plaintext m都有相等的概率被加密為c

很明顯，我們的caesar cipher不滿足這個(gè)條件，假設(shè)我們手里有密文ABC，那么不論我們的key是什么，我們的原文都不可能是BBB，但我們的原文有可能是BCD（如果我們的key k=1的話），故:

所以不滿足我們的perfect secrecy

四、One Time Pad

One time pad的加密方式非常簡(jiǎn)單，對(duì)于我們長(zhǎng)度為d的plaintext?, 我們通過G生成一個(gè)與m同等長(zhǎng)度的key?, 然后我們通過一個(gè)bitwise的xor運(yùn)算得到我們的ciphertext?，

這里有一段自己寫的python代碼來作為演示：

key和code都太長(zhǎng)了，我就不列出來了，感興趣的可以自己運(yùn)行一遍上面的代碼。

這里針對(duì)我們的plaintext m我們的key k只使用一次，每當(dāng)我們換一個(gè)新的m的時(shí)候，我們也要重新生成一個(gè)新的k。

這個(gè)One time pad滿足我們的perfect secrecy，在此就不證明了，而是舉一個(gè)非常簡(jiǎn)單的例子：

五、Shannon's perfect secrecy theorem

Shannon perfect secrecy theorem給出了，如果某個(gè)encryption scheme具備perfect secrecy，那么它必定滿足，這里K代表key space（我們所有可能的key的集合），M代表message space（我們所有可能的plaintext的集合）。具體證明過程參見這個(gè)slide的第28頁（https://www3.cs.stonybrook.edu/~omkant/L02-short.pdf）

后記

密碼學(xué)還是挺有意思的。今天先寫這么多。

參考資料：

Jonathan Katz, Yehuda Lindell - Introduction to Modern Cryptography

（在文中已注明引用地址的內(nèi)容將不再重復(fù)列在這里）

THE END.