密碼學簡史：“矛”與“盾”的千年戰(zhàn)爭

莫提

2019年10月26日，《中華人民共和國密碼法》發(fā)布，自2020年1月1日起施行，這標志著我國在密碼的應用和管理等方面有了專門性的法律保障。從常見的數(shù)字與字母密碼、指紋密碼，再到聲紋密碼、面部識別……密碼無處不在，時刻守衛(wèi)著我們每個人的安全。關于密碼學背后的知識，同學們是否了解呢？讓我們從遙遠的古代開始講起……

古典密碼學

人類使用密碼的歷史幾乎與使用文字的時間一樣長，公元前 400 年，斯巴達人發(fā)明了“塞塔式密碼”，即把長條紙螺旋形地斜繞在一根多棱棒上，將文字沿棒的水平方向從左到右書寫，寫一個字旋轉一下，寫完一行再另起一行從左到右寫，直到寫完。解下來后，紙條上的文字消息雜亂無章、無法理解，但將它繞在另一個同等尺寸的棒子上后，就能看到原始的消息，這是最早的密碼技術。

我國古代也早有以藏頭詩、藏尾詩、漏格詩及繪畫等形式，將要表達的真正意思或“密語”隱藏在詩文或畫卷中特定位置的記載。一般人只注意詩或畫的表面意境，而不會去注意或很難發(fā)現(xiàn)隱藏其中的“話外之音”。如《水滸傳》中寫道，為了拉盧俊義入伙，“智多星”吳用和宋江便想出一個“吳用智賺玉麒麟”的主意來，利用盧俊義正為躲避“血光之災”的惶恐心理，口占四句卦歌：“蘆花叢中一扁舟，俊杰俄從此地游。義士若能知此理，反躬難逃可無憂。”這首卦歌中暗藏“盧俊義反”四字。結果，這首詩成了官府治罪的證據(jù)，終于把盧俊義逼上了梁山。

這一時期的密碼學更像是一門藝術，其核心手段是代換和置換。代換是指明文（沒有加密的文字）中的每一個字符被替換成密文中的另一個字符，接收者對密文做反向替換便可恢復出明文;置換是密文和明文字母保持相同，但順序被打亂。

代換密碼的著名例子有古羅馬的愷撒密碼（公元前1世紀）和法國的維吉尼亞密碼（16世紀）。愷撒密碼是對字母表中每個字母用它之后的第k個字母來代換，如將“comeatnine”加密為“htrjfysnsj”（k=5）。但這種加密方式無法掩蓋各字母的頻率特征，易被破解。

相比之下維吉尼亞密碼提升了安全性，它的密鑰通常是一個單詞，如“hear”。對于上述明文“comeatnine”，加密時將第1個字母后移8位（密鑰“hear”的第一個字母h處于字母表第8位），第2個字母后移5位（密鑰的第二個字母e處于字母表第5位），以此類推，得到的加密后的結果是“ktnwiyoavj”。

近代密碼學

德國工程師亞瑟·謝爾比烏斯于1919年設計出了歷史上最著名的密碼機——德國的恩尼格瑪機（德語：Enigma，又譯啞謎機，或“謎”式密碼機），在第二次世界大戰(zhàn)期間，恩尼格瑪機曾作為德國陸、海、空三軍最高級密碼機，并使得英軍從1942年2月到12月都沒能解讀出德國潛艇發(fā)出的信號。這類密碼機的使用大大提高了密碼加密速度，但由于密鑰量有限，到二戰(zhàn)中后期時，引出了一場關于加密與破譯的對抗。首先是波蘭人利用德軍電報中前幾個字母的重復出現(xiàn)，破解了早期的恩尼格瑪機，而后又將破譯的方法告訴了法國人和英國人。英國人在計算機理論之父——圖靈的帶領下，通過尋找德國人在密鑰選擇上的失誤，奪取德軍的部分密碼本獲得密鑰，以及進行選擇明文攻擊等手段，破解出相當多非常重要的德軍情報。

密碼學正式成為一門新的學科，是受計算機科學蓬勃發(fā)展刺激和推動的結果?？焖匐娮佑嬎銠C和現(xiàn)代數(shù)學方法一方面為加密技術提供了新的概念和工具，另一方面也給破譯者提供了有力武器。計算機和電子學時代的到來給密碼設計者帶來了前所未有的自由，他們可以輕易地避免原先用鉛筆和紙進行手工設計時易犯的錯誤，也不用再面對用電子機械方式實現(xiàn)的密碼機的高額費用。

現(xiàn)代密碼學

1976年，美國密碼學家提出“公鑰密碼”概念。此類密碼中加密和解密使用不同的密鑰，其中，用于加密的叫作公鑰，用于解密的為私鑰。1977年，美國麻省理工學院提出第一個公鑰加密算法——RSA算法之后，ElGamal、橢圓曲線、雙線性對等公鑰密碼算法相繼被提出，密碼學進入了一個新的發(fā)展時期。一般來說，公鑰密碼的安全性由相應數(shù)學問題在計算機上的難解性來保證，以廣為使用的RSA算法為例，它的安全性建立在大整數(shù)質因子分解在計算機上的困難性。

在數(shù)學中，把一個合數(shù)變成質數(shù)乘積的過程被稱為質因子分解。對于一臺計算機來說，把兩個很大的質數(shù)相乘，即使每一個質數(shù)長達100位，計算出結果也并不難。然而，把一個很大的數(shù)分解成質數(shù)的乘積則是出了名的困難。例如，對于整數(shù)22，我們易于發(fā)現(xiàn)它可以分解為2和11兩個質數(shù)相乘，但對于一個幾百上千位的整數(shù)，即使采用相應算法，對于計算機來說，也要很長時間才能完成分解。

世界上沒有攻不破的盾，也沒有不可抵擋的矛。隨著計算能力的不斷增強和質因子分解算法的不斷改進，特別是量子計算機的發(fā)展，公鑰密碼的安全性也漸漸受到威脅，量子密碼等前沿密碼技術逐步成為研究熱點。量子密碼是一種新的重要加密方法，它利用了量子力學中的兩個關鍵點，一個是量子的不可復制性（無法復制密鑰），另一個是量子的不可觀測性（對通信進行竊聽會導致量子狀態(tài)突變），借助量子密鑰分配協(xié)議可實現(xiàn)數(shù)據(jù)傳輸?shù)目勺C性安全。中國科學技術大學教授、中國科學院院士潘建偉在量子領域研究和實用化方面做出了突出的貢獻。近年來，他率領團隊發(fā)射全球首顆量子科學實驗衛(wèi)星“墨子號”，開通全球首條千公里級量子保密通信干線——“京滬干線”，成功實現(xiàn)洲際量子保密通信等一系列研究，使中國在量子保密通信方面研究處于國際領先水平。

密碼學的前景

公鑰密碼思想的提出，標志著現(xiàn)代密碼學的誕生，在國際密碼學發(fā)展史上是具有里程碑意義的大事件。如今，國際上已提出了許多種公鑰密碼體制，如基于分解大整數(shù)的困難性的密碼體制——RSA 密碼及其變種ElGamal 密碼等，這些都得到了廣泛的應用，并且為當今信息化時代提供了各種各樣的安全性服務。

這些公鑰密碼體制的安全性均依賴于數(shù)學難題（大整數(shù)分解難題和離散對數(shù)求解難題）的困難性，然而這些問題在量子計算情形下經(jīng)過算法處理均可變?yōu)橐捉鈫栴}，因而我們可以預言：量子計算機出現(xiàn)之日，便是現(xiàn)今密碼壽終正寢之日。因此，量子密碼加密技術以及抗量子計算機的新算法是未來密碼學的研究方向。

密碼學最基本的學科是數(shù)學，包括離散數(shù)學、線性代數(shù)、概率論等數(shù)學分支學科。想要研究密碼學，不僅要擁有嚴密的邏輯思維，能夠掌握復雜抽象的推導方法，而且要有足夠的耐心和較強的意志力，在擅長學習數(shù)學的同時，能做到對數(shù)學這門學科抱有持久的興趣。另外，計算機科學與技術專業(yè)中的邏輯學、圖形學、信息論等也是必須掌握的知識，很多密碼相關算法的設計涉及復雜的計算過程，需要通過計算機編程來解決，因此計算機與編程技術也很重要。此外，如果想要研究量子計算機、量子密碼，物理學、光學工程、核物理等專業(yè)相關的知識也必不可少。

關于密碼學的起源與發(fā)展，還有許多有趣的故事，若同學們對于密碼學的專業(yè)書籍感覺閱讀有困難的話，大家也可以看一些密碼學相關的文學與影視作品，例如著名的阿瑟·柯南道爾的作品《福爾摩斯探案集》，丹·布朗的作品《達·芬奇密碼》《數(shù)字城堡》等，相信同學們一定會樂在其中。