使用巧合索引查找給定 vigenere 密碼的密鑰長度
我正在開發一種算法，該算法採用 vigenere 密碼並自動生成密鑰長度。但是，當有多個大的巧合索引時，我無法理解如何檢測密鑰長度。
例如，給定這個密碼：
vptnvffuntshtarptymjwzirappljmhhqvsubwlzzygvtyitarptyiougxiuydtgzhhvvmum shwkzgstfmekvmpkswdgbilvjljmglmjfqwioiivknulvvfemioiemojtywdsajtwmtcgluy sdsumfbieugmvalvxkjduetukatymvkqzhvqvgvptytjwwldyeevquhlulwpkt我的算法為每個可能的密鑰長度生成以下重合索引：
KL IoC 1 0.04494435235614492 --> 4% 2 0.0457833618884447 --> 5% 3 0.04358853643122834 --> 4% 4 0.04749622926093514 --> 5% 5 0.039361207897793266 --> 4% 6 0.04714370596723538 --> 5% 7 0.09099225897255454 --> 9% 8 0.04618589743589745 --> 5% 9 0.04078047556308426 --> 4% 10 0.03611528822055138 --> 7% 11 0.04916033399005535 --> 5% 12 0.05126633986928104 --> 5% 13 0.04468864468864469 --> 4% 14 0.09884877027734174 --> 10% 15 0.033455433455433455 --> 3% 16 0.03962703962703963 --> 4% 17 0.04305498423145482 --> 4% 18 0.04747474747474748 --> 5% 19 0.030303030303030304 --> 3% 20 0.03222222222222222 --> 3% 21 0.082010582010582 --> 8% 22 0.0436868686868687 --> 4% 23 0.03260869565217391 --> 3% 24 0.05158730158730159 --> 5% 25 0.03666666666666666 --> 4% 26 0.04441391941391941 --> 4% 27 0.03791887125220458 --> 4% 28 0.1058673469387755 --> 11%這個密碼的正確密鑰長度確實是“7”，但為什麼不是 14、21 或 28？畢竟他們的 IoC 更高？我可以在我的算法中做些什麼來使它產生 7 作為密鑰長度而不是 14、21 或 28（反之亦然）？
重合指數明顯更高
- 正確的密鑰長度
- 它的所有倍數
即使那不是正確的密鑰，您也會有類似的行為。假設您的索引長度很高 $ 7 $ ，那麼根據算法的性質，您將在 $ 14, 21, 28, \dots $ ，無論這是否是正確的密鑰。
所以最好的策略是，從最低值開始，如果它不起作用，則轉移到下一個異常值（這很可能是你的第一個值加倍）。計算所有異常值的 GCD 之類的事情並沒有錯，但沒有必要，如果您可以迭代並在第一次（或前幾次）嘗試中獲得非常高的成功機會。
還有一件事：這種分析只對短文本是錯誤的（如果密鑰長度與消息一樣長，並且密鑰是均勻隨機選擇的，並且只使用一次，則無法破解），而對於較長的文本，法則大數字（特別是，請參閱中心極限定理的變異數）將導致所有其他值非常非常接近您從字母表上的均勻分佈所期望的值。
正如其他答案所指出的那樣，正確密鑰長度的任何倍數也將產生接近實際密鑰長度的 IoC。因此，確定正確密鑰長度的一種實用啟發式方法是根據差異對密鑰長度進行排序 $ \delta $ 在它們的 IoC 和觀察到的任何較短密鑰長度的最大 IoC 之間。（對於密鑰長度 1，定義 $ \delta = 0 $ .)
例如，對於您的範例消息，您會發現以下候選密鑰長度低於 50，其中 $ \delta > 0 $ :
7: ioc = 269 / 2929 = 0.091840, delta = +0.044166 | ###################### 14: ioc = 142 / 1414 = 0.100424, delta = +0.008584 | #### 28: ioc = 70 / 658 = 0.106383, delta = +0.005959 | ### 4: ioc = 248 / 5202 = 0.047674, delta = +0.001795 | # 2: ioc = 482 / 10506 = 0.045879, delta = +0.000887 |請注意正確的密鑰長度 7 如何具有 $ \delta $ 比下一個最佳候選人 14 高出五倍以上。
（順便說一句，我們計算 IoC 的方式似乎有些不同，因為我的數字與您的數字不完全匹配。我通過檢查距離是候選密鑰長度的正整數倍的每對密文字母來計算它，並取字母匹配的那些對的分數。）
附言。如果你開始考慮更長的候選密鑰長度，你最終會想出一些出乎意料的高 IoC 和 $ \delta $ 值僅僅是由於統計雜訊，因為對於更高的密鑰長度，要測試的字母對更少，因此單個幸運匹配有更多機會扭曲結果。
避免這些虛假結果的一種方法是對較長密鑰長度的估計 IoC 進行折扣，例如通過採用適當選擇的信賴區間的下限而不是匹配對的原始比例。
例如，不是簡單地將 IoC 計算為 $ \hat p = \frac{m}{n} $ ， 在哪裡 $ m $ 是匹配對的數量 $ m $ ，您可以改為計算合適的平滑參數的Wilson 得分區間的下限 $ z $ :
$$ \hat p_{-z} = \frac1{n + z^2} \left[m + \frac12 z^2 - z\sqrt{\frac{m(n-m)}{n} + \frac14 z^2} \right]. $$ 對於您的範例密文，使用 $ z = 3 $ （一個適度保守的選擇），我只得到以下候選密鑰長度 $ \delta > 0 $ :
7: ioc >= 0.076744, delta = +0.035886 | ################## 14: ioc >= 0.078286, delta = +0.001543 | #在哪裡 $ \delta $ 根據調整後的 IoC 值計算的密鑰長度 7 現在比下一個候選長度 14 的值高 20 倍以上。對於 $ z = 4 $ 及更高，7 是唯一的候選密鑰長度 $ \delta > 0 $ .