古典密碼學

人類使用密碼，已經有數千年歷史，而使用密碼的目的，就是不讓敵對陣營或不該知道訊息內容的人知道訊息。對使用方塊字的漢人而言，古早年代婦女們所使用之「女書」，對於不知道該內容的男人而言，就是一種密碼法。而西方是使用字母拼音文字的民族，早期的密碼技術，主要以書寫文字之取代 (Substitution)以及位移 (Transposition)為主。

在本文中，我們將討論古典密碼以及其破譯技術，綱要如下：

• 取代加密法 (Substitution Cipher)：

  • 凱撒挪移法 (Caesar Shift Cipher)
  • 仿射密碼 (Affine Cipher)
  • 單套字母替代法與頻率分析
  • Vigenere碼與頻率分析
  • 單次密碼簿
  • Enigma密碼機

• 位移加密法 (Transposition Cipher)：

  • Rail Fence Cipher
  • Columnar Transposition

凱撒挪移碼(Caesar Shift Cipher)：

一種簡易的「單套字母取代法」，即將明文字母 (Plain Alphabet)一一改成在它後三位(不限定挪移幾位)的字母。比如凱撒名言 '' veni vedi veci ''(我來了，我見了，我征服了) 就可以加密成 '' YHQL YLGL YLFL ''。

為了方便起見，可將字母化為數字代碼。

加解密範例：

Alice欲將明文 '' gual is divided into three part '' 加密成密文，傳給Bob。

1. (金鑰產生) Alice與Bob協定編碼方式為明文字母移後4位，即加解密金鑰同為k=4

2. (加密) Alice將明文 '' gual is divided into three part '' 化為數字代碼：
   (6, 21, 0, 11, 8, 18, 3, 21, 8, 3, 4, 3, 8, 13, 19, 14, 19, 7, 17, 4, 4, 15, 0, 17, 19)。

3. 使用加密函數E(m)=m+k=m+4 (mod 26)計算得到：
   (10, 4, 25, 15, 12, 22, 7, 12, 25, 12, 7, 8, 7, 12, 17, 23, 17, 23, 11, 21, 8, 8, 19, 4, 21, 23)

   即密文 " KEYPMWHMZMHIHMRXSXLVIITEXW "。

4. (解密)Bob收到密文後，使用解密函數D(c)=c-k=c-4 (mod 26)計算，並考慮空格，可還原明文：

   (6, 0, 21, 11, 8, 18, 3, 21, 8, 3, 4, 3, 8, 13, 19, 14, 19, 7, 17, 4, 4, 15, 0, 17, 19) = " gual is divided into three part "。

破解範例：

Eve截收到一則Alice傳給Bob的密文，並知道是以凱撒挪移法編碼。密文為 " penpxre "，Eve使用暴力攻擊，試用所有25把金鑰，即解密函數 D(c)=c-k (mod 26) (k=1, 2, 3..., 25)，得到：

(k=1) "odmowqd" , (k=2) "nclnvpc" , (k=3) "mbkmuob" , ...... , (k=13) "cracker" , ......., (k=25) "qfoqysf"

發現只有在k=13才得到有意義的文字 "cracker"。

仿射密碼(Affine Cipher)：

與凱撒挪移法一樣，也是一種「單套字母替代法」，將字母化為數字代碼 a=0, b=1, c=2, ...., z=25，其加密函數為 E(m)=αm+β (mod 26)，其中α與β為整數，且α必須與26互質。

為何α必須與26互質？？

假設gcd(α, 26)=g>1，此時函數E將不是1對1，不同明文字母x1, x2將會對應到相同值。以gcd(α, 26)=g>1而言，g值有可能是2或13，以g=2時為例，只需x1 ≡ x2 (mod 13)，而當g=13時，只需x1 ≡ x2 (mod 2)，都會滿足αx1+β ≡ αx2+β (mod 26)。

當加密函數不是1對1時，就無法存在反函數，如此的情況必須排除。

以集合Z/26 = {0,1,2,3,...,25}而言，可以在該集合上進行模加減乘法，但是「模除法」就不是每個元素都能做(必須要有乘法反元素)。而要觀察x是否有乘法反元素，只需考量x是否與模數n互質-->即xy ≡ 1 (mod 26)有y解並求出(使用Extended Euclidean Algorithm)。

Z/26乘法反元素對照表：

x	1	3	5	7	9	11	15	17	19	21	23	25
x^-1	1	9	21	15	3	19	7	23	11	5	17	25

有了Z/26乘法反元素對照表，就可以很容易找出加密函數之反函數，即D(c) = α^-1(c-β) (mod 26)。

加解密範例：

Alice欲將明文m="affine"用仿射密碼加密，傳訊給Bob而Bob解讀之。

1. (金鑰產生)Alice與Bob事先協定一把密鑰K=(3,8)，其中gcd(3,26)=1。
2. (加密)Alice使用加密函數E(m)=3m+8 (mod 26)計算得： m="affine"=(0,5,5,8,13,4) ----------> (8,23,23,6,21,20)="IXXGVU"=c
3. (解密)Bob收到密文c，使用解密函數D(c)=3^-1(c-8)=9(c-8) (mod 26)計算得： c="IXXGVU"=(8,23,23,6,21,20) ------------> (0,5,5,8,13,4)="affine"=m

弱點：

因爲仿射密碼仍爲單字母表密碼, 其依舊保留了該類別加密之弱點。當α=1，仿射加密為凱撒加密，因為加密方程可簡化為線性移動。 在小於26之數中有12數與26互質，因此共有 12*26=312可能之關鍵值。 因為密碼缺少複雜性，這套系統是不安全的。

單套字母取代法及頻率分析：

前述之凱撒挪移密碼以及仿射密碼均為單套字母取代法之特例。一般而言，所謂單套取代法，就是將明文字母以其他密文字母取代，進行加密，而解密過程就是加密運算之逆運算。

更精確地說，就是考慮字母集合A={a,b,c,d,e,....,y,z}，而加密函數是1對1函數 ƒ : A→A (ƒ為A上置換)，而解密函數就是 ƒ^-1，為 ƒ 的反函數。

加解密範例：

Alice欲以單套字母取代法加密，與Bob傳訊，事先約定密鑰為一串字母"KEYWORD"，傳統上會先把一個關鍵詞寫在字母表最前面，再刪去重複字母，這樣就能得到一個混合表系統。

1. 此時加密函數為 ƒ = ABCDEFGHIJKLMNOPQRSTUVWXYZ

                                KEYWORDABCFGHIJLMNPQSTUVXZ
   

2. 而解密函數為上下兩例交換，並重新按順序排列。

3. 假設明文為m="monoalphabet"。

4. 則密文為c="HJIJKGLAKEOQ"。

以26字母之置換總數共有26! ≈ 4*10^26 > 2^56，

以暴力攻擊，逐一置換代入，要比近代密碼DES之金鑰還高，但26字母所出現頻率並不是平均的，因此可藉由密文所出現字母頻率與習慣英文字母出現比率做比較，只要截收支密文夠長，應足以破譯。

英文字母出現頻率表：

運用這些資訊，明文為英文之單套字母加密之密文可使用「頻率分析」破譯。

Vigenere密碼：

16世紀法國人Vigenere發展了一種「多套字母取代法」(Polyalphabetic Substitution)，與單套字母取代法最大不同，就是加密時，不是針對單一字母加密，而是一個區塊一個區塊加密。

演算法：

• 令區塊長度為d，其中訊息代碼為x=(x1,x2,....,xd)∈(Z/26)^d
• 密鑰為k=(k1,k2,....,kd)∈(Z/26)^d
• 則加密函數為E(x)=x+k=(x1+k1, x2+k2, ....., xd+kd) (mod 26)
• 而解密函數為D(y)=y-k=(y1-k1, y2-k2, ....., yd-kd) (mod 26)
• 當中加解密函數互為反函數

事實上，Vigenere密碼是一種挪移碼，但與凱撒挪移碼不同之處，只是挪移的是字母區塊而非單一字母。

加解密範例：

Alice欲使用Vigenere密碼加密與Bob傳訊，他們已事先協定好所使用的密鑰k=(21,4,2,19,14)。而明文為m="ciphertext"。

其加密過程為：

亦可經由Vigenere Table翻成密文：

破譯方法：

Vigenere密碼在早年，是被視為牢不可破的，主要原因是未能找出密碼區塊長度；一旦區塊長度能確定，就能運用針對單套取代法的頻率分析，找出密鑰值，因此密文攻擊層面主要考量：

1. 找出區塊之長度(即密鑰之長度)。
2. 找出個別之密鑰值。

找出區塊之長度(即密鑰之長度)：

• Kasiski測試法(Kasiski Test)

  Kasiski 測試法是由 Friedrich Kasiski 於1863年所提出，然而早在約1854年這一方法就由Charles Babbage首先發現。它主要基於這樣一個事實：兩個相同的明文段將加密成相同的密文段，它们的位置間距假設為 δ，則 δ≡0(mod m)。反過來說，如果在密文中觀察到兩個相同的長度至少為3的密文段，那麼將给破譯者帶來很大方便，因為它们實際上對應了相同的明文串。

  範例：

  密鑰：FORESTFORESTFORESTFORESTFOR

  明文：better to do well than to say well

  密文： GSKXWKYCUSOXQZKLSGYCJEQPJZC

  第一個YC出現後到第二個YC的結尾一共有12個字母，那麼密鑰的長度應該是12的因数1，2，3，4，6，12之中的一個。

  當密文很長的時候，可以找出幾組重複的密文段，找出它們間距的相同因數，就是密鑰長度。

• 吻合指數法(Index of Coincidence)

  在1920年Wolfe Friedman就曾定應所謂吻合指數：

  令x=x1 x2 x3 ..... xn為長度為n的字母字串，定義此字串x之吻合指數為「任取此字串中的兩字母為相同之機率。」

  定義公式：

  

  常用公式：(xi為字母a,b,c...,z在字串x中所出現的次數，L為密文長度)

  

  對英文而言，根據英文字母出現頻率表，我们可以計算出英文文章的吻合指數為 P(A)^2+P(B)^2+.....+P(Z)^2 = 0.065。

  使用吻合指數法：

  假設使用Vigenere加密後的密文為y = y1 y2 ... yn。将字串y分割成m个長度相等的子字串，分别為y1，y2，...，ym，這樣就可以以列的形式寫出密文，組成一個m×(n/m)矩陣。矩陣的每一行對應於子字串yi，1 ≤ i ≤ m。

  舉例來說：

  密文 ABCDEABCDEABCDEABC 按m=2分组，則每組為

  組1：A C E B D A C E B

  組2：B D A C E B D A C

  若m恰好就是密鑰的長度(或其整數倍)，則每一組的CI值大約為0.065。

  若m不是密鑰的長度，那麼子字串yi的字母應為平均分布，因為它們是通過不同密鑰以移位加密方式獲得的，其CI值約為1/26=0.038。

找出個別之密鑰值：

• 在知道了密鑰長度n以後，就可將密文分組，每一組都是一個挪移碼，然後對每一組用字母頻率分析進行解密，和在一起就能成功解密。
• 首先對每個子字串中各個字母在第一個座標的頻率進行統計（記為 fi , i∈a,.....,z），查看英文字母出現頻率表(記為 pi)，計算子字串長度為n，使用公式：

• 計算出M0，然後對子字串移位25次，同樣地按照上述方法求出M1~M25的值。

• 根據吻合指數的定義可知：一個有意義的英文文章，M ≈ 0.065，所以找出M值接近0.065的移位數，就是密鑰中對應的字母。

單次密碼簿(One-Time Pad)：

最著名的無法破譯系統，應屬單次密碼簿，早在1918年前後，就由Gilbert Vernam以及Joseph Mauborgne所發展出來，這種密碼系統在冷戰時期，尚為蘇聯間諜所使用，而單次密碼簿的密鑰不可重複使用，否則就有被破譯的可能。

加解密範例：

Alice欲將明文m="OK"，藉由單次密碼簿加密成密文c，傳訊給Bob。假設密鑰為k="DA"。

1. (加密)Alice先將明文m化為ASCII代碼(當然雙方必先協定所用之代碼方式)並加密，即
   明文 m = "OK" = (79,75)ASCII = 10011111001011
   密鑰 k = "DA" = (68,65)ASCII = 10001001000001
   ----------------------------------------------------------------------------⊕
   密文 c = 00010110001010

   將密文c傳給Bob。

2. (解密)Bob取得密文，並用密鑰解密：
   密文 c = 00010110001010
   密鑰 k = 10001001000001 = "DA"
   ------------------------------------------------------⊕
   明文 m = 10011111001011 = "OK"

註：英文26個大寫字母只占ASCII代碼很小一部分，如此只用小部分ASCII代碼的編碼方式並不恰當。另外，密鑰必須由適當的亂數產生器產生(至少要是虛擬亂數產生器)，否則有被「猜」到的可能。

單次密碼簿的XOR運算亦可修改文一般模加法運算。

Enigma密碼機：

二次大戰期間，德國發明家Authur Scherbius發明了Enigma密碼機，它突破性地結合機器來進行加密，使得密碼更不易被破解。

基本原理：

• 其中最基本的三大部分為鍵盤、轉輪和燈板。鍵盤共有26個鍵，分別為26個英文字母，其排列接近我們現在所使用的計算機鍵盤。為了使消息盡量簡短且更難破譯，空格和標點符號都被省略。
• 鍵盤、轉輪和燈板由電線相連，轉輪本身也集成了26條線路，把鍵盤的信號對應到燈板不同的小燈上去，每一個字母都一一對應替換為另一個字母 。

零件組合：

1. 鍵盤：為明文字母輸入用。
2. 接線板(Stecker/Plug-Board)：
   • Scherbius在鍵盤和第一轉輪之間增加了一個接線板。這塊接線板允許使用者用一根連線把某個字母和另一個字母連接起來，這樣這個字母的信號在進入轉輪之前就會轉變為另一個字母的信號(字母置換)。
   • 連線最多可以有六根（後期的Enigma具有更多的連線），這樣就可以使6對字母的信號置換，其他沒有插上連線的字母保持不變，當然連接板上的連線狀況也是收發訊息的雙方需要預先約定好的。
3. 滾輪(Rotor)：
   • 當鍵盤上一個鍵被按下時，相應的密文在燈板上顯示，轉輪的方向就自動地轉動一個字母的格子。
   • 但是如果連續鍵入26個字母，轉子就會整整轉一圈，回到原始的方向上，這時編碼就和最初重複了。
   • 於是Scherbius在機器上又加了一個轉輪。當第一個轉子轉動整整一圈以後，它上面有一個齒撥動第二個轉輪，使得它的方向轉動一個字母的位置。用這樣的方法，要26*26=676個字母後才會重復原來的編碼。而事實上Enigma裡有三個轉輪，不重複的方向個數將達到26*26*26=17576個。
4. 反射器(Reflector)：
   • Scherbius十分巧妙地在三個轉輪的一端加上了一個反射器，他把鍵盤和燈板中的相同字母用電線連在一起(固定式置換)。
   • 反射器雖然沒有像轉輪那樣增加可能不重複之方向，但是它可以使解碼的過程和編碼的過程完全一樣，故Enigma密碼為對稱式密碼。
   • 反射器帶來的一個副作用就是一個字母永遠也不會被加密成它自己，因為反射器中一個字母總是被連接到另一個不同的字母，這也使它成為一個被破解的導火線。
5. 燈板：為密文字母輸出用。

Enigma的密鑰：

• 三個轉輪不同的方向組成了26*26*26=17576種不同可能性。
• 三個轉輪間不同的相對位置為3!=6種可能性。
• 接線板上兩兩交換6對字母的可能性數目非常巨大，有72282089880000/6!=100391791500種。
• 於是一共有：17576*6*100391791500=10586916764424000，大於10^16種可能的設定。

接線板與轉輪對Enigma的重要：

• 其實接線板對可能性的增加貢獻最大，那麼為什麼Scherbius要那麼麻煩地設計轉輪之類的東西呢？原因在於連接板本身其實就是一個簡單替代密碼系統，在整個加密過程中，連接是固定的，所以單使用它是十分容易用頻率分析法來解密的。
• 轉輪系統雖然提供的可能性不多，但是在加密過程中它們不停地轉動，使整個系統變成了多元式替代系統，頻率分析法對它再也無能為力，與此同時，接線板卻使得可能性數目大大增加，使得暴力破密法望而卻步。

Rail Fence Cipher：

將明文排列成像鐵道柵欄一樣上下兩行，排列中明文必須扣除空白鍵，並以上下次序排列。明文中不計空白鍵，且明文的字元數必須是四的倍數，不到四的倍數則以“E”字元補滿。

加解密範例：

• 明文：I SIT BY MY WINDOW WAITING FOR YOU 金鑰：2條柵欄

• 鐵道柵欄排列：

• 再將鐵軌排列中的字母，由左至右、由上而下，依序編寫出來，即成為加密後的密文，密文如下：
  密文：IIBMWNOWIIGOYUSTYYIDWATNFROE

• 為了方便起見，我們將密文以每4個字母為單位排成一組，期間用空白隔開：
  密文：IIBM WNOW IIGO YUST YYID WANT FROE

• 以下說明為什麼密文的長度必須是4的倍數的原因。當接收端收到此密文之後，因為他知道加密的順序，因此他可將密文由中間切開分成兩半，如下所示：
  IIBM WNOW IIGO YU │ ST YYID WANT FROE

• 然後左右兩半依序輪流讀出字母便可還原成原來的明文：ISITBYMYWINDOWWAITINGFORYOU

當然，Rail Fence Cipher是用兩行來排列，我們也可以用三行或四行來排列，轉換成更複雜的編碼技巧。

Columnar Transposition：

與Rail Fence Cipher非常相似，但是使用多行列矩陣方式排列；同Rail Fence Cipher將明文的長度調整為四的倍數，調整後的明文由左至右；由上而下的順序排列填入矩陣的方格中，如果還有空格的話，則填入”E”來補滿。另外採用一把取出密文的金鑰，金鑰的長度與矩陣的行數目相同；每相對應行的金鑰數字，為取出密文的次序。例如，金鑰為{4, 3, 1, 2, 5, 6, 7}，則表示第3行是第一個被取出，接著取出第4行；依此類推。取出每一行內的字母時，依由上至下的順序。

加解密範例：

• 明文：I SIT BY MY WINDOW WAITING FOR YOU。

• 填入矩陣後，可依照金鑰所指定的順序取出矩陣內字母，即得密文：IIIRTNTYSWAOIYWFBDIOYONUMWGE。

• 解密時，只要依照金鑰所指定的順序將密文填入矩陣中，再由左至右、由上到下的順序取出，便可以還原明文了。

• 密文每四個字元一組：IIIR TNTY SWAO IYWF BDIO YONU MWGE，依序填入陣列內，如下：

• 再由左至右，從陣列內取出明文：I SIT BY MY WINDOW WAITING FOR YOU

• 如果一次排列的加密易被破解的話，可利用同樣一把鑰匙重複加密，以增加其複雜度與破解的困難度。