密碼學歷史演進經歷了三個時期:古典時期的置換密碼、近代多表替代密碼以及現代的多種非對稱加密。

原文標題:《【圖學院】密碼學:一場智力的巔峯對決》
撰文:PlatON

密碼技術(Cryptography) 包含了密碼學(Cryptography)和密碼分析學(Cryptanalysis)兩大分支,一方爲紅軍(守),一方爲藍軍(攻),兩者缺一不可。

自古以來,密碼學領域加密和解密的故事不斷被演繹,你方唱罷,我方登場。

當前人創造一種看似完美的加密技術,經過若干年,又會被後人通過先進技術解密。在這加密-解密-再加密-解密的過程中,展現出不可估量的人類智力,激發讓人探尋的無窮樂趣。

從攻防角度讀懂密碼學演進史:對稱加密到非對稱加密

本期,讓我們盤點密碼學領域的重要歷史節點,看看前輩大佬們如何運用密碼學交鋒,留下一段段里程碑式的傳奇故事。

一、古典密碼學時期

凱撒大帝:置換密碼

在古典密碼學時期,密碼學主要用於軍事的密文傳遞。公元前 58 年左右,Caesar (凱撒大帝)使用的凱撒密碼就是運用軍事命令的傳遞。他將每一個字母都進行了位移,以防止他的敵人在截獲凱撒的軍事命令之後,直接獲取到他的真實情報。

從攻防角度讀懂密碼學演進史:對稱加密到非對稱加密

加密方法:

加密的雙方首先要對字母的位移數字達成共識,比如,我們約定好的加密位移的數字是 3,那麼,我發送的每一個字母都要經過 3 個位移,(A 變成 D,B 變成 E,C 變成 F... ...)假設我的明文是「attack」 ,經過位移爲 3 的凱撒加密之後,就會變成「dwwtfn」。成功拿到密文的人,再通過把密文的每個字母減 3 的方式,就能得到真實的明文信息。

解密方法:

首先通過頻率分析或者樣式單詞分析的方法,判定是否用的是凱撒密碼。如果是,則可以使用窮舉的辦法,按照字母系統尋找偏移量。由於使用愷撒密碼進行加密的語言一般都是字母文字系統,因此密碼中可能是使用的偏移量也是有限的,26 個英文字母,至多偏移 25 位。

頻率分析是基於某些字母在英文寫作中出現不同頻率的事實 – 例如,E 通常最常出現,其次是 T 和 A;而 Q 和 Z 出現次數最少(見下圖)。

從攻防角度讀懂密碼學演進史:對稱加密到非對稱加密英文字母頻率

參考如下加密文本 :

PZ AOL TVZA MYLXBLUA SLAALY PU AOPZ ZLUALUJL

如果算上字母,你會注意到 L 的出現頻率高於其他任何字母(8 次)。因此,如果這是替換密碼並且原始消息是英語,則 L 代表 E 是安全的猜測,L 與字母表中的 E 相距 7 個空格。如果位移量是 7,則這組密碼文本將變成:

IS THE MOST FREQUENT LETTER IN THIS SENTENCE

對於非常短的消息,手動執行暴力攻擊或頻率分析可能很容易,但對於整個段落或文本頁面來說可能會非常耗時。

二、近代密碼學時期

Enigma (轉輪密碼機) : 多表替代密碼

Enigma (轉輪密碼機)由德國工程師 Arthur Scherbius 創造,在二戰時是德軍用來傳播信息的加密機,彼時,英法聯軍完全不知道德國正在借用此機器傳遞信息。

從攻防角度讀懂密碼學演進史:對稱加密到非對稱加密

加密方法:

Enigma 的加密原理是多表替代——通過不斷改變明文和密文的字母映射關係,對明文字母們進行着連續不斷的換表加密操作。

密碼機設計有 3 個轉輪,在每個轉輪的邊緣上標記 26 個德文字母,藉以表示轉輪的 26 個位置。經過巧妙的設計,每次轉輪旋轉後,都會停留在這 26 個位置中的某個位置上。在轉輪組內,轉輪們相互接觸的側面之間,都有相對應的電路觸點,可以保證轉輪組的內部構成通路。

於是,輸入的字母 K,經過第一個轉輪,變成輸出字母 R;之後這個 R 進入第二個轉輪,咱們假設它又變成了 C;爾後,這個 C 再進入第三個轉輪,假設又變成了 Y。如此,初始字母 K 歷經 3 次輪轉,變成了誰也認不出來的 Y。

解密方法:

二戰時期,阿蘭·麥席森·圖靈(Alan Mathison Turing)基於前人的經驗,從 Enigma 的整個密文入手,設計了「圖靈炸彈機」來進行破解。

從攻防角度讀懂密碼學演進史:對稱加密到非對稱加密

因爲德國人會在特定時間發送特定的電報,而「天氣」和「希特勒」這兩個詞是「明文庫」中最常見的兩個單詞。所以,圖靈採用基於明文的攻擊,在早上六點多的電報密文中尋找「天氣」和「希特勒」兩個單詞加密後的密文,就能根據明文和密文的對應關係計算出密鑰。

關於這段歷史的更多趣聞,感興趣的小夥伴可參見電影《模仿遊戲》。

三、現代密碼學時期

在 1976 年以前,所有的加密方法都是同一種模式:加密、解密使用同一種算法,即對稱加密算法(symmetric encryption algorithm)。在交互數據的時候,彼此通信的雙方就必須將規則告訴對方,否則沒法解密。那麼加密和解密的規則( 簡稱密鑰 )的保護就顯得尤其重要,傳遞密鑰成爲了最大的隱患。

當密碼學進入現代時期,從藝術變成科學,開始建造完備的體系,這一隱患被得以有效解決。同時,多種密碼學技術的誕生,也讓原本神祕變換的密碼學世界變得更加精彩紛呈。

從攻防角度讀懂密碼學演進史:對稱加密到非對稱加密

重大歷史節點 :

  • 1976 年,是現代密碼學的開端,密碼學開始由藝術轉爲科學,並建立一套完整的理論體系。兩位美國計算機學家迪菲(W.Diffie)、赫爾曼(M.Hellman)提出了一種嶄新構思,可以在不直接傳遞密鑰的情況下,完成密鑰交換。這被稱爲「 迪菲赫爾曼密鑰交換 」算法,開創了密碼學研究的新方向。
  • 1977 年,三位麻省理工學院的數學家羅納德·李維斯特(Ron L. Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard M. Adleman)一起設計了一種算法,可以實現非對稱加密。這個算法用他們三個人的姓氏首字母命名,叫做 RSA 算法。
    加密方式需要兩個密鑰:公開密鑰,簡稱公鑰( public key );私有密鑰,簡稱私鑰(private key),公鑰加密,私鑰解密。RSA 算法也具有缺陷 : 效率相對較低 , 字節長度限制等,在實際應用中我們往往會結合對稱性加密一起使用 , 祕鑰使用 RSA 算法。
  • 1978 年,Ron L. Rivest,Leonard M. Adleman 以及 Michael L. Dertouzos 提出了同態加密(Homomorphic Encryption)概念。允許對密文進行特定的代數運算後依然能得到加密的結果,將該結果解密以後的結果與對明文進行同樣運算的結果會保持一致。
  • 1982 年,姚期智先生提出安全多方計算,即 MPC。主要探討 n 個參與方必須各自輸入信息去計算一個約定的函數。除了計算的正確性,這一計算過程還必須保障每個參與方輸入數據的隱私。
  • 1989 年,麻省理工學院研究人員 Goldwasser、Micali 及 Rackoff 提出了「零知識證明」的概念。指的是證明者能夠在不向驗證者提供任何有用的信息的情況下,使驗證者相信某個論斷是正確的。

隨着人類科技水平的不斷進步,密碼學和密碼分析學技術得以推陳出新,這驅動着密碼從業者不斷突破創新,讓密碼學技術發揮出應有價值,得以運用在社會生活的各個角落。

來源鏈接:mp.weixin.qq.com