全世界只有3.14 %?的人關注了

青少年數學之旅

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

1

人類的加密史

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

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

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

20世紀早期，德國發(fā)明了名為enigma的輪轉加密機，能對明文進行自動加密，產生的可能性高達10¹⁶種，當時處于世界領先地位，二戰(zhàn)期間被德軍大量使用。盟軍在很長時間內一籌莫展。后來，波蘭人首先破譯了德軍密碼，并發(fā)明了名為Bomba的密碼破譯機，能在2個小時內破解密碼。波蘭人在被占領前夕，把Bomba交給了英國，并在布萊切利園（Bletchley Park）內繼續(xù)研發(fā)。

“一位被擊倒的騎士在最后一刻把寶劍交給了他的戰(zhàn)友”。

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

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

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

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

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

由于加密和解密使用同樣規(guī)則（簡稱”密鑰”），于是這種模式被稱為“對稱加密算法”。

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

2

劃時代的加密算法

RSA算法走出歷史舞臺

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

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

這種新的模式也被稱為“非對稱加密算法”：

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

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

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

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

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

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

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

RSA算法的三位發(fā)明者

3

將兩個大質數相乘

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發(fā)送加密信息m，他要用公鑰 (n,e)?對m進行加密。加密過程實際上是算一個式子：

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

這樣用戶B知道了用戶A發(fā)的信息是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，意味著信息被破解。

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

4

RSA算法逐步被運用到

人類的各個方面

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

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

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

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

Google Security Key

5

算力即將大幅提升

現有算法可能不堪一擊

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

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

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

轉載來源：超級數學建模

部分素材源于網絡，版權歸原作者所有

如有侵權請留言聯(lián)系刪除，感謝合作

寫在最后

微信公眾號“少年數學家”

提供豐富的數學課外知識

數學人物、數學趣談、科技與數學

想讓孩子懂得更多有趣的數學

記得關注“少年數學家”

總結

以上是生活随笔為你收集整理的世界上迄今为止最安全的加密算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。