動機
替換密碼把每個字母換成另一個字母。表面上,原來的單詞已經消失,但替換過程可能保留足夠多的結構,使觀察者能夠重建原文。研究時應依次提出幾個不同的問題:加密規則是否存在逆映射?不知道逆映射的人能推斷甚麼?哪些觀察足以確定密鑰?這些問題不能混為一談。證明接收者可以正確解密,並不等於證明旁觀者無法了解明文。
本節用模運算描述有限字母表。這個模型既能精確推導仿射替換的解密規則,也能嚴格證明某些資訊必然洩漏。26 個字母與全部數值密鑰僅用於說明計算。
定義
固定整數 ,用剩餘類集合 表示字母表。對於英文大寫字母,取 ,並約定 。長度為 的訊息是剩餘類組成的向量 。大小寫、空格與標點都需要明確的編碼規則。本節例子去掉空格並使用大寫字母;這個約定只是簡化計算。如果通訊的其他部分暴露了單詞邊界,去掉空格並不自動隱藏那些邊界。
定義 5.1.1
(單表替換密碼與仿射密碼)
單表替換密碼在整條訊息中使用同一個字母表置換 ,把各個 變為 。仿射密碼進一步限制替換形式為
其中 是模 的剩餘類,而且 必須可逆。有序對 是密鑰。若存在整數 使 ,就稱 是單位。記號 表示這個乘法逆元,而不是實數意義的倒數 。解密必須能恢復字母表中的每一個符號,不能只對某一條剛好選中的訊息有效。
定理/命題
定理 5.1.2
(仿射解密的判別條件)
設 。映射 是 上的置換,當且僅當 。滿足這個條件時,其逆映射是模 意義下的 。
證明
(以貝祖(Bézout)等式得逆映射,以碰撞證逆命題)
若 ,由貝祖(Bézout)等式可取整數 使 。取模後得到 ,於是
反過來,把 代入加密公式也會得到 ,所以這確實是雙邊逆映射。現在設 。剩餘類 與 不同,但
因此這兩個輸入都加密為 。存在這種碰撞的函數不是單射,不可能在整個字母表上具有解密逆函數。兩個方向均已證明。
加法參數 沒有限制,因為加上 總可以透過加上 撤銷;真正需要檢查的是乘法。當 時,允許的乘數為
所以 有 12 種選擇, 有 26 種選擇,共有 312 個仿射密鑰。不同的有序對確實給出不同的函數:函數在 處的值確定 ,在 處與在 處的函數值之差確定 。一般單表替換可以使用 個置換,但較大的密鑰空間並不會消除所有結構性洩漏。
例題
例題 5.1.3
(加密並解密 MATH)
取 。歐幾里得(Euclid)算法給出 ,故 ,從而 。明文對應的剩餘類 加密為
密文是 QIZR。解密 Q 時,計算 ,還原為 M。其餘三個符號分別給出 、、。逆映射直接恢復整條訊息,不需要猜測其含義。
例題 5.1.4
(乘數非零仍然可能失敗)
規則 不能在全部 26 個字母上唯一解密。A 對應 ,N 對應 ,兩者都會加密為對應 的 D。若把 兩邊除以 2,卻仍保留模數 26,就會錯誤地消除這種歧義。正確的約化結果是 ,它在模 26 下有兩個可能值。
例題 5.1.5
(由兩個已知字母恢復密鑰)
觀察者知道同一個仿射密鑰把 E 變成 C,把 T 變成 Z。用剩餘類表示,就是 與 。相減得 。由於 ,兩邊乘以 7 得 ,再得 。把結果代回兩條原始同餘式可以核對全部數據;只找到一個看來合理的 ,還不算完成檢查。
已知明文與一次同餘方程
上例的關鍵不只是「有兩個觀察」,而是兩個已知明文剩餘類之差可逆。一般地,若已知 與 ,則
若 是單位,第一式給出唯一的候選 ;隨後仍要檢查 是否為單位,以及它是否滿足所有觀察。若這個差不是單位,就不能隨意除以它。此時應使用一般的一次同餘方程定理。
定理 5.1.6
(一次同餘方程的解數)
設 為整數,,且 。同餘方程 有解,當且僅當 。有解時,它在模 下恰有 個不同解。只有同時滿足 的解,才能作為仿射密碼的乘數。
證明
(係數與模數一起約簡)
若 被 整除,則 與 的每個公因數也整除 ,這證明了必要性。反過來,設 ,寫成 、、。原方程等價於 。因為 ,它確定模 的唯一一個類 。如果 ,所有整數都屬於唯一的剩餘類,無需進行逆元計算。該類在模 下的代表可以寫成
這些值模 兩兩不同,而且窮盡所有解。仿射密碼要求乘數為單位,是另外的篩選條件,不能與同餘方程本身的解數混淆。
證明透視
如何安全地約簡同餘式
必要性只用到整除: 與 的公因數整除 及 ,從而整除 。充分性靠一個步驟:把 、 與模數 同時除以 。若只除 與 而保留模數 ,就會犯乘數 例子中的錯誤: 會變成錯誤的 。
約簡後, 使 模 可逆,所以模 恰有一個類 。個數 來自提升:模 的一個類分裂成模 的 個類。整個證明沒有用到仿射乘數的可逆性,所以它必須事後作為另一個篩選條件加上。
定理數的是同餘方程的解,而不是密鑰;下面的情況顯示兩個數目可以相差多遠。
反例模式
兩個已知字母未必確定密鑰
例如,若 A 加密為 D,N 加密為 Q,則 ,並且 。這條方程只說明 是奇數。在它的 13 個解中, 不是單位,其餘 12 個都是合法乘數。因此,這兩個觀察仍留下 12 個仿射密鑰。「任意兩個已知字母一定確定仿射密鑰」是錯誤命題。另一方面,不可逆的差也未必留下多個合法密鑰:方程 有解 ,其中只有 1 是單位。修正正是定理的假設:兩個觀察唯一確定乘數,當且僅當 模 是單位;否則必須用 篩選 個解,並逐一核對每個觀察。
精確資訊洩漏與頻率分析
用固定單表替換得到的密文保留完全相同的重複位置模式:
正向成立是因為函數對相同輸入給出相同輸出;反向成立來自置換的單射性。兩個位置的明文字母相同,當且僅當對應的密文字母相同。因此,每個字母出現的次數也只是被重新標記。若明文符號 出現 次,則密文符號 也出現 次。
這些結論是確定性的。頻率分析則加入了統計假設:用某種語言或文體寫成的較長訊息,往往具有不均勻的符號頻率。分析者可以把密文的實際計數與某個語言模型比較,並嘗試可能的替換。高頻密文符號可能對應高頻明文符號,但這只是候選推斷,不是嚴格證明。短樣本、特殊詞彙、不同語言、刻意限制用字的文章,以及是否保留標點,都可能改變證據的意義。猜測得到的替換關係,應當用整條訊息及其他已知資訊繼續檢驗。
例題 5.1.7
(BANANA 的計數只是換了標籤)
在 時,B N、A I、N V,所以 BANANA 變成 NIVIVI。明文 A、N、B 的次數分別為 ,密文 I、V、N 的次數也是 。位置模式仍然是一個符號、第二個符號、第三個符號、第二個、第三個、第二個。長樣本中猜測最高頻符號可能有幫助,但這個六字母例子本身並不能確立某種語言頻率模型。
一個計數統計量可以進一步區分這兩類論證。對於長度 的字串,定義重合指數
分子計算字元相同的有序不同位置對;分母計算全部有序不同位置對。因此,從字串中均勻抽取兩個不同位置時, 就是所見字元相同的概率。單表替換只改變計數的標籤,所以嚴格保持 。BANANA 的重合指數為 。如果字元獨立地按概率 抽取,則期望的匹配概率是 。這裏的獨立抽樣模型是額外假設,不能當作任意文章都滿足的定理。
對於模 26 的仿射密碼,也可以枚舉全部 312 個密鑰,查看各自給出的候選明文。枚舉是有限搜尋;根據語言是否自然對候選排序,則屬於另一個推斷步驟。如果觀察者能夠請求同一密鑰下選定符號的密文,只需請求 與 ,就能直接得到 與 ,從而恢復整個仿射密鑰。因此,聲稱密碼能夠抵禦觀察者之前,必須先說明觀察者被允許獲得哪些資訊。
一個可嚴格證明的安全邊界
定理 5.1.8
(固定替換必然洩漏一種兩字母區別)
設字母表包含不同符號 。無論如何隨機選擇置換密鑰,只要兩個位置使用相同置換,觀察者就能以確定方式區分訊息 與 :前者的兩個密文符號相同,後者的兩個密文符號不同。
證明
(每個置換都保持相等關係)
每個置換同時保持符號的相等與不等,所以兩種訊息可能產生的密文集合互不相交。觀察者只要檢查兩個密文符號是否相等,就能判斷是哪一種訊息,完全不依賴密鑰的抽樣分佈。即使每條完整訊息都重新抽取一個置換,論證仍然成立;若在不同位置使用不同變換,就已經換成另一種系統。
概念視角結構
均勻隨機替換洩漏的恰好是模式
若長度為 的訊息 對所有位置 都滿足 ,稱它們模式等價。此時規則 在用到的符號上定義良好且為單射,因此可延拓為一個置換 ,使逐座標有 。若 在全部 個置換上均勻分佈,則 亦然;所以 與 同分佈。上面的定理又以確定性區分不同的模式,兩者合起來說明:這種系統洩漏的恰好是等號模式。
這證明固定替換無法隱藏一個明確指定的訊息區別,既不依賴英文頻率,也不依賴密鑰空間小。它並沒有斷言每一種確定公式在任何密鑰實驗中都會失敗。密鑰如何抽樣是關鍵。考慮 上的一次一密:選擇與訊息獨立的均勻密鑰向量 ,並令 。對於任意固定的輸入向量 和密文向量 ,恰好一個密鑰向量產生 ,所以按 的隨機選擇計算,概率為
只要密鑰向量獨立於訊息,同樣長度的每條訊息都會得到相同的密文分佈。這就是該有限模型中的完全保密性。它要求密鑰與明文等長、均勻隨機、獨立生成、保持秘密,而且只使用一次;這些都是實質性假設。
若訊息 重用同一個密鑰向量,則逐座標有 。即使觀察者最初不知道任何一條明文,也會得到兩條明文之間的關係。一條明文後來一旦已知,另一條即可由減法恢復。此外,給密文加上選定向量 ,會使解密明文也增加 。所以保密本身不意味著訊息真實且未被竄改。這些代數事實說明,正確性、機密性、密鑰管理和訊息完整性必須分別討論。本節的仿射例子與抽象一次一密模型,都沒有規定一個可直接部署的通訊協定。
常見錯誤
常見錯誤
(乘數非零不等於可逆)
在域中,例如質數模數的剩餘類中,「乘數非零」確實足以保證可逆;模 26 時卻不成立:乘數 2 把 A 和 N 送到同一個字母。正確的判據是 。
常見錯誤
(模逆元不是倒數)
5 模 26 的逆元是剩餘類 21,因為 。它不是有理數 ;後者根本不是剩餘類。
常見錯誤
(頻率保持不會說出明文字母)
頻率保持並不表示明文最高頻符號一定是 E。它表示實際計數無論是甚麼,替換都會保留這些計數,只改變標籤。一條全由 A 構成的訊息,加密後只顯示一個不斷重複的符號;僅憑這個數學不變量,不能判定該符號原來就是 A。最後,可能密鑰的數量只是搜尋空間的大小,並不概括觀察者能夠利用的全部資訊。結構不變量可能在完全沒有識別密鑰的情況下,就已經回答觀察者關心的問題。
練習
快速檢查
(在模 26 下,求 的解密規則,並加密 CODE。)
解答
因為 ,解密規則是 。CODE 的剩餘類為 ,分別加密為 ,所以密文是 RXYF。將這四個密文值代入解密式,會恢復原來的四個剩餘類。
快速檢查
(字母表大小為 12 時,判斷 與 能否唯一解密。能夠解密時給出逆映射;不能時給出具體碰撞。)
解答
第一式的乘數在模 12 下的逆元是 5,故逆映射為 。第二式的乘數與 12 的最大公因數為 4;因為 ,輸入 和 都加密為 1。因此第二式不能在整個字母表上可逆。
快速檢查
(同一個模 26 仿射密鑰把 A 加密為 F,把 B 加密為 M。求密鑰,並解密 M。)
解答 · 答案
方程為 與 ,故 。由於 ,M 對應的 12 解密為 ,即 B。這與已知觀察吻合。
快速檢查
(解 ,再篩選出能夠用於模 15 仿射密碼的乘數。)
解答
此時 整除 9。把係數、右邊與模數同時除以 3,得到 ,即 。模 15 的解為 。合法乘數是與 15 互質的 4 與 14;9 不滿足要求。
快速檢查
(某段長度為 8 的密文,各符號的非零計數為 。求重合指數。僅憑這個數能否識別原來的明文字母?)
解答 · 答案
重合指數是 。任意重新標記字母都不改變這個數,因此它不能確定具體字母。在明確的統計模型中,它仍可能提供部分證據。
快速檢查
(一個模 26 密鑰墊被重複使用。同一位置的兩條密文剩餘類分別為 8 與 15。若第一條明文在該位置為 2,求第二條明文和密鑰墊在該位置的剩餘類。)
解答 · 答案
密鑰墊剩餘類是 ,第二條明文是 ,對應 J。也可以直接算 。所有等式均在模 26 下解釋。
快速檢查
(證明兩個合法模 仿射密碼的複合仍是合法仿射密碼。進行兩次仿射加密是否擴大了可能的加密函數族?)
解答
先應用 ,再應用 ,結果為 。由於 都是單位, 的逆元為 ,所以複合仍為仿射密碼。任何仿射密碼也都可以與恆等密鑰 複合得到,所以重複仿射加密並不擴大函數族。這個結論討論的是最終的加密函數,而不是能描述同一個函數的不同密鑰對組合的數量。