3000字，看懂密碼學的底層原理
一、密碼學的定義
適用(yong)對象：
經典密碼學(xue)：軍事組織(zhi)和政(zheng)府。
現代(dai)密(mi)碼學：everywhere。
《簡(jian)明牛津英語詞典》：編碼(ma)或破譯密碼(ma)的藝術。（不夠完善準確）
現(xian)在密(mi)碼學：對(dui)保護數字信息、系統(tong)和分布(bu)式計算免受敵方攻擊的(de)數學技術(shu)的(de)研究(jiu)。
其演變過程可表(biao)示(shi)如下：
二、對稱加密簡述
在密(mi)碼學(xue)中，我們將加(jia)密(mi)方案(an)分為private-key (symmetric) encryption和public-key (asymmetric) encryption。
在private-key encryption中(zhong)，當通(tong)信雙方(fang)想要秘密通(tong)信的(de)時(shi)候(hou)，提前(qian)交換一(yi)個(ge)(ge)key。其中(zhong)一(yi)方(fang)可(ke)以使用(yong)(yong)這個(ge)(ge)key來加密一(yi)條消息(xi)，或者叫明(ming)文(wen)(wen) (plaintext)，然后(hou)發送給另一(yi)方(fang)。因此可(ke)以說，其中(zhong)一(yi)方(fang)將一(yi)個(ge)(ge)密文(wen)(wen)ciphertext發送給了另一(yi)方(fang)。接收(shou)者使用(yong)(yong)key解密這個(ge)(ge)密文(wen)(wen)，得到了原始(shi)消息(xi)。這里的(de)key都是相(xiang)同的(de)，并且用(yong)(yong)于明(ming)文(wen)(wen)和密文(wen)(wen)之(zhi)間的(de)轉換。這也(ye)是為(wei)什么人們將之(zhi)稱為(wei)symmetric encryption。然而asymmetric encryption與之(zhi)相(xiang)反，其加密和解密使用(yong)(yong)的(de)是不同的(de)key。
三、加密語法
Gen：密鑰生成算法
Enc：加密算法(fa)
所有(you)由Gen生成的密(mi)鑰k組成了一個密(mi)鑰空間(jian)，記為K。由Dec生成的密(mi)文c 組成了一個明文空間(jian)，記為C。
對稱(cheng)加密流程：運行Gen來生成密鑰k，當一方想(xiang)要發(fa)送(song)明文消(xiao)息m給另一方時，
然后在公開信道(dao)中將密文c發送(song)給對方(fang)。
計算m : = Deck(c)來得到原始消息。
“ := ”表示確定性等(deng)式，假設(she)此處的(de)Enc是確定性的(de)，Enc是概率性的(de)算(suan)法
四、Kerckhoffs原則
“加密(mi)(mi)方案(an)沒有(you)必要保密(mi)(mi)，它可以被敵人(ren)輕易獲(huo)得。”
理(li)由：
2. 如(ru)果誠實方(fang)(fang)共享(xiang)的秘密信(xin)息被(bei)泄(xie)漏，更換密鑰比更換加密方(fang)(fang)案容易(yi)得多(duo)。此外，生成一個(ge)(ge)新的隨機(ji)密鑰是(shi)相(xiang)對簡(jian)單的，而設(she)計一個(ge)(ge)新的加密方(fang)(fang)案則(ze)是(shi)一個(ge)(ge)巨大的工程。
3. 在廣(guang)泛部署加密(mi)方(fang)案(an)之前，鼓勵(li)公眾對該方(fang)案(an)進行審查以(yi)(yi)檢查可能存在的(de)弱點，這(zhe)是一(yi)個(ge)顯著的(de)好處。進一(yi)步地，標準(zhun)化(hua)加密(mi)方(fang)案(an)可以(yi)(yi)確保不同(tong)用戶之間的(de)兼(jian)容性，公眾將使用經過公開審查的(de)強大的(de)加密(mi)方(fang)案(an)。這(zhe)更加令(ling)人信服。
五、經典加密方案
以下介紹的加密方案均已被破解，是不安全的，但是其思想值得學習。
1. 凱(kai)撒加密（Caesar’s cipher）
凱撒(sa)加(jia)(jia)(jia)密(mi)(mi)(mi)是(shi)最古老的(de)加(jia)(jia)(jia)密(mi)(mi)(mi)方(fang)(fang)案之(zhi)一，它(ta)(ta)將(jiang)字母(mu)表中的(de)字母(mu)向右移動3個位(wei)(wei)置(zhi)進行加(jia)(jia)(jia)密(mi)(mi)(mi)。即，a加(jia)(jia)(jia)密(mi)(mi)(mi)為D，b加(jia)(jia)(jia)密(mi)(mi)(mi)為E，以(yi)(yi)此類推(tui)。當移動到字母(mu)表的(de)末尾時(shi)，回到字母(mu)表的(de)開頭，循環移位(wei)(wei)。該方(fang)(fang)案沒有(you)(you)密(mi)(mi)(mi)鑰，且加(jia)(jia)(jia)密(mi)(mi)(mi)方(fang)(fang)法(fa)是(shi)固定的(de)。因此任何人可(ke)以(yi)(yi)通過學習凱撒(sa)加(jia)(jia)(jia)密(mi)(mi)(mi)的(de)加(jia)(jia)(jia)密(mi)(mi)(mi)方(fang)(fang)法(fa)來(lai)輕易的(de)破解密(mi)(mi)(mi)文。其(qi)變體ROT-13依(yi)然被各種在線論壇使用。我們可(ke)以(yi)(yi)從中發(fa)現，它(ta)(ta)們均沒有(you)(you)提供任何的(de)密(mi)(mi)(mi)碼學安全(quan)性(xing)，它(ta)(ta)們僅(jin)僅(jin)是(shi)使得(de)消息(xi)是(shi)令人難以(yi)(yi)理解的(de)，除非消息(xi)的(de)讀者有(you)(you)意識地決定解密(mi)(mi)(mi)它(ta)(ta)。
2. 移位加密
移(yi)位加密可(ke)以(yi)視為凱(kai)撒加密的(de)(de)一(yi)(yi)(yi)(yi)(yi)種密鑰變(bian)體。在(zai)移(yi)位加密中(zhong)，密鑰k是一(yi)(yi)(yi)(yi)(yi)個介于0到25之間的(de)(de)數字(zi)，在(zai)凱(kai)撒加密中(zhong)，字(zi)母(mu)移(yi)動3個位置，而在(zai)移(yi)位加密中(zhong)，字(zi)母(mu)移(yi)動k個位置。其(qi)算法可(ke)概括如下：明(ming)文(wen)(wen)空(kong)間M由任意長度的(de)(de)英文(wen)(wen)字(zi)母(mu)字(zi)符串組(zu)成(cheng)，其(qi)中(zhong)去掉(diao)了(le)標(biao)點(dian)、空(kong)格和數字(zi)，并(bing)且大(da)小寫沒(mei)有(you)區別。Gen輸(shu)出一(yi)(yi)(yi)(yi)(yi)個均勻(yun)一(yi)(yi)(yi)(yi)(yi)致(zhi)的(de)(de)密鑰k ∈ { 0 , . . . , 25 } ，算法Enc將(jiang)(jiang)一(yi)(yi)(yi)(yi)(yi)個密鑰k和一(yi)(yi)(yi)(yi)(yi)個明(ming)文(wen)(wen)作(zuo)為輸(shu)入(ru)，然(ran)后(hou)(hou)將(jiang)(jiang)明(ming)文(wen)(wen)的(de)(de)每個字(zi)母(mu)向(xiang)前移(yi)動k個位置，算法Dec將(jiang)(jiang)一(yi)(yi)(yi)(yi)(yi)個密鑰k和一(yi)(yi)(yi)(yi)(yi)個密文(wen)(wen)作(zuo)為輸(shu)入(ru)，然(ran)后(hou)(hou)將(jiang)(jiang)將(jiang)(jiang)密文(wen)(wen)中(zhong)的(de)(de)每個字(zi)母(mu)向(xiang)后(hou)(hou)移(yi)k個位置。
在不知道密鑰(yao)k的(de)(de)情況下，破(po)解(jie)密文(wen)也是(shi)相當(dang)容易(yi)的(de)(de)。因(yin)為它只有26個可能(neng)的(de)(de)密鑰(yao)，攻擊(ji)者(zhe)只需要用這(zhe)些可能(neng)的(de)(de)密鑰(yao)去解(jie)密密文(wen)即可，故(gu)可得到26種(zhong)可能(neng)的(de)(de)候選(xuan)明(ming)(ming)文(wen)，正確(que)的(de)(de)明(ming)(ming)文(wen)就在這(zhe)26種(zhong)之中。此(ci)外，如(ru)果密文(wen)“足夠(gou)長”，那(nei)么正確(que)的(de)(de)明(ming)(ming)文(wen)很可能(neng)是(shi)列表(biao)中唯一“有意義(yi)”的(de)(de)候選(xuan)明(ming)(ming)文(wen)。（這(zhe)在大多數時候是(shi)正確(que)的(de)(de)）
這種嘗試每一個可能的(de)密鑰(yao)的(de)攻(gong)擊(ji)被稱(cheng)為(wei)蠻(man)力 (brute-force) 或窮舉 (exhausient-search) 攻(gong)擊(ji)。故如果加密方(fang)案要保證安全，就不能輕(qing)易受(shou)到這種攻(gong)擊(ji)，這個觀察被稱(cheng)為(wei)充分密鑰(yao)空(kong)間(jian)原(yuan)理(li)：任(ren)何(he)安全的(de)加密方(fang)案必(bi)須要有足(zu)夠大的(de)密鑰(yao)空(kong)間(jian)來抵抗(kang)窮舉搜索攻(gong)擊(ji)。為(wei)了防止這種攻(gong)擊(ji)，密鑰(yao)空(kong)間(jian)必(bi)須非(fei)常(chang)大，例(li)如，至少280 ，在很多情(qing)況下甚(shen)至更大。
充(chong)分密鑰空間原理給加密方(fang)案(an)的(de)安(an)全性提供了必要(yao)條件，但(dan)不(bu)是充(chong)分條件。
3. 單字母替換(huan)加(jia)密
在“移位(wei)(wei)加(jia)密”中(zhong)，明文到(dao)密文的(de)映射是一(yi)(yi)個由密鑰決定(ding)的(de)固定(ding)的(de)移位(wei)(wei)，而在單字母替換加(jia)密中(zhong)，允(yun)許映射是任意的(de)，只受一(yi)(yi)對一(yi)(yi)的(de)約束。密鑰空間包(bao)含字母表的(de)所有雙射或置(zhi)換。如下圖：
圖(tu)中(zhong)的(de)a映(ying)射到X，等等。
從該加密(mi)方案的名稱上能夠了(le)解到這樣一個事實(shi)：密(mi)鑰定義(yi)了(le)明文中單個字符的(固定)替換(huan)。假設(she)使用的是26英文字母表，那么(me)，密(mi)鑰空間的大小可計算為：26! = 26·25·24···2·1，大約為288 ，蠻力(li)攻擊(ji)是不可行的。
單字(zi)(zi)母(mu)替代加密(mi)可以(yi)利用英(ying)(ying)語語言的(de)(de)統計特性進(jin)行攻擊。由于每(mei)一個字(zi)(zi)母(mu)的(de)(de)映(ying)射(she)都是固定(ding)的(de)(de)，所(suo)(suo)以(yi)，如(ru)果得知e映(ying)射(she)為(wei)D，那么(me)，其余的(de)(de)e都映(ying)射(she)為(wei)D。英(ying)(ying)文字(zi)(zi)母(mu)的(de)(de)概(gai)率分布(bu)如(ru)下圖(tu)所(suo)(suo)示：
4. 維吉尼亞加(jia)密
可以使用(yong)統計(ji)攻擊來破解“單字(zi)(zi)(zi)母替(ti)代加(jia)(jia)密(mi)”，因為它的(de)(de)(de)密(mi)鑰(yao)(yao)(yao)定(ding)義了一個(ge)固定(ding)的(de)(de)(de)映(ying)(ying)射(she)，該(gai)(gai)映(ying)(ying)射(she)逐字(zi)(zi)(zi)應(ying)用(yong)于明文(wen)(wen)。在(zai)“多(duo)字(zi)(zi)(zi)母替(ti)代加(jia)(jia)密(mi)”中(zhong)，該(gai)(gai)攻擊無效，它的(de)(de)(de)密(mi)鑰(yao)(yao)(yao)定(ding)義了應(ying)用(yong)于明文(wen)(wen)字(zi)(zi)(zi)符(fu)塊的(de)(de)(de)映(ying)(ying)射(she)。多(duo)字(zi)(zi)(zi)母替(ti)代加(jia)(jia)密(mi)“平滑(hua)”了密(mi)文(wen)(wen)中(zhong)字(zi)(zi)(zi)符(fu)的(de)(de)(de)頻率分(fen)布，使其(qi)更難(nan)進行統計(ji)分(fen)析。維吉尼亞加(jia)(jia)密(mi)就是(shi)多(duo)字(zi)(zi)(zi)母替(ti)代加(jia)(jia)密(mi)的(de)(de)(de)一種，可以看作是(shi)將移位(wei)密(mi)碼的(de)(de)(de)不(bu)(bu)同實例應(ying)用(yong)于明文(wen)(wen)的(de)(de)(de)不(bu)(bu)同部分(fen)。如下圖所示，它的(de)(de)(de)密(mi)鑰(yao)(yao)(yao)是(shi)一個(ge)字(zi)(zi)(zi)符(fu)串。加(jia)(jia)密(mi)是(shi)通過按密(mi)鑰(yao)(yao)(yao)的(de)(de)(de)下一個(ge)字(zi)(zi)(zi)符(fu)表示的(de)(de)(de)數量(liang)移動每個(ge)明文(wen)(wen)字(zi)(zi)(zi)符(fu)來完成(cheng)的(de)(de)(de)，必要時在(zai)密(mi)鑰(yao)(yao)(yao)中(zhong)環繞。
六、現代密碼學的原則
· 原則二：精(jing)確的(de)假設：事(shi)實證(zheng)(zheng)明，大(da)多數密(mi)碼證(zheng)(zheng)明依賴(lai)于關于某些數學問題的(de)算(suan)法難度的(de)目前未被證(zheng)(zheng)明的(de)假設
· 原則三：安全性證明：任(ren)何這樣(yang)的(de)假(jia)設都(dou)必須明確并精確地陳述。
; 安(an)全的加(jia)密方案應該保證(zheng)：不(bu)管攻擊者已經擁(yong)有什么信(xin)(xin)息，密文都不(bu)應該泄露(lu)關于底層明文的額(e)外(wai)信(xin)(xin)息。
威脅模型(xing)（按(an)強度增加的順序(xu)）：
1. 唯(wei)密文(wen)攻(gong)擊（Ciphertext-only attack）：敵(di)手只觀察一(yi)個密文(wen)(或多(duo)個密文(wen))，并試圖確定關于底層明(ming)文(wen)(或多(duo)個明(ming)文(wen))的信息。
2. 已知明(ming)文(wen)攻擊（Known-plaintext attack）：在這里，對手能(neng)夠學習使(shi)用某個(ge)密(mi)鑰(yao)生成的(de)一(yi)個(ge)或(huo)多個(ge)明(ming)文(wen)/密(mi)文(wen)對。然后，對手的(de)目標是推(tui)斷使(shi)用相同密(mi)鑰(yao)產(chan)生的(de)其他密(mi)文(wen)的(de)基礎明(ming)文(wen)的(de)信(xin)息。
3. 選擇明文攻擊（Chosen-plaintext attack）：在這種攻擊中(zhong)，對(dui)手可以(yi)獲得如(ru)上(shang)所述的明文/密文對(dui)，用于其選擇的明文。
4. 選擇密(mi)(mi)文(wen)(wen)攻(gong)(gong)擊（Chosen-ciphertext attack）：攻(gong)(gong)擊者(zhe)能夠額(e)外獲得其(qi)選擇的(de)密(mi)(mi)文(wen)(wen)的(de)解密(mi)(mi)(一些(xie)信息(xi))，例如，解密(mi)(mi)攻(gong)(gong)擊者(zhe)選擇的(de)一些(xie)密(mi)(mi)文(wen)(wen)是(shi)否會產(chan)生(sheng)(sheng)有(you)效的(de)消息(xi)。同樣，對手的(de)目標是(shi)了解使用相(xiang)同密(mi)(mi)鑰(yao)生(sheng)(sheng)成的(de)其(qi)他密(mi)(mi)文(wen)(wen)(對手無法直接獲得其(qi)解密(mi)(mi))的(de)底(di)層明文(wen)(wen)信息(xi)。
（來源：賽(sai)迪密碼信息安全）
