密碼的數學（簡體書）

目錄：

前言
致謝
第一章 密碼和替換密碼
1.1 愛麗絲與鮑勃與卡爾與尤利烏斯：術語與凱撒密碼
1.2 關鍵問題：凱撒密碼的一般化
1.3 乘法密碼
1.4 仿射密碼
1.5 破曉攻擊：簡單替換密碼的密碼分析
1.6 剛好登上這座山：多字替換密碼
1.7 已知明文攻擊
1.8 展望
第二章 多表替換密碼
2.1 同音密碼
2.2 純屬巧合還是處心積慮？
2.3 阿爾伯蒂密碼
2.4 我好方：表格法，又稱維吉尼亞方陣密碼
2.5 多少才算多？確定字母表數量
2.6 超人留下吃晚餐：疊置與還原
2.7 多表密碼的乘積
2.8 轉輪機和轉子機
2.9 展望
第三章 換位密碼
3.1 這就是斯巴達！密碼棒
3.2 柵欄與路徑：幾何換位密碼
3.3 排列與排列密碼
3.4 排列乘積
3.5 帶密鑰的縱行換位密碼
補充閱讀3.1 實用虛無主義
3.6 決定矩形的寬度
3.7 拼字遊戲
補充閱讀3.2 然而一說到攪亂
3.8 展望
第四章 密碼與計算機
4.1 辛苦娘子磨豆腐：多項密碼與二進制數字
4.2 分餾密碼
4.3 如何設計數字密碼：SP網絡與法伊斯特爾網絡
補充閱讀4.1 明文數字化
4.4 數據加密標準
4.5 高級加密標準
4.6 展望
第五章 序列密碼
5.1 流動密鑰密碼
補充閱讀5.1 原來你也在這裡
5.2 一次性密碼本
5.3 帶著你的妹妹帶著你的嫁妝趕著那馬車來：自動密鑰密碼
5.4 線性反饋移位寄存器
5.5 向LFSR添加非線性
5.6 展望
第六章 帶指數的密碼
6.1 用指數加密
6.2 費馬小定理
6.3 用指數解密
6.4 離散對數問題
6.5 合數為模
6.6 歐拉函數
6.7 以合數為模時的解密
補充閱讀6.1 哼哼哈兮
6.8 展望
第七章 公鑰密碼
7.1 公鑰密碼的思路：完全公開
7.2 迪菲-赫爾曼密鑰協議
7.3 非對稱密碼學
7.4 RSA
7.5 注水啟動：素數檢驗
7.6 為什麼說RSA是（好的）公鑰系統？
7.7 RSA的密碼分析
7.8 展望
附錄一 公鑰密碼學的隱秘歷史
第八章 其它公鑰系統
8.1 三次傳遞協議
8.2 賈邁勒（ElGamal）
8.3 橢圓曲線密碼學
8.4 數字簽名
8.5 展望
第九章 密碼學的未來
9.1 量子計算
9.2 後量子密碼學
9.3 量子密碼學
9.4 展望

第一章 密碼和替換密碼
1.1 愛麗絲與鮑勃與卡爾與尤利烏斯：術語與凱撒密碼
幾乎從書寫的誕生開始，人們就在試圖隱藏書面信息的內容了，也由此發展出了很多不同的方法來實現這一點。也幾乎就從人們試著隱藏信息開始，學者也開始對這些方法進行分類和描述。不好玩的地方在於，這樣一來我就不得不直接扔給你們一大堆專門術語。更糟糕的是，有很多我們日常會話中會用到的可以互換的詞，在這個領域的專家眼裡卻有著特殊的含義。不過要找到竅門摸清楚到底什麼是什麼，倒也不是真的那麼難。
我要舉的第一個例子是，研究秘密信息的人經常用術語代碼（code）和密碼（cipher）來指代兩個不同的東西。大衛·卡恩（David Kahn）寫過一本密碼學的歷史，也許算得上是終極論述，他對此說得不能再好了：“代碼由成千上萬的單詞、短語、字母、音節組成，帶有可代替明文組分的代碼編碼或代碼編號，……至於說密碼，其基本單位是字母，有時候是字母對……大串字母的情況很少見。”發送秘密信息的第三種方法是隱寫術，包括隱藏已經存在的信息，比如說用看不見的墨水來書寫。在本書中我們將集中精力考察密碼，這是因為從數學上來看，密碼通常是其中最有意思的，不過其它方法的例子也會時不時地刷刷存在感。
在我們開始之前，再學幾個別的術語會大有幫助。研究如何用代碼和密碼發送秘密信息的學問叫做密碼學（cryptography），而研究如何擅自讀取這些秘密信息的學問叫做密碼分析（cryptanalysis），或是密碼破譯（codebreaking）。這兩個領域合在一起就組成了密碼編碼學（cryptology）。（有時候“密碼學”一詞也會用來表示這兩個領域的集合，但我們會努力把這些術語都區分開。）
當我們談論密碼學時，我們會說到愛麗絲想發送信息給鮑勃，這已經成為約定俗成的習慣了。但跟這兒我打算從尤利烏斯說起。這就是尤利烏斯·凱撒（Julius Caesar），他不只是羅馬“千秋萬代的獨裁者”，也是軍事天才、作家，以及……密碼工作者。
我們今天叫做“凱撒密碼”的這玩意，很可能最開始並不是凱撒發明的，但肯定是因為他才變得這麼有名。羅馬歷史學家蘇埃托尼烏斯（Suetonius）這樣描述凱撒密碼：
他（凱撒）除了寫給西塞羅（Cicero）的信，還有就私人事務寫給至交好友的。在私人信件中，他要是想說一些機密的事情，就會寫成密碼，也就是改變字母表中字母的順序，寫出來就字不成字了。要是有人想破譯這些文字知道它們都是什麼意思，他就得把字母表中的第四個字母，也就是D替換成A，並對其它字母也以此類推。
換句話說，當愛麗絲想要發送信息時，她先得寫出明文（plaintext），也就是把信息用正常的語言寫出來的文本。接著她得把這條信息譯成密碼（encipher），也就是用密碼將其寫成秘密形式，得到的結果就是這條信息的密文（ciphertext）。要把信息變成代碼的話，就得對其進行編碼（encode），或者用加密（encrypt）這個術語也可以。對明文中的每一個a，愛麗絲在密文中將其替換成D，再將每一個b都替換成E，以此類推。每一個字母都在字母表中往後移動了三位。這可真是太簡單了。但是當愛麗絲一直進行到字母表的最後，把字母都用完了的時候，好玩的地方就出現了。字母w變成了Z，那字母x該去哪兒？它繞了一圈回到開頭，變成了A！於是字母y變成B，而z變成了C。舉個例子：“你也有份嗎布魯圖（and you too, Brutus）[ 據說這是凱撒遇刺時的最後一句話，因莎士比亞劇作《尤利烏斯·凱撒》而家喻戶曉，也在英語世界中廣泛運用，表示來自好友的始料未及的背叛。——譯者注]”這條信息就變成了：
明文：a n d y o u t o o b r u t u s
密文：D Q G B R X W R R E U X W X V
這就是愛麗絲要發給鮑勃的信息了。
“繞回去”這種思路，實際上你從小時候起就已經在用了。一點之後再過三小時是幾點？四點鐘。兩點之後再過三小時是五點鐘。十點之後再過三小時又是幾點呢？一點鐘。你看，繞回去啦。
1.2 關鍵問題：凱撒密碼的一般化
在凱撒看來，他的密碼夠安全了，畢竟能截獲他的消息的人多半大字不識一個，就更不用說還能分析密碼了。但是從現代密碼學的角度來看，凱撒密碼有很大的缺點：你一旦搞清楚人家用的是凱撒密碼，就能對整個系統都一覽無余。沒有密鑰或別的只言片語的信息能讓你對密碼做出變化。這看起來糟糕得很。
停下來想一會兒吧。多大個事兒呢？你的密碼要麼是個秘密要麼不是，對吧？這就是凱撒那個時代的看法，在那之後好多好多年也還是如此。但到了1883年，奧古斯特·柯克霍夫（Auguste Kerckhoffs）發表了一篇劃時代的文章，文中宣稱：“系統必須不需要保密，而且就算被敵方竊取，也不會帶來麻煩。”太神了！怎樣才能讓你的系統就算被竊取也不帶來麻煩呢？
柯克霍夫接著指出，竊聽者伊芙要發現艾麗絲和鮑勃用的是什麼系統可太輕而易舉了。跟凱撒那個時候一樣，在柯克霍夫的年代密碼學還是主要用於軍事和政府，因此柯克霍夫想的是，敵人可能通過賄賂或是抓獲愛麗絲或鮑勃的一名工作人員來獲取信息。就算到了今天，在很多情況下這些問題也仍然值得關注，我們還可以添進去諸如伊芙竊聽電話、在計算機上安裝間諜軟件和純靠運氣瞎猜的可能性。
不過在另一種情況下，如果愛麗絲和鮑勃有一個需要密鑰來進行加密和解密的系統，事情就沒有那麼糟糕了。就算伊芙發現了正在使用的通用系統是什麼，她也還是不能輕易讀取任何信息。試著在沒有密鑰的情況下讀取信息，以及／或確定用於一段信息的密鑰是什麼，就叫做密碼分析，或是密碼運算，或者再通俗一點，叫做破解。而就算伊芙設法找到了愛麗絲和鮑勃的密碼，那也不算大勢已去。要是愛麗絲和鮑勃夠聰明，他們就會時常倒換密鑰。因為基本系統還是一樣的，倒換密鑰也不會很難，而就算伊芙拿到了其中一些信息的密鑰，她也還是沒辦法讀取所有信息。
所以我們得找個辦法來對凱撒密碼做一點點改動，這取決於一些密鑰的值。合情合理的出發點是，問一下為什麼愛麗絲是將她的明文移動了3個位置，而不是別的數字？並沒有特別的理由，也許凱撒只是對數字3情有獨鐘罷了。他的繼任者奧古斯都（Augustus）用的是跟他相似的系統，但每個字母只向右移動了一位。“回轉13位”密碼將每個字母移動了13位，走到頭的時候又繞回到起點。這種密碼經常在網絡上用到，用來隱藏笑話的包袱，或是有可能會冒犯到某些人的內容。移動k個字母（或者說加k模26）的一般思路就叫做以k為密鑰的移位式密碼，或是加法密碼。比如說，假設有個以21為密鑰的移位式密碼，那凱撒的消息就會變成：
明文: a n d y o u t o o b r u t u s
數字: 1 14 4 25 15 21 20 15 15 2 18 21 20 21 19
加21: 22 9 25 20 10 16 15 10 10 23 13 16 15 16 14
密文: V I Y T J P O J J W M P O P N
那一共會有多少個不同的密鑰呢？移動0個字母恐怕不是個好主意，但你也可以這麼幹。移動26個字母又跟移動0個字母是一樣的——要不換個說法，以26為模數，26就和0是一樣的。移動27個字母也跟移動1個字母殊途同歸，等等。所以，一共有26種移動方法能實際帶來不一樣的結果，也就是說有26個密鑰。記住這裡面也有0，那個“沒頭腦密鑰”，實際上對信息沒有做任何處理。加密時什麼都沒幹，術語就叫做無用密碼。假設愛麗絲用移位式密碼給鮑勃發了一條信息，而且被伊芙截獲了。就算伊芙設法知道了愛麗絲和鮑勃用的是移位式密碼，她也還是要試26次不同的密鑰來解密信息。這不是個大數目，但總比凱撒密碼強一點。