動機
每次只改變一個字母的代換,很容易用代數來描述。用矩陣混合若干個字母似乎能隱藏更多結構,而讓位移量隨位置變化似乎能擊敗單一的代換表。這些都是值得研究的有用的數學改進,但單靠任何一種運算都不能確立保密性。解釋解密的同一套代數,也揭示了觀察者能夠學到甚麼。
我們把矩陣密碼和週期位移密碼當作有限的代數系統來考察。我們的問題是精確的:解密何時是唯一確定的?需要多少已知明文才能確定一個矩陣?即使密鑰未知,加密之後仍保留哪些關係?回答這些問題不需要對典型英文文本作任何假設,也不依賴統計攻擊的效果。
字母用剩餘類表示,A 為零,B 為一,如此類推。例子使用模二十六,但證明對一般的剩餘類環都成立。這些是經典的教學構造,並不是對當代訊息的保護方案。它們在這裏的價值,在於把可逆性、密鑰重用與可區分的訊息分佈聯繫起來。
定義
定義 5.2.1
(Hill 密碼)
設 ,。長度為 的區塊上的 Hill 密碼使用矩陣 和列明文區塊 ,密文為 。一個合法的解密密鑰必須使該映射在所有區塊上都是雙射。所有例子均使用列向量約定;採用行向量約定會改變矩陣作用在哪一側。
定義 5.2.2
(週期加法密碼)
週期為 的週期加法密碼使用密鑰 。對長度為 的明文,其輸出為
當字母表大小為二十六時,這就是 Vigenère 密碼通常的代數模型。在作相應的恢復論斷時,我們假定區塊邊界與密鑰對齊方式是已知的。若訊息不能填滿一個區塊,則必須另行約定填充規則;區塊映射的可逆性並沒有規定填充。
概念視角結構
週期密碼是交錯排列的幾個移位密碼
按相位劃分位置:對 ,第 組包含 。在第 組上,密碼只加上同一個常數 ,所以每組都是帶自身密鑰的單表移位。因此,週期為 的密鑰恰好是作用於交錯子序列上的 個獨立移位密碼。固定替換的每個不變量,例如等號模式和重新標記後的符號計數,都在每組內保留;同相位差恆等式正是移位情形下的這一事實。
定義 5.2.3
(完美保密性)
作為比較,完美保密性是指:對於任意與密鑰獨立的明文分佈,觀察到密文後明文的分佈保持不變。等價地,所有允許的明文誘導出相同的密文分佈。這個強的有限概念不同於計算上無法區分訊息,並且允許用特別選取的明文給出精確的反例。
定理/命題
定理 5.2.4
(剩餘類環上正確的可逆性檢驗)
Hill 映射對每個區塊都能唯一解密,當且僅當 是 中的單位,等價地 。對於 ,可逆矩陣密鑰的個數為
在合數模下,非零的行列式不一定是單位。
定理 5.2.5
(已知區塊與週期差分會揭示結構)
若 個已知明文區塊構成行列式為單位的矩陣 ,則它們的密文矩陣 唯一確定 Hill 密鑰為 。在週期加法密碼中,模週期同餘的位置 滿足 。特別地,對長度超過週期的所有訊息,重複使用的週期密鑰不能給出完美保密性。
定理 5.2.6
(完美保密性的有限密鑰空間障礙)
對有限的訊息集與密鑰集,若加密是確定性的、解密是正確且確定性的,並且具有完美保密性,則當所有訊息都允許時,要求具有正概率的密鑰至少與訊息一樣多。因此,當 時,僅有 種可能取值的週期為 的密鑰,無論其密鑰分佈如何,都不能完美地隱藏 中每一條長度為 的訊息。
證明思路或證明
行列式必須是單位,而不僅僅是非零
證明
(單位、伴隨矩陣與中國剩餘定理計數)
若 有矩陣逆 ,則在交換環中 ,所以 是單位。反之,伴隨矩陣恆等式 在乘以行列式的逆之後給出逆矩陣。由 Bézout 恆等式, 中的單位恰是與 互質的剩餘類。
為了把矩陣可逆性與所述的可解密性質聯繫起來:雙射 對每個標準基列向量都有原像。把這些原像放入矩陣 中,得到 。由行列式可知 是單位,再由伴隨矩陣得到雙側逆。這樣就避免了事先假設任意逆函數都可由矩陣表示。反之,矩陣逆顯然給出唯一解密。
中國剩餘定理把模二十六的每個元素對應到它模二與模十三的一對剩餘類。這是環同構,所以它把矩陣乘積與逆矩陣變為逐分量的乘積與逆。矩陣可逆當且僅當兩個域上的矩陣都可逆。在有 個元素的域上,可逆二階矩陣的第一列可以是任一非零向量,共 種選擇。它的生成空間有 個元素;第二列在其外選取,有 種選擇。由此得到乘積公式,代入二與十三即得所示的計數。若數遍全部 個矩陣,則會包含許多不能解密的密鑰。
只有當數據構成一組基時,才能由已知明文求解
證明
(右乘數據矩陣的逆)
把已知區塊寫成列。加密給出 ,所以若 可逆,右乘 得 。這同時證明了恢復性與唯一性。僅有觀察到的區塊的個數是不夠的;它們必須在實際的剩餘類環中滿足可逆條件。
反例模式
數據的行列式非零並不足夠
例如,在 上 不可逆。兩個可逆密鑰 與 在這些觀察上給出相同的密文矩陣 。因此,即使行列式非零(此處為四),兩個觀察到的區塊也不足以確定一個二階密鑰。在這個環上,普通的域上線性無關性並不是正確的檢驗。修正正是定理的假設:數據矩陣 的行列式必須是單位,在這裏即與 互質。
即使沒有任何已知明文,也存在洩露。可逆線性映射只把零映到零。因此無論在可逆密鑰上使用甚麼分佈,零區塊與任何非零區塊的密文分佈的支撐都不相交。純粹的 Hill 密碼無法完美地隱藏這一對。更一般地,設 為 中由一個區塊的各座標生成的理想。由於 的每個座標都是 各座標的線性組合,所以 。再應用逆映射即得相等。因此,所生成的座標理想是與密鑰無關的不變量,所揭示的不僅是該區塊是否為零。
重複使週期密鑰相互抵消
證明
(相同相位消去密鑰)
在密鑰相位相同的位置,把兩個密文等式相減會消去密鑰符號,給出差分恆等式。為看出精確的保密性失敗,設 ,並比較兩個明文:全零字與僅在位置 處為一的字。對前者, 必然成立;對後者,該差必然為一。無論週期密鑰取何種分佈,觀察者都能完美地區分它們。不需要任何語言頻率的估計。
當兩條訊息用相同對齊的加法密鑰加密時,同樣的重用現象也會發生:把密文相減就揭示了明文之間的差。此時已知的某條訊息會暴露它所用到的每個對應密鑰符號。然而,如果密鑰對每個訊息位置有一個獨立均勻的符號且只使用一次,則每個明文都誘導出所有密文字上的均勻分佈。對任何給定的明文和密文,恰好存在一個把它們聯繫起來的加法密鑰。因此在此模型中,一次性密碼本具有完美保密性;重複一個較短的密鑰會使這一性質消失。
兩種攻擊遵循同一模式:觀察者都不需要先恢復整個密鑰。只要兩條允許的訊息迫使某個可觀察不變量取不同的值,保密性斷言就失敗了,即使窮舉密鑰搜尋並不方便。
為甚麼密鑰空間的下界不可避免
證明
(從訊息到密鑰支撐集的單射)
選取一個給每條允許的訊息賦予正概率的明文分佈。某個密文 以正概率出現。完美保密性要求在觀察到它之後每條訊息仍然是可能的。因此,對每條訊息 ,必須存在一個具有正概率、把 加密為 的密鑰。不同的訊息需要不同的密鑰:由於正確性,一個固定的密鑰和密文只能解密為一條訊息。為每條訊息指定一個這樣的密鑰,就得到從訊息集到密鑰支撐集的單射。因此密鑰支撐集不能更小。
證明透視
每個假設在計數論證中的位置
全支撐的先驗分佈是關鍵一步。它由證明者選取,這是容許的,因為完美保密性必須對每個明文分佈成立;有了它,完美保密性就表示:觀察到任何正概率的密文後,沒有訊息會變得不可能。固定一個這樣的密文 ,安全性定義便變成存在性陳述:每條訊息 都有正概率的密鑰使 。
正確的確定性解密只用來使選取 成為單射,因為固定密鑰只把 解密為一條訊息。證明以比較基數收結。「所有訊息都允許」這個假設是必要的:若只允許 與 兩條訊息,則只在第一個位置加上一個均勻符號,就能用 個密鑰完美隱藏它們,不論長度為何。
這個計數條件是必要的,而不是充分的。一大族線性密鑰仍然保持零不變,如前所示。反之,較短密鑰的方案可以以計算安全性而非完美保密性為目標;這個計數定理並不反駁一個精確陳述的計算性假設。明確保持安全性概念,能防止把密鑰數量的觀察誤當作關於所有加密的普遍論斷。
例題詳解
例題 5.2.7
(加密並求逆一個雙字母區塊)
取模二十六下的 。它的行列式是九,九的逆元是三。因此
字母 HI 構成列向量 。相乘得 ,即字母 TC。再應用逆矩陣得 ,恢復出 HI。如果取轉置而不改變列向量約定,就會得到一個不同的密碼,所以編碼與解密的計算都必須使用所聲明的方向。
例題 5.2.8
(由一對合適的區塊恢復密鑰)
設已知明文矩陣為 。對前面的密鑰,密文矩陣為 。由於模二十六下 ,計算 即恢復出 。該攻擊使用兩個完整對齊的區塊,不需要猜測字母頻率。對於前面所述行列式非單位的觀察,其證明就會失效。
例題 5.2.9
(一個三符號的週期位移)
使用密鑰剩餘類 與明文 HELLOW,它表示為 。重複密鑰後得到密文 ,即 KFPOPA。位置零與位置三相位相同,它們的密文之差為 ,恰等於明文之差 。其餘相位相同的差模二十六分別為十與十一。若前三個明文符號已知,把它們從前三個密文符號中減去即恢復整個週期,並能以相同的對齊方式解密所有後續位置。
常見錯誤
常見錯誤
(可逆的密碼不一定能隱藏訊息)
可逆性是正確性性質。單位矩陣是可逆的,卻暴露其全部明文。即使在所有可逆 Hill 密鑰中均勻選取,零和座標理想仍被保持。可逆性、大的密鑰空間與完美保密性是三個獨立的斷言,需要分別論證。
例如,座標生成偶數剩餘類理想的區塊,在可逆矩陣作用下不可能加密為生成整個環的區塊。量 與代表元的選取無關地描述了這個理想。選擇另一個可逆矩陣無法消除這種洩露。
常見錯誤
(重複使用平移區塊會重新引入關係)
加上一個獨立均勻的平移區塊 以得到 ,會使一個區塊在任意固定的 條件下是均勻的,因為平移是雙射。這一觀察針對的是新取樣的全長度遮罩。在多個區塊上重複使用同一個 ,會使它們的密文差等於 乘以明文差,重新引入關係。僅僅把該密碼稱為仿射並沒有規定安全的密鑰使用實驗。
總結
矩陣解密要求在剩餘類環中行列式為單位。合適的已知明文會暴露矩陣,而座標理想即使沒有恢復密鑰也已經揭示了結構。重複使用的加法密鑰會暴露相位相同位置之間的差。精確的計數解釋了為甚麼較短的有限密鑰不能完美地隱藏每條更長的訊息,而一次性密碼本則展示了完整的獨立遮罩如何滿足這一強要求。
練習
快速檢查
(為甚麼 在模二十六下不能唯一解密?給出兩個發生衝突的明文區塊。)
在核中找一個非零區塊。
解答
它的行列式二不是單位。不同的區塊 與 都加密為零,因為模二十六下 。在有零因子的環中,非零的行列式並不能阻止出現非平凡的核。
快速檢查
(計算 上可逆二階矩陣的個數。)
先數第一列,再數不在其生成空間中的第二列。
解答 · 答案
非零的第一列有八種選法。它的生成空間有三個向量,所以第二列有六種選擇。個數為 。
快速檢查
(週期為二的密鑰加密四符號訊息 與 。在不知道密鑰的情況下,給出一個能區分這兩個密文分佈的觀察量。)
用兩個密鑰相位相同的位置。
解答 · 答案
觀察 。這兩個位置的密鑰相位相同。對第一條訊息該差總為零,對第二條訊息總為一,所以在任何密鑰分佈下它們的密文支撐都不相交。
快速檢查
(為甚麼有限密鑰空間的下界並不能證明一個碰巧密鑰多於訊息的密碼具有完美保密性?)
問一個基數條件能否說明密文分佈。
解答
該定理只給出一個必要的基數條件,對於不同訊息是否誘導出相同的密文分佈則隻字未提。Hill 族給出了充分性的反例:無論它有多少個密鑰,每個線性密鑰都把零送到零,並把每條非零訊息送到非零密文。