密码学安全实践-Crypto Hacking 课件 第3章 分组密码

第3章分组密码3.1分组密码概述3.2DES算法3.3DES安全性分析3.4多重DES

3.1分组密码概述

3.1.1分组密码模型一个分组密码系统(BlockCipherSystem,BCS)可以用一个五元组来表示,即BCS={P,C,K,E,D}。其中,P(Plaintext)、C(Ciphertext)、K(Key)、E(Encryption)、D(Decryption)分别表示明文、密文、密钥、加密算法和解密算法。分组密码系统的模型如图3.1所示。

图3.1分组密码模型

(1)明文:待加密的消息。明文消息会划分为固定长度的分组。分组通常是二进制表示的序列,比如DES密码算法的分组长度是64个比特(位),相当于8个字符。明文消息的长度通常不是分组长度的倍数,此时加密前需要进行填充处理。

(2)密文:每个明文分组加密后的密文分组组合得到的消息。根据分组操作模式的不同,每个密文分组可以只和对应的明文分组有关,也可以和之前的所有的明文分组有关,这取决于加密采用的操作模式。

(3)加密算法:在密钥控制下,通过某种变换隐藏明文消息的含义,使得未授权用户无法获得明文消息内容。

(4)解密算法:在密钥控制下,还原密文中的明文消息。通常解密算法和加密算法是一致的,而且是公开的。

(5)密钥:由安全信道分发给参与加解密运算的各方。各方使用相同密钥对消息加解密。整个密码系统的安全性只依赖于密钥,而不是加解密算法。

3.1.2分组密码设计

为了保证分组密码的安全强度,防止密钥通过逆推被破解、明文被破译,分组密码的设计应遵循以下基本原则。

(1)分组长度足够长,防止明文穷举攻击。

(2)密钥空间足够大,同时需要尽可能消除弱密钥的使用,防止密钥穷举攻击,但是由于对称密码体制存在密钥管理问题,密钥的存储、传输和管理本身就是一个大的安全隐患。

(3)产生子密钥的密钥调度算法足够复杂,能够抵御各种已知攻击,如差分攻击、线性攻击、侧信道攻击等。

(4)加密和解密的运算简单,易于软硬件系统的高速实现。

(5)差错传播尽可能小,明文或密文分组出错,对后续明文或密文的加解密影响应尽可能小。

(6)混淆和扩散是香农在遵循柯克霍夫原则(即使密码系统的加解密算法细节公开,只要密钥未泄漏,密码系统也是安全的)前提下,提出的设计密码系统的两个基本方法,目的

是抗击攻击者对密码系统的统计分析。混淆要求密码的设计应使得明文、密文、密钥之间的依赖关系非常复杂,即使攻击者得到了密文的统计特性,也无法推测密钥。扩散则要求将明文的统计特性(如每个字母出现的频度)散布到密文中去,模糊化明文统计结构和规律,防止密钥被反推出来。

(7)非线性:在分组密码中,实现非线性运算的部件是S盒。例如,AES密码S盒使用的有限域上元素求逆就是典型的非线性操作。

(8)雪崩性:改变明文或者密钥的任意一个比特,会影响对应密文的多个比特,且是随机的。如图3.2所示的DES加密,可使用轮函数f

达到的雪崩效应。

图3.2雪崩效应

3.1.3分组密码结构

香农在1949年的论文

AMathematicalTheoryofCommunication中提出了一种乘积密码,以实现混淆和扩散。所谓的乘积密码就是一连串的替换和置换操作。现代分组密码也是采用了类似的结构设计,重复替换和置换步骤,只不过每个步骤的操作都由密钥来控制。我们把多重替换变换(S)和置换变换(P)称为替换-置换网络(SPN),如图3.3所示。S替换操作起到混淆的作用,P置换操作起到扩散的作用。

图3.3替换

置换网络

SP网络的一个典型代表是Feistel网络,其采用的轮结构如图3.4所示,对应算法为

·将明文分组分为等长的左右两部分Li、Ri;

·使用高度非线性函数f,计算下一轮的左右两部分Li+1、Ri+1,即

图3.4单轮(层)Feistel网络

Feistel网络结构与以下的参数和特性有关。

(1)分组大小:分组越大,安全性越高,加密速度越慢。分组大小通常不小于64比特。

(2)密钥大小:密钥越长,安全性越高,加密速度越慢。密钥长度通常为128比特。

(3)轮数:多轮结构可以提高安全性,一般轮数取16。

(4)子密钥生成算法:该算法的复杂性越大,则密码分析的困难性也越大。

(5)轮函数f:轮函数f

复杂性越大,密码分析的困难也越大。

3.2DES算法

DES全称为DataEncryptionStandard,是由IBM公司在1972年研发的对称加密算法。DES密钥长度为64位,有效密钥长度是56位,另外8位作为校验位。明文和密文按64位进行分组。算法使用16轮的Feistel网络结构实现混淆和扩散,使用8个S盒实现非线性变换。整个DES加密包含16轮运算,每轮的子密钥由密钥调度算法(KeyScheduleAlgorithm)生成。算法加密过程如图3.5所示。

图3.5DES加密过程

图3.5中的DES加密过程可以分为三个部分:分别是互逆的初始置换(IP)和逆初始置换(IP-1)操作,中间是16轮相同结构的Feistel网络,每轮子密钥由密钥调度算法产生。为便于学习DES算法的核心思想和整个工作流程,接下来将以实际例子来讲解DES密码。

令明文P=897A57B439DE18FE,密钥K=823452593FBCDDE7,其中P

和K

都是十六进制表示。若以二进制分别表示P

和K,则为

3.2.1初始置换和逆初始置换

初始置换是DES算法的第一步,根据初始置换表改变明文比特位的位置,即重新组织明文内容。初始置换表如图3.6(a)所示。初始置换表是一个8×8的表格,含有64个元素,

每个元素代表一个位置,分别是1~64。例如,表中的第一个元素是58,表示明文消息的第58位比特置换到密文输出的第1位;表中的最后一个元素值是7,表示明文消息的第7位比特是密文输出的最后一位(第64位)。

图3.6初始置换和逆初始置换

初始置换对应的Python代码实现如下:

将初始置换应用于之前给定的明文P,则得到输出IP:

逆初始置换是DES算法的最后一步,它是初始置换的逆变换,其置换顺序如图3.6(b)所示。原来明文消息的第1位被放到了第40位,因此在逆置换时,把第40位放回到第一位,这就是逆置换表的第一个元素值40,剩下位读者可自行验证互逆关系。

逆初始置换的Python代码实现如下:

将逆初始置换应用于之前给定的IP,则得到最初的明文P。

3.2.2子密钥生成

DES算法由64位初始密钥生成16个48位子密钥,这16个子密钥分别用在16轮DES运算中。子密钥的产生过程如图3.7所示。

图3.7DES密钥调度算法

64位初始密钥首先进行如图3.8所示的PC_1置换,去掉8个奇偶校验位后,密钥长度降至56位。56位数据分成左右两半:Ci(28位)和Di(28位)。

例如,原始64位密钥K=823452593FBCDDE7,经PC_1置换得到56位的初始密钥K'。

接下来分别是16轮的循环移位加置换操作得到16个子密钥。

图3.8PC_1置换表

第一轮对C0

和D0

循环左移后生成C1

和D1,C1

和D1

通过如图3.9所示的PC_2置换生成子密钥

K1。其中,第1、2、9、16轮运算只循环左移一位,其他轮都是左移两位。

图3.9PC_2置换表

第二轮对C1

和D1

循环左移后形成C2和D2,C2

和D2

再通过PC_2置换生成子密钥K2。以此类推,得到16个子密钥。

经过一系列的循环左移和PC_2置换操作,得到16个子密钥如下:

对应的DES密钥调度算法的Python实现代码如下:

3.2.3轮函数f

运算

经过初始置换和子密钥生成之后,后续就是16轮的轮函数计算。DES算法的轮结构如图3.10所示,整个过程分为四步:E扩展置换盒、子密钥异或、S替换盒运算、P置换盒。

图3.10f

函数运算

E扩展置换把明文数据的右半部分Ri

从32比特扩展到48比特,目的就是为了和48比特的子密钥保持长度一致以便于进行异或运算。类似的,扩展置换同样是根据扩展置换表(E-Box)改变比特位的次序,并增加比特位。E扩展置换如图3.11所示。

图3.11E扩展置换

在输入的6个比特当中,第1和第6比特表示对应S盒的行,第2、3、4、5比特表示S盒的列。例如,对于S2替换盒,其第1和第6比特是00,表示第0行;第2至第5比特为1111,表示第15列,对应的表项就是10,转换为二进制是1010。因此,输入的6个比特“011110”替换操作的结果就是“1010”,如图3.12所示。

图3.12S2替换盒

DES分组密码算法的8个S盒分别如下(见图3.13):图3.13S盒

P盒置换是f函数的最后一步,对8个S盒输出的32比特中间结果进行置换操作。P盒置换如图3.14所示。图3.14P盒置换

至此,整个f函数运算结束,其Python代码实现如下:

根据此前计算得到的明文和子密钥,给出了第一轮运算的结果如下:

接下来进行16轮的Feistel网络迭代。注意在最后一轮,左右两部分不交换,而是直接合并形成R16L16,然后进行逆初始置换IP-1操作。

3.2.4DES解密

DES解密过程和加密过程类似,同样是经过初始置换、16轮轮函数运算、逆初始置换。唯一不同的是加密和解密应用子密钥的顺序正好相反,其解密过程如图3.15所示。

图3.15DES解密

3.3DES安全性分析

3.3.1互补性由DES加密算法可知,C=EK（P

）。若明文P逐位取补(反),密钥K也逐位取补,则加密所得的结果C'是C

的补。这就是DES算法的互补性。若攻击者采取选择明文攻击,分别对明文P

及其补P'

进行加密,则有

3.3.2弱密钥和半弱密钥

如果给定初始密钥

K,最后产生的16轮的子密钥都相同,那么这个初始密钥

K

就是弱密钥。弱密钥

K

有以下性质:

即使用弱密钥

K

对明文P

加密两次或者解密两次皆可恢复出明文。

上述弱密钥产生的16个子密钥都是相同的,还有一些称为半弱密钥的密钥,其所产生的子密钥只有两种可能:SK1和SK2。每一个子密钥在运算的过程中分别使用8次。若两个半弱密钥

K1

和

K2

生成的子密钥恰好是对称的,那么由一个半弱密钥加密的信息可以通过另一个半弱密钥再次加密来解密,即EK1(EK2(P))=P。

以半弱密钥K1=011F011F010E010E和

K2=1F011F010E010E01为例,查看

K1

和K2

的子密钥及使用

K1

和

K2

连续加密两次明文的结果。

3.4多

重DES

3.4.1双重加密和中间相遇攻击双重加密(或二重DES加密)就是采用两个加密密钥

K1

和

K2

对明文进行两次加密:用第一个加密密钥

K1

加密后,再用另一个密钥

K2

进行第二次加密。解密则先用第二个加密的密钥

K2

解密,然后再用第一次加密的密钥

K1

进行解密,二重DES加密过程如图3.16所示。

图3.16二重DES加密

但二重DES的密钥总长度并不是我们所期望的112比特,事实上破译双重DES的难度为257量级。这种破译方法就是中间相遇攻击MeetInTheMiddleAttack),属于分治法攻击。假设攻击者有一对(明文、密文),攻击者首先暴力破解左边的加密,用所有可能的密钥

K1

对明文进行加密得到中间结果Z1,整个计算需要的攻击次数为256

次。然后攻击者再对右边的密文进行解密暴力破解,用所有可能的密钥

K2

对密文进行解密得到中间结果Z2,需要的攻击次数也是256

次。如果中间结果Z1

和Z2

当中的一条记录相等,则对应的K1

和

K2

就是正确结果,整个攻击的复杂度为256+256=257。对应的数学描述和图示(见图3.17)如下。

图3.17中间相遇攻击

若有明文、密文对(P,C)满足C=EK2(EK1(P)),则有Z=EK1(P)=DK2(C)。

整个中间相遇攻击的实现步骤:

(1)给定明文、密文对(P,C),以密钥K1

的所有256

个可能的取值对明文P

加密,并将密文C按顺序存储在表中;

(2)从密钥

K2

所有可能的256

个值中选出一个对密文C

解密,并将解密结果Z在上

述表中查找相匹配的值,一旦找到,则可确定密钥

K1

和

K2;

(3)用上述

K1

和

K2

依次对P

进行加密,若结果为C,则获得正确密钥。

根据二重分组加密代码,中间相遇攻击的过程如图3.18所示。图3.18中间相遇攻击恢复密钥

首先对明文进行穷举计算,并把结果保存到字典table当中。其中密码是3个字符,表示成16进制,就是6个字符,因此以下暴力破解代码用的是166。字典table是以密文为键(Key)、密钥为数值(Value)进行保存,便于后续搜索比对。左边爆破代码如下:

计算得到所有可能的

K1

以及密文,接着从已知密文开始,穷举

K2

的所有可能值。针对每个K2,解密密文,并把解密结果同table中的结果进行比对,一旦有匹配的,说明对应的密钥是正确的。右边解密爆破代码如下:

3.4.2三重加密

由于二重DES加密存在中间相遇攻击,一种更为安全的解决方法就是三重DES(3DES)。3DES使用3个56位的密钥(K1、K2、K3)对数据进行三次加密,其加密过程如图3.19所示。

相较DES而言,3DES的安全增强主要体现在以下两点:

(1)三次使用DES加密,攻击者很难通过密码分析直接攻击。

(2)总密钥位更长,使得可能的密钥空间