說起密碼，我們馬上會想到詹姆斯·邦德或者《柏林諜影》。但是，幾乎所有人都會在日常生活中用密碼進行一些完全正常、合法的活動，比如使用網上銀行的密碼。我們和銀行之間的通信是加密的，信息被編寫成密碼，因此犯罪分子無法讀取，也不能接觸到我們的錢——至少不那麼容易。在英語字母表里有26 個字母，實際的密碼也經會常用到26。例如，德國人在第二次世界大戰時使用的恩尼格瑪密碼機，這種機器採用的轉子有 26 個檔位，檔位和字母相對應。所以，這個數為密碼學提供了一個合理的切入點。不過，26 在密碼領域中並沒有特殊的數學性質，類似的原理也可以用於其他數。
凱撒密碼
1
密碼的歷史至少可以上溯到公元前1900 年左右的古埃及。尤利烏斯·凱撒在秘密信函里也使用過一種簡單的密碼，被用於傳遞軍事機密。凱撒的傳記作者蘇埃托尼烏斯寫道：「如果他有什麼秘密要說，就會把它寫成密碼。他會更改字母表上的字母順序，令人無法看出它是哪個單詞。如果有人想破譯它們並得到本意，就必須把字母表上的第4 個字母給換掉，那麼 A 對應的就是 D，其他字母也類似。」
在凱撒生活的那個時代，字母表里沒有字母J、U 和 W。但我們仍使用現代字母表來解釋，因為我們更熟悉它。凱撒的思路是，先按常規順序把字母表寫下來，然後在它下面寫一個移位的字母表，有可能如下所示：
現在，你可以把每個常規字母表上的字母對應到移位字母表上相同位置的字母，從而加密消息。也就是說，A 變成E，B 變成G，以此類推。就像這樣：
想要破譯消息，你只需看一下字母表之間的反向對應關係：
為了製作一種將字母繞在環上的實用機械裝置，我們把字母放置在一個圓環或圓筒上（圖1）。
圖1：繞在環上的實用裝置
凱撒密碼過於簡單，因此並不安全，後面會解釋其中的原因。但它包含了一些對所有密碼（編碼系統）都通用的基本概念（圖2）。
明文：原始信息。
密文：原始信息加密後的版本。
加密算法：用來把明文轉換成密文的方法。
解密算法：用來把密文轉換成明文的方法。
密鑰：加密和解密文本所需的秘密信息。
在凱撒密碼里，密鑰就是字母表移位的步數。加密算法是「用密鑰將字母表移位」。解密算法是「用密鑰將字母表反向移位」，也就是減去相同方向的移位步數。
圖2：密碼系統的一般特徵
在這個密碼系統里，加密密鑰和解密密鑰之間關係密切——一個是另一個的負數，也就是說，它們的移位步數相同，只不過方向相反。在這種情況下，知道了加密密鑰實際上就知道了解密密鑰。這類系統被稱為對稱密鑰密碼。
凱撒顯然使用了更複雜的密碼——幸好他是這麼做的。
1.1
數學公式化
利用模運算，我們可以通過數學表示凱撒密碼。在這裡， 模數等於26，即字母表上字母的個數。計算和平時一樣，但需要加上一條：任何26 的倍數都可以替換成0。這正是我們需要的，讓移位的字母表「繞一圈」後從頭開始。現在，用數字0~25 代表字母A~Z，即A=0、B=1、C=2，以此類推， 直至 Z=25。把 A（位置 0）移動到 F（位置 5）的加密過程就是數學規則
n n+5 mod 26
請注意，U（位置20）成了20+5=25 mod 26，它代表Z，而V（位置21）成了
21+5=26=0 mod 26
它代表A。這說明了數學公式是如何確保字母表正確地繞圈的。
解密過程也有類似的規則：
n n-5 mod 26
因為 n+5-5=n mod 26，所以解密把加密還原了。更一般地，當密鑰為k時，意味著「向右移動k步」，於是加密過程的規則成了
n n+k mod 26
而解密的規則是
n n-k mod 26
把密碼轉換成數學語言的優點在於，我們可以用一種精確的方式來描述 密碼，並分析它們的性質，同時還不必考慮字母本身。一切都是用數字表 示的。我們也可以考慮其他符號，如小寫字母a、b、c……，以及標點符 號，還有數字。只要把26 換成某個更大的數，然後一次性確定如何分配這些數就行了。
1.2
破解凱撒密碼
凱撒密碼非常不安全。如前所述，它只有26 種可能性，因此你可以窮盡所有可能，直到某個解密消息看起來有含義。還有一種名叫替換碼的變體也很脆弱，雖然這種編碼會打亂字母表，而不只是移動。這樣一來，就產生了26! 種編碼，這個數非常大。然而，利用簡單方法就可以破解所有這類編碼。對某種給定的語言來說，某些字母會比另一些更常見（圖 3）。
圖3：在典型的英語文本里，字母出現的頻率
在英語裡，最常見的字母是E，它大約占全部出現頻率的13% ；接下 來是T，大約是9% ；再往下是A，大約是8%，等等。如果你截取了一段很長的密文，並猜測它是通過打亂字母表的方法生成的，那麼就能計算所有字母的頻率。由於文本各式各樣，因此它們或許並不能和理論值精確地吻合。但是，比方說，如果在密文里的字母Q出現得比其他字母更頻繁， 那麼你可以試著用E代替Q。如果接下來最常見的字母是M，那麼試試看用T代替M結果會怎樣，以此類推。當然，你還可以微調它們的順序。即便如此，你需要嘗試的可能性也會少很多。
例如，假設部分密文如下：
X J M N Q X J M A B W
你發現在整個密文里，頻率最高的3個字母依次分別是Q、M 和 J。用E代替 Q、T 代替 M、A 代替 J，並把其他地方留白後得到：
- A T - E - A T - -
不難猜測這條消息實際上是
M A T H E M A T I C S
如果有更多密文，你很快就會發現它的含義，因為你已經可以猜測X 解碼為M、N 解碼為H、A 解碼為I、B 解碼為C，而W 解碼為S。如果另一段密文是
W B A Q R B Q H A B M A L R
那麼你可以試著把它解密成
S C I E - C E - I C T I -
進而猜它應該是
S C I E N C E F I C T I O N
出現兩次的N 更加有助於確認你的猜測。現在，你知道N、F 和 O 分別是由什麼字母加密的了。整個過程很快，甚至通過人工處理也能快速破解編碼。編碼方式有成千上萬種。破解編碼的過程就是在不知道算法或密鑰的情況下，找到如何解密消息的方法。這一過程依賴於編碼本身。在現實中，一些編碼方法破解起來非常困難，因為密碼學家們在擁有足夠的信息進而嘗試破解編碼之前，密鑰會保持不斷變化。第二次世界大戰期間，人們使用「單次密本」來實現這一點：從根本上說，它需要一本有許多複雜密鑰的記事本，每個密鑰只用於一條短消息，隨後便馬上被銷毀。這類方法的最大問題是，間諜們必須帶著密碼本到處跑——如今某些電子小配件也有相同的功能，而密碼本可能會在他們的私人物品中被發現。
恩妮格瑪密碼機
2
在第二次世界大戰期間，德軍使用的恩尼格瑪密碼機是最著名的密碼系統之一。在英國布萊切利莊園工作的數學家和電子工程師們破解了恩尼格瑪的編碼，而這些人中最出名的就是計算機科學先驅——艾倫·圖靈。他們得到了一台可以使用的恩尼格瑪密碼機，為完成破解任務帶來了極大 的幫助。它是由一組波蘭密碼學家在1939 年提供的，當時，這些波蘭專家已在破譯恩尼格瑪編碼方面取得了重大進展。德國人還有一些別的編碼也被破解過，其中包括更複雜的洛倫茲密碼，但破解這個編碼時並沒有用到實體設備。當時，在拉爾夫·特斯特的領導下，一個密碼分析小組從設備發送的消息里推測出了洛倫茲密碼的可能結構。接著，威廉·圖特靈光一閃，向破解編碼走出了第一步：他推測出與設備運行方式有關的重要信息。此後，這項工作的進展大大加速。實際上，破解這種編碼用到了一台電子設備，它就是由托馬斯·弗勞爾斯領導的團 隊設計和建造的「巨人」計算機（Colossus）。事實上，「巨人」計算機是為某項特定任務而設計的早期電子計算機之一。
恩尼格瑪密碼機包括一個用於輸入明文的鍵盤和一系列轉子，每個轉子都有26個檔位，檔位和字母表上的字母相對應（圖4）。早期的密碼機有3個轉子，後來被擴展成一組5個德國海軍甚至用到了8個，但使用者每天只選用其中的3個。轉子的作用是，在每輸入一個新字母時，打亂明文字母的方式就會改變。確切的方法很複雜，詳見：
http://www.codesandciphers.org.uk/enigma/example1.htm
圖4：恩格斯密碼機
粗略地講，整個過程大致是這樣的。密碼機根據轉子所處的檔位決定移位情況，轉子就像凱撒密碼一樣把字母表打亂。當一個字母被傳遞到第一個轉子時，產生的移位結果就會傳給第二個轉子，同時產生新的移位。而這一結果又會傳給第三個轉子，並產生第三個移位（圖5）。此時產生的信號會到達一面反射鏡。這面反射鏡實際是一組把字母連成對的13根線，它把結果字母與相連的另一個字母做交換。最後，結果再次返回到3個轉子，從而生成與給定輸入相對應的最終編碼結果。
密文可以從識別燈盤上得到，燈盤上有26 盞燈，每個字母背後都有一盞，每當燈亮起時，就說明這個密文字母與剛剛輸入的明文相對應。
這種密碼機最具獨創性的地方在於，在每次連續擊鍵時，明文字母和產生的密文字母之間的對應關係會以獨特方式發生變化。在鍵盤上每敲擊一個新字母，轉子都會轉到下一個位置，因此轉子會以不同方式打亂字母表。右側的轉子每次都向前移動一格。當右側的轉子從Z 回到A 時，中間的轉子才會移動一格。左側的轉子相對於中間的轉子，也是這樣的。
圖 5：一組 3 個轉子
因此，轉子的運作很像汽車裡（被電子化之前）的里程計。里程計的「個」位數碼從0到9，再回歸0，每次動一格。「十」位數碼也一樣，但只有從個位得到「進位」信號時才會動，這時，個位從9 回歸到0。類似地， 只有從十位得到「進位」信號時，「百」位數碼才會加1。因此，這3 個數 位從 000 到 999，每次加 1，最終再恢復到 000。然而，恩尼格瑪密碼機的轉子從A到Z共有 26 個「數位」，它比10 更 多。並且，轉子的開始狀態是可以任意設置的，一共有26×26×26=17 576種位置。在實際使用中，起始位置是在一天開始的時候設置的，並在使用 24 小時後被重新設置。
我是按照左、中、右的順序來介紹轉子的步進過程的，但實際上，密碼機可以使用轉子的所有6 種排列順序。將初始化的可能性乘以6，於是一共有 105 456 種可能性。
在軍事用途中，插接板為設備額外提高了一個安全等級：按不同方式在 字母間插連接線，可以成對地交換字母（圖6）。這種連接線超過10 根， 因此提供了 150 738 274 937 250 種 A 可能性。同樣，插接板的設置也是每天變化的。
對使用者而言，這個系統在實用性方面有一個很大的優點：它是對稱的。相同的機器可以用作解密消息。給定日期的初始化設置必須傳達給所有使用者，因此德國人使用一種單次密本。
圖 6：插了兩根連接線的插接板
2.1
破解恩尼格瑪編碼
但是，整個過程也導致了一些缺陷。其中最明顯的就是，如果敵軍（在這裡指盟軍）能推算出設置，那麼當天發送的所有消息都能被解密。還有一些別的弱點，尤其是，如果連續兩天使用了相同的設置——這是偶爾發生的錯誤，那麼編碼就會被破解。
通過利用這些漏洞，布萊切利莊園的研究團隊於1940 年 1 月首次成功破解了恩尼格瑪編碼。他們的工作依賴於一個波蘭密碼團隊取得的知識和 思路。波蘭團隊的領導人是馬里安·雷耶夫斯基，自從1932 年以來，他就一直在嘗試破解恩尼格瑪。通過研究把當天的設置傳遞給使用者的方式，波蘭團隊發現了一個缺陷，有效地把需要考慮的設置數量從一億億種降低到大約十萬種。將這些設置進行編目，波蘭人可以很快地算出哪天用的是什麼設置。他們發明了一種名叫記轉器的設備來幫助破解。他們還花了大約一年時間準備編目，不過當編目大功告成後，推斷當天的設置和破解編碼就只需要 15 分鐘。
德國人在1937 年升級了系統，於是波蘭團隊必須從頭開始。他們發展了幾種方法，並用其中最強大的方法製造了一種名叫密碼邏輯炸彈（bomba kryptologiczna）的設備。每台設備都具備強大的分析能力，旨在推斷由3 個轉子形成的17 576 種初始化設置，以及每種設置因轉子的不同排列而得到 6 種可能。
1939 年，圖靈剛到布萊切利莊園不久就發明了英國人自己的「炸彈」，它被稱為「炸彈機」。同樣，該設備的功能也是推斷初始轉子的設置，以及所有轉子的順序。截至1941 年 6 月，已有5台炸彈機投入使用。而在1945年戰爭結束時，設備數量達到了210 台。當德國海軍改用4 個轉子的設備時，改進的炸彈機也隨之誕生。當德國人將系統升級以提高安全時，破解密碼的英國專家們也找到了 使升級失效的方法。到1945 年，盟軍已經可以破解幾乎全部的德軍消息了，但德軍最高統帥部仍然相信，所有通信是絕對安全的。他們的密碼學家們還沉浸在安全的假象中，絲毫沒有懷疑別人可能會花費極大的力氣來破解編碼。盟軍雖然取得了極大的優勢，但他們必須小心使用，以免暴露自己具有破解消息的能力。
非對稱密鑰密碼
3
在密碼學領域，最了不起的概念大概要算非對稱密鑰了。在非對稱密鑰里，加密密鑰和解密密鑰是不同的，因此，即使你知道加密密鑰，也不可能真的計算出解密密鑰。這似乎是不可能的，因為一個過程的逆過程就是另一個過程，但一些方法可以實現這一點，從而終結「反推加密方法」。RAS編碼就是其中一例，它基於模運算里的質數性質。在這樣的系統里，可以公開加密算法、解密算法和加密密鑰——即便如此，人們也不可能推斷出解密密鑰。不過，合法的接收者是可以知道解密方法的， 因為他們還有一個私鑰，可以告訴接收者如何解密消息。
文章來源：《不可思議的數》
不可思議的數
《不可思議的數》涵蓋了數學經典知識和最新研究領域的眾多成果，從數本身開始，打開通向代數、幾何、集合論、數論乃至物理和宇宙的入口。這裡有各種各樣的數：從常見的自然數0至10到負數，從「簡單」的有理數到複雜多變的有理數和無理數；從已知最大的質數到最小的無窮大。每個數都它自己的故事，而圍繞著這些數，作者不但講述了每個數背後的歷史，更拓展出眾多有趣的數學問題，讓這些數成為帶讀者進入神奇數學世界的「引路人」。
編輯：zyi