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

假設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－

,

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!

查看全部