一個劃時代的演算法，驚天動地

一個只能用算力來破解的加密演算法

人類的加密史

公元前5世紀，古希臘人使用一根叫scytale的棍子來傳遞加密信息。要加密時，先繞棍子卷一張紙條，把信息沿棒水平方向寫，寫一個字旋轉一下，直到寫完。解下來后，紙條上的文字消息雜亂無章，這就是密文。將它繞在另一個同等尺寸的棒子上后，就能看到原始的消息。如果不知道棍子的粗細，則無法解密裡面的內容。

古希臘人用於加密的scytale棍子

公元前1世紀，凱撒大帝為了能夠確保他與遠方的將軍之間的通信不被敵人的間諜所獲知，發明了Caesar密碼。每個字母都與其後第3位字母對應，然後進行替換，比如，「a」對應於「d」，「b」對應於「e」，以此類推。

20世紀早期，德國發明了名為enigma的輪轉加密機，能對明文進行自動加密，產生的可能性高達1016種，當時處於世界領先地位，二戰期間被德軍大量使用。盟軍在很長時間內一籌莫展。後來，波蘭人首先破譯了德軍密碼，並發明了名為Bomba的密碼破譯機，能在2個小時內破解密碼。波蘭人在被佔領前夕，把Bomba交給了英國，並在布萊切利園（BletchleyPark）內繼續研發。

「一位被擊倒的騎士在最後一刻把寶劍交給了他的戰友」。

就在這裡，在眾多科學家的努力下，設計出了世界上第一台電子計算機巨人（Colossus），破解了大量德軍密文，為逆轉形勢提供了大量重要情報。如果密碼沒有破譯成功，盟軍可能戰敗，歷史可能改寫。

enigma密碼機的核心部件：控制輪

關於密碼學歷史，有許多動人的故事，但事實上密碼學一直緩慢發展。其實在1976年以前，所有的加密方法都是同一種模式：

（1）甲方選擇一種加密規則，對信息進行加密；

（2）乙方使用同一種規則，對信息進行解密。

由於加密和解密使用同樣規則（簡稱」密鑰」），於是這種模式被稱為「對稱加密演算法」。

這種模式有一個最大弱點：甲方必須把密鑰告訴乙方，否則無法解密。保存和傳遞密鑰，就成了最頭疼的問題。

劃時代的加密演算法

RSA演算法走出歷史舞台

時間來到了1976年，兩位美國計算機學家威特菲爾德·迪菲（WhitfieldDiffie）和馬丁·赫爾曼（MartinHellman），首次證明可以在不直接傳遞密鑰的情況下，完成解密。這被稱為「Diffie-Hellman密鑰交換演算法」。

DH演算法的出現有著劃時代的意義：從這一刻起，啟示人們加密和解密可以使用不同的規則，只要規則之間存在某種對應關係即可。

這種新的模式也被稱為「非對稱加密演算法」：

（1）乙方生成兩把密鑰，公鑰和私鑰。公鑰是公開的，任何人都可以獲得，私鑰則是保密的。

（2）甲方獲取乙方的公鑰，用它對信息加密。

（3）乙方得到加密后的信息，用私鑰解密。

公鑰加密的信息只有私鑰解得開，只要私鑰不泄漏，通信就是安全的。

就在DH演算法發明后一年，1977年，羅納德·李維斯特（RonRivest）、阿迪·薩莫爾（AdiShamir）和倫納德·阿德曼（LeonardAdleman）在麻省理工學院一起提出了RSA演算法，RSA就是他們三人姓氏開頭字母拼在一起組成的。

新誕生的RSA演算法特性比DH演算法更為強大，因為DH演算法僅用於密鑰分配，而RSA演算法可以進行信息加密，也可以用於數字簽名。另外，RSA演算法的密鑰越長，破解的難度以指數倍增長。

因為其強大的性能，可以毫不誇張地說，只要有計算機網路的地方，就有RSA演算法。

RSA演算法的三位發明者

將兩個大質數相乘

RSA演算法是這樣工作的

RSA演算法名震江湖，那它到底是如何工作的?

第一步，隨機選擇兩個不相等的質數p和q。

第二步，計算p和q的乘積n。n的長度就是密鑰長度，一般以二進位表示，一般長度是2048位。位數越長，則越難破解。

第三步，計算n的歐拉函數φ(n)。

第四步，隨機選擇一個整數e，其中是1< e < φ(n)，且e與φ(n) 互質。

第五步，計算e對於φ(n)的模反元素d。所謂「模反元素」就是指有一個整數d，可以使得ed被φ(n)除的餘數為1。

第六步，將n和e封裝成公鑰 (n,e) ，n和d封裝成私鑰 (n,d) 。

假設用戶A要向用戶B發送加密信息m，他要用公鑰 (n,e) 對m進行加密。加密過程實際上是算一個式子：

用戶B收到信息c以後，就用私鑰 (n, d) 進行解密。解密過程也是算一個式子：

這樣用戶B知道了用戶A發的信息是m。

用戶B只要保管好數字d不公開，別人將無法根據傳遞的信息c得到加密信息m。

RSA演算法以(n, e)作為公鑰，那麼有無可能在已知n和e的情況下，推導出d？

（1）ed≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

（3）n=pq。只有將n因數分解，才能算出p和q。

所以，如果n可以被很簡單地分解，則很容易算出d，意味著信息被破解。

但是目前大整數的因式分解，是一件非常困難的事情。目前，除了暴力破解，還沒有發現別的有效方法。也就是說，只要密鑰長度足夠長，用RSA加密的信息實際上是不能被解破的。

RSA演算法逐步被運用到人類的各個方面

由於RSA演算法的可靠性，現在非常多的地方應用了這個技術。

最重要的運用，莫過於信息在互聯網上傳輸的保障。運用RSA演算法，在傳輸過程中即使被截獲，也難以進行解密，保證信息傳輸的安全。只有擁有私鑰的人，才可能對信息進行解讀。

銀行交易的U盾，是用戶身份的唯一證明。U盾第一次使用時，運用RSA演算法，產生私鑰並保存在U盾之中。在以後的使用中，用私鑰解密交易信息，才能執行後面的交易操作，保障用戶的利益。

現在假冒偽劣產品不少，企業需要使用一些防偽手段。目前最常見的是二維碼防偽，方便消費者通過簡單的掃一掃操作進行產品驗證。但是二維碼如果以明文形式展示，則容易被不法分子利用，目前已有人運用RSA演算法對二維碼的明文進行加密，保障消費者的利益。

Google Security Key

算力即將大幅提升，現有演算法可能不堪一擊

RSA演算法是這個時代最優秀的加密演算法之一，其安全性建立在一個數學事實之上：將兩個大質數相乘非常容易，但要對其乘積進行因式分解卻非常困難。因此可以將其乘積公開作為加密的密鑰。

「江山代有才人出,各領風騷數百年」。一個時代，必然有屬於這個時代的優秀演算法，RSA是我們所處這個時代的佼佼者。但隨著量子計算機的誕生，計算能力即將急劇增長，算力在未來可能不是一個稀缺物品。

而算力是又破解RSA演算法的唯一鑰匙。到那個時候，又有什麼演算法能夠保障我們的信息安全呢？