希爾密碼，無序字母表
我將對我的輸入應用一個簡單的替換密碼，然後使用希爾密碼對結果進行加密。在選擇的明文威脅模型中，如何打破這一點？
換句話說，我將隨機重新排序它們（例如，A=22，B=12，…），而不是字母到數字的標準映射（A=0，B=1，..，Z=25） ，其中字母和數字之間的特定雙射是鍵的一部分。然後，我將使用希爾密碼對結果進行加密。到目前為止，我一直在使用 Hill 密碼 $ 2\times 2 $ 矩陣，但我也對一般的答案感興趣 $ n \times n $ 矩陣。
這可以被打破。攻擊的確切性質將取決於您用於希爾密碼的模數：您是以素數為模工作，還是以 26 為模工作？
以素數為模工作 $ p $
一個簡單的攻擊，不需要花哨的數學。 一種簡單的攻擊是首先請求對 26 條消息 AAAA、BBBB、CCCC、DDDD、…、ZZZZ 進行加密。
注意，經過簡單替換後，消息 AAAA 將變為 4-vector $ (a,a,a,a) $ 對於一些數字 $ a $ ，然後我們將通過乘以向量來加密它 $ (a,a,a,a) $ 矩陣是希爾密碼的密鑰。同樣，消息 BBBB 將變為 $ (b,b,b,b) $ 然後將乘以相同的矩陣。因為每個數字都有一個反模 $ p $ , 有一些常數 $ c $ 這樣 $ b=a \times c \pmod p $ （即， $ c = b a^{-1} \pmod p $ ）。這意味著 $ (b,b,b,b) $ 是一個常數 $ c $ 乘以向量 $ (a,a,a,a) $ . 因此，希爾密碼加密 $ (b,b,b,b) $ 將是一個常數 $ c $ 乘以向量的希爾密碼加密 $ (a,a,a,a) $ .
猜猜 A 映射到什麼數字；說 A 映射到數字 $ a $ . 然後每個其他密文將是 AAAA 密文的常數倍數，並且該常數將揭示相應字母映射到的內容。例如，假設 BBBB 密文中的每個數字是 AAAA 密文中相應數字的 9 倍；那麼我們知道 B 映射到 $ 9a \pmod p $ . （一般來說，可以保證總會有一些常數可以代替 9。）因此，如果我們正確猜測 A 映射到什麼數字，那麼我們將了解每個其他字母映射到什麼數字。
現在應用標準攻擊來擊敗希爾密碼。你會重複這個 $ p $ 次，每次猜測 A 映射到的數字一次。您可以通過確認您是否成功破解希爾密碼並可以將密文解密為看起來有意義的明文來確認猜測是否正確。你的 26 個猜測中的一個將導致正確的明文；這是正確的猜測，現在你完成了。
工作模數 26
一個簡單的攻擊，不需要花哨的數學。 我們可以概括上述攻擊，以便在我們使用模 26 時它也可以工作。現在我們必須處理並非所有數字都具有反模 26 的事實。
和以前一樣，我們首先請求對 26 條消息 AAAA、BBBB、CCCC、DDDD、…、ZZZZ 進行加密。其中之一將加密為全零密文；說是QQQQ的留言。然後你已經知道 Q 映射到 0。
另一個密文將只包含數字 0 和 13；說這是加密到這個的消息DDDD。然後你已經知道 D 映射到 13。
現在你可以應用類似的攻擊，通過猜測 A 映射到哪個數字，然後應用類似的推理。
更華麗的攻擊
通過使用一些更高級的數學，您可以使用更複雜的方法來解決這個問題。引入26個未知數 $ x_A, x_B, \dots,x_Z $ . 這裡 $ x_A $ 表示 A 映射到的數字， $ x_B $ 表示 B 映射到的數字等。我們先驗地不知道這些數字是什麼；這就是為什麼它們是未知數（變數）。
另外，讓 $ n\times n $ 矩陣 $ M $ 表示用於加密的希爾密碼矩陣 $ n $ - 信函。我們可以想到每一個 $ n^2 $ 的條目 $ M $ 作為另一個未知數；IE， $ M_{i,j} $ 是一個未知數，對於每個 $ i,j $ .
現在，每個已知的明文-密文對都為我們提供了一個關於這些未知數的方程組。例如，假設消息 WINK 加密為密文 $ (17,5,20,2) $ . 然後我們學習以下等式：
$$ M (x_W, x_I, x_N, x_K) = (17,5,20,2). $$ 為什麼？因為經過簡單的替換，WINK就變成了列向量 $ (x_W, x_I, x_N, x_K) $ . Hill-cipher-encipherment 然後將其乘以矩陣 $ M $ . 我們知道生成的密文是什麼。
請注意，這是一個系統 $ n $ 方程在 $ n^2+26 $ 未知數。可悲的是，它們不是線性方程。它們是二次方程。儘管如此，有一些已知的技術可用於求解二次方程組。我們可以預期，一旦我們獲得多一點 $ n^2+26 $ 方程在 $ n^2+26 $ ，會有一個獨特的解決方案。當方程的數量足夠大時，有一些技術（例如，重新線性化）可以計算這個唯一的解。例如，如果我們至少有 $ (n^2+26)^2 $ 二次方程 $ n^2+26 $ 未知數，簡單的重新線性化將使用以下方法為我們找到所有這些未知數的值 $ O(n^{12}) $ 時間。觀察後可以收集到這個數量的方程 $ (n^2+26)^2/n $ 已知的明文-密文對。
變得更花哨
嘿，為什麼停在那裡？我們實際上可以純粹用線性代數來解決這個問題。
請注意，我們可以將前面的等式重寫為
$$ (x_W, x_I, x_N, x_K) = M^{-1} (17,5,20,2). $$ 所以現在讓我們選擇一組稍微不同的未知數：未知數是 $ x_A, x_B, \dots,x_Z $ （這部分與之前相同）和條目 $ M^{-1} $ ， IE， $ (M^{-1})_{i,j} $ 對於每個 $ i,j $ （這部分不同）。仍然有 $ n^2+26 $ 未知數。
通過這種變化，每個已知的明文-密文對都為我們提供 $ n $ 線性方程組 $ n^2+26 $ 未知數。現在方程是線性的，所以它們更容易求解。一旦我們獲得了超過 $ n^2+26 $ 方程，應該有唯一解，可以用高斯消元法求出 $ O(n^6) $ 時間。所以，如果我們可以收集一點 $ (n^2+26)/n $ 已知明文-密文對，我們可以使用線性代數破解密碼。酷，嗯？