你能幫我做這個 DES 變體分析嗎？
我正在為一些作為練習得到的 DES 變體而苦苦掙扎（練習取自 Katz-Lindell Ex5.14）。
變體如下：
主密鑰的左半部分用於推導第 1-8 輪的所有子密鑰，而主密鑰的右半部分用於推導第 9-16 輪的所有子密鑰。
我的方向是執行中間相遇攻擊。我們可以觀察到，如果我們猜測主密鑰的 28 位左半部分，我們可以完全計算 $ L_8 $ 和 $ R_8 $ ，另外，如果我們猜測主密鑰的 28 位右半部分，我們可以完全計算 $ L_8 $ 和 $ R_8 $ 也是，但現在是相反的方向。因此，我們廣泛猜測右半部分和左半部分的所有可能鍵，這將花費 $ O(2\cdot2^{28}) $ 時間和空間——因為每次猜測 $ L_k $ 我們儲存的左半鍵 $ L_k:<L_8,R_8> $ 由它計算，我們將所有這些鍵值對儲存在集合中 $ S_L $ ，我們對右半部分的猜測做同樣的事情，並將值儲存在集合中 $ S_R $ . 當然正確 $ L_k $ 和 $ R_k $ 將應用相同的 $ <L_8,R_8> $ .
我的問題
- 多少 $ L_k $ 和 $ R_k $ 我會找到嗎？這要怎麼分析？
- 我需要多少明文和密文對才能找到高機率的密鑰？這要怎麼分析？
密鑰的每一半是 28 位長，所以會有 $ 2^{28} $ 他們每個人的可能選擇。
在攻擊的第一部分，您從已知的明文塊開始，並在前 8 輪中使用每個可能的密鑰左半部分對其進行加密。這給你 $ 2^{28} $ “半加密”的 64 位塊。這小於生日界限，所以很可能這些塊都是不同的，儘管有很小的機會（大約 1 英寸 $ 2^9 $ ) 至少有一次碰撞。儘管如此，出於實際目的，我們可以假設不同的半加密塊的數量接近 $ 2^{28} $ .
在攻擊的第二部分中，您從已知的密文塊開始，使用每個可能的密鑰右半部分對其解密 8 輪，然後在半加密塊列表中查找生成的“半解密”塊在攻擊的第一部分編譯。顯然，如果密文確實是用你描述的修改後的DES算法加密相應明文的結果，那麼至少會有一個匹配對應正確的一對半密鑰。
至於其他半鍵，每個 $ 2^{28} $ 右半邊有一個 $ 2^{28}/2^{64} = 1/2^{36} $ 產生一個半解密塊的機會，恰好與第一部分中計算的半加密塊中的一個匹配。由於這些機率本質上是獨立的，因此“假陽性”匹配的預期總數為 $ 2^{28} \times 1/2^{36} = 1/2^8 $ . 根據罕見事件定律，誤報的實際數量近似Poisson分佈，並且由於預期數量顯著小於 1，因此至少有一個誤報的機率也大約等於預期數量。
因此，機率約為 $ 1 - 1/2^8 $ ，只要對一對已知的明文和密文塊執行這種中間相遇攻擊，就會產生一對對應於正確密鑰的半密鑰。如果您確實不走運並最終得到多個候選密鑰，則在第二個明文/密文塊上測試它們將排除每個錯誤的機率 $ 1 - 1/2^{64} $ .
**編輯：（**從下面的評論中複製和擴展。）上面的所有分析都是在理想的密碼模型中進行的，即它假設你修改的 DES 的每一半都可以被視為一個隨機排列家族（一組 64 位塊）由相應的 28 位半鍵索引。當然，DES 和它的修改版本實際上都不是理想的密碼，但是，就像任何好的分組密碼一樣，它們的設計通常看起來像一個，所以對於像這樣的基本統計分析，理想的密碼近似通常是好的。
如果在實際執行攻擊時，您的（半）DES 變體的統計行為與理想密碼顯著不同，這很可能意味著密碼中存在比單純（！）漏洞更根本的弱點中間相遇攻擊（並不是說它本身不是一個毀滅性的漏洞，因為密鑰長度已經很低了）。特別要注意 DES 與理想密碼的多種已知偏差，例如互補屬性，在這裡並不真正適用，因為我們已經固定了輸入。
至於 $ 1/2^9 $ 碰撞率， $ 2^{28} $ 鑰匙給 $ 2^{28}(2^{28}-1)/2 \approx (2^{28})^2/2 = 2^{55} $ 成對的輸出。這些輸出中的每一個都有大約一個 $ 1/2^{64} $ 碰撞的機會（假設獨立，這當然不是真的，而是一個合理的近似值），給出預期的數量 $ 2^{55}/2^{64} = 1/2^9 $ 碰撞。由於這遠小於 1，根據罕見事件定律，它也近似等於至少發生一次碰撞的機率。
計算碰撞機率的另一種方法是注意，為了在 $ 2^{28} $ 半加密塊，在我們逐個計算它們時，它們中的每一個都必須評估為不同的 64 位值。因此，沒有發生衝突的確切機率（在理想密碼假設下）是
$$ \begin{aligned} & (1 - 0/2^{64})\cdot(1 - 1/2^{64})\cdot(1 - 2/2^{64})\dotsb(1 - (2^{28}-1)/2^{64}) \ \approx& 1 - 0/2^{64} - 1/2^{64} - 2/2^{64} - \dots - (2^{28}-1)/2^{64} \ =& 1 - (0 + 1 + 2 + \dots + (2^{28}-1)) / 2^{64} \ =& 1 - (2^{28}(2^{28}-1) / 2) / 2^{64} \ =& 1 - 1/2^9 + 1/2^{37} \ \approx& 1 - 1/2^9 \end{aligned} $$