04 密碼學：素數的秘密生活 Cryptography: the Secret Life of Primes

讀者朋友現在應該能夠體會，從很早開始，自然數的集合就已經被看作謎語和秘密的源泉，產出了很多直到今天都沒能解決的問題。對我們中的不少人來說，這已經是繼續進行關於數本身嚴肅研究足夠的理由。不過其他人可能會有不同的態度：雖然這些難題可能耐人尋味、充滿挑戰，但是也可以想象，它們對人類文明的其他方麵影響甚微。然而，這樣的想法是個錯誤。

過去的幾十年裏，人們逐漸意識到，我們時不時會有保密的需求，某些普通信息構成的秘密可以被編碼成關於數的秘密。現在，密碼學已經得到了全麵的應用。我們最為珍貴的秘密，無論是商業的、軍事的、個人的、財務的、一般政治性的還是徹頭徹尾醜聞性質的，都可以在互聯網上被保護起來——用有關普通自然數的秘密。

化身為數的秘密

這一切都是怎麽做到的呢？任何信息，無論是一首詩還是一份銀行賬單，一張武器設計圖還是一套計算機程序，都可以用詞語來描述。當然，我們可能需要拓展用來表示詞語的字母表，使它不僅限於含有普通的字母。我們或許會加上數字符號和標點符號，包括代表詞語之間空格的特殊符號。即便如此，我們希望傳輸的所有信息(包括生成相片和圖表的指令)總可以由一張字母表來表達。讓我們假設這張表包含的符號不超過一千個。我們可以數一數這些符號，然後用一個獨一無二的數來表示每個符號。因為數的成本低廉，取之不盡。為了我們的目的，或許使用位數相同的數會比較方便。比如，每個符號都被一個獨一無二的4位個體識別碼(personal identification number， PIN)表示。我們可以將這些符號按順序串連起來，從而得到一個很大很長的數，裏麵包含故事的全部。我們要是願意，甚至可以在二進製下做這件事。這樣我們可以設計一個方法將信息轉譯成一長串0和1。於是，我們想要發送的每條信息都可以編碼為一個二進製字符串，然後在接收端由具有相應程序的計算機解碼，再被編譯為我們都可以理解的普通語言。這就是我們的第一層領悟：要傳遞信息，從理論和實用兩方麵來說，能從一個人向另一個發送數字就足夠了。

但是將信息變成數並不是關鍵的思想。明確一點說，將所有信息數字化的具體過程可以被藏起來，不被大眾知曉，但這並不能形成有效的保護、免遭竊聽。的確，從密碼學的觀點來看，我們可以將任何信息——所謂的明文(plaintext)——與代表它的數等同看待，於是便可以把數看作明文本身。這是因為我們假定，任何人都有辦法掌握這兩者互相轉換的途徑。隻有當我們用別的數掩蓋明文數碼的時候，信息才真正具有了保密性。

密碼學便是關於密碼(ciphers)(機密的代碼)的學問。讓我向你介紹一些虛擬角色吧，他們經常出現在密碼學所考慮的各類情境中。我們設想愛麗絲(Alice)和鮑勃(Bob)想互相通信，但不想讓竊聽者伊芙(Eve)聽見[1]。我們也許會本能地同情愛麗絲和鮑勃，而將伊芙想象成壞人。但是這可能與真相相反，伊芙或許代表了正義的警方，努力保護著我們免受鮑勃和愛麗絲的邪惡計劃的傷害。

無論參與者的道德立場如何，愛麗絲和鮑勃都可以運用一個古老的方法，來將伊芙排除在對話內容之外，哪怕伊芙截取了他們之間傳遞的信息。方法就是用密鑰(cipher key)來加密數據，而這個密鑰隻有愛麗絲和鮑勃自己知道。他們可以預定在一個安全的環境會麵，交換一個秘密數字(比方說57)，然後各自回家。當時機到來時，愛麗絲想要發送一條信息給鮑勃。這裏為了敘述方便，我們假設信息可以用一個1～9之間的數字來表示。在那個重大的日子，愛麗絲想將信息“8”發給鮑勃。她取出信息，加入秘密數字。也就是說，她通過加上57把真實的數值掩藏了起來，然後將信息8+57 = 65通過一個未經保護的渠道發給鮑勃。鮑勃收到這條信息，減去秘密數字，從而獲取愛麗絲的明文65-57 = 8。

不過，不懷好意的伊芙很清楚這兩個人在幹些什麽，並且她也確實截獲了加密過的信息65。但是她能對它做什麽呢？她可能像我們一樣，知道愛麗絲發送給鮑勃九種可能的信息1，2，3，…，9中的一個，也知道她通過將信息加上一個數進行了加密，這個加密數一定在65-9 = 56到65-1 = 64之間。然而，因為她不知道這九個數字中的哪一個被使用了(她被排除在這個秘密之外)，她沒法進一步搞清楚愛麗絲給鮑勃發送的明文信息。九種信息中的每一種都有相同的可能性。她知道的全部就是愛麗絲給鮑勃發送了一條信息，但是不知道信息的內容。

看起來愛麗絲和鮑勃對伊芙的邪惡滲透已經防得滴水不漏，他們似乎可以使用這個奇妙的數57來掩藏所有想說的內容，從而不受限製地通信。但是，實際卻非如此。他們最好換一換這個數，實際上每次都使用一個新的密碼會更好。不然這套係統就會開始泄露線索給伊芙。比如說，在未來某一周愛麗絲想向鮑勃傳送一條相同的信息8。每件事都會與之前一樣，再一次伊芙從電波中截獲了神秘的數65，但這次會讓她讀出一些東西。伊芙會知道，無論這條信息是什麽，這和愛麗絲第一周發給鮑勃的是一樣的——而這類事情正是愛麗絲和鮑勃所不希望伊芙知道的。

當然，對於愛麗絲和鮑勃來說，這看起來也不是什麽大問題。當他們第一次見麵“互換密鑰”時，愛麗絲可以不隻是約定一個密碼，而是提供給鮑勃一張長長的有順序的列表，裏麵有上千個密碼。他們可以依次使用這些密碼，從而避免了在公開通信中出現有意義重複的可能性。

我們確實也是這樣操作的。這種密碼係統在業內被稱為一次性密碼本(one-time pad)。發送者和接收者從密碼本中找到一個一次性的數，用以掩藏他們的明文。當信息被發送和解密後，密碼本中的那一頁會被發送者和接收者一起撕掉。一次性密碼本代表了一種徹底安全的係統，因為在公共領域傳輸的不安全文本不含有任何關於明文內容的信息。為了解碼，攔截者需要拿到密碼本才能獲得加密/解密的鑰匙。

密鑰和密鑰交換

一次性密碼本似乎完全解決了安全通信的問題。某種角度上說確實如此。但是，參與者必須交換一份密鑰，才能使用一次性密碼本，類似的密碼都有這樣的問題。在實踐中，交換密鑰很麻煩。對於高層通信，比如在白宮和克裏姆林宮之間，錢不是問題，所以必要的信息交流會在最高安全級別下開展。另一方麵，在日常生活中，各類人和機構都需要以保密的方式互相溝通。參與者負擔不起安全交換密鑰所需的時間和精力，即使通過受信任的第三方來安排，加密可能依然價格不菲。

所有使用了幾千年的密碼——直到20世紀70年代——都有一個共同的缺點：它們都是對稱密碼(symmetric ciphers)，就是說加密和解密的鑰匙在本質上是一樣的。無論是尤利烏斯·愷撒(Julius Caesar)的簡單的字母位移式密碼，還是第二次世界大戰中的複雜的英格瑪密碼(Enigma Cipher)，它們都擺脫不掉共同的弱點，即一旦對手知悉你是如何編碼信息的，他們就能與你一樣順利地解碼。為了使用對稱密碼，通信雙方需要一種安全的密鑰交換方式。

一直以來，我們似乎默認加密代碼有不可避免的原則——要運用一套密碼，雙方需要用某種方式交換相應的密鑰，並對敵人保密。的確，有人可能把它當作了數學常識。

這種假設恰恰會令一個數學家心生疑惑。本質上，我們麵對的是一個數學問題，因而人們會預期這樣一條“原理”有著堅實的基礎，甚至表達成某種形式的數學定理。然而，並沒有這種定理。之所以沒有，是因為這條原則根本就是不對的。下麵這個思想實驗可以證明。

從愛麗絲那裏傳送一條機密信息給鮑勃，這本身並不一定需要交換一份密鑰，因為他們可以按下麵的程序來操作。愛麗絲寫好她要給鮑勃的明文信息，然後將它放進一個盒子裏，再掛上她自己的鎖，隻有愛麗絲有鎖的鑰匙。她接著將盒子寄給了鮑勃。當然，鮑勃沒法打開它，不過他可以給盒子加上第二把鎖，而隻有他一個人有這把鎖的鑰匙。接下來，盒子被寄還給愛麗絲，她會打開自己的鎖，第二次把盒子寄給鮑勃。這次，鮑勃便可以打開盒子，讀到愛麗絲的信息。寄送過程中，我們知道伊芙即使想從中作梗，也沒辦法看到內容，因此信息是安全的。這樣，一條機密信息便可以通過不安全的渠道安全地傳送，卻從不需要愛麗絲和鮑勃交換密鑰。這個假想的情境說明，在密信的傳遞過程中，沒有定律規定密鑰必須轉手。在真實係統中，愛麗絲和鮑勃的“鎖”可能是他們各自對信息的編碼，而不是一個分隔潛在竊聽者和明文的實體設備。愛麗絲和鮑勃可以利用這個初始的交換來建立一套普通的對稱密碼，接下來這套密碼便可以掩藏未來的所有通信。

其實在真實世界中，安全的通信渠道經常是這樣建立起來的。不過，用個人代碼代替實體的鎖並不是那麽容易。解讀(即解鎖)的過程需要愛麗絲在先，鮑勃在後。不像普通的鎖，愛麗絲和鮑勃的編碼可能會相互幹擾，從而導致這一過程無法進行。但是，1976年，惠特菲爾德·迪菲(Whitfield Diffie)和馬丁·赫爾曼(Martin Hellman)首次公開證明了這個方法是有效的。

另一種相關的方法是不對稱(asymmetric)或者說公開密鑰加密(public key cryptography)的思想。在這個方法中，每個人發布他們自己的公開密鑰，要發送給一個人的信息都用他的公開密鑰來加密。但是，每個人還有一份私人密鑰。如果沒有私人密鑰，使用對應的公開密鑰加密的信息就沒法解讀。如果接著用掛鎖比喻的話，愛麗絲提供給鮑勃一個盒子用來裝他的明文信息，外加一隻開著的鎖(她的公開密鑰)，而隻有她自己手裏握著鑰匙(她的私人密鑰)。

看起來，建立一個實用的公開密鑰係統需要滿足太多條件，因為安全性和易用性這兩個要求密不可分，但似乎又互相矛盾。不過，快速、安全的加密方法已經在互聯網上廣為應用了，即便大家很少意識到它的存在和它為人們提供的保護。讓這一切得以實現的，說到底都是數，尤其是素數。

用素數的秘密守護我們的秘密

回憶一下，我們把每條明文信息都看作一個單獨的數，我們自然努力想用其他數來掩蓋它。最常用的方法是用所謂的RSA(Rivest-Shamir-Adleman)加密過程，這是由它的創始人羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和萊昂納德·艾德曼(Leonard Adleman)在1978年發表的。在RSA中，每個人的私有密鑰由三個數p，q，d組成，p和q是(非常大的)素數，而第三個數d是愛麗絲保密的解密數，我們到下麵合適的時候再解釋它。愛麗絲公開給大家的是兩個秘密素數之積n =pq，以及一個加密數e(這是一個普通的整數，與第2章中提到的特殊常數e沒有任何關係)。

為了說明RSA如何發揮作用，我們舉一個簡單的例子。假設愛麗絲的素數是p= 5和q= 13，於是n = 5×13 = 65。如果愛麗絲把她的加密數設為e = 11，那麽她的公開密鑰就是(n， e) = (65， 11)。為了加密信息m，鮑勃隻需要n和e。然而，要想解碼鮑勃發送給愛麗絲的經過加密的信息E(m)，就需要有解碼數d。在這個例子中，可以推知d= 35，這個我們待會兒就來證明。計算出d的數學方法需要知道素數p和q。在這個簡單的例子裏麵，給定n = 65，任何人都會很快發現p = 5而q = 13。然而，如果素數p和q極其地大(通常它們有幾百位數字那麽長)，在實際操作上，至少是在較短的時間(比如說兩到三周內)，幾乎沒有任何計算機係統能完成這項任務。總的來說，RSA加密係統是基於一個經驗事實，即找到一個很大很大的數n的素因數極為困難，困難到在實際操作中無法實現。這個方法設計得真正聰明的地方，在於代表信息的數m可以隻用公開的數n和e來加密，但在實際操作中，解密需要知曉n的素因數。在這章剩下的部分裏，我們就來詳細解釋這一點。

RSA是這樣起作用的：鮑勃通過網絡發送的不是m本身，而是me除以n所得的餘數(remainder)。然後愛麗絲拿到這個餘數r，計算rd除以n得到的餘數，就能重新得到m。這背後的數學保證了愛麗絲得到的結果正是原始的信息m，愛麗絲的計算機可以進一步將它解碼為普通明文。當然，對於任何真實生活中的“愛麗絲”和“鮑勃”，這一過程都是在幕後無縫銜接地完成的。

這麽看來伊芙所缺的唯一重要的東西是解密數d。倘若伊芙知道d，那她也能像愛麗絲一樣完美地解碼信息。事實上，存在著一個特殊的方程，d恰好是它的一個解。從計算的角度來講，借助於公元前300年的《幾何原本》[2](Books of Euclid)中發表的歐幾裏得算法，求解這個方程是很容易的。這不是困難之處。麻煩的地方在於，除非你知道p和q中至少一個，否則不可能準確地找到那個要解的方程。這便是擋在伊芙道路上的障礙。

我們可以再進一步解釋，以上涉及的數如何在這個係統中各司其職。首先，很明顯鮑勃一開始就麵臨著一個大問題，m很大，n更是可怕(在200位數字這個量級上)。即便e的值不像那樣誇張，me也是極其大的。計算出它之後，我們還得將me除以n來得到餘數r，這代表了被加密的文本。這些計算太過繁雜，以至於看起來也許並不可行。我們需要意識到，即使現代計算機異常強大，它們還是有能力極限。當計算涉及很高次的冪，就可能會超過任何計算機處理能力的極限。我們不能假設電腦可以在短時間內完成任何我們交給它們的計算任務。

鮑勃有根救命稻草是，他完全可以不做很長的除法就找到要求的餘數r。實際上，餘數僅僅取決於餘數。這裏我們舉一個例子來說明，739的最後兩位是多少？(換句話說，當這個數被100除後餘多少？)為了回答這個問題，我們可以從計算7的前幾次冪開始：71 = 7， 72 = 49， 73 = 343， 74 = 2401，75 = 16 807，…。不過很快我們就清楚地發現，離739還遠著的時候，這些數已經變得相當大，我們都處理不過來了。另一方麵，隨著我們算出一個又一個冪次，一個關鍵的規律出現了。當計算連續的冪次時，結果的最後兩位數字僅依賴於前一個數的最後兩位。這是因為我們做乘法時，百位及以上的數字並不會影響到結果在個位和十位上的數字。

同時，因為74末尾兩位是01，所以接下來四個冪的末尾依次是07， 49， 43，接著又是01。因此，隨著我們挨個計算冪次，末尾兩位的數字隻會一遍又一遍地重複這個長度為4的循環。回到我們手上的問題，由於39 = 4×9+3，我們會經曆這個循環九次，然後還需要三步來計算739的最後兩位數，因此結果一定是43。

這樣的技巧是相當普適的。比方說，為了找到某個冪次ab除以n所得的餘數，我們隻需要取a除以n所得的餘數r，並追蹤r的各次冪除以n之後的餘數。餘數r一定是大於或等於0、小於或等於n-1之間的一個數。在我們隻關心r的時候，數學家們說我們是在求模(modulo)n。我們舍棄了所有n的整數倍，因為它們除以n餘0，所以不會對最終的餘數r有任何貢獻。

你可能還是在懷疑，我是不是通過選擇特殊的例子操縱了證據，這個例子裏一個很小的冪次就給出了餘數1——這裏74比100的某個整數倍大1。然而，你懷疑的情況隻在部分程度上成立。事實上，如果我們取任意兩個數，a和n，它們的最大公因數為1，我們說這些數是互素的(coprime)，那麽總存在一個指數t，使得冪at等於1模n——也就是說被n除時餘1。從這個角度說，連續次冪的餘數會構成周期為t的循環。但是，預測t的值卻很難。不過人們知道t總等於一個特殊的數或是它的某個因數。這個數傳統上被寫作φ(n)，代表歐拉φ函數(phi function)的值。

這跟我們直接從定義得到的結果是一樣的。使用這個方法，你可以自己驗證φ(100)=40。因此，可以推出740同餘於1模100。當然，就像我們已經看到的，餘1的7的最小冪次不是40，而是它的因數4。

以上這些都是為了表明，鮑勃確實可以求出發送給愛麗絲的數，me模n，同時不需要鮑勃的計算機做出太多努力。不過，在實際操作中涉及的數依然大到可怕，因此我們有必要進一步說明如何處理它們。計算me所涉及的高次冪可以分階段進行，這個過程叫作快速求冪(fast exponentiation)。簡而言之，這一方法運用連續求平方以及冪的相乘來得出me模n，我們可以用二進製形式的e引導算法，從而在相對少的步數裏快速找到想要的餘數。

歐幾裏得教愛麗絲找到她的解密數

為了找到d，愛麗絲的電腦可以利用一個代數工具——歐幾裏得算法，這一工具已經有2300多歲了。稍後我們就來介紹它。如果伊芙的計算機知道去解哪個方程，那它當然也能做到同樣的事情。然而，因為p和q是愛麗絲私有的，(p-1)(q-1)也是，因此伊芙並不知道從哪裏著手。

加密數(公開的)e需要滿足一個溫和的限製條件，才能保證d的存在。愛麗絲必須確保e與φ(n)沒有公因數。這很容易做到，愛麗絲可以檢驗用不同的素數除φ(n)的結果，從而保證既不泄露p和q的值也讓e滿足限製條件。實際應用中，e的值常常使用第四個所謂的費馬素數(Fermat prime)e=65 537=216+1。這個值，224+1，具有一個尤其稀有的性質，即可以用直尺和圓規(straightedge and compass)作出一個有e條邊的正多邊形。不過，它在密碼學中的用處在於它是一個很大的(恰好比某個2的冪大1的)素數，這非常適合運用之前提到的快速求冪過程。

回到歐幾裏得算法。這個算法是通過推廣以下的觀察結果得到的，即對於兩個數a＞b，可以通過連續的相減來找到最大公因數(highest common factor)，最大公因數也叫作最大公約數(greatest common divisor)。我們注意到r = a-b有一項性質：a，b，r中任意兩者的公因數也是第三個數的因數。例如，如果c是a和b的公因數，於是a = ca1並且b = cb1，我們看到r=a-b=ca1-cb1=c(a1-b1)，這就得出了r包含c的一個因數分解。於是，a和b的最大公因數等於b和r的最大公因數。因為這兩個數都小於a，我們現在麵對的是跟之前一樣的問題，不過是相對於兩個更小的數。重複應用這個方法，最終會得到一對數，它們的最大公因數可以一眼看出。(實際上，最後手中的兩個數會變成相等的，因為如果不是這樣，我們可以繼續多做一步。這對數共同的值就是我們找的那個數。)

比如，要找a = 558和b = 396的最大公因數，第一次減法後我們得到r = 558-396 = 162，因此新數對是396和162。由於396-162 = 234，所以我們的第三對數是234和162。隨著我們繼續下去，完整的數對依次是：

(558，396)→(396，162)→(234，162)→(162，72)→(90，72)→(72，18)→(54，18)→(36，18)→(18，18) .

因此558和396的最大公因數是18。

還可以根據待考察的數對各自的素因數分解來寫出它們的最大公因數。在這個例子裏，558=2×32×31，而396=22×32×11；取兩個分解中各個素數的共同次冪，我們得最大公因數為2×32=18。然而，對於大數而言，使用歐幾裏得算法需要的工作量少得多，因為一般執行減法運算比尋找素因數分解更簡單。

歐幾裏得算法的另一項優點是總可以倒著做，這樣便可以將最大公因數用原始的兩個數來表示。為了更好地看清楚這是怎麽做到的，我們在剛才這個例子裏將計算壓縮。在依次相減的過程中，同樣的數重複出現了好幾次，我們可以把它們表達在一個方程裏。這樣我們就得到以下幾個等式：

558 = 396+162；

396 = 2×162+72；

162 = 2×72+18；

72 = 4×18 .

從第二行開始到最後一行，我們可以用各個等式逐個消去中間餘數。在這個例子中，先利用倒數

第二個等式，然後是它上麵的那個，我們得到：

18=162-2×72=162-2×(396-2×162)

=5×162-2×396.

最後再用第一個等式，我們可以把第一個中間餘數162也消去：

5×162-2×396=5×(558-396)-2×396=

=5×558-7×396=18.

無論是對於實踐還是理論，可以倒過來執行這一程序都是很重要的。特別是在解密裏，為了找出愛麗絲的解密數d，我們想要d滿足de除以φ(n)餘1的條件。為了簡潔，我們用一個單獨的符號k來代表φ(n)。現在就可以看出我們堅持要e和k互素的原因了。因為如果它們的最大公因數是1，當我們對e和k執行歐幾裏得算法時，最終出現的餘數自然是1。倒過來執行這一算法，我們就能最終把1表示成e和k的組合。特別地，我們會找到整數c和d，它們滿足ck+de = 1，或者換句話說de=1-ck。因此de除以k會餘1。

這個相對簡單的過程將給出愛麗絲的解密數d：直接從方程裏得出的d的值可能不在1到k的範圍內；倘若不在，通過加上或減去合適的k的倍數，我們最終可以找到那個d，在給定範圍內，它是唯一具有de除以k餘1這個神奇性質的數。(我們可以輕鬆證明d的唯一性，不過這裏還是不要離題太遠了。)這便是如何計算解密數d的方法。我們可以回到前麵的例子來說明，這裏p=5，q=13，於是n=pg=5×13=65。我們有φ(n)=(p-1)(q-1)=4×12=48。愛麗絲設定e=11，由於11與48互素，這在遊戲規則所允許的範圍內。應用歐幾裏得算法於φ(n)=k=48和11，可得：

48 = 4×11+4；

11 = 2×4+3；

4 = 1×3+1 .

這顯示k和e的最大公因數確實是1。將算法反轉，我們得到：

1=4-3=4-(11-2×4)=3×4-11

=3(48-4×11)-11=3×48-13×11.

為了滿足11d除以48餘1的條件，我們解出d的初步值-13。為了得到一個在要求範圍內的正的d的值，我們在這個數的基礎上加上48，於是d=48-13=35。

d能幫助愛麗絲解密信息，其原因可以歸結為模算術(modular arithmetic)的特性，以及當de除以k=φ(n)時餘1這一事實。愛麗絲計算(me)d=mde模n。現在de具有1+kr的形式，這裏r是某個整數。正如之前解釋的那樣，mk除以n餘1，這通常被稱為歐拉定理(Euler’s Theorem)，而這對於(mk)r=mkr也是對的。因此，m1+kr=m×mkr，它除以n餘m。(詳細的驗證需要一點代數運算，不過結果的確是這樣的。)通過這個方法，愛麗絲得到了鮑勃的信息——m。

順便指出，我們在證明素因數分解唯一性的時候缺少了一環，歐幾裏得算法恰好提供了這缺失的環節。因為它使得我們能夠驗證歐幾裏得性質，即如果素數p是乘積ab的一個因數，比方說ab=pc，那麽p是a和b之中至少一個的因數。如果p不是a的一個因數，那麽由於p是素數，a和p的最大公因數是1。應用歐幾裏得算法於a和p這對數，並將其反轉，我們可以找到整數r和s，使得ra+sp=1。這已經足夠證明p是b的一個因數了，由於ab=pc，我們有：

b=b×1=b(ra+sp)=r(ab)+psb:

=r(pc)+psb=p(rc+sb).

這便是想要找的b的分解，它顯示p正是一個因數。

總而言之，RSA加密背後的關於數的理論保證了係統的可靠性。當然，要保證係統的完整，還需要遵守很多這裏沒有解釋的協議。可能出現的問題包括身份驗證(authentication)(假如伊芙偽裝成鮑勃聯係愛麗絲怎麽辦？)、不可抵賴性(nonrepudiation)(假如鮑勃裝作伊芙發送了信息給愛麗絲怎麽辦？)以及身份欺詐(identity fraud)(假如愛麗絲濫用鮑勃發給她的保密的身份信息，試圖在網上假扮他怎麽辦？)。另外，當可預測的或者重複的信息大量出現，這個係統的其他弱點也可能會暴露。不過，這些困難在任何公開密鑰加密係統中都可能出現。它們是可以被克服的，並且總體來說與背後的數學技術沒有太大關係，而那些數學技術才是保證加密的高質量和穩定性的因素。

這一章展示了素數以及整除性和餘數理論的一項主要應用。我們不僅從廣義的原理上，還在細節層麵對此進行了解釋，這都要感謝歐幾裏得的古代數學和歐拉在18世紀的貢獻。

我們這本書的第一部分會在第5章告一段落，該章裏我們將要介紹一些特殊類型的整數，它們與某些自然呈現的分組現象有關。

[1]　“竊聽者”的英語單詞為eavesdropper，因此虛擬的竊聽者常用名字Eve來代表。

[2]　一般稱為The Elements of Euclid，共有13卷。