希爾密碼

本文的閱讀等級:初級

希爾密碼 (Hill cipher) 由美國數學家希爾 (Lester S. Hill) 於1929年發明,它是線性代數於密碼學的一個經典應用。希爾密碼是一種替換式密碼,加密一方按照特定規律將明文取代為密文,密文接收者解密時必須使用相反規律才能取得原文本[1]。舉例來說,凱撒密碼是最廣為人知的一種簡易替換式密碼,加密方式係將明文訊息的每一個字母替換為循環移位後的對應字母,位移量即為密鑰 (key)。以英文為例,除了26個字母,還可加入標點符號和空格以方便閱讀。譬如,若移位量為3,則29個明文字母 (含句號「.」,問號「?」與空格「\sqcup」) 與對應的密文字母如下所示:

明文字母表:ABCDEFGHIJKLMNOPQRSTUVWXYZ .?\sqcup
密文字母表:DEFGHIJKLMNOPQRSTUVWXYZ .?\sqcupABC

為便利計算,我們將29個字母以數字 0, 1, 2,…, 28 依序編碼,即 A\to0,B\to1,C\to2,以此類推。簡單講,每一個字母可視為二十九進制的數字。設非零整數 k 表示密鑰,凱撒密碼的加密公式為 E_k(x)=(x+k)\mod{29},解密公式為 D_k(y)=(y-k)\mod{29}。不同於凱撒密碼的簡易加密法,希爾密碼採用表格式 (polygraphic) 加密,我們不再單獨替換個別字母,而是替換一組字母。首先將明文訊息切割為相同大小的單元,稱為組,每一組包含 n (n\ge 2) 個字母,接著使用矩陣乘法將每組明文轉換成密文,所乘矩陣即為密鑰。解密同樣使用矩陣乘法,惟所乘矩陣為密鑰的逆矩陣。希爾密碼其實是由 n\times n 階密鑰矩陣表達的一線性變換,n 維明文向量形成定義域,n 維密文向量形成到達域,矩陣乘法實現加密與解密程序。下面我們說明希爾密碼的加密與解密過程以及破解方法,模算術是必要的預備知識 (見“利用模算術判定可逆矩陣”)。

 
加密

設計希爾密碼的第一個步驟是確定字母集 S。前面提到除了26個英文字母,另外可加入句號「.」,問號「?」與空格「\sqcup」,合計29個字母。當然我們可以繼續擴充字母集,但最好能維持一個原則:字母集的基數 (cardinal number,即字母總數) \vert S\vert 為一質數 (素數)。這麼做的好處是只要密鑰的行列式不被 \vert S\vert 整除,密鑰即為可逆矩陣 (密鑰必須可逆,否則無法解密)。如果字母集僅含26個字母,則密鑰的行列式必須與26互質才能保證密鑰可逆。

 
考慮明文訊息

I\sqcupNEED\sqcupHELP.

假設每一組包含 n=3 個字母,明文訊息可切割成4組:

I\sqcupN   EED   \sqcupHE   LP.

若明文訊息的字母總數不等於3的倍數,可重複最末一個字母補齊。譬如,PLANE 切割成為2組 PLA 和 NEE。密文接收者解密後必須自行判讀 PLANEE 包含多餘一個字母 E。按照前述的數字編碼方式,每一組字母可用三維向量表示,原文本的有序向量編碼如下:

\displaystyle  \left[\!\!\begin{array}{r}  8\\  28\\  13  \end{array}\!\!\right],~\left[\!\!\begin{array}{c}  4\\  4\\  3  \end{array}\!\!\right],~\left[\!\!\begin{array}{r}  28\\  7\\  4  \end{array}\!\!\right],~\left[\!\!\begin{array}{c}  11\\  15\\  26  \end{array}\!\!\right]

任何 3\times 3 階整數可逆矩陣皆可作為密鑰,例如,

\displaystyle  A=\left[\!\!\begin{array}{crr}  4&9&-2\\  3&5&7\\  1&-6&11  \end{array}\!\!\right]

這裡可逆矩陣的意義不同於實矩陣,稍後將詳細說明。我們用模算術計算矩陣乘法以加密,如下:

\displaystyle\begin{aligned}  \left[\!\!\begin{array}{crr}  4&9&-2\\  3&5&7\\  1&-6&11  \end{array}\!\!\right]\left[\!\!\begin{array}{rcrc}  8&4&28&11\\  28&4&7&15\\  13&3&4&26  \end{array}\!\!\right]&=\left[\!\!\begin{array}{rcrr}  258&46&167&127\\  255&53&147&290\\  -17&13&30&27  \end{array}\!\!\right]\\  &\equiv\left[\!\!\begin{array}{ccrr}  26&17&22&11\\  23&24&2&0\\  12&13&1&27  \end{array}\!\!\right]\pmod{29}.\end{aligned}

最後將有序向量的數字解碼,即得下列密文訊息:

. XM   RYN   WCB   LA?

 
解密

密文接收者必須擁有密鑰 A 方可解密,這部分涉及建立於模算術的有限體,稱為素體 (或素域,prime field)。若 p 是一質數,同餘類集合 \mathbb{Z}/p\mathbb{Z} 是一素體,記為

\displaystyle  \mathbb{F}_p=\mathbb{Z}/p\mathbb{Z}=\{0,1,2,\ldots,p-1\}

在素體 \mathbb{F}_p 中,每一非零同餘類存在唯一的乘法逆元 (見“有限體與模算術”)。換句話說,我們可以用模算術實現加減乘除四則運算。上例中,p=29\det A=200\equiv 26\pmod{29},因此確定 A 可逆。考慮定義於 \mathbb{F}_p 的線性方程 A\mathbf{x}=\mathbf{b},其中 An\times n 階密鑰,\mathbf{b}n 維密文向量。在 \mathbb{F}_p 中,若 \det A\neq 0 (即 \det A 不被 p 整除),則得唯一解 \mathbf{x}=A^{-1}\mathbf{b},此即 \mathbf{b} 所對應的明文向量。

 
下面解釋如何計算定義於 \mathbb{F}_{29} 的密鑰逆矩陣 A^{-1}。如果 n 的數值不大,我們可以採用逆矩陣公式 \displaystyle  A^{-1}=(\det A)^{-1}\hbox{adj}A (見“三階逆矩陣公式”)。使用嘗試錯誤法可得 (\det A)^{-1}\equiv 19\pmod{29},驗證如下:(\det A)(\det A)^{-1}=26\times 19=494\equiv 1\pmod{29}。接著代入公式,

\displaystyle\begin{aligned}  A^{-1}&=19\left[\!\!\begin{array}{rrr}  \left|\!\!\begin{array}{rr}  5&7\\  -6&11  \end{array}\!\!\right|&-\left|\!\!\begin{array}{rr}  9&-2\\  -6&11  \end{array}\!\!\right|&\left|\!\!\begin{array}{cr}  9&-2\\  5&7  \end{array}\!\!\right|\\  &&\\  -\left|\!\!\begin{array}{cr}  3&7\\  1&11  \end{array}\!\!\right|&\left|\!\!\begin{array}{cr}  4&-2\\  1&11  \end{array}\!\!\right|&-\left|\!\!\begin{array}{cr}  4&-2\\  3&7  \end{array}\!\!\right|\\  &&\\  \left|\!\!\begin{array}{cr}  3&5\\  1&-6  \end{array}\!\!\right|&-\left|\!\!\begin{array}{cr}  4&9\\  1&-6  \end{array}\!\!\right|&\left|\!\!\begin{array}{cc}  4&9\\  3&5  \end{array}\!\!\right|  \end{array}\!\!\right]=19\left[\!\!\begin{array}{rrr}  97&-87&73\\  -26&46&-34\\  -23&33&-7  \end{array}\!\!\right]\\  &=\left[\!\!\begin{array}{rrr}  1843&-1653&1387\\  -494&874&-646\\  -437&627&-133  \end{array}\!\!\right]\equiv\left[\!\!\begin{array}{crc}  16&0&24\\  28&4&21\\  27&18&12  \end{array}\!\!\right]\pmod{29}.\end{aligned}

密文接收者將密文訊息分組並轉成有序向量,再與逆密鑰 A^{-1} 相乘以解密,即得原文本的數字編碼:

\displaystyle\begin{aligned}  \left[\!\!\begin{array}{crc}  16&0&24\\  28&4&21\\  27&18&12  \end{array}\!\!\right]\left[\!\!\begin{array}{ccrr}  26&17&22&11\\  23&24&2&0\\  12&13&1&27  \end{array}\!\!\right]&=\left[\!\!\begin{array}{rrcc}  704& 584& 376& 824\\  1072& 845& 645& 875\\  1260& 1047& 642& 621  \end{array}\!\!\right]\\  &=\left[\!\!\begin{array}{rcrc}  8&4&28&11\\  28&4&7&15\\  13&3&4&26  \end{array}\!\!\right]\pmod{29}  .\end{aligned}

 
破解

假設密碼分析者得知下列三組明文、密文對:

明文:POT   TOP   OPT
密文:DQY   ?AN   ISR

當然他必須先猜測每組包含 n=3 個字母。觀察發現三組明文的差異僅在於字母的位置互換,但三組密文卻非常不同。這是因為矩陣乘法具有擴散 (diffusion) 效果,意思是使明文與密文的關係複雜化。不過,這並不表示密碼分析者無法破解密鑰。因為希爾密碼的本質是線性變換,很容易被已知明文攻擊 (known-plaintext attack),即密碼分析者獲知多組明文、密文對,並據此解出密鑰。令 P 是有序明文向量組成的編碼矩陣,每一行向量表示一明文組,同樣地,C 是相同尺寸的密文向量組成的編碼矩陣。以前述三組明文、密文對為例,

\displaystyle  P=\begin{bmatrix}  15&19&14\\  14&14&15\\  19&15&19  \end{bmatrix},~~C=\left[\!\!\begin{array}{rcr}  3&27&8\\  16&0&18\\  24&13&17  \end{array}\!\!\right]

密碼分析者知道 3\times 3 階密鑰 A 滿足 AP=C。因為 \det P=192\equiv 18\pmod{29}P 包含三個線性獨立的行向量,故為可逆矩陣,所以 A=CP^{-1}。使用上述逆矩陣算法,

\displaystyle  P^{-1}=\left[\!\!\begin{array}{crr}  20&19&13\\  22&22&0\\  13&14&13  \end{array}\!\!\right]

再代入計算可得

\displaystyle  A=CP^{-1}=\left[\!\!\begin{array}{ccc}  758& 763& 143\\  554& 556& 442\\  987& 980& 533\\  \end{array}\!\!\right]\equiv\left[\!\!\begin{array}{crr}  4& 9& 27\\  3& 5& 7\\  1& 23& 11\\  \end{array}\!\!\right]\pmod{29}

密碼分析者破解出的密鑰與真實密鑰對於模29同餘,即

\displaystyle  \left[\!\!\begin{array}{crr}  4&9&-2\\  3&5&7\\  1&-6&11  \end{array}\!\!\right]\equiv\left[\!\!\begin{array}{crr}  4& 9& 27\\  3& 5& 7\\  1& 23& 11\\  \end{array}\!\!\right]\pmod{29}

 
雖然矩陣乘法本身不能衍生安全的希爾密碼,但若與其他非線性運算結合,仍不失為一個有效的步驟。因為矩陣乘法具有擴散效果,只要選擇適當的矩陣,微小的差異可被乘法運算放大。譬如,美國聯邦政府採用的進階加密標準 (Advanced Encryption Standard, AES) 的 MixColumns 步驟便使用了矩陣乘法。目前,進階加密標準是對稱金鑰加密中最流行的演算法之一[2]

 
參考來源:
[1] 維基百科:替換式密碼
[2] 維基百科:進階加密標準

Advertisements
本篇發表於 線性代數專欄, 應用之道 並標籤為 , , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s