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

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

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

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

1 古典密碼

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

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

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。用這個字標記矩陣的列，把第一步的結果組成如下矩陣：

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

AGDFAFXFGFAX

XDGGGXGXGDGAA

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

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

3 ADFGX加密法的改進

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

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

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

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

（1）初始矩陣的生成。

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

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

現在，我們開始就這三個方面開始陳述。

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

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

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

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

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

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

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

假設，明文為：

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

去掉標點與空格，為

godsinhisheavenallsrightwiththeworld

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

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

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

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

再選取一個關鍵字（KEY），我們稱之為KEY-2。這個關鍵字是加密者根據一階密文的長度，也即明文長度的兩倍選取，以其可以湊成的矩陣的行或列的個數兩者中最大者為最小取值來確定。例如，在本例中，一階密文可以湊成一個9×8階矩陣，于是我們可以選擇一個元素個數為9的向量，其中的元素是0～35的整數（避免重復），一般來說都可以對應一個英文單詞，這可以是一個便于記憶的單詞。具體的，我們可以選擇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）

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

W1WLH1MMGZKW1RYCN421Z1G2I1TUZCHZINYW

GZOJHZC1TLNEL4UEUTNTWNGZIK2U1N2ONCNY

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

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

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

參考文獻

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

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

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