在古典密碼學范疇下對ADFGX加密法的改進

摘 要：密碼學作為保護關鍵信息的手段，最早被應用在軍事以及外交領域。隨著人們?nèi)粘Ｉ畹男枨笠约翱萍嫉陌l(fā)展等因素，密碼學的應用已經(jīng)逐漸進入了人們的生活中。密碼學的發(fā)展歷程可以分為古典密碼學以及現(xiàn)代密碼學兩個階段。1949年，C.E.Shannon發(fā)表了題為《Communication theory of secrecy systems》的著名論文，首次將信息論引入密碼系統(tǒng)，建立了密碼學的數(shù)學模型，將密碼學領到了科學的軌道上。使得密碼學的發(fā)展進入了現(xiàn)代密碼學的階段。在此之前的密碼學都稱為古典密碼學。一切現(xiàn)有的現(xiàn)代密碼學的加密方法，幾乎都是由古典密碼學加密方法的組合而來的。所以研究古典密碼學，能對現(xiàn)代密碼學的加密、解密以及破解有很高的幫助。在這里，我們對古典密碼學中的經(jīng)典之作“ADFGX加密法”進行進一步的改善，來管窺一下古典密碼學的奧妙所在。

關鍵詞：密碼學古典密碼學 ADFGX加密法 Polybius方陣

中圖分類號：B81 文獻標識碼：A 文章編號：1674-098X（2013）05（b）-0217-03

1 古典密碼

古典密碼，即密碼術，它的歷史極為久遠。在計算機出現(xiàn)前，密碼學，即古典密碼學是基于字符的密碼體制組成的。不同的密碼算法是字符之間互相代換或者是互相之間換位，較好的密碼體制是這二種方法的多次運算。

古典密碼中流傳下來的這些密碼比較簡單，但它們的破譯是一切現(xiàn)代密碼破譯的基礎。古典密碼的破譯采用歸納法與演繹法。步驟是：分析、假設、推測、最后證實或否定，該文將介紹幾種典型的古典密碼。

2 ADFGX加密法

ADFGX加密的過程如下。將字母表中的字母放入一個5×5的矩陣（Polybius方陣），i和j作為同一個字母（由于Polybius時代的希臘字母為25個，所以最初的Polybius方陣使用25個字母剛好。此處ADFGX加密法是由德國人是用的，所以在德文中是講i和j看做一個字母。行和列用字母A、D、F、G、X標記。例如，矩陣可以是：

每個明文字母都用它所在的行和列的標記替代。例如s變成了FA，z變成了DG。假設明文是

Kaiser Wilhelm

這一初始步驟（分解）的結果就是：

XA FF GG FA AG DX GX GG FD XX AG FD GA

目前位置可以看到，這是一個明顯的替換密碼。下一步極大地增加了復雜度。選擇一個關鍵字（移位密鑰，KEY），如Rhein。用這個字標記矩陣的列，把第一步的結果組成如下矩陣：

現(xiàn)在對列進行調(diào)整，使標記按照字母序排列；最后，按照列的次序來讀字母（標記忽略），得到密文：

AGDFAFXFGFAX

XDGGGXGXGDGAA

只要知道了關鍵字，解密不難。關鍵字和密文的長度決定了矩陣每一列的長度。字母放入列中，調(diào)整次序和關鍵字匹配，再利用初始矩陣就可以恢復明文了。

初始矩陣和關鍵字要常變動，增加了分析的難度，因為對每一種組合只有有限數(shù)量的密文。但是，這個密碼系統(tǒng)最終還是成功地被法國的密碼專家Georges Painvin和Bureau du Chiffre破解了，并且破譯了相當數(shù)量的消息。

3 ADFGX加密法的改進

Claude Shannon在其現(xiàn)代密碼學的奠基性論文《Communication theory of secrecy systems（保密系統(tǒng)的通信原理）》中，給出一個好的密碼系統(tǒng)抵抗統(tǒng)計分析所需的兩條性質：擴散（diffusion）和混淆（confusion）。

擴散的意思是，如果明文的一個字符改變了，相應密文的幾個字符也應該改變；同樣，如果密文的一個字符改變了，相應明文的幾個字符也應該改變。可以看到，Hill密碼具有這一性質。這就意味著，明文中字母、雙連字和三連字等的統(tǒng)計頻率，擴散到明文中的多個字符中去了，這樣進行一次有意義的統(tǒng)計攻擊就需要更多的密文。

混淆的意思是，密鑰不是和密文簡單的相關。特別地，密文中的每一個字符應該依賴于密碼的多個部分。例如，假設有一個n×n矩陣的Hill密碼，已知n個足以解出加密矩陣的密明文對。如果改變密文的一個字符，矩陣的一列將會完全改變。當然，整個密鑰都改變了更好。當這種情況出現(xiàn)時，分析者可能需要同時解決所有的密鑰，而不是一段一段地逐個進行。

所以要對ADFGX加密法進行改進，可考慮的就是盡量多的擴散與混淆。故現(xiàn)在對ADFGX密碼在古典密碼學范疇下進行改進。總的來說，對于ADFGX密碼，可以從以下三個方面進行改進。

（1）初始矩陣的生成。

（2）初始加密后密文的再次加密。

（3）橫放縱取階段的再次加密。

現(xiàn)在，我們開始就這三個方面開始陳述。

4 ADFGX加密法的改進·初始矩陣的生成

由于ADFGX加密法，在最初使用時，是在開始使用前，制定好所有的初始矩陣并記錄到密碼本上，并規(guī)定好在什么時間段內(nèi)使用哪個矩陣。所以只要保證記錄矩陣的密碼本的安全性，就能保證初始矩陣的安全性。

顯然，這種方法在現(xiàn)在看來是非常不可靠的。在這里，我們可以用其他方法來生成初始矩陣。方法如下：

在現(xiàn)在的技術下，密文的發(fā)送與接收可以認為都是瞬間完成的。故，我們認定發(fā)送者與接收者是即時進行密文的傳送。所以，我們記錄下密文發(fā)送的月份α（α=1，2，…，12）與日期β（β=1，2，…，31），并構建仿射函數(shù)y=αxij2+β（mod 36）。其中xij是來自矩陣

的第i行j列的元素，在此矩陣中，0～25表示英文字母a～z，26～36表示數(shù)字0～9。

即：

在本例中，我們選擇2月20日，即α=2，β=20。我們按照行序開始運算，即從i=1開始，依次取j=1，2，…，6時的xij的取值。

下面將結果轉成新的矩陣，具體步驟如下：

（1）x與y的值保持對應關系，按照x取值的升冪順序開始進行操作。即，從初始矩陣中的x11=0位置處開始操作，此時，y=20。依次向下進行，將x的取值插到空白的y的取值所對應的地方。

（2）若x所對應的插入點已經(jīng)填入過數(shù)字，那么，記錄該點的行、列序。先按照同一列從上向下的順序將x的值放入最開始的空白處；若列滿，則按照同一行從左到右排列將x的取值放入最開始的空白處；若行也滿，則移至下一行繼續(xù)進行同一行從左到右排列將x的取值放入最開始的空白處；若新的行也滿，則繼續(xù)進行上一步，直至將該x的取值填到空白處。特別的，若已經(jīng)進行到新矩陣的x66的位置處，則從x11的位置重新開始行的操作。在最終得到的新的矩陣中，仍然是0～25表示英文字母a～z，26～36表示數(shù)字0～9。

這就是本例中最終的初始矩陣。同時仍然用ADFGVX進行標記，則有：

5 ADFGX加密法的改進·初始加密后密文的再次加密

假設，明文為：

God’s in his heaven. All’s right with the world！

去掉標點與空格，為

godsinhisheavenallsrightwiththeworld

則，由示例中的初始矩陣可得（如表1）。

此時，用Vigenere加密法繼續(xù)進行加密處理。我們將上一步得到的密文序列稱為分解加密結果。示例中的分解加密結果為72個字符，由加密者自主選擇一個關鍵字（KEY），我們在這稱之為KEY-1。先確定密鑰的長度，如6；再選擇一個元素個數(shù)為6的向量，其中的元素是0～35的整數(shù)（避免重復），一般來說都可以對應一個英文單詞，這可以是一個便于記憶的單詞。在本例中，我們選取Wright作為KEY-1，此時，wright相應原始矩陣的向量為K1=（22，17，8，6，7，19）。

用這個密鑰加密消息。首先，取第一個字母，移動22個位置，記下新位置在初始矩陣中對應的元素。然后，取第二個字母，移動17個位置，記下新位置在初始矩陣中對應的元素。以此類推繼續(xù)下去。一旦到達密鑰的末尾，我們就返回到密鑰的第1個字母。在此過程中，始終進行（mod 36）處理。則，得到第一階密文如下：ZWNGHY2UI14TZCI1NWZCN1NY WUN14T2WLGKT2UOGHEZWL1NZ 1UI1NZZCOMKE1CNJMT2RLGHY

ADFGX加密法的改進·橫放縱取階段的再次加密

再選取一個關鍵字（KEY），我們稱之為KEY-2。這個關鍵字是加密者根據(jù)一階密文的長度，也即明文長度的兩倍選取，以其可以湊成的矩陣的行或列的個數(shù)兩者中最大者為最小取值來確定。例如，在本例中，一階密文可以湊成一個9×8階矩陣，于是我們可以選擇一個元素個數(shù)為9的向量，其中的元素是0～35的整數(shù)（避免重復），一般來說都可以對應一個英文單詞，這可以是一個便于記憶的單詞。具體的，我們可以選擇masterily作為KEY-2，其對應的向量為K2=（12，0，18，19，4，17，8，11，24）。

先構造一個9×9的空白方陣，里面共有81個元素。而我們在示例中得到的一階密文為72位，這其中少了9個元素。

特此，我們要在開始構造的9×9的空白方陣中構造9個“擋板”（或稱“漏格”）來彌補這9個元素的位置。構造方法，為最開始構造初始矩陣的方法，只不過在此處由6×6變成了9×9，而且只要得出位置即可。

故，整理后得到擋板位置為（13，19，20，20，31，38，52，65，67）

現(xiàn)在，橫向將所得到的一階密文填入到該矩陣中，遇到“擋板”則越過。同時，用剛才的KEY-2標記這個矩陣；然后，對列進行調(diào)整，使標記按照對應的0～35的順序排列；最后，按照列的次序來提取字母（忽略標記與“擋板”），得到最終密文：

W1WLH1MMGZKW1RYCN421Z1G2I1TUZCHZINYW

GZOJHZC1TLNEL4UEUTNTWNGZIK2U1N2ONCNY

考慮到當輸入內(nèi)容過多，如若明文內(nèi)容在648位（雖然一般的機密信息傳輸不會涉及如此多的信息，但是也不能排除此類情況的發(fā)生），則第一階密文將達到1296位，即362，此時若KEY-2還是限制為36個不重復的組合，無法進行插入“擋板”的橫放縱取階段。所以此時要放棄KEY-2不能重復的限制。

具體操作為：當有兩個及以上字母（或數(shù)字）重復時，對于第一個出現(xiàn)的首個重復的字母（或數(shù)字），將位于該字母（或數(shù)字）序列以后的字母（或數(shù)字）統(tǒng)一做+1處理。這樣重復的字母（或數(shù)字）就比第一個出現(xiàn)的首個重復的字母（或數(shù)字）要“大”一個位數(shù)，故不再重復，且后面重復的字母就會位于第一個出現(xiàn)的首個重復的字母后面，即這些重復的字母（或數(shù)字）的出現(xiàn)的相對順序不會改變，且后面的字母（或數(shù)字）的相對順序也不會改變。在進行橫放縱取階段時也保留這些進行+1處理的字母（或數(shù)字），這樣KEY-2有重復的結果與KEY-2無重復的結果不會有邏輯上的不一致。

在進行傳輸時，只需發(fā)出KEY-1、KEY-2與密文即可。其中，可將KEY-1、KEY-2結合到一起。例如，此例中，便可將KEY-1、KEY-2結合為Wright’s masterily來進行發(fā)送。解密時，進行逆過程操作即可。

參考文獻

[1]Bruce Schneier.Applied Cryptography，Protocols，Algorithms，and Source Code in C（應用密碼學——協(xié)議、算法和C源程序）[J].祝世雄，譯.通信保密，1994（3）：72-73.

[2] 杜生輝，阮傳概.現(xiàn)代密碼學基本思想及其展望[J].Communications TechnologyDevelopment，1997（3）：37-38.

[3] Wade Trappe，Lawrence C.Washington.密碼學與編碼理論[M].王金龍，王鵬，林昌露，譯.北京：人民郵電出版社，2008：18-20.