Lehmer 隨機數生成器密碼 - 尋找微分
我正在尋找我的玩具加密方案中的差異。我找不到任何東西。
讓我們考慮線性同餘生成器：
$ X_{k+1} = a \cdot X_{k} \mod 2^{128} $
這樣 $ a $ 是每個 128 位輸入的某個數字 $ X_{k} $ 從 $ 0 $ 至 $ 2^{128}-1 $ 會給我們不同的輸出 $ X_{k+1} $ 從 $ 0 $ 至 $ 2^{128}-1 $ . 所以我們在這裡得到了雙射（我們可以找到很多這樣的奇怪 $ a $ ）。現在假設我們將選擇這樣的 128 位 $ a_{1},a_{2}, …, a_{10} $ 作為鍵，隨機。我們做 $ 10 $ 像這樣的幾輪加密：
- $ a_{1} \cdot INPUT \mod 2^{128} $
- 撤銷 $ 128 $ 位塊。
- $ a_{2} \cdot (2^{128}-INPUT) \mod 2^{128} $
- $ a_{3} \cdot INPUT \mod 2^{128} $
- 撤銷 $ 128 $ 位塊。
- $ a_{4} \cdot (2^{128}-INPUT) \mod 2^{128} $
等等…
您在這裡看到任何差異嗎？讓我們跳過零塊的加密問題 - 它可以很容易地解決，例如，如果我們將在每一輪之前使用 xoring。當然，它只是鍵控 Lehmer 隨機數生成器，其模數是 2 的冪 - 這種生成器存在低位問題，但在這種情況下我無法使用它來查找差異。
您在這裡看到任何差異嗎？
是的; 考慮一個差值，其中一側是值 $ X $ 另一邊是價值 $ 2^{127}-X $ .
您的密碼由三個操作組成：
- 將目前值乘以奇數值 $ a_i $ 模組 $ 2^{128} $
此操作保留機率為 1 的微分；一側將評估為 $ a_i \cdot X $ 另一方將評估為 $ a_i \cdot (2^{127} - X) = a_i \cdot 2^{127} - a_i \cdot X = 2^{127} - a_i \cdot X $
- 否定目前值（作為第 2-10 輪的一部分完成）
此操作保留機率為 1 的微分；發生這種情況是因為 $ -(2^{127} - X) = 2^{127} - (-X) $
- 反轉目前值中的位
此操作保留機率為 0.5 的微分；即，如果 lsbit $ X $ （相當於， $ 2^{127} - X $ ) 是 1。發生這種情況是因為，當 lsbit 為 1 時，這種關係等價於 $ X \oplus (2^{127}-X) = 2^{127}-2 $ . 當您反轉位時，後一種關係被保留，因此前一種也是如此。
這為您提供了一個具有機率的差異 $ 2^{-10} $ 通過十輪密碼。