密碼學(xué)--加密演算法

勝利是屬于“公理正義”的一方。在歷史長河中，取得戰(zhàn)爭勝利的一方，往往取得歷史的“解釋權(quán)”，他們的意識(shí)形態(tài)就理所當(dāng)然地成為所謂的“主流價(jià)值觀”，因此，勝利者會(huì)被“解釋”成“公理正義”的一方，而失敗者會(huì)被無情地“污名化”、“妖魔化”。一般而言，勝利是屬于“掌握優(yōu)勢資源”的一方，這些優(yōu)勢資源包括了軍事力量、先進(jìn)科技、生產(chǎn)技術(shù)等等，同時(shí)也包括了為人諱言的“密碼技術(shù)”。

二次世界大戰(zhàn)中，日本海軍聯(lián)合艦隊(duì)可以說是當(dāng)時(shí)世界上最強(qiáng)的艦隊(duì)，而美國在珍珠港戰(zhàn)役之后，海軍實(shí)力已處于劣勢。然而，美國卻能破譯日本的密碼，在一連串所破譯的密電中，顯示出了日本海軍大將山本五十六的行蹤以及聯(lián)合艦隊(duì)的動(dòng)向，使美國能夠在山本五十六飛往所羅門群島途中將其狙殺，并以劣勢兵力贏得中途島海戰(zhàn)，這是整個(gè)太平洋戰(zhàn)役的轉(zhuǎn)折點(diǎn)。

勿庸置疑，密碼學(xué)的確是一門實(shí)用的科學(xué)；從以往王侯將相用來對(duì)他們所發(fā)布的信息加密，到今日的電子商務(wù)、“自然人認(rèn)證”、網(wǎng)絡(luò)安全等，其中所用的核心技術(shù)就是密碼學(xué)。

談到當(dāng)代密碼學(xué)的核心，我們就不可避免地要了解當(dāng)代密碼系統(tǒng)的運(yùn)作機(jī)制；要想對(duì)其安全性評(píng)估，就不可避免地要了解密碼系統(tǒng)的算法；如果只是將密碼系統(tǒng)算法輕描淡寫，或只是套用一些專業(yè)術(shù)語，充其量只能是“按圖索驥”，對(duì)于使用密碼學(xué)技術(shù)不會(huì)有實(shí)質(zhì)性的幫助。因?yàn)槿魏蚊艽a學(xué)所能提供的安全保證，不是建立在“入侵者無知”的假設(shè)上，其所要面對(duì)的是精通各類信息技術(shù)、了解密碼系統(tǒng)算法的超級(jí)駭客。

誠然，信息安全的漏洞，往往不是發(fā)生在所用的密碼算法上，而主要是由系統(tǒng)管理員造成的；也許密碼系統(tǒng)程序員能夠遵循密碼學(xué)算法，編寫一份近乎“完美無缺”的系統(tǒng)，卻可能忽略了運(yùn)行系統(tǒng)隨機(jī)產(chǎn)生的軟硬件問題；有時(shí)甚至所使用的密碼學(xué)產(chǎn)品本身就是泄密機(jī)。即使是以當(dāng)代密碼機(jī)RSA、DES、Triple DES為加密系統(tǒng)的“保健IC卡”或是“自然人認(rèn)證”，都曾發(fā)生過資料保密上的紕漏，被人視為近乎“完美無缺”的系統(tǒng)，卻無法保證非密碼層面不出問題。

本書并不想對(duì)整個(gè)信息安全的大架構(gòu)進(jìn)行討論，因?yàn)槌�了理論上的探討外，必須很�?shí)際地，從管理層面探討，這并非單從算法、協(xié)定中能解釋清楚的，這是大師級(jí)的工作，絕非筆者所長，但是當(dāng)代密碼學(xué)各類算法，有精確的數(shù)學(xué)描述方式，可以將其程序化，并將這些內(nèi)容列入教材，成效會(huì)豐常顯著。

一個(gè)成熟耐用的密碼系統(tǒng)，首先要有能經(jīng)得起嚴(yán)謹(jǐn)理論考驗(yàn)的算法。綜觀當(dāng)代密碼系統(tǒng)，主要可分為公開密鑰密碼系統(tǒng)（Public Key Cryptosystem）以及對(duì)稱密鑰密碼系統(tǒng)（Symmetric Key Cryptosystem）兩類。以前者為代表的有RSA、ElGamal、橢圓曲線密碼系統(tǒng)，而以后者為代表的有DES、AES等。這些密碼系統(tǒng)，都要用到一些數(shù)學(xué)上的概念，而用到最多的數(shù)學(xué)相關(guān)知識(shí)，是被數(shù)學(xué)王子高斯譽(yù)為“數(shù)學(xué)女王”、被人們視為最冷門的“數(shù)論”（Number Theory）；由于真正“了解內(nèi)情”的人實(shí)在不多，所以用當(dāng)代密碼技術(shù)為幌子行騙的空間很大，鑒于此，筆者特將相關(guān)的基礎(chǔ)數(shù)論內(nèi)容列入本書，其實(shí)就是大學(xué)“代數(shù)”以及部分“質(zhì)數(shù)”理論，這些內(nèi)容都是研究當(dāng)代密碼學(xué)的基礎(chǔ)。

由于當(dāng)代密碼技術(shù)的應(yīng)用已經(jīng)不是只在“紙上談兵”而已，必須依賴程序應(yīng)用。所以在本書編排上，特別用類似C/C++/Java的語法，對(duì)部分已成熟的算法寫成偽碼，只需很少的修改，就可以執(zhí)行運(yùn)算。對(duì)于密碼算法的學(xué)習(xí)，有相當(dāng)?shù)膸椭��?/p>

盡管古典密碼早已不符合當(dāng)代信息安全的需求，但就其中所帶來的益智性樂趣，筆者實(shí)在不想只是輕描淡寫；就二次大戰(zhàn)期間德國人所用的Enigma密碼機(jī)而言，除了歷史上的樂趣外，其中的加密解密運(yùn)算，其實(shí)就是對(duì)稱群的置換作用，就如同轉(zhuǎn)動(dòng)魔方一樣，是絕佳的“群”作用范例，令人著迷不已。

記得1998、1999年冬天，曾與RSA的A合作過的黃明德在臺(tái)灣大學(xué)講述他的一系列工作，在那時(shí)筆者領(lǐng)略到高深的“數(shù)論”以及“代數(shù)幾何”應(yīng)用到密碼學(xué)的研究是深邃而引人入勝的。

本書在撰寫中，費(fèi)時(shí)最久的是書中的每個(gè)例題，這些例題，除了少數(shù)參考了其他文獻(xiàn)外，大多數(shù)都是程序執(zhí)行的結(jié)果整理而成，部分也取自筆者的研究內(nèi)容。

另外，本書部分內(nèi)容，如RSA密碼、非對(duì)稱密鑰密碼與離散對(duì)數(shù)、數(shù)字簽名以及部分古典密碼的介紹，都是筆者在清云科技大學(xué)教授“密碼學(xué)”、“公開鑰密碼系統(tǒng)”時(shí)講授過的。筆者所指導(dǎo)的專題學(xué)生，也分別以“RSA電子投票研究”、“保健IC卡研究”、“RSA與PGP研究”當(dāng)作專題研究方向，專題學(xué)生林俊余與黃明宗等人，也做出以Java撰寫的RSA為基礎(chǔ)的“電子投票系統(tǒng)”的半成品，雖然離成熟產(chǎn)品還有很大距離，但也屬難能可貴。感謝這些專題學(xué)生林俊余、林罔永、許豐琳、楊賀杰、黃明宗、徐效群、林克儒、陳惠甄、陳華君、陳麗君、陳俞婷、李建志、潘丹尼、吳英綺的熱心參與，使得筆者在密碼學(xué)的授課以及學(xué)生研究會(huì)討論過程中，增加不少互動(dòng)。所謂“教學(xué)相長”，這對(duì)本書的撰寫也有一定的幫助。

在本書即將完成之際，筆者仍發(fā)現(xiàn)密碼學(xué)實(shí)在涉略廣大，許多內(nèi)容只好忍痛割舍，限于各種因素，無法面面俱到，作為教材不免有遺珠之憾。

特別感謝（臺(tái)灣）中央研究院數(shù)學(xué)所謝春忠教授對(duì)本書算法及算式逐一檢查校閱。感謝中央研究院數(shù)學(xué)所提供筆者短期訪問的機(jī)會(huì)，不少研究密碼學(xué)的相關(guān)文獻(xiàn)資料，都是在此取得。更感謝清云科技大學(xué)的系主任李振燾教授及系同事的支持與協(xié)助。另外在Lilie的協(xié)助下，本書也加上了“福爾摩斯密碼”一節(jié)，替本書增色不少。

本書部分函數(shù)圖形由數(shù)學(xué)軟件Mathematica產(chǎn)生，部分精美的圖案由全華科技圖書繪制而成。感謝Bletchley Park Trust所提供的珍貴照片及Sue May的協(xié)助，也感謝Brian Smith的居中聯(lián)絡(luò)。

鄧安文

序
前言
第1章 緒論 1
1.1 通信安全 1
1.2 公開密鑰密碼系統(tǒng)與對(duì)稱密鑰密碼系統(tǒng) 5
第2章 古典密碼 7
2.1 凱撒挪移碼 8
2.2 仿射密碼 9
2.3 單套字母替代法以及頻率分析 10
2.4 福爾摩斯密碼 13
2.5 Vigenère密碼 15
2.6 Hill密碼 20
2.7 單次密碼本 21
2.8 Enigma密碼機(jī) 22
2.9 破譯Enigma與對(duì)稱群 27
第3章 基礎(chǔ)數(shù)論 31
3.1 模運(yùn)算與輾轉(zhuǎn)相除法 31
3.2 中國余式子定理（Chinese Remainder Theorem） 36
3.3 Lagrange定理與費(fèi)馬小定理 38
3.4 原根 39
3.5 二次剩余（Quadratic Residue） 41
3.6 Galois域 45
3.7 質(zhì)數(shù)理論 48
3.8 連分?jǐn)?shù) 51
3.9 密碼安全偽隨機(jī)數(shù)生成器 54
第4章 信息理論 57
4.1 概率 57
4.2 完美秘密 58
4.3 熵 60
4.4 自然語言之熵 62
第5章 對(duì)稱密鑰密碼系統(tǒng) 66
5.1 DES與Feistel密碼 66
5.2 Triple DES挑戰(zhàn)DES 73
5.3 AES 75
5.4 IDEA 79
5.5 區(qū)塊密碼加密模式 83
第6章 RSA密碼 87
6.1 公開密鑰密碼系統(tǒng) 87
6.2 RSA算法 89
6.3 RSA的數(shù)論背景 92
6.4 RSA數(shù)字簽名 96
6.5 同時(shí)進(jìn)行RSA加密和RSA數(shù)字簽名 98
6.6 RSA-129挑戰(zhàn)與因數(shù)分解 100
6.7 二次篩法Pollard的p－1法 103
6.7.1 二次篩法 104
6.7.2 Pollard的p-1法 107
6.8 利用RSA私鑰因數(shù)分解 108
6.9 RSA密碼系統(tǒng)使用的注意事項(xiàng) 110
6.10 Wiener低冪次d攻擊 112
6.11 Rabin密碼 115
第7章 非對(duì)稱密鑰密碼系統(tǒng)與離散對(duì)數(shù) 119
7.1 Pohlig-Hellman密碼與離散對(duì)數(shù) 120
7.2 Diffie-Hellman密鑰交換 123
7.3 ElGamal密碼 126
7.4 Pohlig-Hellman算法 127
7.5 Index Calculus 129
第8章 數(shù)字簽名 131
8.1 數(shù)字簽名方案 131
8.2 RSA盲簽名 133
8.3 Hash函數(shù)簡介 135
8.4 生日攻擊 136
8.5 ElGamal數(shù)字簽名 137
8.6 DSA數(shù)字簽名 140
8.7 Schnorr數(shù)字簽名 143
8.8 Nyberg-Rueppel數(shù)字簽名 144
8.9 MD5 Hash函數(shù) 147
8.10 SHA-1 Hash函數(shù) 150
8.11 信息校驗(yàn)碼MAC 152
第9章 質(zhì)數(shù)與大整數(shù)算術(shù) 154
9.1 大整數(shù)的加減乘法 154
9.2 大整數(shù)的除法 157
9.3 Montgomery算術(shù) 159
9.4 Miller-Rabin質(zhì)數(shù)測試 161
9.5 Agrawal-Kayal-Saxena算法 163
9.6 公開密鑰密碼的質(zhì)數(shù) 165
9.6.1 強(qiáng)質(zhì)數(shù) 165
9.6.2 DSA質(zhì)數(shù) 166
9.7 Java的BigInteger Class 167
9.8 大整數(shù)算術(shù)與數(shù)論套件及軟件 171
第10章 橢圓曲線密碼 173
10.1 橢圓曲線 174
10.2 橢圓曲線（mod p） 179
10.3 加權(quán)投影坐標(biāo) 183
10.4 定義在Galois域 的橢圓曲線 185
10.5 密碼安全曲線 188
10.6 將信息轉(zhuǎn)化為橢圓曲線代碼 189
10.7 橢圓曲線公開密鑰密碼算法 190
10.8 橢圓曲線因數(shù)分解 196
10.9 ECCp-109挑戰(zhàn) 199
10.10 并行Pollard Rho法 201
第11章 公開密鑰基礎(chǔ)建設(shè) 204
11.1 認(rèn)證機(jī)構(gòu)CA 204
11.2 X.509 206
11.3 認(rèn)證機(jī)構(gòu)CA 207
第12章 量子密碼 208
12.1 量子實(shí)驗(yàn) 208
12.2 量子密鑰分配 210
12.3 淺談Shor之量子算法 212
參考文獻(xiàn) 214