[[356018]]

置換加密法是指重新排列文本中的字母。這種加密法與拼圖游戲相似。在拼圖游戲中，所有的圖塊都在這里，但它們最初的排列位置并不正確。置換加密法設(shè)計(jì)者的目標(biāo)是設(shè)計(jì)一種方法，使您在知道密鑰的情況下，能將圖塊很容易地正確排序。如果沒(méi)有這個(gè)密鑰，就很難正確地拼接圖塊。密碼分析者（攻擊者）的目標(biāo)是在沒(méi)有密鑰的情況下重組拼圖，或從拼圖的特征中發(fā)現(xiàn)密鑰。設(shè)計(jì)置換加密法的目標(biāo)是讓攻擊者的這兩個(gè)目標(biāo)都很難實(shí)現(xiàn)。

置換加密法的分類結(jié)構(gòu)如圖1所示。

圖1  置換加密法的分類結(jié)構(gòu)

1、Skytale加密法

斯巴達(dá)人是最早將置換加密法用于軍事消息傳遞的人之一。他們發(fā)明了一種被稱為Skytale的工具（見(jiàn)圖2）。Skytale就是一種加密用的、具有一定粗細(xì)的棍棒或權(quán)杖。斯巴達(dá)人把重要的信息寫(xiě)在纏繞于Skytale上的皮革或羊皮紙上之后，再把皮革或羊皮紙解下來(lái)，這樣就能有效地打亂字母順序。只有把皮革或羊皮紙?jiān)僖稽c(diǎn)點(diǎn)卷回與原來(lái)加密的Skytale同樣粗細(xì)的棍棒上后，文字信息才能逐圈并列呈現(xiàn)在棍棒的表面，進(jìn)而還原出它本來(lái)的意思。

[[356019]]

圖2  Skytale示例

置換加密法使用的密鑰通常是一些幾何圖形，它決定了重新排列字母的方式。例如，Skytale加密法的密鑰是Skytale桿，就是用它來(lái)打亂字母順序的。明文字母按一個(gè)方向填寫(xiě)（例如，Skytale加密法是從上到下填寫(xiě)），再?gòu)牧硪粋€(gè)方向讀?。ɡ?，Skytale加密法是將皮革或羊皮紙卷起來(lái)后從左到右讀取）。

2、柵欄密碼加密法

柵欄密碼（Rail-fence）加密法（見(jiàn)圖3）不是按從上到下的方式填寫(xiě)明文和讀取密文的，而是使用了對(duì)角線方式。在這種加密法中，明文是按“Z”字形的方式填寫(xiě)在矩形的對(duì)角線上的，然后按行讀取以生成密文。例如，如果矩形的高為3，長(zhǎng)為11，那么明文“this is a test”在該矩形中的填寫(xiě)如圖3所示，此時(shí)，按行讀取所生成的密文就是“tiehsstsiat”。

圖3  Rail-fence加密法示例

同樣的過(guò)程可以應(yīng)用于其他幾何圖形。例如，在一個(gè)固定大小的矩形中，可以將明文填寫(xiě)成一個(gè)三角形，然后，按列讀取生成密文。圖4是將明文“You mustdo that now”填寫(xiě)在一個(gè)7×4的矩形中，此時(shí)，按列讀取生成的密文是“tuhosayuttmdnoow”。

圖4  三角加密法示例

3、平移置換加密法

置換加密法的一種簡(jiǎn)單實(shí)現(xiàn)形式是平移置換加密法，這很像洗一副紙牌。在平移置換加密法中，將密文分成了固定長(zhǎng)度的塊。通常，塊越大越不容易破譯。設(shè)塊大小為s，置換函數(shù)f用于從1到s中選取一個(gè)整數(shù)，每個(gè)塊中的字母根據(jù)f重新排列。這種加密法的密鑰就是（s，f）對(duì)應(yīng)的具體數(shù)值。例如，設(shè)s為4，f給定為（2，4，1，3）。這意味著第1個(gè)字符移到位置2，第2個(gè)字符移到位置4，第3個(gè)字符移到位置1，第4個(gè)字符移到位置3。

例如，利用這種置換加密法將明文“The only limit to our realization of tomorrow will be our doubts of today”加密。首先，設(shè)置密鑰（s，f），如將s設(shè)為7，則明文將被分成塊，每塊包含7個(gè)字母，不足的用空字符填滿。然后，根據(jù)給定的函數(shù)f=（4，2，3，5，7，6，1）將每個(gè)塊重新排列，生成對(duì)應(yīng)的密文，如圖5所示。

圖5  明文和密文示例

可以用密文攻擊法和已知明文攻擊法來(lái)破解平移置換加密法。密文攻擊法通過(guò)查看密文塊，查找出可能生成可讀單詞的排列方式。一旦發(fā)現(xiàn)了某個(gè)塊的置換方式，就可以將其應(yīng)用到03密文的所有塊中。如果密碼分析員熟悉通過(guò)顛倒字母順序來(lái)構(gòu)成單詞，那么破解平移置換加密法就是一個(gè)簡(jiǎn)單的工作了。已知明文攻擊法就更簡(jiǎn)單，知道了明文中可能包含的一個(gè)單詞后，攻擊法可分3個(gè)步驟對(duì)密文進(jìn)行破解：

1）找出包含組成已知單詞的各字母的塊；

2）通過(guò)比較已知單詞與密文塊，確定置換方式；

3）在密文的其他塊上測(cè)試上面得出的置換方式。

4、列置換加密法

列置換加密法是將明文按行填寫(xiě)在一個(gè)矩形中，而密文則是以預(yù)定的順序按列讀取生成的。例如，如果矩形是4列5行，那么短語(yǔ)“encryption algorithms”可以如圖6所示寫(xiě)入矩形中。

圖6  列置換矩形示例

按一定的順序讀取列以生成密文。對(duì)于這個(gè)示例，如果讀取順序是4、1、2、3，那么密文就是“riliseyogtnpnohctarm”。這種加密法要求填滿矩形，因此，如果明文的字母不夠，可以添加“x”或“q”甚至空字符。

這種加密法的密鑰是列數(shù)和讀取列的順序。如果列數(shù)很多，則記起來(lái)可能會(huì)比較閑難，因此可以將它表示成一個(gè)關(guān)鍵詞，以方便記憶。該關(guān)鍵詞的長(zhǎng)度等于列數(shù)，而其字母順序決定讀取列的順序。

例如，關(guān)鍵詞“general”有7個(gè)字母，意味著矩形有7列。若按字母在字母表中的順序進(jìn)行排序，則由關(guān)鍵詞general可知讀取列順序?yàn)?、2、6、3、7、1、5。圖7給出了一個(gè)列置換矩形加密示例。

圖7  列置換矩形加密示例

對(duì)于列置換矩形加密的破譯，強(qiáng)力攻擊法就是嘗試所有可能的列和行，代價(jià)較高且收效甚微。正確的方法是將這個(gè)問(wèn)題進(jìn)行分解，可以通過(guò)3步來(lái)破解列置換加密法。首先，嘗試確定換位矩形的可能大?。ǘ嗌傩泻投嗌倭校?。然后，嘗試在這些可能的矩形中找出正確的。最后，知道正確的矩形之后，嘗試重新排列矩形列，以便還原消息。

（1）確定列的可能大小

這是強(qiáng)力攻擊法的第一步，也是最簡(jiǎn)單的工作。因?yàn)樵摷用芊ㄍ耆橇袚Q行，所以密文字符的數(shù)目必須是行數(shù)乘以列數(shù)的積。例如，假設(shè)截獲的消息有153個(gè)字符，153可以分解為3×51、51×3、17×9或9×17。假設(shè)這個(gè)消息是在一個(gè)矩形中換位的，那么這4個(gè)積肯定定義了其大小，也就是說(shuō)，這個(gè)矩形有3行51列、51行3列、17行9列或9行17列。沒(méi)有其他矩形可以完全填滿這153個(gè)字符了。由于3×51或51×3的列和行相差較大，因此不太可能是加密用的矩形。最有可能的是17×9或9×17。因此，下一步就是找出這兩者之間哪個(gè)是正確的。

（2）確定正確的矩形

這個(gè)過(guò)程是基于一個(gè)事實(shí)，即矩形的每行表示的都是標(biāo)準(zhǔn)英語(yǔ)的一行。明文的所有字母仍出現(xiàn)在密文中，它們只是錯(cuò)位了而已。因此可以依靠英語(yǔ)的常見(jiàn)屬性來(lái)檢測(cè)密文最可能的排列方式。例如，英語(yǔ)中的每句話包含大約40%的元音字母，如果某個(gè)矩形的元音字母分布滿足每行40%的標(biāo)準(zhǔn)，那么這種推測(cè)很可能就是正確的。

9×17的矩形有9行，因此每行應(yīng)有大約3.6個(gè)元音字母。將密文填入這個(gè)矩形中，并計(jì)算每行的元音字母數(shù)目。計(jì)算出實(shí)際的元音字母數(shù)與期望的元音字母數(shù)之差的絕對(duì)值，并將這些差值相加，即可生成該矩形的得分。最佳得分對(duì)應(yīng)的差值總和最小。

（3）還原列的順序

破解列置換加密法的最后一步是找出列的正確順序。這是通過(guò)顛倒字母順序來(lái)構(gòu)成詞的過(guò)程，需要充分利用字母的一些特征，如引導(dǎo)字符、連字集加權(quán)等。

根據(jù)列置換加密法的加密原理還衍生出一些變種，如鐵軌法。鐵軌法要求明文的長(zhǎng)度必須是4的倍數(shù)，若不符合要求，則在明文最后加上一些字母以符合加密的條件。將明文以從上到下的順序分兩行逐行寫(xiě)出。依序由左而右再由上而下地寫(xiě)出字母即為密文（在寫(xiě)明文時(shí)也可以寫(xiě)成3行或4行等，寫(xiě)法不同，解法也相應(yīng)不同）。例如，明文“STRIKE WHILE THE IRON IS HOT”，首先，該明文不滿足條件，故在尾端加上字母“E”，使明文的長(zhǎng)度變成4的倍數(shù)。然后，將明文以從上到下的順序逐行寫(xiě)出，如下所示：

S R K W I E H I O I H T

T I E H L T E R N S O E

依序由左而右再由上而下地寫(xiě)出字母，即為密文：SRKWIEHIOIHTTIEHLTERNSOE。

鐵軌法的解密過(guò)程也非常簡(jiǎn)單，如上例中將密文每4個(gè)字母一組，組間用空格隔開(kāi)，即可得：

SRKW IEHI OIHT TIEH LTER NSOE

因?yàn)橹兰用艿捻樞颍越邮辗娇蓪⒚芪挠靡恢本€從中間分為兩個(gè)部分，如下所示：

SRKW IEHI OIHT | TIEH LTER NSOE

然后左右兩半依序輪流讀出字母便可還原明文。

路游法可以說(shuō)是鐵軌法的一種推廣。此方法也必須將明文的長(zhǎng)度調(diào)整為4的倍數(shù)，之后再將調(diào)整過(guò)的明文依序由左而右再由上而下的順序（此順序稱為排列順序）填入方格矩形中。依照某一事先規(guī)定的路徑（稱為游走路徑）來(lái)游走矩形并輸出所經(jīng)過(guò)的字母，即為密文。路游法的安全性主要取決于排列順序與游走路徑的設(shè)計(jì)，但必須注意的是，排列順序與游走路徑絕不可相同，否則便無(wú)法加密。

依前例明文為：STRIKE WHILE THE IRON IS HOT，將此明文放入矩形且若以圖8所示的路徑游走，則可得到密文：ETNETOEKILROHIIRTHESIHWS。

圖8  游走路徑示意

法國(guó)人在第一次世界大戰(zhàn)時(shí)期使用的是一種換位算法——中斷列換位法。在這種加密法中，先讀取某些預(yù)定的對(duì)角線字母，然后再讀取各列，讀取各列時(shí)忽略已讀的字母。例如，在圖9所示的模式中，首先讀取對(duì)角線的字母，然后再讀取各列，結(jié)果密文為“haik aito sk eeb ic twhs swc pan irr”。

圖9  中斷列換位法字母讀取模式示意

雙重列換位加密法，正如其名稱所暗示的那樣，會(huì)先用列換位法將明文加密，然后再用列換位法將第一次換位加密的密文加密。這兩次換位所使用的關(guān)鍵詞可以相同。經(jīng)兩次換位后，明文字母的位置會(huì)被完全打亂。

5、雙重?fù)Q位加密法

第一次世界大戰(zhàn)時(shí)期，德國(guó)使用過(guò)一種著名而復(fù)雜的雙重?fù)Q位加密法。一個(gè)關(guān)鍵詞短語(yǔ)（使用字母順序方法）會(huì)被轉(zhuǎn)換成一個(gè)數(shù)字序列。例如，關(guān)鍵詞短語(yǔ)為“next time”，那么其數(shù)字短語(yǔ)對(duì)應(yīng)如下：

n e x t t i m e

5 1 8 6 7 3 4 2

首先，將明文（如“bob I need to see you at the office now alice”）“逐行”填寫(xiě)在這個(gè)數(shù)字序列的下面，如下所示：

5 1 8 6 7 3 4 2

b o b i n e e d

t o s e e y o u

a t t h e o f f

i c e n o w a l

i c e

然后，按列的順序?qū)⑦@些列下的字母“逐行”填寫(xiě)在相同的數(shù)字序列下面，如下所示：

5 1 8 6 7 3 4 2

o o t c c d u f

l e y o w e o f

a b t a i i i e

h n n e e o b s

t e e

最后，按列的順序讀取這些字母，就會(huì)生成密文“oebne ffesd eiouo ibola htcoa ecwie tytne”。

利用該加密法通常會(huì)生成沒(méi)有完全填充滿的列換位，這會(huì)使密碼分析員破解密碼更加困難。在第一次世界大戰(zhàn)爆發(fā)之前，法國(guó)已經(jīng)開(kāi)始準(zhǔn)備加密工作了。他們最初的成就是開(kāi)發(fā)了一個(gè)功能強(qiáng)大的無(wú)線通信分析系統(tǒng)。法國(guó)人的努力得到了回報(bào)，他們可以破解和閱讀德國(guó)用雙重列換位加密法加密的很多消息。

6、旋轉(zhuǎn)方格加密法

在第一次世界大戰(zhàn)期間，德國(guó)軍隊(duì)使用的加密法從換位加密法改成了替換加密法。到了1916年，他們又改回了換位加密法。這一次他們采用了旋轉(zhuǎn)方格。旋轉(zhuǎn)方格首次出現(xiàn)在興登堡（Hindenburg）于1796年寫(xiě)的一本書(shū)中，并很快就流行了起來(lái)。旋轉(zhuǎn)方格加密法在18世紀(jì)末被使用得很頻繁，后來(lái)又在第一次世界大戰(zhàn)時(shí)期被德國(guó)使用。圖10是一個(gè)典型的旋轉(zhuǎn)方格和一些樣本明文（this is an example of a turning grille for us）。如果將旋轉(zhuǎn)方格放在明文上面，那么顯示的第一個(gè)密文集就如圖11～圖14所示。這些密文按行的順序可寫(xiě)為“hinxetios”，最終的密文為“hinxetios iampouile tseanrlfu salfrnggr”。

圖10  典型旋轉(zhuǎn)方格示例與明文

圖11  未旋轉(zhuǎn)時(shí)的旋轉(zhuǎn)方格示例與明文

圖12  旋轉(zhuǎn)方格第1次旋轉(zhuǎn)與明文

圖13  旋轉(zhuǎn)方格第2次旋轉(zhuǎn)與明文

圖14  旋轉(zhuǎn)方格第3次旋轉(zhuǎn)與明文

旋轉(zhuǎn)方格的解密過(guò)程很簡(jiǎn)單，只須每次順時(shí)針旋轉(zhuǎn)90°時(shí)將對(duì)應(yīng)的密文填入空白格，即可恢復(fù)明文。

總之，隨著密碼分析技術(shù)和計(jì)算能力的迅猛發(fā)展，明文和密文在變換過(guò)程中僅做位置上的移動(dòng)是遠(yuǎn)遠(yuǎn)不夠的，還必須要有碼值上的變化。原始的換位密碼算法在抗攻擊方面的最大弱點(diǎn)是它不能抵抗差分攻擊。若要抵抗差分攻擊，明密文間必須要有很好的混合與擴(kuò)散性質(zhì)。因此，實(shí)用的換位密碼算法必須借助某種代替變換作為輔助手段，依此加強(qiáng)明密文變換間的非線性，以便抵抗一些現(xiàn)代密碼攻擊方法。

由于換位密碼算法有兩個(gè)優(yōu)點(diǎn)：一是換位密碼算法有廣闊的密鑰空間，二是換位變換是一種極易實(shí)現(xiàn)的快速變換，因此它還不會(huì)被人們遺忘。盡管代替作業(yè)密碼相比換位密碼已經(jīng)極其遜色，但其仍然具有頑強(qiáng)的生命力，當(dāng)然這種生命力的客觀存在依賴于未來(lái)密碼設(shè)計(jì)者的精心呵護(hù)。