[[356018]]

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

置換加密法的分類結構如圖1所示。

圖1  置換加密法的分類結構

1、Skytale加密法

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

[[356019]]

圖2  Skytale示例

置換加密法使用的密鑰通常是一些幾何圖形，它決定了重新排列字母的方式。例如，Skytale加密法的密鑰是Skytale桿，就是用它來打亂字母順序的。明文字母按一個方向填寫（例如，Skytale加密法是從上到下填寫），再從另一個方向讀取（例如，Skytale加密法是將皮革或羊皮紙卷起來后從左到右讀取）。

2、柵欄密碼加密法

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

圖3  Rail-fence加密法示例

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

圖4  三角加密法示例

3、平移置換加密法

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

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

圖5  明文和密文示例

可以用密文攻擊法和已知明文攻擊法來破解平移置換加密法。密文攻擊法通過查看密文塊，查找出可能生成可讀單詞的排列方式。一旦發現了某個塊的置換方式，就可以將其應用到03密文的所有塊中。如果密碼分析員熟悉通過顛倒字母順序來構成單詞，那么破解平移置換加密法就是一個簡單的工作了。已知明文攻擊法就更簡單，知道了明文中可能包含的一個單詞后，攻擊法可分3個步驟對密文進行破解：

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

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

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

4、列置換加密法

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

圖6  列置換矩形示例

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

這種加密法的密鑰是列數和讀取列的順序。如果列數很多，則記起來可能會比較閑難，因此可以將它表示成一個關鍵詞，以方便記憶。該關鍵詞的長度等于列數，而其字母順序決定讀取列的順序。

例如，關鍵詞“general”有7個字母，意味著矩形有7列。若按字母在字母表中的順序進行排序，則由關鍵詞general可知讀取列順序為4、2、6、3、7、1、5。圖7給出了一個列置換矩形加密示例。

圖7  列置換矩形加密示例

對于列置換矩形加密的破譯，強力攻擊法就是嘗試所有可能的列和行，代價較高且收效甚微。正確的方法是將這個問題進行分解，可以通過3步來破解列置換加密法。首先，嘗試確定換位矩形的可能大小（多少行和多少列）。然后，嘗試在這些可能的矩形中找出正確的。最后，知道正確的矩形之后，嘗試重新排列矩形列，以便還原消息。

（1）確定列的可能大小

這是強力攻擊法的第一步，也是最簡單的工作。因為該加密法完全是列換行，所以密文字符的數目必須是行數乘以列數的積。例如，假設截獲的消息有153個字符，153可以分解為3×51、51×3、17×9或9×17。假設這個消息是在一個矩形中換位的，那么這4個積肯定定義了其大小，也就是說，這個矩形有3行51列、51行3列、17行9列或9行17列。沒有其他矩形可以完全填滿這153個字符了。由于3×51或51×3的列和行相差較大，因此不太可能是加密用的矩形。最有可能的是17×9或9×17。因此，下一步就是找出這兩者之間哪個是正確的。

（2）確定正確的矩形

這個過程是基于一個事實，即矩形的每行表示的都是標準英語的一行。明文的所有字母仍出現在密文中，它們只是錯位了而已。因此可以依靠英語的常見屬性來檢測密文最可能的排列方式。例如，英語中的每句話包含大約40%的元音字母，如果某個矩形的元音字母分布滿足每行40%的標準，那么這種推測很可能就是正確的。

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

（3）還原列的順序

破解列置換加密法的最后一步是找出列的正確順序。這是通過顛倒字母順序來構成詞的過程，需要充分利用字母的一些特征，如引導字符、連字集加權等。

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

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

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

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

鐵軌法的解密過程也非常簡單，如上例中將密文每4個字母一組，組間用空格隔開，即可得：

SRKW IEHI OIHT TIEH LTER NSOE

因為知道加密的順序，所以接收方可將密文用一直線從中間分為兩個部分，如下所示：

SRKW IEHI OIHT | TIEH LTER NSOE

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

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

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

圖8  游走路徑示意

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

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

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

5、雙重換位加密法

第一次世界大戰時期，德國使用過一種著名而復雜的雙重換位加密法。一個關鍵詞短語（使用字母順序方法）會被轉換成一個數字序列。例如，關鍵詞短語為“next time”，那么其數字短語對應如下：

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”）“逐行”填寫在這個數字序列的下面，如下所示：

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

然后，按列的順序將這些列下的字母“逐行”填寫在相同的數字序列下面，如下所示：

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

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

利用該加密法通常會生成沒有完全填充滿的列換位，這會使密碼分析員破解密碼更加困難。在第一次世界大戰爆發之前，法國已經開始準備加密工作了。他們最初的成就是開發了一個功能強大的無線通信分析系統。法國人的努力得到了回報，他們可以破解和閱讀德國用雙重列換位加密法加密的很多消息。

6、旋轉方格加密法

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

圖10  典型旋轉方格示例與明文

圖11  未旋轉時的旋轉方格示例與明文

圖12  旋轉方格第1次旋轉與明文

圖13  旋轉方格第2次旋轉與明文

圖14  旋轉方格第3次旋轉與明文

旋轉方格的解密過程很簡單，只須每次順時針旋轉90°時將對應的密文填入空白格，即可恢復明文。

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

由于換位密碼算法有兩個優點：一是換位密碼算法有廣闊的密鑰空間，二是換位變換是一種極易實現的快速變換，因此它還不會被人們遺忘。盡管代替作業密碼相比換位密碼已經極其遜色，但其仍然具有頑強的生命力，當然這種生命力的客觀存在依賴于未來密碼設計者的精心呵護。