3000字，看懂密碼學(xué)的底層原理
一、密碼學(xué)的定義
適用對(duì)象：
經(jīng)典密碼學(xué)：軍事組織和政府。
現(xiàn)代密碼學(xué)：everywhere。
《簡(jiǎn)明牛津英語(yǔ)詞典》：編碼或破譯密碼的藝術(shù)。（不夠完善準(zhǔn)確）
現(xiàn)在密碼學(xué)：對(duì)保護(hù)數(shù)字信息、系統(tǒng)和分布式計(jì)算免受敵方攻擊的數(shù)學(xué)技術(shù)的研究。
其演變過(guò)程可表示如下：
二、對(duì)稱加密簡(jiǎn)述
在密碼學(xué)中，我們將加密方案分為private-key (symmetric) encryption和public-key (asymmetric) encryption。
在private-key encryption中，當(dāng)通信雙方想要秘密通信的時(shí)候，提前交換一個(gè)key。其中一方可以使用這個(gè)key來(lái)加密一條消息，或者叫明文 (plaintext)，然后發(fā)送給另一方。因此可以說(shuō)，其中一方將一個(gè)密文ciphertext發(fā)送給了另一方。接收者使用key解密這個(gè)密文，得到了原始消息。這里的key都是相同的，并且用于明文和密文之間的轉(zhuǎn)換。這也是為什么人們將之稱為symmetric encryption。然而asymmetric encryption與之相反，其加密和解密使用的是不同的key。
三、加密語(yǔ)法
Gen：密鑰生成算法
Enc：加密算法
所有由Gen生成的密鑰k組成了一個(gè)密鑰空間，記為K。由Dec生成的密文c 組成了一個(gè)明文空間，記為C。
對(duì)稱加密流程：運(yùn)行Gen來(lái)生成密鑰k，當(dāng)一方想要發(fā)送明文消息m給另一方時(shí)，
然后在公開信道中將密文c發(fā)送給對(duì)方。
計(jì)算m : = Deck(c)來(lái)得到原始消息。
“ := ”表示確定性等式，假設(shè)此處的Enc是確定性的，Enc是概率性的算法
四、Kerckhoffs原則
“加密方案沒有必要保密，它可以被敵人輕易獲得。”
理由：
2. 如果誠(chéng)實(shí)方共享的秘密信息被泄漏，更換密鑰比更換加密方案容易得多。此外，生成一個(gè)新的隨機(jī)密鑰是相對(duì)簡(jiǎn)單的，而設(shè)計(jì)一個(gè)新的加密方案則是一個(gè)巨大的工程。
3. 在廣泛部署加密方案之前，鼓勵(lì)公眾對(duì)該方案進(jìn)行審查以檢查可能存在的弱點(diǎn)，這是一個(gè)顯著的好處。進(jìn)一步地，標(biāo)準(zhǔn)化加密方案可以確保不同用戶之間的兼容性，公眾將使用經(jīng)過(guò)公開審查的強(qiáng)大的加密方案。這更加令人信服。
五、經(jīng)典加密方案
以下介紹的加密方案均已被破解，是不安全的，但是其思想值得學(xué)習(xí)。
1. 凱撒加密（Caesar’s cipher）
凱撒加密是最古老的加密方案之一，它將字母表中的字母向右移動(dòng)3個(gè)位置進(jìn)行加密。即，a加密為D，b加密為E，以此類推。當(dāng)移動(dòng)到字母表的末尾時(shí)，回到字母表的開頭，循環(huán)移位。該方案沒有密鑰，且加密方法是固定的。因此任何人可以通過(guò)學(xué)習(xí)凱撒加密的加密方法來(lái)輕易的破解密文。其變體ROT-13依然被各種在線論壇使用。我們可以從中發(fā)現(xiàn)，它們均沒有提供任何的密碼學(xué)安全性，它們僅僅是使得消息是令人難以理解的，除非消息的讀者有意識(shí)地決定解密它。
2. 移位加密
移位加密可以視為凱撒加密的一種密鑰變體。在移位加密中，密鑰k是一個(gè)介于0到25之間的數(shù)字，在凱撒加密中，字母移動(dòng)3個(gè)位置，而在移位加密中，字母移動(dòng)k個(gè)位置。其算法可概括如下：明文空間M由任意長(zhǎng)度的英文字母字符串組成，其中去掉了標(biāo)點(diǎn)、空格和數(shù)字，并且大小寫沒有區(qū)別。Gen輸出一個(gè)均勻一致的密鑰k ∈ { 0 , . . . , 25 } ，算法Enc將一個(gè)密鑰k和一個(gè)明文作為輸入，然后將明文的每個(gè)字母向前移動(dòng)k個(gè)位置，算法Dec將一個(gè)密鑰k和一個(gè)密文作為輸入，然后將將密文中的每個(gè)字母向后移k個(gè)位置。
在不知道密鑰k的情況下，破解密文也是相當(dāng)容易的。因?yàn)樗挥?6個(gè)可能的密鑰，攻擊者只需要用這些可能的密鑰去解密密文即可，故可得到26種可能的候選明文，正確的明文就在這26種之中。此外，如果密文“足夠長(zhǎng)”，那么正確的明文很可能是列表中唯一“有意義”的候選明文。（這在大多數(shù)時(shí)候是正確的）
這種嘗試每一個(gè)可能的密鑰的攻擊被稱為蠻力 (brute-force) 或窮舉 (exhausient-search) 攻擊。故如果加密方案要保證安全，就不能輕易受到這種攻擊，這個(gè)觀察被稱為充分密鑰空間原理：任何安全的加密方案必須要有足夠大的密鑰空間來(lái)抵抗窮舉搜索攻擊。為了防止這種攻擊，密鑰空間必須非常大，例如，至少280 ，在很多情況下甚至更大。
充分密鑰空間原理給加密方案的安全性提供了必要條件，但不是充分條件。
3. 單字母替換加密
在“移位加密”中，明文到密文的映射是一個(gè)由密鑰決定的固定的移位，而在單字母替換加密中，允許映射是任意的，只受一對(duì)一的約束。密鑰空間包含字母表的所有雙射或置換。如下圖：
圖中的a映射到X，等等。
從該加密方案的名稱上能夠了解到這樣一個(gè)事實(shí)：密鑰定義了明文中單個(gè)字符的(固定)替換。假設(shè)使用的是26英文字母表，那么，密鑰空間的大小可計(jì)算為：26! = 26·25·24···2·1，大約為288 ，蠻力攻擊是不可行的。
單字母替代加密可以利用英語(yǔ)語(yǔ)言的統(tǒng)計(jì)特性進(jìn)行攻擊。由于每一個(gè)字母的映射都是固定的，所以，如果得知e映射為D，那么，其余的e都映射為D。英文字母的概率分布如下圖所示：
4. 維吉尼亞加密
可以使用統(tǒng)計(jì)攻擊來(lái)破解“單字母替代加密”，因?yàn)樗拿荑€定義了一個(gè)固定的映射，該映射逐字應(yīng)用于明文。在“多字母替代加密”中，該攻擊無(wú)效，它的密鑰定義了應(yīng)用于明文字符塊的映射。多字母替代加密“平滑”了密文中字符的頻率分布，使其更難進(jìn)行統(tǒng)計(jì)分析。維吉尼亞加密就是多字母替代加密的一種，可以看作是將移位密碼的不同實(shí)例應(yīng)用于明文的不同部分。如下圖所示，它的密鑰是一個(gè)字符串。加密是通過(guò)按密鑰的下一個(gè)字符表示的數(shù)量移動(dòng)每個(gè)明文字符來(lái)完成的，必要時(shí)在密鑰中環(huán)繞。
六、現(xiàn)代密碼學(xué)的原則
· 原則二：精確的假設(shè)：事實(shí)證明，大多數(shù)密碼證明依賴于關(guān)于某些數(shù)學(xué)問(wèn)題的算法難度的目前未被證明的假設(shè)
· 原則三：安全性證明：任何這樣的假設(shè)都必須明確并精確地陳述。
安全的加密方案應(yīng)該保證：不管攻擊者已經(jīng)擁有什么信息，密文都不應(yīng)該泄露關(guān)于底層明文的額外信息。
威脅模型（按強(qiáng)度增加的順序）：
1. 唯密文攻擊（Ciphertext-only attack）：敵手只觀察一個(gè)密文(或多個(gè)密文)，并試圖確定關(guān)于底層明文(或多個(gè)明文)的信息。
2. 已知明文攻擊（Known-plaintext attack）：在這里，對(duì)手能夠?qū)W習(xí)使用某個(gè)密鑰生成的一個(gè)或多個(gè)明文/密文對(duì)。然后，對(duì)手的目標(biāo)是推斷使用相同密鑰產(chǎn)生的其他密文的基礎(chǔ)明文的信息。
3. 選擇明文攻擊（Chosen-plaintext attack）：在這種攻擊中，對(duì)手可以獲得如上所述的明文/密文對(duì)，用于其選擇的明文。
4. 選擇密文攻擊（Chosen-ciphertext attack）：攻擊者能夠額外獲得其選擇的密文的解密(一些信息)，例如，解密攻擊者選擇的一些密文是否會(huì)產(chǎn)生有效的消息。同樣，對(duì)手的目標(biāo)是了解使用相同密鑰生成的其他密文(對(duì)手無(wú)法直接獲得其解密)的底層明文信息。
（來(lái)源：賽迪密碼信息安全）
