重複鍵異或和漢明距離
我讀到打破重複鍵xor你可以做以下事情：嘗試一個keysize $ n $ 併計算第一個之間的漢明距離 $ n $ 加密字元串的位和位 $ n+1 $ 到 $ 2n $ 加密字元串並按密鑰大小標準化。
真正的密鑰大小可能會最小化這一點。為什麼？
它還建議對以這種方式計算的幾個接近最小值的值進行平均。但是為什麼不正確的鍵大小會幫助計算真正的鍵大小呢？
是的，你沒記錯。是的，這是找到密鑰長度的合理方法。
這樣做的原因是，通常情況下，明文不是均勻隨機的。例如，明文可能不是隨機位串，而是一些英文文本，以 ASCII 編碼。如果 $ X,Y $ 表示兩個隨機英文字母，用ASCII編碼，然後是Hamming距離的期望值 $ \text{wt}(X \oplus Y) $ 可能是 2-3 位。相反，如果 $ U,V $ 是兩個隨機的 8 位字節，然後是漢明距離的期望值 $ \text{wt}(U \oplus V) $ 是 4 位，明顯更大。如果您查看多個字元的序列，而不是一次查看單個字母，則差異會變得更大。
這如何適用於您的情況？
- 好吧，如果你猜對了密鑰長度，那麼你的密文包括 $ X\oplus K $ 和 $ Y\oplus K $ （正如 Dilip Sarwate 解釋的那樣），其中 $ X,Y $ 來自明文分佈。現在請注意，這兩者之間的漢明距離與之間的漢明距離相同 $ X $ 和 $ Y $ ，即它是 $ \text{wt}(X \oplus Y) $ . 正如我們之前解釋的，您可以預期這可能是 2-3 位乘以 $ X $ 以字節為單位。
- 相反，如果您猜錯了密鑰長度，那麼您正在查看表單的密文 $ X \oplus K $ 和 $ Y \oplus K’ $ . 兩者之間的漢明距離基本上歸結為之間的漢明距離 $ U $ 和 $ V $ ， 在哪裡 $ U $ 和 $ V $ 是均勻隨機分佈的（因為 $ K,K’ $ 是均勻隨機分佈的），因此是 $ \text{wt}(U \oplus V) $ . 如前所述，您可以預期這應該是大約 4 位乘以 $ X $ 以字節為單位。
因此，如您所見，當您正確猜到密鑰長度時，漢明距離明顯更小。
對於類似的方法，請閱讀巧合指數；您可以期望它在某些情況下更有效，而在其他情況下效果較差。
我最近開始了 Matasano 加密挑戰（又名 Cryptopals），它在本練習中提出了基本相同的原則。具體來說，如果要破解重複密鑰異或密碼，請嘗試找到使任意兩個長度為n的密文塊之間的漢明距離最小的n值，並且**n通常對應於密碼密鑰的大小。
雖然這種策略在這種特殊情況下有效，但我並不清楚為什麼它應該有效。我已經從基本原理進行了推理，並得出了一些結論。注意：我絕不是密碼學專家，這個論點完全有可能是似是而非的，或者我使用了不正確的術語。
**在高層次上……**我相信這在這種情況下基本上是有效的，因為您正在使用 8 位字節對英語密文進行編碼，並且英語語言的熵遠低於所有可能的 8 位組合的熵。即英文只有26個字母，但是8位有256種可能的組合。熵似乎是通過重複鍵異或保留的，因此您實際上是在尋找最小化它的塊大小。
這意味著如果您找到某種方法來實現將字母數字純文字轉換為字母數字密文的重複密鑰異或，則此方法將不起作用。
**更具體地說……**我認為漢明距離是一個度量，它可以通過重複密鑰異或來對基礎文本進行轉換，因為它適用於與密碼密鑰長度匹配的文本塊。對於小塊和密鑰大小，這很容易顯示。例如，假設明文為 001010，密鑰為 010，因此密文為 011000。明文兩半之間的漢明距離為 2，密文兩半之間的漢明距離也為2. 我相當肯定這可以擴展到任何文本和密鑰長度，再次假設您正在獲取與密鑰大小相同的塊之間的距離。
現在考慮我上面所說的，與整個可能字節空間的熵相比，英語的熵相當低。這意味著兩個英文文本塊之間的漢明距離通常小於兩個隨機字節塊之間的漢明距離。
結合這些原則，很明顯，至少在理論上，如果您選擇正確的塊大小/密鑰大小，則密文的漢明距離將被最小化（因為它已經被明文最小化並且在異或變換中仍然存在）。如果您沒有選擇正確的密鑰大小，那麼您將採用基本上隨機字節的漢明距離，這通常會更高。