在介紹完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=B1B2B3B4B5B6B7B8.

③ 使用8個S盒S1,S2,...,S8,每個S盒為6進4出。用4×16矩陣描述。

對 Bj = b1b2b3b4b5b6 計算 Sj(Bj)

b1b6對應Sj的行

b2b3b4b5對應Sj的列

對應二進制錶示 Cj=Sj(Bj)

例:有 B1 = 100110

此時有 b1b6=10,b2b3b4b5=0011.則對應第2行第3列(序號從0開始)。

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

④ 將長為32比特的 C=C1C2...C8通過固定置換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比特奇偶校驗比特;打亂重排,形成C0(左28比特)、D0(右28比特)。

  ② 循環移比特

作用:對Ci、Di分別循環左移比特。

  ③ 置換選擇2

作用:從Ci和Di(56比特)中選擇出一個48比特的子密鑰Ki.

說明:從Ci中取24比特,Di中取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的加密算法是對合運算,因此解密和加密可以共用同一個算法

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

第一次解密迭代使用子密鑰K16,第二次解密迭代使用子密鑰K15,...,第十六次解密迭代使用子密鑰K1

數學描述:

Ri-1=Li         i=16,15,...,1.

Li-1=Ri-1⊕f(Li,Ki)  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輪中的主要運算為Fi,即

Fi(Li-1,Ri-1)=(Li-1⊕f(Ri-1,Ki),Ri-1)

Fi2(Li-1,Ri-1)=Fi(Li-1⊕f(Ri-1,Ki),Ri-1)=(Li-1⊕f(Ri-1,Ki)⊕f(Ri-1,Ki),Ri-1)=(Li-1,Ri-1)=I

所以,Fi=Fi-1.

所以,Fi變換是對合運算。

(3)結合(1)(2),便構成了DES的輪運算:

Hi=FiT

因為(FiT)(TFi)=(Fi(TT)Fi)=FiFi=I,所以(FiT)-1=(TFi),(TFi)-1=(FiT)

(4)初始置換IP和逆初始置換IP-1是互逆的。

(5)加解密錶示
    ① DES(M) = (M)IP(F1T)(F2T)...(F15T)(F16)IP-1 = C

② DES-1(C) = (C)IP(F16T)(F15T)...(F2T)(F1)IP-1 = M

故有DES-1DES(M) = (M)IP(F1T)(F2T)...(F15T)(F16)IP-1IP(F16T)(F15T)...(F2T)(F1)IP-1

= (M)IP(F1T)(F2T)...(F15T)(F16)(F16T)(F15T)...(F2T)(F1)IP-1

= (M)IP(F1T)(F2T)...(F14T)(F15)(F15T)(F14T)...(F2T)(F1)IP-1

= (M)IP(F1T)(F2T)...(F13T)(F14)(F14T)(F13T)...(F2T)(F1)IP-1

= ......

= (M)IP(F1T)(F2)(F2T)(F1)IP-1

= (M)IP(F1)(F1)IP-1

= (M)IP IP-1

=  M

所以DES是可逆的。

② 對合性證明

DES  = IP(F1T)(F2T)...(F15T)(F16)IP-1 

DES-1 = IP(F16T)(F15T)...(F2T)(F1)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)比差分密碼攻擊更有效。

  • 强力攻擊:平均255次嘗試(56比特有效密鑰比特,256平均÷2=255
  • 差分密碼分析法:使用247對明密文的選擇明文攻擊
  • 線性密碼分析法:使用247對明密文的已知明文攻擊

6.10 DES的安全性

① 攻擊:窮舉攻擊(目前最有效的方法)、差分攻擊、線性攻擊。

② 安全弱點:

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

- DES的弱密鑰:

通過密鑰擴展算法產生的16個子密鑰出現重複:k1=k2=k3=...=k15=k16.

由密鑰擴展算法,易知C、D兩個寄存器如果取值“全0”或“全1”,則通過循環移比特和置換選擇2得到的子密鑰總是重複的。

6.11 三重DES

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

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

但雙重DES並不安全,雙重DES存在中間相遇攻擊。使它的强度跟一個56比特DES的强度差不多。

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

① 先用256個可能的K1加密M,得到256個可能的值,將這些值從小到大存入一個錶中。

② 再對256個可能的K2解密C,每次做完解密,將所得到的值與錶中的值比較,如果產生匹配,則它們對應的密鑰可能是K1和K2

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

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

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

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

(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.

分組密碼(三)DES 算法— 密碼學複習(六)的更多相關文章

  1. 聊聊密碼學中的DES算法

    用心分享,共同成長 沒有什麼比你每天進步一點點更實在了 本文已經收錄至我的github,歡迎大家踴躍star 和 issues. https://github.com/midou-tech/artic ...

  2. Java利用DES/3DES/AES這三種算法分別實現對稱加密

    轉載地址:http://blog.csdn.net/smartbetter/article/details/54017759 有兩句話是這麼說的: 1)算法和數據結構就是編程的一個重要部分,你若失掉了 ...

  3. IDAPython實戰項目——DES算法識別

    在CTF的逆向中我們需要的是找到加密的主函數,結合了yara的識別原理,通過對常量數組的引用的查找,一步步遞歸構建調用樹.調用樹根部就是可能的密碼算法主函數. 由於這種辦法需要常量分布於算法的各個步驟 ...

  4. AES算法,DES算法,RSA算法JAVA實現

    1     AES算法 1.1    算法描述 1.1.1      設計思想 Rijndael密碼的設計力求滿足以下3條標准: ① 抵抗所有已知的攻擊. ② 在多個平臺上速度快,編碼緊凑. ③ 設計 ...

  5. DES算法原理完整版

    1.所需參數 key:8個字節共64比特的工作密鑰 data:8個字節共64比特的需要被加密或被解密的數據 mode:DES工作方式,加密或者解密 2.初始置換 DES算法使用64比特的密鑰key將64比特的 ...

  6. 基於DES算法加密的防撞庫密碼系統項目總結

    項目內容:基於DES算法加密的防撞庫密碼系統 小組名:zqhzkzkj 目標:1.對用戶輸入的8比特字符進行DES加密,要求用戶輸入8比特密鑰 2.對於不同的網站,不同的用戶名生成不同的密碼 小組成員:周 ...

  7. MFC 簡單實現 DES 算法

    前言 徐旭東老師說過學者就應該對知識抱有敬畏之心,所以我的博客的標題總喜歡加上"簡單"二字,就是為了提醒自己,自己所學知識只是皮毛,離真理還遠矣. DES 算法 DES算法是密碼體 ...

  8. Asp.Net 常用工具類之加密——對稱加密DES算法(2)

    又到周末,下午博客園看了兩篇文章,關於老跳和老趙的程序員生涯,不禁感歎漫漫程序路,何去何從兮! 轉眼畢業的第三個年頭,去過蘇州,跑過上海,從一開始的淩雲壯志,去年背起行囊默默回到了長沙准備買房,也想有 ...

  9. 安全體系(一)—— DES算法詳解

    本文主要介紹了DES算法的步驟,包括IP置換.密鑰置換.E擴展置換.S盒代替.P盒置換和末置換. 安全體系(零)—— 加解密算法.消息摘要.消息認證技術.數字簽名與公鑰證書 安全體系(二)——RSA算 ...

  10. Web安全學習筆記之DES算法實例詳解

    轉自http://www.hankcs.com/security/des-algorithm-illustrated.html 譯自J. Orlin Grabbe的名作<DES Algorith ...

隨機推薦

  1. 【MSP是什麼】MSP認證之項目群管理學習心得

    學習了項目群管理後,我深受啟發,在此發錶下自己的一些個人感想. 項目群是指經過協調統一管理以便獲取單獨管理時無法取得的效益和控制的一組相互聯系的項目. 項目群中的項目需要共享組織的資源, 需要進行項目 ...

  2. 【bzoj2823】 AHOI2012—信號塔

    http://www.lydsy.com/JudgeOnline/problem.php?id=2823 (題目鏈接) 題意 求最小圓覆蓋 Solution 關於最小圓覆蓋的做法,論文裏面都有.其實真 ...

  3. 為測試框架model類自動生成xml結果集

    問題:有大量類似於theProductId這樣名字的字符串需要轉換成the_product_id這種數據庫column名的形式. 思路:見到(見)大寫字母(縫)就插入(插)一個“_”字符(針)進去,最 ...

  4. 棧的應用2——超級計算器(中綴與後綴錶達式)C語言

    輸入中綴錶達式輸出結果(結果可以是小數,但輸入必須是整數)  #include<stdio.h> #include<stdlib.h> //需要兩個棧,一個儲存結果,一個儲存運 ...

  5. 《轉》python 網絡編程

    原地址:http://blog.163.com/benben_long/blog/static/19945824320121225918434/ 網絡客戶端: 1. 理解socket: socket是 ...

  6. JDBCTemplate簡化JDBC的操作(二)

    一.Spring對不同的持久化支持: Spring為各種支持的持久化技術,都提供了簡單操作的模板和回調 ORM持久化技術 模板類 JDBC org.springframework.jdbc.core. ...

  7. C# .net 語言加密方案

    C# .net 語言加密方案 方案背景 當前C# .net語言的應用範圍越來越廣泛,IIS 的服務器架構後臺代碼.桌面應用程序的 winform .Unity3d 的邏輯脚本都在使用.C# .net ...

  8. Oracle創建用戶、授權、規則

    ---用戶登錄命令--管理員登錄conn sys/oracle as sysdba;--創建用戶方案必須是管理員權限--創建用戶命令 create user useranme identifild b ...

  9. 使用擴展方法(Chapter3 P39-41)

    namespace LanguageFeatures { public class ShoppingCart { public List<Product> Products { get; ...

  10. python數據類型-----列錶

    今天來總結下python3.4版本列錶的一些操作方法. 列錶(list): 1.列錶就像一個線性容器,但是比C++的 lis t擴展多得多,列錶裏的元素可以是相同類型,也可以包含各種類型,比如列錶裏嵌 ...