密碼學(xué)簡(jiǎn)史：“矛”與“盾”的千年戰(zhàn)爭(zhēng)

莫提

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

古典密碼學(xué)

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

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

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

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

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

近代密碼學(xué)

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

密碼學(xué)正式成為一門(mén)新的學(xué)科，是受計(jì)算機(jī)科學(xué)蓬勃發(fā)展刺激和推動(dòng)的結(jié)果。快速電子計(jì)算機(jī)和現(xiàn)代數(shù)學(xué)方法一方面為加密技術(shù)提供了新的概念和工具，另一方面也給破譯者提供了有力武器。計(jì)算機(jī)和電子學(xué)時(shí)代的到來(lái)給密碼設(shè)計(jì)者帶來(lái)了前所未有的自由，他們可以輕易地避免原先用鉛筆和紙進(jìn)行手工設(shè)計(jì)時(shí)易犯的錯(cuò)誤，也不用再面對(duì)用電子機(jī)械方式實(shí)現(xiàn)的密碼機(jī)的高額費(fèi)用。

現(xiàn)代密碼學(xué)

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

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

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

密碼學(xué)的前景

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

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

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

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