希爾密碼，未知字母值
我已經在這個問題上苦苦掙扎了一段時間：眾所周知，希爾密碼因其線性而容易受到已知明文攻擊。給定一個關鍵矩陣 $ K $ 大小的 $ n\times n $ , 只需 $ n^2 $ 明文/密文對。
在 Internet 上找到的所有範例都假定一個字母表，其中 $ A=0, B=1 \dots Z=25 $ ，但是我們如何在沒有任何關於字母排列或密鑰矩陣的線索的情況下使用已知明文攻擊來破解希爾密碼？
我已經嘗試了幾件事，例如將整組方程線性化在一起，但是它需要幾個除法 $ \bf{Z}_{26} $ 這是不可能的（即除以偶數或 13）
好吧，我假設我們將在字母和整數之間使用相同的映射來將明文轉換為整數（被矩陣相乘），並將整數（在矩陣相乘之後）轉換回密文。而且，我們不知道映射，關鍵矩陣 $ K $ ，以及可能的值 $ n $ .
如果是這樣，顯而易見的起點是嘗試解決這個問題 $ \bmod \ 2 $ . 關鍵矩陣 $ K $ 由以 26 為模的整數組成；因為 2 是 26 的除數，所以可以將其視為由以 2 為模的整數組成。映射將 13 個字元分配給偶數，將 13 個字元分配給奇數；有 $ \binom{26}{13} = 10,400,600 $ 可能性。所以，我們（實際上是一台電腦，這對於手工計算來說有點多）可以做的是掃描所有 1000 萬種可能性（以及通過 $ n $ ，如果我們不知道的話），並檢查到偶數/奇數字元的映射是否與已知的明文/密文一致。
其結果將是映射的 lsbits（這是 13 個偶數字元，哪些是奇數字元），元素的 lsbits $ K $ ，以及 $ n $ .
如果我們有足夠的明文，下一個明顯的攻擊就是恢復偶數字元的映射。有 $ 13! = 6,227,020,800 $ 這種可能的映射；如果我們能找到（說） $ n+1 $ 僅由偶數字元組成的塊（明文和密文塊都將由偶數字元組成；我們知道這一點是因為映射是一致的 $ \bmod \ 2 $ )，那麼我們就可以掃過13了！可能的映射，並查看每個這樣的映射是否與所有映射一致 $ n+1 $ 明文/密文對。如果 $ n=5 $ ，那麼如果我們有至少 1200 個已知明文字元，我們期望能夠找到 6 個這樣的塊；不無道理。
一旦我們擁有了它，這給了我們價值 $ K $ ，以及偶數字元的映射。這樣，推斷奇數字元的映射就很簡單了。
線性化應該可以正常工作。您必須進行細微調整以處理我們正在使用模 26 的事實，但以下兩個簡單調整中的任何一個都應該可以正常工作：
- 你可以使用廣義高斯消除，廣義上的工作 $ \mathbb{Z}/26\mathbb{Z} $ （標準高斯消元假設我們在一個場上工作，但這裡我們在一個環上工作）。
- 或者，您可以使用中國剩餘定理。線性化給你一些方程模 $ 26 $ . 首先，以 2 為模減少它們，所以現在你得到了方程 $ \mathbb{Z}/2\mathbb{Z} $ ; 這是一個場，因此您可以使用標準高斯消元法對它們進行模 2 求解。其次，將方程模 13 化簡，得到一些方程 $ \mathbb{Z}/13\mathbb{Z} $ 也可以使用高斯消元法解決。現在，對於每個未知數，您知道它的模 2 和模 13 的值；然後中國剩餘定理立即告訴你它的值模 26。
第二種方法可能會更容易。
讓我提醒大家線性化是什麼意思：這意味著我們引入了額外的未知數，使方程變得完全線性。我應該詳細說明在這種情況下如何運作。
例如，讓我們假設 $ n=6 $ ，所以所有消息都是 6 個字母長。我們會有未知數 $ A_{i,j},B_{i,j},\dots,Z_{i,j} $ 和 $ A’,B’,\dots,Z’ $ , 使用如下。假設我們有一個已知的明文 ATTACK 和對應的密文 QXUZAD。這將牽涉到未知數 $ A_{1,j} $ , $ T_{2,j} $ , $ T_{3,j} $ , $ A_{4,j} $ , $ C_{5,j} $ , $ K_{6,j} $ 在哪裡 $ A_{1,j} = K_{1,j} \pi(A) $ , $ T_{2,j} = K_{2,j} \pi(T) $ 等，其中 $ \pi $ 是未知的明文排列和 $ K $ 是未知矩陣（鍵）。請注意，密文的第一個字母將具有值 $ (\pi(A), \pi(T), \dots, \pi(K))^T \cdot K $ ，就我們的新未知數而言，這正是 $ A_{1,1} + T_{2,1} + T_{3,1} + \dots + K_{6,1} $ . 我們將在一分鐘內使用它。由於密文有字母Q、X、U、Z、A、D，它將暗示未知數 $ Q’, X’, U’, Z’, A’, D’ $ ，其中未知的值 $ Q’ $ 是密文字母Q對應的數字（在未知密文置換映射之後）。
這樣，已知的明文/密文對 ATTACK/QXUZAD 產生以下線性方程：
$$ A_{1,1} + T_{2,1} + T_{3,1} + \dots + K_{6,1} = Q’. $$ $$ A_{1,2} + T_{2,2} + T_{3,2} + \dots + K_{6,2} = X’. $$ $$ \vdots $$ $$ A_{1,6} + T_{2,6} + T_{3,6} + \dots + K_{6,6} = D’. $$ 這些都是未知數的線性方程。每個已知的明文/密文對我們得到 6 個方程。總的來說，我們將擁有 $ 26 \times 6^2 + 26 = 962 $ 未知數，每個已知文本有 6 個方程，因此給定 161 個已知明文/密文對，我們應該有足夠的資訊來唯一地恢復所有未知數的值——然後很容易恢復密鑰 $ K $ 以及明文排列和密文排列。那是線性化，在這裡也應該可以正常工作，並在我的答案頂部提到了一些細微的調整。
或者，使用雨披的答案。Poncho 的答案也是一種很好的方法，在實踐中可能更有效，更容易實施，並且需要更少的已知文本 - 所以他的答案在實踐中可能更優越。我只是想分享一些數學理論，以防你感興趣。