密码学教程 课件 3-分组密码

第三章分组密码

3.1概述

3.2DES（数据加密标准）3.3AES（高级加密标准）

3.4SM4（我国商用分组算法）

3.5分组密码的工作模式3.1概述为了克服统计分析，可以采用扩散和混淆两种基本方式。扩散：就是使明文的每一位影响密文中的许多位，这样可以隐蔽明文的统计特性。

混淆：密文的每一位受密钥尽可能多位的影响。

使密文和密钥关系复杂，从而统计分析更加困难。

换位变换可以实现有效的扩散，打乱明文字母之间、

字母组合之间的统计关系。

代替变换(非线性的)可以达到比较好的混淆效果。

不论是数、还是其它信息，经过编码后都变为二进制串，可称之为数据。如果对其加密，数据就是明文：11001011’10110010’

01101010’11101011’……..分组密码的加密是每次对一段明文进行加密，类似古典密码的多表密码：

……..每个明文段叫作一个明文分组，对应密文叫作密文分组。明文分组密钥密文分组En明文分组密钥密文分组De01…1101…P盒－permutationbox;S盒－substitutionbox。SP结构（替代－置换网络）：每轮处理整个分组明文，加解密算法不同。分组密码的整体结构有两种基本类型：（迭代类型）Feistel结构：每轮处理一半明文，加解密算法相同。DES是Feistel结构的代表；AES是SP结构的一个代表。乘积密码系统是S盒与P盒变换的组合，两者结合得到的密码系统比单独一种更强。这一方式成为数据加密标准DataEncryptionStandard(DES)的基础。

Feistel结构SP结构En

分组密码：

多次迭代一个轮函数，同时处理一组明文段。

密钥长度固定，且对不同明文段保持不变。序列密码：

产生（伪）随机的密钥流，每次处理一个明文字母。

加密过程简单，但需要密文与密钥同步。分组密码适用性更广，易于标准化；序列密码主要用于保密性，速度更快，可实时通信。

3.2DES（数据加密标准）DES（DataEncryptionStandard）从1977年提出（原计划用10年）到1997年被认为不安全，经历了20多年，是分组密码设计的一个典范。

一、DES的加解密过程

明文分组：64bit(即64位二进制串)密文分组：64bit密钥：64bit，其中8bit为校验位，实际56bit轮数：

16轮（圈）加密函数：8个6-4S盒；P置换。整体结构：FeistelLRLRLRIP-1IP16轮64bit64bit算法：整体结构步(轮)函数密钥扩展密钥扩展ffDES整体结构：32Bit！32Bit！64Bit！48Bit！一共16轮！64bit！注意：最后一轮不交换！DES的加密函数f：8个不同的6-4S盒！48bit！48bit！32bit！4×8=32bit查表！扩展并置换查表：输入6比特的首尾2位确定行，中间4位确定列，交叉处为输出。密钥扩展：64bit输入密钥！56bit－去掉8、16等8个监督位56bit48bit28bit循环移位，1、2、9、16轮左移1位，其它轮左移2位!Feistel结构：记住这个特点即可！！加密解密密钥反序L在右侧加两次，消掉！明文

M(8bit)IPT0(4bit)T1(4bit)f(T1,K1)T1(4bit)T2(4bit)IP-1密文组C(8bit)密钥K(8bit)P1C0(4bit)D0(4bit)4-置换Qf(T2,K2)T3(4bit)T2(4bit)4-置换RC1(4bit)D1(4bit)4-置换Q-14-置换R-1P2K1(6bit)C2(4bit)D2(4bit)P2K2(6bit)小DES（1）如果密钥扩展过程中，

P1=(41768253)，

P2=(571842)，Q=(3142)，R=(4312)，

输入主密钥为K=11001010，

求经密钥扩展后的K1和K2。（2）如果IP=(86421357)，

f函数如左图所示，

两个S盒见下页。S1P=(3,1,2,4)f(T,K)(4bit)K(6bit)E=(4,1,2,2,3,4)T(4bit)T’(6bit)Z2(3bit)Z1(3bit)S2U2(2bit)U1(2bit)(第1bit决定行,第2、3bit决定列)解：（1）经置换，C1D1=10010101，经P2得K1=001110C2D2=01100110，经P2得K2=010001。S101230301211320S201230213013021若已知明文01011100，在密钥K下得到的密文是什么？

并通过解密得到原明文验证加密的正确性。（2）T1=0010，T1’=000010，Z1=001，Z2=100U1=00，U2=11，f(T1,K1)=1001，T2=1110；T2’=011110，Z1=001，Z2=111，U1=00，U2=01，f(T2,K2)=0001，T3=0011，T4=1110，1111100001011100(86421357)01110010F

0010

1110

(54637281)

11111000

11001010(41768253)01100110(3142)F

0011

1110

(4312)10010101(2413)(3421)P200111001100110P2

010001

二、DES的特点

除密钥顺序之外，加密和解密步骤完全相同；

主要的批评：密钥太短，迭代次数可能太少，

S盒可能存在不安全隐患。

差分分析：通过分析明文对的差值（异或）对密文对的差值的影响来恢复某些密钥比特。

穷举攻击：现在人们利用网络计算可以在20多小时破译56位的DES。DES已变得不安全了。

线性分析：一种已知明文攻击，它试图建立起明文、密文和密钥之间的一组近似线性方程。

三、多重DES

为了提高安全性，防止穷举攻击，DES还有多重形式。

双重DES：

但存在中间相遇攻击：（已知一对明密文）穷举k2！穷举k1！

三重DES：

中间一层用解密形式是为了可以利用三重DES对单重DES加密的密文进行解密(

k1=k2或k2=k3)。DESk1mDESk2－1DESk3cDESk1－1DESk2DESk3－13.3AES（高级加密标准）

1997年美国国家标准技术研究所（NIST）征集AES(AdvancedEncryptionStandard)。

要求：（1）比三重DES快且至少与它一样安全；（2）分组长度为128bit；

密钥长为128bit，192bit和256bit；（3）算法要能抵抗已知的密码分析方法，无明显漏洞；（4）算法实现要有效率，有一定的灵活性（适应不同的环境），软硬件两种方法实现。15种算法参加第一轮评选，5种进入第二轮：

RC6、Rijndael、Serpent、Twofish、Mars2000年获胜者是Rijndael算法，是比利时密码设计者所作。

一、AES的加解密过程明文分组：128bit密文分组：128bit密钥：128、192、256bit轮数：10、12、14轮（圈）加密函数：8-8的S盒、P（行移位、列混合）密钥生成：扩展、递归总体结构：SP结构

10-14轮128bit128bit16个字节SP结构

AES是面向字节的算法：字节为最小单位进行处理。输入明文分组：128bit=16×8bit＝16个字节，排成4×4的字节数组，称为状态矩阵（StateMatrix）

按列排！轮函数就是对这个数组进行变换。乘以常数字（4字节）AES解密过程：加密过程的逆过程，需要相应的逆变换。

AddRoundKey：将每一轮的密钥与状态矩阵直接异或；

InvSubBytes：逆字节替代变换，需要8-8的逆s盒。InvShiftRows：逆行移位变换；InvMixColumns：逆列混合变换；

AES密钥扩展过程：

产生各轮子密钥，主密钥直接作为开始的轮密钥，

后面的由前面轮密钥字，经S盒等运算递归产生。

4个字节为1个字

AES中的列混合：AES是面向字节的算法——字节的运算！以下介绍字节替代和列混合这两个部件的实现原理二、AES中的运算

0000——0x00110——0x61100——0xC0001——0x10111——0x71101——0xD0010——0x21000——0x81110——0xE0011——0x31001——0x91111——0xF0100——0x41010——0xA0101——0x51011——0xB11000001——C1AES是面向字节的算法，最小单位是字节(Byte)。一个字节可用二位十六进制数表示。二进制串常表示为十六进制任意分组表示为128bit的二进制串，分为12个字节，每个字节表示为2位十六进制（省略0x），例如：

AES对此字节矩阵的处理即是对字节的运算，需要将所有字节组成的集合变为代数结构（可以加减乘除）。

仿照对“数”的处理，将这些数据视为“数”00000000=0x0000000001=0x01-----00001111=0x0F-----11111111=0xFF加、减、乘、除——域！运算结果还在此域中S盒——字节除法列混合——字节乘法1、中的运算（字节运算）

中一共有个元素，可以有多种方式表示，AES中用多项式表示（以便能进行乘/除运算）。

一个字节8bit：

对应多项式：

一个字节8比特，可以看作中的一个元素。例题：0x57即01010111，对应多项式：

对于域的加法就是多项式对应项相加，系数模二加：

‘57’

‘83’

01010111

10000011＝11010100‘D4’AES中两个字节相加的含义！对于域的减法，就是加上减法逆（就是本身）。对于域的乘法，要模一个8次既约多项式m(x)，AES中选取的

例题：‘57’·‘83’

对应：

二进制表示：01010111•10000011＝11000001十六进制表示：57•83＝c1AES中两个字节相乘的含义！

分配律！

复杂运算化简为简单运算的迭代都是乘x

乘一个x，相当于字节中的1左移1位

06=00000110=00000100+00000010=02+04

将一个字节表示为只有一个1的字节之和，而只有一个1的字节都是不断乘x得到的。

xtime()运算：x

b(x)

更高次的乘法可以通过重复使用xtime（）实现。

(1)如果，则xtime()运算就是左移一位，后补零；如果，则xtime()左移一位，后补零，再异或1b。

xtime()算法：例题：57

13=01010111

00010011

“13”=

00010011

=

00000001

+00000010

+00010000因此13=“01”+

“02”+

“10”字节13是16进制，不是十进制，十进制数对应19。

57

02=xtime(57)=xtime(01010111)=ae57

04=xtime(ae)=xtime(10101110)=4757

08=xtime(47)=xtime(01000111)=8e57

10=xtime(8e)=xtime(10001110)=0757

13=57

(01⊕02⊕10)

=57⊕ae⊕07=fe对于域的除法，也就乘以除数的乘法逆。一般地，可以利用多项式的扩展欧几里得算法求乘法逆。

例题：求多项式模的逆元。验证：表示为输入的线性组合两边模M(x),可得逆元。因为：或者采用以下迭代算法：每次剩余可表示为n与u的代数和。

注意顺序AES中规定：

53的字节代替。二进制为01010011，表示的域元素为例题：表示为二进制为11001010。

逆元为，

所以53代替为11101101，即“ed”。

注意顺序！2、系数在的多项式运算（字运算）

这时元素用多项式表示，就是系数在中的小于4次的多项式。

加法就是多项式对应项的系数相加，因此也就是中元素相加，即逐位模二加。

列混合是字的运算

AES中两个字相加的含义！乘法是多项式相乘后，模一个4次多项式，

AES中两个字相乘的含义！不是既约的：(01+01=00)

都成为四项之和为了进行解密，a(x)应当有逆。AES中的列混合：MDS码，最佳扩散性；重量轻，计算简单

例题：

AES列混合的性质：

混合前后两列的四个字节之和保持不变。

三、AES的特点

结构简单，适应性强；加解密结构相同，但是解密使用加密的逆模块；逆S盒逆S盒对于AES的攻击：主要利用AES代数结构的特点。

积分分析：通过预测几轮之后的积分值来猜测密钥。

代数攻击：用某种代数方程系统描述S盒。

侧信道攻击：加密中间过程电磁泄漏可能暴露密钥信息。

（sidechannelattack）（差分能量攻击）

AES的设计能够抵御已有的线性分析和差分分析；采用较大的S盒，并且能进行代数上的定义，而不像DES的S盒是“随机”代替（不易判断安全性）。宽轨迹策略Feistel结构SP结构En

3.4SM4（我国商用密码算法）SM4是2006年我国公布的商用分组密码算法。特点：分组长度和密钥长度都是128比特；加密算法和密钥扩展都是32轮非线性迭代；采用一个8*8的S盒；采用32bit的异或和移位运算L；结构为非对称的Feistel；加解密算法相同，只是轮密钥顺序颠倒。Electronic-CodeBook(ECB)：电码本模式Cipher-BlockChaining(CBC)：密码分组链接模式CipherFeedBack(CFB)：密码反馈模式OutputFeedBack(OFB)：输出反馈模式

为了防止攻击，分组密码需要有一定的工作模式。CFB和OFB两种模式：可利用分组密码实现流密码！3.5分组密码工作模式

（另外新的还有：计数器模式、加密认证模式等）这些模式适用于各种分组密码，以下仅以DES为例。DESDESm1c1km2c26464kDESkcnmnDES-1DES-1c1m1kc2m26464kDES-1kmncnECB模式（electroniccodebook）相同明文产生相同密文！以DES为例但这种模式存在以下问题：

相同明文对应相同密文。CBC

模式(cipherblockchaining)DESD