分組密碼（三）DES 演算法— 密碼學複習（六）

2021 年 9 月 18 日
筆記
密碼學複習

在介紹完Feistel結構之後，接下來進入到著名的DES演算法。

6.1 DES演算法的意義

在正式介紹DES之前，首先介紹幾個重要的歷史時間節點。

① 1973年，美國國家標準局(NBS)向社會公開徵集加密演算法，一直盯加密演算法標準。

② 1974年，第二次徵集。

③ 1975年，選中IBM的演算法，公布徵求意見。

④ 1977年1月15日正式頒布。

⑤ 1998年底以後停用。

⑥ 1999年頒布3DES為新標準。

標準加密演算法的目標：

① 用於保護政府機構和商業部門的非機密的敏感數據。

② 用於加密保護靜態存儲和傳輸信道中的數據。

③ 安全使用10~15年。

DES演算法是單射的分組密碼演算法，是密碼學發展的一個重要的階段（現代密碼學誕生的標誌之一），對演算法的標準化研究和分組密碼的發展有重大意義。

目前攻擊DES的最有效的辦法是密鑰窮舉攻擊。

6.2 DES演算法概述

密碼的整體特點：

① 分組密碼：明文、密文和密鑰的分組長度都是64位。

② 面向二進位數據的密碼演算法：因而能夠加解密任何形式的電腦數據。

③ 對合運算：加解密使用同一個演算法，使工程量減半。

④ 綜合運用了置換、代替、代數等基本密碼技術。

⑤ 基本結構屬於Feistel結構。

首先，簡單看一下DES演算法的整體結構，其主要由初始置換IP、輪函數、逆初始置換IP^-1以及密鑰擴展演算法組成。這裡直接放上書上的圖。

DES演算法時迭代型分組密碼演算法，16輪的Feistel型密碼基本參數：

·分組長度：64比特

·密鑰長度：64比特

·有效密鑰長度：56比特（8比特校驗位）

·迭代圈數：16圈

·圈密鑰長度：48比特

DES加密標準的核心是採用Fesitel結構。明文分組長度是64比特，初始密鑰長度也是64比特（實際上採用的是56比特，8比特校驗位），循環輪數為16輪。

6.3 Fesitel型密碼

Fesitel模型的優缺點：

優點：設計容易，f函數不要求可逆。

缺點：輪變換有一半的輸入沒有改變，左右塊的處理不能並行實施。

6.4 DES中的輪函數 f(A,J)

A為32比特串，J為48比特串，輸出為f(A,J)為32比特串。

① A根據一個固定擴展函數E擴展成一個長為48比特串E(A).

② 計算E(A)⊕J,並將所得結果分成8個長為6的比特串，記為B=B₁B₂B₃B₄B₅B₆B₇B₈.

③ 使用8個S盒S₁,S₂,…,S₈,每個S盒為6進4出。用4×16矩陣描述。

對 B_j = b₁b₂b₃b₄b₅b₆ 計算 S_j(B_j)

b₁b₆對應S_j的行

b₂b₃b₄b₅對應S_j的列

對應二進位表示 C_j=S_j(B_j)

例：有 B₁ = 100110

此時有 b₁b₆=10，b₂b₃b₄b₅=0011.則對應第2行第3列（序號從0開始）。

查找S盒找到對應的數字——8.故S₁(B₁)=1000.

④ 將長為32比特的 C=C₁C₂…C₈通過固定置換P（P盒）：

P(C) = f(A,J)

擴展變換 —— E盒擴展

作用：將輸入的32比特擴展為48比特。

擴展方式：分別將第i-1塊最右比特和第i+1塊最左比特添加到第i塊的左邊和右邊。形成輸出的第i個6比特塊。

S盒

S盒代替是DES演算法中唯一的非線性變換。在DES演算法中起核心作用。

S盒的設計標準對於實現DES演算法的安全性，對於實現混亂和擴散原則，對於保障DES演算法的密碼強度，具有十分重要的作用。

S盒只要稍微改變，其密碼強度就會大大改變。

P盒

P盒的設計特點：

① P盒的各輸入塊的4比特都分配到不同的輸出塊中。

② P盒的各輸出塊的4比特都來自不同的輸入塊。

6.5 輪密鑰產生

輪密鑰的產生主要包含三個部分：

① 置換選擇1 （64比特 -> 56比特，去掉8比特奇偶校驗位）

② 循環移位（分左28比特，右28比特）

③ 置換選擇2 （56比特 -> 48比特）

最終得到 16 個 48比特的輪密鑰。

① 置換選擇1

作用：去掉密鑰中8比特奇偶校驗位；打亂重排，形成C₀（左28比特）、D₀（右28比特）。

② 循環移位

作用：對C_i、D_i分別循環左移位。

③ 置換選擇2

作用：從C_i和D_i（56比特）中選擇出一個48比特的子密鑰K_i.

說明：從C_i中取24比特，D_i中取24比特。

6.6 加密過程

加密過程可以簡單分為三個部分：①初始置換IP ②16輪Feistel結構 ③逆初始置換IP^-1

① 初始置換 IP

作用：把64位明文打亂重排。

注意：IP中的置換是有規律的，則對保密是不利的。

② 逆初始置換 IP^-1

作用：把64位中間密文打亂重排，形成最終64位密文。

相逆性：IP 與 IP^-1互逆

如：在IP中把輸入的第1位置換到第40位，而在IP^-1中把輸入的第40位置換到第1位。

但保密作用不大。由於沒有密鑰參與，在IP與IP^-1公開的條件下，其保密意義不大。

③ 16輪Feistel結構

（a）擴展置換E

作用：把32位輸入擴充為48位中間數據，通過重複使用數據，實現數據擴充。

（b）代替函數組S（S盒）

S盒的一般性質：

S盒是DES中唯一的非線性變換，是DES安全的關鍵。

在保密性方面，起混淆作用。

共有8個S盒，並行作用。

每個S盒有6個輸入，4個輸出，是非線性壓縮變換。

改變S和任一輸入比特，其輸出至少2比特發生改變。

其他準則：

非線性準則：S盒必須有足夠的非線性度，否則不能抵抗線性攻擊。

差分均勻性準則：S盒的差分性應均勻，否則不能抵抗差分攻擊。

代數次數及項數分布準則：S盒必須有足夠的代數次數和項數，否則不能抵抗插值攻擊和高階差分攻擊。

S盒的密碼學特性保證了DES的安全。

（c）置換運算P

把數據打亂重排。

在保密性方面，其擴散作用。因為S盒是6位輸入，4位輸出，其非線性作用是局部的，因此需要把S盒的混淆作用擴散開來。

S盒和P盒相互配合，共同確保DES安全。

6.7 解密過程

DES的加密演算法是對合運算，因此解密和加密可以共用同一個演算法。

不同點：子密鑰的使用順序不同

第一次解密迭代使用子密鑰K₁₆，第二次解密迭代使用子密鑰K₁₅，…，第十六次解密迭代使用子密鑰K₁。

數學描述：

R_i-1=L_i i=16,15,…,1.

L_i-1=R_i-1⊕f(L_i,K_i) i=16,15,…,1.

6.8 DES的對合性和可逆性

① 可逆性證明

（1）定義：變換T是把64位數據的左右兩半交換位置。

T(L,R)=(R,L)

因為TT(L,R)=T(R,L)=(L,R)=I，其中I為恆等變換。

又顯然TT^-1=I，於是TT^-1=TT，所以有

T=T^-1

所以T變換是對合運算。

（2）記DES第i輪中的主要運算為F_i，即

F_i(L_i-1,R_i-1)=(L_i-1⊕f(R_i-1,K_i),R_i-1)

F_i²(L_i-1,R_i-1)=F_i(L_i-1⊕f(R_i-1,K_i),R_i-1)=(L_i-1⊕f(R_i-1,K_i)⊕f(R_i-1,K_i),R_i-1)=(L_i-1,R_i-1)=I

所以，F_i=F_i^-1.

所以，F_i變換是對合運算。

（3）結合（1）（2），便構成了DES的輪運算：

H_i=F_iT

因為(F_iT)(TF_i)=(F_i(TT)F_i)=F_iF_i=I,所以(F_iT)^-1=(TF_i),(TF_i)^-1=(F_iT)

（4）初始置換IP和逆初始置換IP^-1是互逆的。

（5）加解密表示
① DES(M) = (M)IP(F₁T)(F₂T)…(F₁₅T)(F₁₆)IP^-1= C

② DES^-1(C) = (C)IP(F₁₆T)(F₁₅T)…(F₂T)(F₁)IP^-1 = M

故有DES^-1DES(M) = (M)IP(F₁T)(F₂T)…(F₁₅T)(F₁₆)IP^-1IP(F₁₆T)(F₁₅T)…(F₂T)(F₁)IP^-1

= (M)IP(F₁T)(F₂T)…(F₁₅T)(F₁₆)(F₁₆T)(F₁₅T)…(F₂T)(F₁)IP^-1

= (M)IP(F₁T)(F₂T)…(F₁₄T)(F₁₅)(F₁₅T)(F₁₄T)…(F₂T)(F₁)IP^-1

= (M)IP(F₁T)(F₂T)…(F₁₃T)(F₁₄)(F₁₄T)(F₁₃T)…(F₂T)(F₁)IP^-1

= ……

= (M)IP(F₁T)(F₂)(F₂T)(F₁)IP^-1

= (M)IP(F₁)(F₁)IP^-1

= (M)IP IP^-1

= M

所以DES是可逆的。

② 對合性證明

DES = IP(F₁T)(F₂T)…(F₁₅T)(F₁₆)IP^-1

DES^-1 = IP(F₁₆T)(F₁₅T)…(F₂T)(F₁)IP^-1

DES和DES^-1除了子密鑰的使用順序相反之外是相同的。

不考慮子密鑰的使用順序，則有：

DES = IP(FT)(FT)…(FT)(F)IP^-1

DES^-1 = IP(FT)(FT)…(FT)(F)IP^-1

顯然 DES = DES^-1

所以DES的運算是對合運算。

6.9 DES的破譯

1990年，以色列密碼學家Eli Biham和Adi Shamir提出了差分密碼分析法。可對DES進行選擇明文攻擊。

線性密碼分析（1993）比差分密碼攻擊更有效。

強力攻擊：平均2⁵⁵次嘗試（56位有效密鑰位，2⁵⁶平均÷2=2⁵⁵）
差分密碼分析法：使用2⁴⁷對明密文的選擇明文攻擊
線性密碼分析法：使用2⁴⁷對明密文的已知明文攻擊

6.10 DES的安全性

① 攻擊：窮舉攻擊（目前最有效的方法）、差分攻擊、線性攻擊。

② 安全弱點：

密鑰太短
存在弱密鑰
存在互補對稱性（設C=DES(M,K),則有~C=DES(~M,~K)）

– DES的弱密鑰：

通過密鑰擴展演算法產生的16個子密鑰出現重複：k₁=k₂=k₃=…=k₁₅=k₁₆.

由密鑰擴展演算法，易知C、D兩個暫存器如果取值「全0」或「全1」，則通過循環移位和置換選擇2得到的子密鑰總是重複的。

6.11 三重DES

在講三重DES之前首先考慮一下雙重DES。

用DES加密兩次，每次使用不同的密鑰。

但雙重DES並不安全，雙重DES存在中間相遇攻擊。使它的強度跟一個56位DES的強度差不多。

若已知明文密文對(M,C)，攻擊方法如下：

① 先用2⁵⁶個可能的K₁加密M,得到2⁵⁶個可能的值，將這些值從小到大存入一個表中。

② 再對2⁵⁶個可能的K₂解密C，每次做完解密，將所得到的值與表中的值比較，如果產生匹配，則它們對應的密鑰可能是K₁和K₂。

③ 用一個新的明文密文對檢測兩個密鑰，如果產生正確的密文，則它們是正確的密鑰。

為了防止中間相遇攻擊，採用三次加密方案。

（1）下面是使用兩個密鑰的三重DES（加密-解密-加密 E-D-E）方案

注意：加密與解密在安全性上來說是等價的。這種加密方案窮舉攻擊代價是2¹¹².

（2）三把密鑰的三重DES的（有效）密鑰長度是168位，採用加密-解密-加密（E-D-E）方案

3DES的優點和缺點：

優點：

① 密鑰長度是168位，足以抵抗窮舉攻擊；

② 3DES的底層加密演算法與DES加密演算法相同，該加密演算法比任何其它加密演算法收到分析的時間要長得多，也沒有發現有比窮舉攻擊更有效的密碼分析攻擊方法。

缺點：

加解密速度慢，分組長度只有64位。

優勢：

3密鑰的3DES：密鑰長度是168位。

2密鑰的3DES：密鑰長度是112位。

安全：密鑰足夠長，經過最充分的分析和實踐檢驗。

兼容性好。

弱勢：

速度慢。

6.12 DES的歷史回顧

DES的貢獻：

DES很好地體現了香農的密碼設計理論；
DES體現了密碼公開設計原則，開創了公開密碼演算法的先例；
DES代表當時商業密碼的最高水平，是商用密碼的典範；
DES對確保國際資訊安全和提高國際密碼設計水平都發揮了重要作用。

DES給我們的啟示：

商用密碼應當堅持公開設計原則；
商業密碼標準應當公布演算法。

參考文獻：

[1]張煥國，唐明. 密碼學引論（第三版）[M].武漢：武漢大學出版社, 2015.

Tags: 密碼學複習