數據加密實質上是對以符號為基礎的數據進行移位和置換的變換算法。一般來說，有一個稱為密鑰的關鍵數據作為這個變化算法的參數。而解密過程就是這個算法的逆算法，同時也需要密鑰參數。

假設p、q為兩個很大的質數，p*q=n。如果已知n，求唯一的p或q是一件很困難的事情。需要知悉的是，如果p、q為兩個很大的合數，則其積的因式分解會有多個，不是唯一的。利用兩個質數的積的因式分解的唯一性及逆運算的複雜性，似乎在加密領域可以做點事情。

質數（prime number，也叫素數，在大於1的自然數中，除了1和它本身以外不再有其他因數）被利用在密碼學上，將想要傳遞的信息在編碼時加入質數，編碼之後傳送給收信人，任何人收到此信息後，若沒有此收信人所擁有的密鑰，則解密的過程中（實為尋找素質數的過程），將會因為找質數的過程（分解質因數）過久，使即使取得信息也會無意義。

1 對稱加密算法：DES和AES

在傳統的加密算法中，加密密鑰與解密密鑰是相同的，或者可以由其中一個推知另一個，稱為對稱密鑰算法。這樣的密鑰必須祕密保管，只能為授權用戶所知，授權用戶既可以用該密鑰加密信息，也可以用該密鑰解密信息。DES(Data Encryption Standard數據加密標準)是對稱加密算法中最具代表性的。DES可以對任意長度的數據加密，實際可用密鑰長度56ibt。加密時首先將數據分為64bit的數據塊，採用ECB、CBC、CFB等模式之一，每次將輸入的64bit明文變換為64bit密文。最終，將所有輸出數據塊合併，實現數據加密。DES的保密性僅取決於對密鑰的保密，而算法是公開的。DES內部的複雜結構是很難找到破譯方法的根本原因。

在對稱加密算法中，數據發信方將明文（原始數據）和加密密鑰一起經過特殊加密算法處理後，使其變成複雜的加密密文發送出去。收信方收到密文後，若想解讀原文，則需要使用加密用過的密鑰及相同算法的逆算法對密文進行解密，才能使其恢復成可讀明文。在對稱加密算法中，使用的密鑰只有一個，發收信雙方都使用這個密鑰對數據進行加密和解密，這就要求解密方事先必須知道加密密鑰。

攻擊 DES 的主要形式被稱為蠻力的或徹底密鑰搜索，即重複嘗試各種密鑰直到有一個符合為止。DES採用64位密鑰技術，實際只有56位有效，8位用來校驗的。譬如，有這樣的一臺PC機器，它能每秒計算一百萬次，那麼256位空間它要窮舉的時間為2285年。所以這種算法還是比較安全的一種算法。

在應用方面，儘管DES在安全上是脆弱的，但由於快速DES芯片的大量生產，使得DES仍能暫時繼續使用，為提高安全強度，通常使用獨立密鑰的三級DES。

AES是美國國家標準技術研究所NIST旨在取代DES的21世紀的加密標準。

AES的基本要求是，採用對稱分組密碼體制，密鑰的長度最少支持為128、192、256，分組長度128位，算法應易於各種硬件和軟件實現。1998年NIST開始AES第一輪分析、測試和徵集，共產生了15個候選算法。1999年3月完成了第二輪AES2的分析、測試。2000年10月2日美國政府正式宣佈選中比利時密碼學家Joan Daemen 和 Vincent Rijmen 提出的一種密碼算法RIJNDAEL作為AES。

2 RSA

多年來，許多人都認為DES並不是真的很安全。事實上，即使不採用智能的方法，隨著快速、高度並行的處理器的出現，強制破解DES也是可能的。"公開密鑰"加密方法使得DES以及類似的傳統加密技術過時了。公開密鑰加密方法中，加密算法和加密密鑰都是公開的，任何人都可將明文轉換成密文。但是相應的解密密鑰是保密的（公開密鑰方法包括兩個密鑰，分別用於加密和解密），而且無法從加密密鑰推導出，因此，即使是加密者若未被授權也無法執行相應的解密。

本世紀七十年代，幾位美國數學家提出一種編碼方法，這種方法可以把通訊雙方的約定公開，然而卻無法破譯密碼，這種奇蹟般的密碼就與質數有關。

人們知道，任何一個自然數都可以分解為素數（兩個或兩個以上）的乘積，如果不計因數的次序，分解形式是唯一的。這叫做算術基本定理，歐幾里得早已證明了的。可是將一個大整數分解卻沒有一個簡單通行的辦法，只能用較小的素數一個一個去試除，耗時極大。如果用電子計算機來分解一個100位的數字，所花的時間要以萬年計。可是將兩個100位的數字相乘，對計算機卻十分容易。

公開密鑰加密思想最初是由Diffie和Hellman提出的，最著名的是Rivest、Shamir以及Adleman提出的，通常稱為RSA（以三個發明者的首位字母命名）的方法，該方法基於下面的兩個事實：

I 已有確定一個數是不是質數的快速算法；

II 尚未找到確定一個合數的質因子的快速算法。

RSA方法的工作原理如下：

1) 任意選取兩個不同的大質數p和q，計算乘積r=p*q；

2) 任意選取一個大整數e，e與(p-1)*(q-1)互質，整數e用做加密密鑰。注意：e的選取是很容易的，例如，所有大於p和q的質數都可用。

3) 確定解密密鑰d：

(d * e) modulo（p - 1）*（q - 1） = 1

根據e、p和q可以容易地計算出d。

4) 公開整數r和e，但是不公開d；

5) 將明文P (假設P是一個小於r的整數)加密為密文C，計算方法為：

C = P^e modulo r

6) 將密文C解密為明文P，計算方法為：

P = C^d modulo r

然而只根據r和e（不是p和q）要計算出d是不可能的。因此，任何人都可對明文進行加密，但只有授權用戶（知道d）才可對密文解密。

3 簡單實例說明RSA工作原理

下面舉一簡單的例子對上述過程進行說明，顯然我們只能選取很小的數字。

例：選取p=3, q=5，則r=15，（p-1）*（q-1）=8。選取e=11（大於p和q的質數），通過（d*11）modulo(8) = 1。

計算出d =3。

假定明文為整數13。則密文C為

C = P^e modulo r

= 13^11 modulo 15

= 1,792,160,394,037 modulo 15

= 7

復原明文P為：

P = C^d modulo r

= 7^3 modulo 15

= 343 modulo 15

= 13

因為e和d互逆，公開密鑰加密方法也允許採用這樣的方式對加密信息進行"簽名"，以便接收方能確定簽名不是偽造的。假設A和B希望通過公開密鑰加密方法進行數據傳輸，A和B分別公開加密算法和相應的密鑰，但不公開解密算法和相應的密鑰。A和B的加密算法分別是ECA和ECB，解密算法分別是DCA和DCB，ECA和DCA互逆，ECB和DCB互逆。若A要向B發送明文P，不是簡單地發送ECB（P），而是先對P施以其解密算法DCA，再用加密算法ECB對結果加密後發送出去。

密文C為：

C = ECB（DCA（P））

B收到C後，先後施以其解密算法DCB和加密算法ECA，得到明文P：

ECA（DCB（C））

= ECA（DCB（ECB（DCA（P））））

= ECA（DCA（P）） /*DCB和ECB相互抵消*/

= P /*DCB和ECB相互抵消*/

這樣B就確定報文確實是從A發出的，因為只有當加密過程利用了DCA算法，用ECA才能獲得P，只有A才知道DCA算法，沒有人，即使是B也不能偽造A的簽名。

RSA提出後，三位發明家曾經公佈了一條密碼，懸賞100美元破譯，他們預言，人們至少需要20000年，才能破譯，即使計算機性能提高百倍，也需要200年。但只過了不到18年，這個密碼就被人破譯，意思是：“The magic words are squeamish ossifrage”。這個密碼如此快的破解，是因為全世界二十多個國家的六百多位工作者自發聯合起來，利用計算機網絡，同時進行因式分解，並不斷交流信息，彙總計算結果，用了不到一年的時間，就將129位的N分解成64位和65位的兩個素數的積。計算機網絡將分解效率提高了近萬倍，這是發明者當初沒有預想到的。但是，如果提高位數到200或300位，工作量將會大的不可思議，即使計算機技術有重大突破，破譯也幾乎不可能。

RSA加密使用了"一對"密鑰。分別是公鑰和私鑰，使用公鑰加密的數據，利用私鑰進行解密。使用私鑰加密的數據，利用公鑰進行解密。這個公鑰和私鑰其實就是一組數字！其二進制位長度可以是1024位或者2048位。長度越長其加密強度越大，目前為止公之於眾的能破解的最大長度為768位密鑰，只要高於768位，相對就比較安全。所以目前為止，這種加密算法一直被廣泛使用。

4 關於質數的猜想

大約在公元前300年,歐幾里得就證明了素數有無窮多個。設2,3,…,p是不大於p的所有素數，q=2*3*…*p+1。容易看出q不是2，3，…，p的倍數。由於q的最小正除數一定是素數，因此，或者q本身是一個素數，或者q可被p與q之間的某兩個素數所整除[比如：2*3*5*7*11*13+1=30031=59*509]。所以必有大於p的素數存在，由此即知素數有無窮多個。

素數在自然數中佔有極其重要的地位，但是它的變化非常不規則。人們至今沒有找到，大概也不可能找到一個可以表示全體素數的有用公式。最初的研究方法，是通過觀察素數表來發現素數分佈的性質。現有的較完善的素數表是D.B.扎蓋爾於1977年編制的，列出了不大於50000000的所有素數。從素數表可以看出：在1到100中間有25個素數,在1到1000中間有168個素數,在1000到2000中間有135個素數, 在2000到3000中間有127個素數，在3000到4000中間有120個素數,在4000到5000中間有119個素數,在5000到10000中間有560個素數。由此可看出，素數的分佈越往上越稀少。

4.1 黎曼猜想

黎曼猜想是關於黎曼ζ函數ζ(s)的零點分佈的猜想，由波恩哈德·黎曼1859年提出的，這位數學家於1826年出生在當時屬於漢諾威王國的名叫佈列斯倫茨的小鎮。1859年，黎曼被選為了柏林科學院的通信院士。作為對這一崇高榮譽的回報，他向柏林科學院提交了一篇題為“論小於給定數值的素數個數”的論文，在這篇文章裡，黎曼闡述了質數的精確分佈規律。

素數分佈是以黎曼公式為中心，高斯公式為上限的正態分佈，這在現在來說是經驗公式，待數學家給出嚴格證明之後才能成為數學定理。

4.2 哥德巴赫猜想

是否每個大於2的偶數都可寫成兩個素數之和？

1742年6月7日，哥德巴赫寫信給歐拉，提出了著名的哥德巴赫猜想：隨便取某一個奇數，比如77，可以把它寫成三個素數之和，即77=53+17+7；再任取一個奇數，比如461，可以表示成461=449+7+5，也是三個素數之和，461還可以寫成257+199+5，仍然是三個素數之和。例子多了，即發現“任何大於5的奇數都是三個素數之和。”

1742年6月30日歐拉給哥德巴赫回信。這個命題看來是正確的，但是他也給不出嚴格的證明。同時歐拉又提出了另一個命題：任何一個大於2的偶數都是兩個素數之和。但是這個命題他也沒能給予證明。

－End－