確定給定密文和明文的密鑰?
給定兩組明文及其對應的密文,如何確定密鑰 $ K $ ?
密文如下:
$$ C_1= (P_1 \oplus K_0) + K_1 $$ 和
$$ C_2= (P_2 \oplus K_0) + K_1 $$ $ K = K_0 || K_1 $ (位串)。
在哪裡 $ + $ 表示加法模式 $ 2^n $ .
我們如何找到未知數(例如, $ K_1 $ )?
有一種簡單的蠻力方法。例如,取最低的 $ 8 $ 一切的位,並檢查有效值 $ K_1 $ 和 $ K_2 $ , 反對 $ 2^8 $ . 您將需要大約 $ 2^{16} $ 檢查以降低 $ 8 $ 位 $ K_1 $ 和 $ K_2 $ . 然後繼續值 mod $ 2^{16} $ ,如你所知,較低的 $ 8 $ 位 $ K_1 $ 和 $ K_2 $ , 只有位 $ 8\dots15 $ 這些必須檢查,努力是 $ 2^{16} $ 再次。繼續直到你得到 $ K_1 $ 和 $ K_2 $ 在全。
更好的是,做同樣的事情,而不是 $ 8 $ 位增量做 $ 1 $ 位增量。因此,值 mod 2、mod 的蠻力 $ 4 $ … 反對 $ 2^n $ . 你需要檢查 $ 4 $ 每一步都有不同的值(一位來自 $ K_1 $ 另一個來自 $ K_2 $ ),然後執行此操作 $ n $ 次。因此,尋找成本 $ K_1 $ 和 $ K_2 $ 是 $ 4n $ ,這意味著這不僅僅是關於位數的多項式:它是線性的。
但是,必須注意的是,如果 $ P_1 \equiv P_2 \pmod{2^i} $ ,那麼第一個 $ i $ 位 $ K_1 $ 和 $ K_2 $ 是不確定的,因此需要更多的明文/密文對,直到找到一些對 $ P_1 \not\equiv P_2 \pmod{2} $ ,然後檢索整個密鑰。
更新:可能有(對於給定的 $ n $ ) $ 2 $ 對 $ (K_1,K_2) $ 與適當的兼容 $ (P_1,P_2) $ 對,所以這個方法應該增量檢查 $ 2 $ 成對的鑰匙。
使用此密碼,很容易檢索至少 1 個與 2 對 plaintext,ciphertext 一致的密鑰。(其他密碼在使幾乎不可能恢復與給定明文,密文一致的1個密鑰方面幾乎是不可能的)。
使用此密碼,僅從 2 對已知的明文、密文對中完全檢索密鑰是不可能的。(其他密碼在明文、密文對洩露後在保持密鑰秘密方面更好或更差)。
例如:(為簡單起見,n=2)
c1 = ( 00 xor 01 ) + 10 (mod 2^2) == 11 c2 = ( 10 xor 01 ) + 10 (mod 2^2) == 01 c3 = ( 11 xor 01 ) + 10 (mod 2^2) == 00
所以(明文,密文)對00–>11和10–>01與K0==01,K1==10一致。
然而,
c1 = ( 00 xor 00 ) + 11 (mod 2^2) == 11 c2 = ( 10 xor 00 ) + 11 (mod 2^2) == 01 c3 = ( 11 xor 00 ) + 11 (mod 2^2) == 10
所以(明文,密文)對00–>11和10–>01也符合K0==00,K1==11。
如您所見,第三對 11–>00 或 11–>10 可以區分這兩種可能,因此它們不是等效鍵。
(另一方面,密鑰 K0=00, K1==11 等價於密鑰 K0=10, K1=01——給定任何明文,任一密鑰給出與另一組密鑰相同的密文)。
找到與給定的一組明文、密文對(但不一定是密鑰)一致**的密鑰的快速方法是:
- 從候選鍵 K0 == 0 和 K1 == 全一開始,然後使用以下過程迭代改進它們。
- 從 B0 作為最高有效位位置開始,從 B1 作為下一個最高有效位位置開始。(每次通過循環,將 B0 和 B1 移動 1 位到下一個最重要的位置)。
環形:
從目前候選鍵生成 8 個候選鍵:
- 保持 K0 和 K1 相同。
- 在位位置 B0 翻轉 K1。
- 在位位置 B0 翻轉 K0。
- 在位位置 B0 翻轉 K0 和 K1。
- 至 8. 與上述 1 至 4 相同,不同之處在於在位位置 B1 處翻轉 K1 以阻止進位鏈。
使用 8 個候選密鑰中的每一個來加密所有明文。
如果任何候選者在其密文和實際密文之間沒有差異,則該候選者可能是實際使用的密鑰。完畢!
否則,對於每個候選者,找到與該明文對應的實際密文和該試驗密碼之間不同的最高有效位位置。
如果該位位置與 B0 相同或更重要的位位置,則該候選位置更差——將其丟棄。
應該至少有 1 個更好的候選者——在下一次循環中使用這些候選者。