密碼算法

陳道蓄

自從人類進(jìn)入階級社會以來，軍事與政治斗爭催生了保密通信。對需要傳遞的信息加密，即使信件落入敵方手中，其內(nèi)容也無法被理解?，F(xiàn)在，隨著網(wǎng)絡(luò)滲透到每個普通人生活的方方面面，信息安全成了全社會的“剛性”需求。使用互聯(lián)網(wǎng)的每個普通人恐怕每天都得有幾次需要輸入密碼的時候，其實只要你在網(wǎng)上使用信息服務(wù)，不管你是否知道，總有加密解密算法在無聲地為你服務(wù)，包括你進(jìn)入各種服務(wù)的登錄信息，往往也會被加密，避免他人很容易得到你的個人身份信息。

凱撒密碼

一般教科書上都會將古羅馬時代的凱撒密碼稱為我們能夠確知的第一種密碼系統(tǒng)。這種密碼非常簡單。

假設(shè)我們通信時只使用26個英文字母（不區(qū)分大小寫），加上空格符號，我們的“字母表”總共有27個符號。英文字母是有確定次序的，我們分別用0到25表示字母表中相應(yīng)的字母，并令空格符的編號為26。

凱撒密碼的“密碼機(jī)”如圖1所示。大小不一的兩個同心圓周上依次分布著26個字母。內(nèi)圈的小圓盤可以旋轉(zhuǎn)，如當(dāng)前位置狀態(tài)下小圓上的字母A對應(yīng)大圓上的字母S，B對應(yīng)T，以此類推。（注意：圖中未包含空格符，但讀者很容易理解，這個“密碼機(jī)”工作原理不依賴于具體符號內(nèi)容）

我們將明文中的符號（小圓）替換為對應(yīng)符號（大圓）即可得到密文。根據(jù)圖1中標(biāo)示的編號，如果用c（x），p（x）表示密文與明文中分別使用的符號在字母表中序號，則加密過程可以用以下公式表示：c（x）=p（x）+18 mod 26。這里使用模算術(shù)，即結(jié)果為簡單加法和對26取余數(shù)，保證不會出現(xiàn)“字母表溢出”。

18即在字母表中的“位移量”（大小兩個圓對應(yīng)字母在字母表中的距離），因此凱撒密碼是一種簡單位移碼，這個例子中“密鑰”是18，解碼時只要按照公式p（x）=c（x）-18 mod 26即可。這個過程很簡單，下面直接給出相應(yīng)的Python代碼段（如下頁圖2）。

函數(shù)encode_decode既用于編碼也用于解碼。這里采用的“密鑰”是5，并限定使用的字母表只包含小寫英文字母、十進(jìn)數(shù)字、最基本的標(biāo)點符號以及空格符，一共40個。利用上述編碼方式，報文“we will arrive at railway station 3 pm tomorrow afternoon.”將被加密為“1je1nqqefwwn0jefyewfnq1f3exyfyntse8eureytrtwwt1efkyjwsttsb”。

由于凱撒密碼中可選的密鑰不大于字母表的長度（長了沒意義），所以在計算機(jī)時代通過窮舉法即刻可以破解。即使使用人工方法，這個密碼也不難破解。注意，上述過程中空格符也同樣移位，如果空格符不處理，那手工破解這樣的密文只能作為小學(xué)生智力測試的題目。讀者不妨自己編寫一個程序破解凱撒密碼。

如果不是使用一個固定的移位量，顯然可以使破解的難度增大。考慮不用一個數(shù)字做密鑰，而是選擇一個英語單詞做密鑰，如“algorithm”。這個單詞由9個字符構(gòu)成，用它們在英文字母表中的序號（從0開始）作為相應(yīng)的“移位量”，則分別是“0，11，6，14，17，8，19，7，12”?，F(xiàn)在加密是依次輪流使用這9個不同的位移量值，這只需對密鑰字長度取模即可。讀者很容易修改前面的過程，實現(xiàn)多位移量加密。即使是使用多位移量，密鑰不是太長時，計算機(jī)仍然很容易破解。

置換碼

顯然，如果不是采用固定的“移位方式”，而是定義一個字母表上的一一對應(yīng)的映射，由于長度為n的字母表中字母可能的排列方式有n！種，采用字母表上的置換方式定義密鑰比凱撒密碼安全得多，至少人工破解非常困難了。

我們用隨機(jī)方式生成字母表的任意一種排列。這樣的排列共有n！種，盡管我們知道現(xiàn)在的計算機(jī)中不可能產(chǎn)生真正意義上的“隨機(jī)”，但下面的算法可以保證得到任意一種排列的概率是相同的（如圖3）。

因為Python中的string不支持內(nèi)容的修改，所以需要將原字母表轉(zhuǎn)為list。新的排列相當(dāng)于在字母表上定義了一個一一對應(yīng)的函數(shù)，這就是“密鑰”。讀者應(yīng)該很容易實現(xiàn)相應(yīng)的加密與解密算法。

表面上看n！雖然對計算機(jī)而言也是巨大的數(shù)，用窮盡方法破解很不現(xiàn)實，但自然語言中字符出現(xiàn)的頻度有明顯差異，只要積累足夠的密文，通過頻度分析就能找到解密的突破口。

轉(zhuǎn)置碼

小朋友可能玩過一種游戲。在一張硬紙板上畫出包含4k個小方格的方陣，將其中k個挖空。將硬紙板放置在白紙上，如果挖的位置適當(dāng)，可以按照特定方向旋轉(zhuǎn)90度的方式依次在挖空位置上寫字而不重疊?？偣矊懲?k個字后就形成了含4k個字的密文。挖空的位置就相當(dāng)于“密鑰”。圖4中是僅含16個空格的簡單例子：利用左邊的“密鑰”，以逆時針方向旋轉(zhuǎn)對中間的“明文”加密得到右側(cè)的密文。（這里為了簡單只用16個位置）

這種加密方法與前面介紹的移位碼與置換碼不同。字母表中每個字符在密文中的對應(yīng)字符不由字符本身決定，而是取決于該字符在原文中出現(xiàn)的位置（不是字母表中的位置）以及加密時采用的位置對應(yīng)關(guān)系。這個例子中用的紙板上挖孔的方式當(dāng)然不適合計算機(jī)實現(xiàn)（但讓計算機(jī)幫我們決定合適的挖空位置是一個很好的編程練習(xí)）。計算機(jī)中基于同樣思想的方法稱為“轉(zhuǎn)置碼”。注意這種方法與字母表的字符表示無關(guān)。

轉(zhuǎn)置碼的基本原理可以描述如下：假設(shè)明文包含n個字符。先確定一個“行寬”值，假設(shè)為w?？梢岳斫饷魑氖前葱袝鴮懙?。加密時通過轉(zhuǎn)置使得原來的“行”變成“列”，但密文仍舊按照按行輸出形式生成。如圖5所示，左邊為明文，右邊為密文。

這里假設(shè)密鑰m=9（行寬），整個明文長度未必是m的整數(shù)倍，最后空格可以用任意字符填滿至行寬。（為什么填任何字符都可以？）

其實在計算機(jī)中并不需要“行列”的概念，只需適當(dāng)控制輸入與輸出中字符相應(yīng)index的關(guān)系就可以了。具體說，把左邊的明文編碼為右邊的密文，明文中index從0開始順序遞增，右邊密文中字符的index依次是km+i，其中m是密鑰，k從0開始，每“行”加1，i=0，1，2，…，m。

為了提高安全性，可以在應(yīng)用轉(zhuǎn)置碼時除m外再加一個密鑰，它可以是一個長度為m的字符串，如“algorithm”，按照英文字母表排序作為該字符串內(nèi)元素序號，“algorithm”將對應(yīng)（1，5，2，7，8，4，9，3，6）， 編碼是用此序列作為“列”的順序。見圖5最右邊。

編碼算法過程的Python實現(xiàn)如下頁圖6所示，讀者可類似地自行實現(xiàn)解碼過程。

公鑰密碼與RSA算法

前面提到轉(zhuǎn)置碼雖然可能的密鑰數(shù)量巨大，但通過字符頻度分析容易找到破解的入口。頻度分析依賴樣本數(shù)量，如果經(jīng)常換密鑰，顯然安全性會提高。極端地說，如果每個密鑰只用一次，可以認(rèn)為這樣的密碼是無法破解的。

可是，我們前面介紹的方法加密與解密必須使用相同的密鑰，這稱為“對稱”密碼。通信雙方必須保有相同的密鑰，經(jīng)常更換代價很高。讀者一定看過影視劇中關(guān)于傳遞“密碼本”的情節(jié)，代價往往是犧牲許多人的生命。

20世紀(jì)70年代以前人們一直確信對稱對于加密和解密是鐵定的規(guī)則。非對稱密碼的出現(xiàn)是一次重大的突破。相關(guān)的學(xué)者有5人為此得到計算機(jī)領(lǐng)域最高獎“圖靈獎”。

在討論密碼通信時，我們常用兩個假想的人物Alice和Bob表示發(fā)件人和收件人。我們可以用一個形象的比喻解釋“非對稱”的含義。如果Bob在公眾場所放置了多個信箱，上面掛了鎖，但并不鎖上，只有Bob本人有信箱的鑰匙。當(dāng)Alice打算發(fā)一封密信給Bob時，她只要將信放入Bob的信箱，隨即將鎖鎖上（當(dāng)然她自己也無法將信取出來了）。Bob只需用自己的鑰匙開鎖就可以拿到密信。

基于非對稱的思想可以開發(fā)“公鑰”密碼。密鑰被分為兩部分，Alice用Bob公開的密鑰（稱為公鑰）對報文加密，但解密需要的部分（稱為私鑰）只有Bob本人掌控。計算機(jī)實現(xiàn)時，不是像前面那些方法那樣逐個字符轉(zhuǎn)換。我們將整個報文看作一個數(shù)（計算機(jī)中任意的字符串總可以看作一個二進(jìn)制數(shù)），當(dāng)然可能是非常大的數(shù)。我們需要的是一對函數(shù)與相應(yīng)的反函數(shù)，其中一個方向計算容易，但逆運(yùn)算卻非常困難。

這原理說起來似乎不難理解，但要在思想上突破傳統(tǒng)觀念的約束并能真正找到可行的實現(xiàn)方法是非常困難的。文獻(xiàn)[1]有關(guān)于這段歷史的詳細(xì)描述。

本文不打算涉及太多的相關(guān)數(shù)學(xué)概念，我們下面僅通過一個簡化的例子描述公鑰密碼的使用過程。我們在算法園地欄目前面的文章中介紹過兩個很大的整數(shù)相乘的算法，在計算機(jī)上很容易實現(xiàn)。反之，如果我們知道的是兩個很大的質(zhì)數(shù)的乘積，要想通過分解知道原來兩個乘數(shù)究竟是什么就非常困難了。當(dāng)數(shù)字很大時，現(xiàn)在的計算機(jī)也無法在可以容忍的時間內(nèi)算出結(jié)果。這里強(qiáng)調(diào)“兩個質(zhì)數(shù)”的乘積，就是避免包含很小的因子，為分解提供突破口。

公鑰密碼使用的RSA算法選擇密鑰的過程可簡述如下：

1.隨機(jī)選擇兩個不同的大質(zhì)數(shù)p，q，如1000位以上的。

2.計算：n=p×q。

3.計算 m=（p-1）×（q-1），選一個較小的奇數(shù)e，與m互質(zhì)。

4.計算d，滿足ed=1（mod m）。

5.將e，n公布，作為公鑰;安全保存d，作為私鑰。

Alice將明文M加密為密文C，并將C發(fā)給Bob，按如下方式計算（前面說了，M可以看作一個數(shù)字）：

P（M）=Me（mod n）， 這里只需要公鑰，P是加密函數(shù)

Bob將密文C還原為明文M，按如下方式計算：

S（C）=Cd（mod n）， 可以證明：Cd=Med（mod n）

為便于讀者理解，這里舉一個很小的例子。

假設(shè)Alice要發(fā)給Bob的明文M=“88”：

1.Bob已經(jīng)選擇兩個質(zhì)數(shù)11，17， 乘積為187;并選擇了小奇數(shù)7（與160互質(zhì)）。Bob將187和7公布，作為公鑰;并計算出d=23，滿足23×7=1（mod 160=（11-1）×（17-1）），23作為密鑰保存。

2.Alice將88加密為C=887（mod 187）=11，并發(fā)給Bob。

3.Bob利用私鑰23解密：原文=C23（mod 187）=1123（mod 187）=88

這里會用到幾個乘冪計算與質(zhì)數(shù)算法，感興趣的讀者可參閱文獻(xiàn)[2]，那里也給出了上述例子中用到的公式的正確性證明。

本文開始時提到互聯(lián)網(wǎng)的廣泛應(yīng)用使得每個普通人日常都需要使用加密解密功能，如果沒有公鑰密碼，每個人去維護(hù)對稱密鑰是完全不可能的。但一方面，公鑰密碼并不能替代對稱密碼，因為更高要求的信息安全度公鑰密碼并不能保證滿足，另一方面，從上面的介紹中大家也能看出它需要的計算量很大，效率受到影響。現(xiàn)在的對稱密碼的設(shè)計復(fù)雜度遠(yuǎn)不是我們前面介紹的那些方法可比的。密碼涉及非常深的數(shù)學(xué)概念，盡管現(xiàn)在有關(guān)密碼的書可謂“汗牛充棟”，但一般讀者能理解的并不多。文獻(xiàn)[3]介紹了用Python語言實現(xiàn)一些簡單密碼方法，不僅介紹加密解密，還介紹了一些破解密碼的“黑客”算法。這本書對密碼與Python程序設(shè)計的要求都是“零基礎(chǔ)”，所以很適合中小學(xué)生用于課外活動。

參考文獻(xiàn)：

[1]Simon Singh.The Code Book：the Secret History of Codes and Codebreaking， Fourth Estate，1999，中譯本——碼書：編碼與解碼的戰(zhàn)爭[M].南昌：江西人民出版社，2018.

[2]Thomas Cormen， etc.： Introduction to Algorithms， 3rd ed.， MIT Press， 2009， 中譯本——算法導(dǎo)論[M].北京：機(jī)械工業(yè)出版社，2012.

[3]Al Sweigart： Cracking Codes with Python： An Introduction to Building and Breaking Cyphers， No Starch Press， 2018.

注：作者系南京大學(xué)軟件學(xué)院原院長，計算機(jī)系原系主任。