差分密碼分析可以破解 DES 嗎？

by 伊曼紐爾·烏多菲亞 / 星期五，09 August 2024 / 出版於網路安全, EITC/IS/CCF 經典密碼學基礎, DES 分組密碼密碼系統, 數據加密標準 (DES) - 密鑰調度和解密

差分密碼分析是一種主要適用於分組密碼的密碼分析形式，涉及分析輸入對中的特定差異對輸出差異的影響。這種方法由 Eli Biham 和 Adi Shamir 在 1980 世紀 XNUMX 年代末提出，自此成為密碼分析者工具箱中的基本工具。資料加密標準（DES）是一種用於加密數位資料的對稱金鑰演算法，一直是差分密碼分析的主要主題之一。

DES 演算法由 IBM 於 1970 世紀 1977 年代初期設計，並於 64 年被美國國家標準與技術研究院 (NIST) 採用為聯邦標準，使用 56 位元金鑰對 16 位元資料區塊進行操作。 DES 採用 XNUMX 輪 Feistel 網絡，其中每一輪由密鑰調度確定的一系列替換和排列組成。

要了解 DES 是否可以透過差分密碼分析來破解，重要的是要考慮 DES 結構的細節和差分密碼分析的原理。

DES 結構與金鑰表

DES 建立在替換和排列運算的組合之上。每回合 DES 都涉及以下步驟：
1. 擴展（電子盒）： 使用擴展排列將 32 位元半塊擴展為 48 位元。
2. 調音混合： 擴展的半塊與使用密鑰調度從主密鑰導出的輪密鑰進行異或。
3. 替換（S 盒）： 48 位元結果被分成 6 個 4 位元段，每個段都通過相應的 S 盒以產生 4 位元輸出。八個 32 位元輸出連接起來形成一個 XNUMX 位元區塊。
4. 排列（P 盒）： 使用固定排列表對 32 位元區塊進行排列。
5. 異或和交換： 置換後的區塊與資料區塊的另一半進行異或，然後交換兩半。

密鑰調度從原始 16 位元密鑰產生一系列 48 個輪密鑰，每個輪密鑰長度為 56 位元。這個過程涉及排列選擇操作和左循環移位。

差分密碼分析原理

差分密碼分析涉及研究明文對中的差異如何透過密碼傳播以產生密文中的差異。基本想法是選擇具有特定差異的明文對，對其進行加密，並分析所得到的密文差異。透過觀察這些差異如何在密碼輪次中演變，攻擊者可以推斷出有關密鑰的資訊。

差分密碼分析中的關鍵概念包括：
- 微分： 兩個值之間的 XOR 差異。例如，如果 $P$ $P'$ 是兩個明文，它們的差分是 $\Delta P = P \oplus P'$ .
- 特點： 描述輸入差分如何在密碼輪次中傳播的差異序列。
- 可能性： 給定輸入差異在一定輪數後產生特定輸出差異的可能性。

DES 的應用

DES 是專門為抵抗差分密碼分析而設計的，這種技術在其設計時並未為公眾所知，但已被 IBM 和 NSA 所理解。 DES 中的 S 盒經過精心選擇，以最大限度地減少差異特徵的機率，從而使差異密碼分析變得更加困難。

然而，Biham 和 Shamir 證明 DES 不能免於差分密碼分析的影響。他們表明，儘管完整的 16 輪 DES 能夠抵抗實際的差分攻擊，但該密碼的縮減輪次版本卻很容易受到攻擊。具體來說，他們開發了少於 16 輪的 DES 攻擊。

例如，對 8 輪 DES 的攻擊的複雜度約為 $2 ^ {} 47$ 選擇明文，這比對完整密鑰空間進行暴力攻擊要有效得多。對於完整的 16 輪 DES，差分密碼分析的複雜性要高得多，這使得其在研究時可用的計算資源下不切實際。

DES 差分密碼分析範例

為了說明差分密碼分析的工作原理，請考慮使用減少輪數 DES 的簡化範例：

1. 選擇差速器： 選擇特定的輸入差分 $\Delta P$ 。為了簡單起見，假設 $\Delta P$ 僅影響少數位。
2. 生成明文對： 產生大量明文對 $（P，P'）$ 這樣的 $P \oplus P' = \Delta P$ .
3. 加密明文對： 對每一對進行加密以獲得密文 $（C，C'）$ .
4. 分析輸出差異： 計算輸出差值 $\Delta C = C \oplus C'$ 對於每對。
5. 識別特徵： 識別輸出差異中的模式，這些模式顯示密碼內部結構的特定特徵。
6. 推斷關鍵訊息： 使用識別出的特徵來推斷有關輪密鑰的信息，並最終推斷出主密鑰。

實際考慮

雖然差分密碼分析是一種強大的工具，但在 DES 的實際應用需要大量的運算資源和大量選定的明文。現代加密實踐已經發展到使用更複雜和更安全的演算法，例如高級加密標準 (AES)，其設計不僅可以抵禦差分密碼分析，還可以抵禦各種其他密碼分析攻擊。

差分密碼分析是密碼學領域一項成熟的技術，可用於分析並在某些情況下破解 DES 等分組密碼。雖然完整的 16 輪 DES 可以抵抗實際的差分攻擊，但 DES 的縮減輪次版本很容易受到攻擊。 DES 的設計，特別是其 S 盒，反映了對差分密碼分析原理的認識，並展示了仔細的密碼設計在確保安全性方面的重要性。

最近的其他問題和解答數據加密標準 (DES) - 密鑰調度和解密:

查看資料加密標準 (DES) - 金鑰安排和解密中的更多問題和解答

EITCA學院