加密．解謎．密碼學：從歷史發展到關鍵應用，有趣得不可思議的密碼研究

01
「只要解出來，算你了不起」
古典密碼：高手過招的智慧博弈


2009年1月23日，農曆臘月二十八，正當網友們準備迎接春節的到來時，一位暱稱為「HighnessC」的網友於淩晨4時12分在百度「密碼吧」發布了一個帖子：

最近和一個心儀的女生告白，
誰知道她給了我一個摩斯密碼，說解出來了才答應和我約會。
可是我用盡了所有方法都解不開這個密碼。好鬱悶啊。只能向你們求救了。
****- / *---- / ----* / ****- / ****- / *---- / ---** / *---- / ****- / *---- / -**** /
***-- / ****- / *---- / ----* / **--- / -**** / **--- / **--- / ***-- / --*** / ****- /
她唯一給我的提示就是，這是個5層加密的密碼……
也就是說要破解了5層密碼才是答案……
好鬱悶啊……
救救我啊……

求助帖很快得到了網友的熱烈回應。一段時間後，網友很快分成了兩派。一部分網友的態度很悲觀，在回帖中無奈地表示「5層基本沒救了，節哀吧」。另一派網友準備迎難而上，嘗試破解這個「基本沒救」的密碼。很快，網友「PorscheL」於4時57分在6樓回帖，表示第1層密碼已經解開。但是，後面4層密碼的破解似乎困難重重，進度暫時陷入停滯狀態。
12時24分，樓主「HighnessC」從心儀的女生那裡得到了一些提示，他在12樓發帖稱：

經過昨天一晚的奮鬥，
我還是破解不了。
不過今天我死磨她，叫她給提示，她說中間有一個步驟是「替代密碼」，而密碼表則是我們人類每天都可能用到的東西。
我會再多套一點資訊的……
希望大大幫忙解答啊……
畢竟我也希望不要她親口說出這個密碼的答案……

這個提示為密碼的破解帶來了巨大的幫助。16時45分，網友「片翌天使」沿著38樓網友「幻之皮卡丘」提供的思路，於83樓成功解開了第2層密碼；17時9分，網友「巨蟹座的傳說」於93樓提供了解開第3層密碼的思路；18時39分，網友「片翌天使」於158樓宣布密碼已經完全破解，並稱「樓主你好幸福哦」；20時02分，網友「片翌天使」於207樓整合了完整的解密步驟，公布了密碼破解結果。至此，經過14個小時的努力，這個5層加密的密碼終於被破解！破解結果也是皆大歡喜，密碼吧的網友見證了他們的愛情。衷心希望這一對情侶能夠在網友的見證下走到一起，共度美好的未來。

樓主「HighnessC」曾在帖子中表示，給他出這道題的女生很喜歡古典密碼。那麼古典密碼是什麼？如何破解這個5層加密的古典密碼？這個5層加密的古典密碼中又蘊含著怎樣的歷史故事呢？

歷史上，密碼設計者和密碼破譯者曾進行過曠日持久的鬥爭。電腦誕生之前，密碼設計者用自己的聰明才智設計出了很多看似牢不可破的密碼。然而，這些密碼設計思想的背後並沒有堅實的理論基礎。在大多數情況下，密碼破譯者都能在鬥爭中大獲全勝，把這些密碼完美破解。根據這些相對簡單、但無堅實理論基礎支撐的設計思想所建構出的密碼，被稱為古典密碼（Classical Cryptography）。

電腦誕生之後，密碼設計者在數學與電腦科學領域逐漸找到了設計密碼的理論依據，最終設計出了一系列真正難以被破解的密碼。這類依據堅實理論基礎而設計出的密碼被稱為現代密碼（Modern Cryptography）。借助數學與電腦科學的強大武器，密碼設計者終於柳暗花明，在與密碼破譯者的鬥爭中打了個漂亮的勝仗。

雖然在現代通訊領域中，已不再使用古典密碼，但不能否認古典密碼在密碼學發展史上的重要作用。本章將細數古典密碼的歷史故事，為讀者拆解密碼設計者和密碼破譯者在密碼戰爭中的各種招數。在了解古典密碼的原理和設計思想後，本章將回顧網友「片翌天使」對5層密碼的破解過程，重溫誕生於「密碼吧」的愛情故事。了解了常用的古典密碼後，各位也可以建構屬於自己的密碼，用這種特殊的方式向心儀的人傳達心意。

在開啟古典密碼之旅前，首先要了解另一個概念：編碼（Code）。編碼看似密碼，但嚴格來說並不是密碼。編碼的根本目的是尋找一種方式，通過電報、電台、網路等傳輸媒介進行遠距離通訊。因此，可以把編碼看成是機器之間互相交流的「機器語言」。所謂編碼過程（Encode），就是把人類語言翻譯成機器語言。與編碼過程對應的解碼過程（Decode），就是把機器語言翻譯成人類語言。知乎上有很多利用編碼作為密碼的例子。對於這類「密碼」，只要知道編碼和解碼方式，就很容易恢復隱藏於其中的資訊。

01
「只要解出來，算你了不起」
古典密碼：高手過招的智慧博弈


2009年1月23日，農曆臘月二十八，正當網友們準備迎接春節的到來時，一位暱稱為「HighnessC」的網友於淩晨4時12分在百度「密碼吧」發布了一個帖子：

最近和一個心儀的女生告白，
誰知道她給了我一個摩斯密碼，說解出來了才答應和我約會。
可是我用盡了所有方法都解不開這個密碼。好鬱悶啊。只能向你們求救了。
****- / *---- / ----* / ****- / ****- / *---- / ---** / *---- / ****- / *---- / -**** /
***-- / ****- / *---- / ----* / **--- / -**** / **-...

自 序
2017年5月，我接到了知乎編輯的邀請，邀我寫一本密碼學的科普書籍。要用生動淺顯的例子，在不涉及複雜數學知識的條件下為晦澀難懂的密碼學原理進行科普，其難度可想而知。然而，伴隨著網際網路的蓬勃發展，網路的資安問題也日益嚴重。密碼學是維護網路安全的核心技術之一。作為一名專攻密碼學的博士，為讀者朋友撰寫一本淺顯易懂的密碼學科普讀物，使讀者朋友了解默默保護著我們的密碼技術，是一種義務，也是一種責任。我最終接受了這個挑戰，完成了這本書。
密碼學的發展可以分為兩個時期：古典密碼學時期與現代密碼學時期。在古典密碼學時期，密碼學家還沒有掌握設計出安全密碼的科學方法。當時密碼的設計完全仰賴密碼設計者的聰明才智，而密碼的破解更是要靠密碼破譯者的靈光一現。到了20世紀中期，電腦科學的奠基人圖靈（Alan Turing）和資訊理論的奠基人夏農（Claude Shannon）為密碼學找到了可靠的理論基礎，密碼學才正式步入現代密碼學時期，為資料安全保駕護航。現在，是時候讓密碼學這位幕後英雄走到台前，在讀者面前亮相了。
從2014年起，我開始在知乎上回答密碼學領域的相關問題，並因此收到了很多朋友的讚揚與感謝。2016年，我成為知乎密碼學領域的優秀回答者，並完成了電子書《質數了不起》。現在，《質數了不起》的擴展版本——也就是本書，也終於要和讀者朋友見面了。本書與《質數了不起》比起來約有80%的內容為新增內容，補充了大量原本未涉及或簡述的章節。我很希望能夠過本書所講解的內容，為讀者朋友介紹密碼學的基本概念和基本原理，介紹隱藏在密碼學背後的數學知識，也希望這本書能激發各位對密碼學的興趣。
在此，我想真誠感謝為本書的撰寫和出版做出貢獻的朋友們。非常感謝我的妻子李雯對本書的大力支持。她幫助我修正了很多語法錯誤，並站在讀者的角度為本書提出了很多寶貴的建議。感謝我的師妹金歌為本書中出現的德文詞彙和語句提供準確的翻譯，並對本書進行了認真的校對，指出了很多語言問題。感謝我在阿爾法字幕組的合作夥伴吳詩湄為本書繪製插圖，她的繪圖為本書增添了更多活力。感謝阿里巴巴集團數據技術及產品部的張磊老師、馮偵探老師、沈則潛老師、高愛強老師等，謝謝你們的支持和幫助。
國際計算機協會（ACM）和電機電子工程師學會（IEEE）會士、浙江大學網絡空間安全學院院長任奎老師，北京航空航天大學密碼學教授伍前紅老師，阿里巴巴集團安全部密碼學與隱私保護技術總監洪澄老師，騰訊安全雲鼎實驗室總監錢業斐老師，深信服首席安全研究員、藍軍首席架構師彭峙釀老師，知乎密碼學話題優秀答主段立老師，都在閱讀樣稿後給予了熱情的推薦。我的博士生導師、北京航空航天大學網絡空間安全學院院長劉建偉教授更是為本書撰寫了推薦序。我在此向他們致以衷心的感謝！雖然我已經盡我所能確保本書的正確性和嚴謹性，但由於我個人的知識水準有限，書中難免出現錯誤或表述不當之處，懇請讀者朋友提出寶貴的意見和建議。

劉巍然 2020年11月

自 序
2017年5月，我接到了知乎編輯的邀請，邀我寫一本密碼學的科普書籍。要用生動淺顯的例子，在不涉及複雜數學知識的條件下為晦澀難懂的密碼學原理進行科普，其難度可想而知。然而，伴隨著網際網路的蓬勃發展，網路的資安問題也日益嚴重。密碼學是維護網路安全的核心技術之一。作為一名專攻密碼學的博士，為讀者朋友撰寫一本淺顯易懂的密碼學科普讀物，使讀者朋友了解默默保護著我們的密碼技術，是一種義務，也是一種責任。我最終接受了這個挑戰，完成了這本書。
密碼學的發展可以分為兩個時期：古典密碼學時期與現代密碼學時...

自序
01
「只要解出來，算你了不起」
古典密碼：高手過招的智慧博弈
1.1 換種表示：編碼 16
1.1.1　最初的編碼：摩斯電碼 18
1.1.2　摩斯電碼的困境 24
1.1.3　博多碼與ASCII碼 29
1.1.4　琳琅滿目的各國編碼標準 36
1.1.5　Unicode與UTF 38
1.1.6　Base16、Base32與Base64 41

1.2 換個位置：移位密碼 45
1.2.1　移位密碼的起源：斯巴達密碼棒 45
1.2.2　柵欄密碼 47
1.2.3　帶金鑰的柵欄移位密碼 50
1.2.4　其他移位密碼 53
1.2.5　知乎上的移位密碼破解實例 55

1.3 換種符號：代換密碼 59
1.3.1　代換密碼的起源：凱撒密碼 59
1.3.2　簡單的代換密碼 61
1.3.3　複雜的代換密碼 65
1.3.4　將字母代換成符號 68
1.3.5　代換密碼的安全性 72

1.4 密碼吧神帖的破解 78
1.4.1　第一層密碼：摩斯電碼 78
1.4.2　第二層密碼：手機鍵盤代換密碼 78
1.4.3　第三層密碼：電腦鍵盤代換密碼 80
1.4.4　第四層和第五層密碼：格柵密碼與字母逆序 81

02
「今天有小雨，無特殊情況」
戰爭密碼：生死攸關的較量
2.1 將古典進行到底：第一次世界大戰中的密碼 92
2.1.1　齊默曼電報 92
2.1.2　ADFGX密碼 96
2.1.3　ADFGVX密碼 99

2.2 維吉尼亞密碼：安全密碼設計的思路源泉 102
2.2.1　維吉尼亞密碼的發明史 102
2.2.2　維吉尼亞密碼的缺陷 107
2.2.3　維吉尼亞密碼的破解 110
2.2.4　《消失》：不能用頻率分析法攻擊的文本 115

2.3 恩尼格瑪機：第二次世界大戰德軍的密碼 119
2.3.1　恩尼格瑪機的核心：轉子 119
2.3.2　恩尼格瑪機的組成和使用方法 125
2.3.3　恩尼格瑪機的工作原理 128
2.3.4　恩尼格瑪機的破解方法 136

03
「曾愛理不理，現高攀不起」
數論基礎：密碼背後的數學原理
3.1 質數的定義：整數之間的整除關係 154
3.1.1　最簡單的運算：加、減、乘、除 154
3.1.2　加、減、乘、除引發的兩次數學危機 158
3.1.3　質數的定義 164
3.1.4　哥德巴赫猜想 164

3.2 質數的性質 170
3.2.1　質數的分布 171
3.2.2　質數螺旋與孿生質數 172
3.2.3　質數的判定 178
3.2.4　最大公因數及其應用 183

3.3 同餘算數及其性質 186
3.3.1　同餘算數 186
3.3.2　模數為2的同餘算數：電腦的基礎 187
3.3.3　模數為N的同餘算數：奇妙的互質 193
3.3.4　模數為p的同餘算數：單純許多 199
3.3.5　看似簡單卻如此困難：整數分解問題與離散對數問題 201

3.4 身份證號碼中隱藏的數學玄機 209
3.4.1　身份證號碼的出生日期碼擴展 209
3.4.2　身份證號碼的校驗方法 212
3.4.3　身份證校驗碼所蘊含的數學原理 218
3.4.4　有關身份證號碼的擴展問題 221

04
「你說你能破解，你行你上呀」
安全密碼：守護數據的科學方法
4.1 「誰來都沒用，上帝也不行」：對稱密碼 230
4.1.1　對稱密碼的基本概念 230
4.1.2　避免金鑰重複使用的另一種加密構想：滾動金鑰 234
4.1.3　一次一密：從看似不可破解到可證明不可破解 239
4.1.4　完備保密性的缺陷與計算安全性 246
4.1.5　實現計算安全性：DES與AES 248

4.2 「給我保險箱，放好撞上門」：公開金鑰密碼 253
4.2.1　信件安全傳遞問題 254
4.2.2　狄菲—赫爾曼金鑰協商協定 259
4.2.3　狄菲與赫爾曼的好幫手默克 265
4.2.4　撞門的保險箱：公開金鑰加密 271
4.2.5　RSA公鑰加密方案與ElGamal公鑰加密方案 273

4.3 「鑰匙防調包，本人簽個字」：數位簽章 278
4.3.1　威力十足的中間人攻擊 279
4.3.2　防止鑰匙或保險箱調包的數位簽章 282
4.3.3　RSA數位簽章方案 286

4.4 RSA的破解之道 291
4.4.1　質數選得足夠大，合數的質因數分解難度並不一定大 293
4.4.2　在使用RSA時，永遠不要使用相同的合數 295
4.4.3　公鑰和私鑰都不能選得特別小 296
4.4.4　RSA中的其他安全問題 298

後記 303
專有名詞、人名一覽表 305

自序
01
「只要解出來，算你了不起」
古典密碼：高手過招的智慧博弈
1.1 換種表示：編碼 16
1.1.1　最初的編碼：摩斯電碼 18
1.1.2　摩斯電碼的困境 24
1.1.3　博多碼與ASCII碼 29
1.1.4　琳琅滿目的各國編碼標準 36
1.1.5　Unicode與UTF 38
1.1.6　Base16、Base32與Base64 41

1.2 換個位置：移位密碼 45
1.2.1　移位密碼的起源：斯巴達密碼棒 45
1.2.2　柵欄密碼 47
1.2.3　帶金鑰的柵欄移位密碼 50
1.2.4　其他移位密碼 53
1.2.5　知乎上的移位密碼破解實例 55

1.3 換種符號：代換密碼 59
1.3.1　代換密碼的起...