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

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

勿庸置疑，密碼學的確是一門實用的科學；從以往王侯將相用來對他們所發布的信息加密，到今日的電子商務、“自然人認證”、網絡安全等，其中所用的核心技術就是密碼學。

談到當代密碼學的核心，我們就不可避免地要了解當代密碼系統的運作機制；要想對其安全性評估，就不可避免地要了解密碼系統的算法；如果只是將密碼系統算法輕描淡寫，或只是套用一些專業術語，充其量只能是“按圖索驥”，對于使用密碼學技術不會有實質性的幫助。因為任何密碼學所能提供的安全保證，不是建立在“入侵者無知”的假設上，其所要面對的是精通各類信息技術、了解密碼系統算法的超級駭客。

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

本書并不想對整個信息安全的大架構進行討論，因為除了理論上的探討外，必須很實際地，從管理層面探討，這并非單從算法、協定中能解釋清楚的，這是大師級的工作，絕非筆者所長，但是當代密碼學各類算法，有精確的數學描述方式，可以將其程序化，并將這些內容列入教材，成效會豐常顯著。

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

由于當代密碼技術的應用已經不是只在“紙上談兵”而已，必須依賴程序應用。所以在本書編排上，特別用類似C/C++/Java的語法，對部分已成熟的算法寫成偽碼，只需很少的修改，就可以執行運算。對于密碼算法的學習，有相當的幫助。

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

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

本書在撰寫中，費時最久的是書中的每個例題，這些例題，除了少數參考了其他文獻外，大多數都是程序執行的結果整理而成，部分也取自筆者的研究內容。

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

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

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

本書部分函數圖形由數學軟件Mathematica產生，部分精美的圖案由全華科技圖書繪制而成。感謝Bletchley Park Trust所提供的珍貴照片及Sue May的協助，也感謝Brian Smith的居中聯絡。

鄧安文

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