密碼學 - 資料加密標準

---

---

DES 代表資料加密標準演算法，是一種由 IBM 團隊在 20 世紀 70 年代初期建立的對稱金鑰分組密碼，並在一段時間後被美國國家標準與技術研究院採用。在這種方法中，我們將明文分成 64 位的塊，並藉助 48 位金鑰將其轉換為密文。

如您所知，它是一種對稱金鑰方法，它使用相同的金鑰來加密和解密資料，這在我們之前章節中已經討論過了。如果它是非對稱演算法，則需要不同的金鑰來加密和解密。

一些系統可以破解 DES 演算法。該演算法使用 56 位金鑰。DES 使用此金鑰將 64 位明文塊轉換為 64 位密文塊。

DES 過程包含多個步驟，每個步驟稱為“輪”。輪數根據我們使用的金鑰大小而異。例如，128 位金鑰需要 10 輪，192 位金鑰需要 12 輪，依此類推。

DES 演算法的歷史

DES 基於 LUCIFER Feistel 分組密碼，該密碼由 IBM 密碼學研究員 Horst Feistel 於 1971 年發明。DES 使用 16 輪 Feistel 結構，每輪使用唯一的金鑰。

1976 年 11 月，DES 被批准為政府加密標準，後來在 1983 年、1988 年和 1999 年得到再次確認。

在公開競賽開發替代方案後，高階加密標準 (AES) 於 2002 年取代了 DES 成為公認的標準，結束了 DES 的壟斷地位。2005 年 5 月，NIST 正式撤銷了 FIPS 46-3（1999 年的再次確認），但是三重 DES (3DES) 仍然允許用於敏感的政府資訊，直到 2030 年。

DES 的型別/變體

資料加密標準主要有兩個變體，如下所示：

雙重 DES

雙重 DES 是一種加密型別，其中必須在同一明文中存在兩次 DES。在這兩種情況下，明文都在多個金鑰的幫助下進行加密。為了解密，需要這兩個金鑰。

三重 DES

三重 DES 有兩種型別，如下所示：

使用兩個金鑰的三重 DES - 在使用兩個金鑰的三重 DES 中，只有兩個金鑰 K1 用於第一個和第三個過程，K2 用於第二個過程。

使用三個金鑰的三重 DES - 在三重 DES 中，明文塊 P 首先使用金鑰 K1 加密，然後使用第二個金鑰 K2 加密，最後使用第三個金鑰 K3 加密，其中 K1、K2 和 K3 彼此不同。

DES 的結構

DES 使用 16 輪 Feistel 結構。塊大小為 64 位。儘管金鑰長度為 64 位，但 DES 的有效金鑰長度為 56 位，因為金鑰的 64 位中的 8 位沒有被加密演算法使用（僅用作校驗位）。DES 的一般結構如下圖所示：

由於 DES 基於 Feistel 密碼，因此指定 DES 所需的只是：

• 輪函式
• 金鑰編排
• 任何其他處理 - 初始和最終置換

初始和最終置換

初始和最終置換是彼此互逆的簡單置換盒 (P 盒)。它們在 DES 中沒有密碼學意義。初始和最終置換如下所示：

輪函式

該密碼的核心是 DES 函式 f。DES 函式將 48 位金鑰應用於最右邊的 32 位以產生 32 位輸出。

現在讓我們討論上圖及其術語：

• 擴充套件置換盒 - 由於右側輸入為 32 位，而輪金鑰為 48 位，因此我們首先需要將右側輸入擴充套件到 48 位。置換邏輯在下圖中以圖形方式描述：

• 圖形描述的置換邏輯通常在 DES 規範中以表格形式描述，如下所示：

• XOR（白化器） - 在擴充套件置換之後，DES 對擴充套件的右側部分和輪金鑰進行 XOR 操作。這是唯一使用輪金鑰的操作型別。
• 替換盒 - S 盒執行真正的混合（混淆）。DES 中使用了 8 個 S 盒，每個 S 盒都有 6 位輸入和 4 位輸出。請參閱下圖：

• S 盒規則如下所示：

• 共有 8 個 S 盒表。然後將所有 8 個 S 盒的輸出組合成 32 位部分。
• 直線置換 - S 盒的 32 位輸出然後進行直線置換，規則如下圖所示：

DES 演算法

以下步驟定義了演算法過程：

• 步驟 1 - 64 位明文塊最初提供給初始置換 (IP) 函式以啟動該過程。
• 步驟 2 - 之後，明文經過初始置換 (IP)。
• 步驟 3 - 然後，第一個置換 (IP) 生成左明文 (LPT) 和右明文 (RPT)，它們是置換塊的兩側。
• 步驟 4 - 加密過程包括對每個 LPT 和 RPT 進行 16 個迴圈。
• 步驟 5 - 最後，LPT 和 RPT 成為一個，並且新組合的塊經過最終置換 (FP)。
• 步驟 6 - 此過程產生預期的 64 位密文。

加密過程的步驟 4 可以進一步細分為五個階段：金鑰轉換、擴充套件置換、S 盒置換、P 盒置換、XOR 和交換。

我們對解密應用相同的過程，但我們反轉了 16 個輪金鑰的順序。

接下來，我們將探索DES的幾種操作模式，以更好地理解DES。

金鑰生成

輪金鑰生成器從56位的密碼金鑰中生成十六個48位的金鑰。金鑰生成過程如下圖所示：

該演算法執行16輪加密，並且每輪都會生成一個唯一的金鑰。在轉換到步驟之前，必須瞭解在明文中，位從1到64進行標記，其中1是最重要的位，64是最不重要的位。金鑰生成過程如下：

• 輪金鑰生成器從56位的密碼金鑰中生成十六個48位的金鑰。密碼金鑰以64位金鑰的形式提供，其中8個額外位是奇偶校驗位，在實際的金鑰生成過程開始之前會被丟棄。
• 奇偶校驗位丟棄過程從64位金鑰中丟棄奇偶校驗位（第8位、第16位、第24位、第32位…第64位），並根據預定義規則對剩餘位進行置換，如下面的奇偶校驗位丟棄表所示。
• 這些剩餘的56位通常用於金鑰生成。
• 置換後，金鑰被分成兩個28位的部分。每個部分都會向左移動一位或兩位，具體取決於輪數。
• 在第1、2、9和16輪中，移位一位；在其他輪中，移位兩位。這兩個部分被整合以構建一個56位的部分。
• 因此，壓縮D盒將其轉換為48位。這48位被用作一輪的金鑰。

奇偶校驗位丟棄、移位和壓縮P盒的邏輯在DES描述中給出。

DES分析

DES滿足分組密碼的兩個期望屬性。這兩個屬性使密碼非常強大。

• 雪崩效應 - 密文對明文即使很小的變化也會發生顯著的變化。明文中的一個位發生變化會導致密文中某些位發生變化。雪崩效應的優勢可以在使用DES和AES演算法的嵌入式軟體安全中得到體現。攻擊者試圖大量竊取資料庫中儲存的資料。
• 完整性 - 完整性效應定義了密文的每個位元都需要基於明文中的某些位元。DES中由D盒和S盒產生的擴散和混淆，表現出非常強的完整性效應。完整性特性進一步強化了雪崩的概念。它要求密文的變化對於輸入明文或金鑰的每個變化位都一致地分佈。

在過去的幾年裡，密碼分析發現，當選擇弱金鑰時，DES存在一些弱點。這些金鑰應該避免使用。

DES已被證明是一個設計非常好的分組密碼。除了窮舉金鑰搜尋之外，還沒有對DES進行任何重要的密碼分析攻擊。

DES強度

DES的強度如下：

• 使用56位金鑰 - 56位的加密金鑰提供了256個可能的金鑰，由於組合數量巨大，使得暴力攻擊變得不可能。即使一臺機器每微秒執行一次DES加密，解密密碼也需要數千年的時間。

  Diffie和Hellman提出了一個並行機器的可行性，該機器具有100萬個加密單元，每個單元每微秒能夠執行一次加密。但是，解密訊息可能不僅僅需要嘗試所有可能的金鑰，特別是如果訊息是英文明文，因為英文明文很容易識別。如果在加密前壓縮文字，則解密變得更具挑戰性。

• 演算法的性質 - 密碼分析師可以透過利用DES演算法的特性對其進行密碼分析。他們專注於每次迭代中使用的八個替換表或S盒的弱點。雖然研究人員發現了S盒中的許多規律性和意外行為，但還沒有人發現其中的弱點。

  多年來，這種持續的研究導致識別了S盒中的許多不規則性和意外行為。

• 定時攻擊 - 定時攻擊是一種安全漏洞，屬於更廣泛的側通道攻擊類別，攻擊者透過測量系統對不同輸入的響應時間來提取敏感資料。Kocher設計了一種專門針對RSA解密金鑰的定時攻擊，主要用於智慧卡等硬體安全令牌。

  這些攻擊側重於公鑰演算法，透過觀察多個密文的解密時間來提取有關金鑰或明文的資訊。為了減輕定時攻擊，使用了諸如“盲化”之類的技術，以確保無論處理的金鑰或訊息是什麼，計算時間都保持一致。

DES的優點

DES方法的優點是：

• 美國當局已將其設定為標準。
• 它在硬體上的執行速度比在軟體上快。
• 三重DES使用一個難以破解的168位金鑰。

DES的缺點

DES的缺點或劣勢如下：

• 它是一種安全性較弱的演算法。
• 它可以使用暴力攻擊破解。
• 市場上有一種名為Deep Crack的DES破解裝置。

對DES的攻擊

對DES的攻擊有多種，如下所示：

• 差分密碼分析 - 差分密碼分析的主要目標是檢視密文中的統計分佈和模式，以提供推匯出密碼中使用的金鑰的元素。

  差分密碼分析是密碼學中的一門研究分支，它比較輸入方法與加密輸出方法的差異。它主要用於研究分組密碼，以確定明文的更改是否會導致加密密文中出現任何非隨機結果。

• 相關金鑰密碼分析 - 相關金鑰密碼分析認為攻擊者不僅瞭解特定明文在原始（未知）金鑰K下的加密，還了解在某些派生金鑰K0 = f (K)下的加密。

  在選擇相關金鑰攻擊中，攻擊者定義了金鑰的修改方式；已知相關金鑰攻擊是指金鑰差異已知但無法由攻擊者選擇的情況。

  它可以強調攻擊者瞭解或選擇金鑰之間的關係，而不僅僅是實際的金鑰值。

  相關金鑰密碼分析是對金鑰交換協議的實際攻擊，這些協議不提供金鑰完整性，攻擊者能夠在金鑰中翻轉位元，而無需瞭解鍵盤金鑰更新協議（這些協議使用已知函式更新金鑰，例如K、K + 1、K + 2等）。相關金鑰攻擊也用於攻擊轉子裝置，例如操作員持續錯誤地設定轉子。

• 線性密碼分析 - 線性密碼分析是一種通用的密碼分析形式，它依賴於發現密碼元素的仿射近似。針對分組密碼和流密碼已經產生了攻擊。線性密碼分析是兩種最常用的分組密碼攻擊之一，另一種是差分密碼分析。

  線性近似方程依賴於最佳（n-2）輪表示式，並且金鑰候選者的可靠性從這些方程中改變。前者減少了所需的明文數量，而後者提高了攻擊的成功率。

• 暴力攻擊 - 在密碼分析中，暴力攻擊是一種透過嘗試大量可能性來破壞密碼方案的方法。

  例如，它可以窮舉所有可能的金鑰以解碼訊息。根據實施暴力攻擊的實際可行性選擇合適的金鑰長度。

  對於對稱金鑰密碼，暴力攻擊通常意味著對金鑰空間進行暴力搜尋；也就是說，檢查所有可能的金鑰以找到用於建立特定密文的明文。

  在暴力攻擊中，在找到正確金鑰之前預期的嘗試次數類似於金鑰空間大小的一半。例如，如果有264個可能的金鑰，則暴力攻擊通常可以在263次嘗試後找到金鑰。

影響DES安全性的因素

有一些因素會影響DES的安全性，如下所示：

• 弱金鑰 - 由於初始金鑰被修改以接收演算法每個輪次的子金鑰的方法，因此某些初始金鑰是弱金鑰。初始金鑰值被分成兩半，每一半獨立地進行修改。

  如果每一半中的所有位都為0或1，則該金鑰可用於演算法的某些迴圈，並且在演算法的所有迴圈中都相同。如果金鑰完全為1，完全為0，或者金鑰的一半完全為1，另一半完全為0，則可能出現這種情況。這使得DES安全性降低。

• 代數結構 - DES加密操作可以形成一個群，並且用k1加密一組明文塊，然後用k2加密，可以等於用k3加密這些塊。

  更糟糕的是，DES可能容易受到中間相遇已知明文攻擊，該攻擊只需228步即可執行。如果DES是封閉的，那麼對於任何k1和k2，都將存在一個k3，使得：

  Ek2(Ek1(P))=Ek3(P)

• 金鑰長度 - 如果有可能透過時空權衡來加速搜尋過程。計算和儲存256個可能的加密單個明文塊在每個可能的金鑰下的結果，然後破解未知金鑰的可能性，並且需要將資料塊新增到加密流中，恢復生成的密文並檢視金鑰。

  輪數 - 輪數保持為16，因為輪數減少會導致受到強烈攻擊。具有三輪或四輪的DES很容易被破解。具有少於16輪的任何數量輪的DES都可以使用已知明文攻擊比暴力攻擊更有效地破解。

DES的測試和實現

實現DES需要安全提供商。即使有多種選擇，選擇供應商也是實施過程中的重要第一步。您使用的語言（如MATLAB、Java、Python或C）可能會影響您的選擇。

選擇提供商後，您必須決定是使用位元組陣列還是明文隨機構建金鑰生成器將產生的金鑰。

測試加密對於確保正確使用加密也很重要。

DES的設計問題

DES中的設計問題包括S盒、D盒和輪數。

• S盒用於將48位輸入替換為32位輸出，為加密過程新增非線性性和複雜性。它們遵循特定的屬性，例如行內建換和非仿射變換。
• D盒類似於轉置密碼，將輸入位從一輪置換到下一輪，確保每個S盒輸入來自不同的S盒輸出，並避免輪內重複。
• DES使用了十六輪Feistel密碼，但已證明在八輪之後，每個密文都成為每個明文和金鑰位的函式，表明安全性足夠。