第3章分组密码-3

第3章分组密码本章主要内容概述 分组密码的设计原则与评估分组密码的设计方法数据加密标准－DES高级加密标准－AES 分组密码的工作模式其它分组密码

第3章分组密码3.1概述

分组密码具有速度快、易于标准化和便于软硬件实现等特点。通常是信息与网络安全中实现数据加密和认证的核心体制，它在计算机通信和信息系统安全领域有着最广泛的应用。第3章分组密码3.2分组密码的设计原则与评估

3.2.1分组密码的设计原则 针对安全性的一般设计原则明文分组长度和密钥长度望尽可能大混乱原则：又称混淆原则，是指密钥和明文以及密文之间的依赖关系尽可能的复杂扩散原则：密钥或明文的每一位影响密文的许多位以便隐蔽明文的统计特性 针对实现的设计原则软件实现的设计原则硬件实现的设计原则第3章分组密码 3.2.2分组密码的评估

(1)安全性

评估中的最重要因素，包括下述要点：算法抗密码分析的强度，可靠的数学基础，算法输出的随机性，与其他候选算法比较的相对安全性

(2)性能

在各种平台上的计算效率和对存储空间的需求

(3)算法和实现特性

灵活性、硬件和软件适应性、算法的简单性等

第3章分组密码3.3分组密码常见的设计方法

3.3.1Feistel结构

Feistel结构是典型的迭代密码.Feistel结构的解密与加密是完全一样的，除了所使用的子密钥的顺序正好相反。Li-1Ri-1FKiLi=Ri-1Ri=Li-1

F(Ri-1,Ki)

第3章分组密码 3.3.2SPN结构

SPN结构也是一种特殊的迭代密码。SPN结构和Feistel结构相比，可以得到更快速的扩散，但是SPN密码的加解密通常不相似。3.4S-DES(SimplifiedDES)S-DES全称SimplifiedDES，它是一个供教学而非安全的加密算法，与DES的特性和结构类似，但参数小，便于理解。S-DES算法的输入是一个8位的明文或者密文组和一个10位的密钥，输出是一个8位的密文或者明文组S-DES算法涉及五个函数：

(1)初始置换IP(initialpermutation)

(2)复合函数fk1，它是由密钥K确定的，具有置换和替代的运算

(3)转换函数SW

(4)复合函数fk2

(5)初始置换IP的逆置换IP-1加密算法的数学表示为：密文=IP-1(fk2(SW(fk1(IP(明文)))))

解密算法的数学表示为：明文=IP-1(fk1(SW(fk2(IP(密文)))))

整体框架如下：

第3章分组密码S-DES(SimplifiedDES)IPfkSWfkIP-1P10P8IPfkSWfkIP-1SHIFTSHIFTP8EncryptionDecryption8-bitplaintext8-bitplaintext8-bitciphertext8-bitciphertextK1K1K2K2第3章分组密码IPE/PS0S1P4E/PS0S1P4SWIP-1K1K244844224S-DES(SimplifiedDES)-F函数第3章分组密码k1k2k3k4k5k6k7k8k2k6k3k1k4k8k5k7若IP[]={2,6,3,1,4,8,5,7};则IP-I[]={4,1,3,5,7,2,8,6};IP-I是IP的逆置换IP-1(IP(X))=X;IP置换的输入是明文或者密文。

若明文X=01110110，则IP(X)=11101001；S-DES(SimplifiedDES)第3章分组密码IP置换k4k1k2k3k2k3k4k1k1k2k3k4S-DES(SimplifiedDES)-Expansion/Permutation(E/P）如果EP[]={4,1,2,3,2,3,4,1};则对于一个四位数的输入（n1,n2,n3,n4），它的直观结果是：n4

n1

n2

n3n2

n3

n4

n1将4位输入扩展成8位第3章分组密码S-Box运算上述结果的第一行输入进S-盒S0，产生2-位的输出；第二行的4位输入进S盒S1，产生2-位的输出。两个S盒按如下定义：

S盒按下述规则运算：

将第1和第4的输入比特做为2-bit数，指示为S盒的一个行；

将第2和第3的输入比特做为2-bit数，指示为S盒的一个列。如此确定为S盒矩阵的（i,j）数。

例如：0100为S0的输入，（P0,0,P0,3）=(00)=0,并且(P0,1,P0,2)=(10)=2，确定了S0中的第0行2列（0，2）的系数为3，记为（11）输出。第3章分组密码密钥的生成第3章分组密码S-DES算法实例P10[]={3,5,2,7,4,10,1,9,8,6};P8[]={6,3,7,4,8,5,10,9};P4[]={2,4,3,1};IP[]={2,6,3,1,4,8,5,7};IPI[]={4,1,3,5,7,2,8,6};EP[]={4,1,2,3,2,3,4,1};S0[][]={

{1,0,3,2},

{3,2,1,0},

{0,2,1,3},

{3,1,3,2},};S1[][]={

{0,1,2,3},

{2,0,1,3},

{3,0,1,0},

{2,1,0,3},};ciphertext=

01110110；key

=

011111

1101；1、计算两个子密钥K1

K2key经过P10置换得

t0=1111110011t0高低位循环左移一位，LS-1之后合并得

t1=1111100111t1经P8置换后计算得

K1=01011111t1高低位循环左移两位，LS-2之后合并为

t2=1111111100t2经P8置换后计算得

K2=111111002、第一轮fk函数密文经IP置换得

m=11101001对m取高低位

L=1110

R=1001经扩张/置换运算

E/P(R)=11000011与K2进行异或得

001111110011进入S盒S0中得到一个二位输出

101111进入S盒S1中得到一个二位输出

11两者合并得到一个四位输出

1011

上一轮结果经P4置换得到

0111上一轮结果与L按位异或得到

1001故第一轮fk函数的结果为

100110013、转换函数SW第一轮fk函数的结果经SW得

10011001第3章分组密码第二轮fk函数对上一轮结果（10011001）取高低位L=R=经扩张/置换运算 E/P(R)=与K1（01011111）进行异或得

进入S盒S0中得到一个二位输出进入S盒S1中得到一个二位输出

两者合并得到一个四位输出上一轮结果经P4置换得到上一轮结果与L按位异或得到故第二轮fk函数的结果为

第二轮fk函数结果经IP逆置换得得到

10011001P10[]={3,5,2,7,4,10,1,9,8,6};P8[]={6,3,7,4,8,5,10,9};P4[]={2,4,3,1};IP[]={2,6,3,1,4,8,5,7};IPI[]={4,1,3,5,7,2,8,6};EP[]={4,1,2,3,2,3,4,1};S0[][]={

{1,0,3,2},

{3,2,1,0},

{0,2,1,3},

{3,1,3,2},};S1[][]={

{0,1,2,3},

{2,0,1,3},

{3,0,1,0},

{2,1,0,3},};Ciphertext=

01110110；key

=

011111

110111000011100111001001110011011101

110101000100100100010110第3章分组密码第3章分组密码3.5数据加密标准－DES

DES是一种明文分组为64比特，有效密钥56比特，输出密文64比特的，具有16轮迭代的分组对称密码算法，DES由初始置换，16轮迭代，初始逆置换组成。输入64位比特明文初始置换IP置换表在密钥控制下16轮迭代交换左右32bitIP逆置换表输出64位比特密文3.5数据加密标准－DESround1函数fLi-1

（32bit）Ri-1

（32bit）Ri=Li-1⊕f(Ri-1,ki)Li=Ri-1Kiround2round16第3章分组密码可以看出，DES加密需要四个关键点：(1)IP置换表和IP-1逆置换表;(2)函数f;(3)子密钥Ki。(4)S盒的工作原理。DES算法的实现步骤第3章分组密码3.5数据加密标准－DES

（1）IP置换表IP置换表58504234261810260524436282012462544638302214664564840322416857494133251791595143352719113615345372921135635547393123157输入的第1位被置换到第40位输入的第2位被置换到第8位40848165624643239747155523633138646145422623037545135321612936444125220602835343115119592734242105018582633141949175725输入的第40位作为第1位输入的第8位作为第2位IP-1逆置换表3.5数据加密标准－DES第3章分组密码IP置换表（续）M=(m1,m2,…..)12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455561234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556IP(M)=(m58,m50

)=(m1

1,m1

2,…..)5850423426181026052443628201246254463830221466456484032241685749413325179161584537292113563554739312315740848165624643239747155523

63

3138646145422623037545135321612936444125220602834242105018582633141949175725IPIP-11第3章分组密码DES算法的实现步骤-（2）f函数函数f(Ri-1,Ki)有两个输入：32位的Ri-1和48位子密钥Ki，f函数的处理流程如下图所示。第3章分组密码子密钥（Ki)第3章分组密码 E-扩展运算

E-扩展运算是扩位运算，将32比特扩展为48比特，用方阵形式可以容易地看出其扩位方法，其中粗方框中的为原始输入数据。3.5数据加密标准－DES第3章分组密码(3)压缩替代S盒(SubstitutionBox)3.5数据加密标准－DES48bit块通过S盒压缩成32bit块48bit寄存器32bit寄存器

S1S2S3S4S5S6S7S86bit4bit共8个S盒第3章分组密码(3)压缩替代S盒(SubstitutionBox)S1盒1441312151183106125907015741421311061211953841148136211151297310501512824917511314100613作用：将6个输入位映射为4个输出位；方法：若定义6个输入位为a1a2a3a4a5a6，a1代表第1位，a6代表第6位，将a1a6组成2位二进制数，对应S盒表中的行号；将a2a3a4a5组成一个4位的2进制数，对应S盒表中的列号；映射到交叉点的数据就是该S盒的输出。输入为101011的输出是？？？交叉点数据为9转化为二进制为：1001a1a6=11->3->第3行a2a3a4a5=0101->5->第5列3.5数据加密标准－DES第3章分组密码（4）置换函数P（Permutaion）P置换的目的是：提供雪崩效应；明文或密钥的一点小的变动都引起密文的较大变化；16072021291228170115232605183110020824143227030919133006221104253.5数据加密标准－DES第3章分组密码DES结构

3.5数据加密标准－DES子密钥生成器密钥(56bit)PC-1K1C0置换选择1D0LS1LS1C1D1LS2LS2C2D2PC-2置换选择228bit28bit56bitK2PC-256bitLS16LS16C16D16K16PC-256bit48bit48bit48bit第3章分组密码3.5数据加密标准－DES循环左移1234567811222222091011121314151612222221密钥表的计算逻辑：轮数574941332517915850423426181025951432527191136052443663554739312315762544638302214661534537292113528201241417112415328156211023191242681672720132415231374755304051453348444939563453464250362932置换选择1置换选择2子密钥生成器-置换选择第3章分组密码3.5数据加密标准－DES第3章分组密码3.5.2DES的安全性分析DES算法正式公开发表以后，引起了一场激烈的争论。1977年Diffie和Hellman提出了制造一个每秒能测试106个密钥的大规模芯片，造价昂贵1997年1月28日，美国的RSA公司在互联网上开展了一项名为“密钥挑战”的竞赛，悬赏一万美元，破解一段用56比特密钥加密的DES密文。1997年6月17日Rocke和志愿者们成功地找到了密钥，在计算机上公布了明文：“Strongcryptographymakestheworldasaferplace”。第3章分组密码3.5.3三重DES

为了增强DES算法的安全性，人们提出了许多DES的改进方案。其中，称为三重DES的多重加密算法是DES的一个重要的改进算法。DES解密DES加密DES加密DES加密DES解密DES解密明文M密文CK1K2K3加密这周五实验，在242第3章分组密码3.5高级加密标准－AES

AES是DES的替代者。1997年9月12日，NIST发布了征集算法的正式公告，要求AES具有128比特的分组长度，并支持128、192和256比特的密钥长度，而且要求AES要能在全世界范围内免费使用。

2000年10月2日，Rijndael算法被选择为高级加密标准。

AES的候选算法根据以下三条主要原则进行评判安全性代价算法与实现特性3.5.1AES算法的数学基础

AES中的运算是按字节的，并把一个字节看成是系数在有限域GF(2)上的次数小于8的多项式（即把一个字节看成是有限域GF(28)中的一个元素)。

一、有限域GF(28)

可以把出b7b6b5b4b3b2b1b0构成的一个字节看成是系数在(0,1)中取值的多项式：

b7x7+

b6x6+

b5x5+

b4x4

+

b3x3+

b2x2+

b1x

+

b0

如{57}（01010111）可写成：x6+

x4

+

x2+

x

+

1注：57H第3章分组密码1.多项式加法

在多项式表示中，两个元素的和是一个多项式，其系数是两个元素的对应系数的模2加(即异或)。例如：“57”和“83”的和为：57⊕83＝D4，或者采用其多项式记法：57→01010111→x6+x4+x2+x+183→10000011→x7+x+1(x6+x4+x2+x+1)+(x7+x+1)＝x7+x6+x4+x2→11010100→D4显然，该加法与简单的以字节为单位的比特异或是一致的。

01010111⊕10000011110101002.多项式乘法

有限域GF(28)中两个元素的乘法为模2元域GF(28)上的一个8次不可约多项式的多项式乘法。对于AES这一8次不可约多项式为例：

m(x)=x8+x4+x3+x+1用十六进制表示为{9B}。第3章分组密码

【例】计算：5783=？

(x6+x4+x2+x+1)

(x7+x+1)=x13+x11+x9+x8+x7+x7+x5+x3+x2+

x+x6+x4+x2+x+1=x13+x11+x9+x8+x6+x5+x4+x3+

1而:(x13+x11+x9+x8+x6+x5+x4+x3+

1)modm(x)=(x13+x11+x9+x8+x6+x5+x4+x3+

1)mod(x8+x4+x3+x+1)；计算时按降幂排

=x7+x6+1所以：(x6+x4+x2+x+1)

(x7+x+1)=x7+x6+1(多项式表示)0101011110000011=11000001(2进制表示)5783=C1(16进制表示)第3章分组密码3.x乘法考虑用x乘以多项式B(x):(b7b6b5b4b3b2b1b0)B(x)＝b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+

b1x

+

b0

x

B(x)＝b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+

b1x2

+

b0x将上面的结果模m(x)求余就得到x

B(x)。如果b7＝0，则：x

B(x)＝b6x7+b5x6+b4x5+b3x4+b2x3+

b1x2

+

b0x

即所得结果字节为：(b6b5b4b3b2b1b00)如果b7＝1，则：x

B(x)＝x8+b6x7+b5x6+b4x5+b3x4+b2x3+

b1x2

+

b0xmod(x8+x4+x3+x+1)=x8+b6x7+b5x6+b4x5+b3x4+b2x3+

b1x2

+

b0x+(x8+x4+x3+x+1)·1=b6x7+b5x6+b4x5+b3x4+b2x3+

b1x2

+

b0x+(x4+x3+x+1)

即所得结果字节为：(b6b5b4b3b2b1b00)⊕(00011011)所以，x

B(x)=(b6b5b4b3b2b1b00)；b7＝0(b6b5b4b3b2b1b00)⊕(00011011)；b7＝1第3章分组密码第3章分组密码例1：f(x)=x6+x4+x2+x+1,g(x)=x7+x+1,m(x)=x4+x3+x+1，求f(x)*g(x)modm(x)现在我们用二进制运算的方法来计算，即（01010111）*(10000011).首先要求出x幂乘01010111的中间结果：（01010111）*(00000010)=(10101110)(01010111)*(00000100)=(01011100)⊕(00011011)=(01000111)(01010111)*(00001000)=(10001110)(01010111)*(00010000)=(00011100)⊕(00011011)=(00000111)(01010111)*(00100000)=(00001110)(01010111)*(01000000)=(00011100)(01010111)*(10000000)=(00111000)所以：(01010111)*(10000011)=(01010111)*[(00000001)+（00000010）+（10000000)] =(01010111)⊕(10101110)⊕(00111000)=(11000001)11000001等价于x7+x6+1第3章分组密码二、GF（28）域上的多项式

一个（4字节）字可以看作是GF（28

）域上的多项式，每个字对应于一个次数小于4的多项式。1.多项式加法

多项式加法通过对应的系数简单相加可以实现。2.多项式乘法

GF(28)域上的多项式乘法为模M(x)=x4+1的乘法。AES概述在Rijndael算法中，分组长度和密钥长度均能分别被指定为128位，192位或256位。在高级加密标准规范中，密钥长度可以使用三者中的任意一种，但分组长度只能是128位在本例题中假定密钥的长度为128位，这是最广泛的实现方式Rijndael具有如下特性：所有已知的攻击具有免疫性在各种平台上，其执行速度快而且代码紧凑设计简单AES加密和解密流程1．给定一个明文M，将轮密钥与M异或（称为AddRoundKey）；2．对前Nr-1轮中的每—轮，用s盒进行一次替换操作（称为SubBytes）；对替换的结果做行移位操作（称为ShiftRows）；再对结果做列混淆变换（称为MixColumns）；然后进行AddRoundKey(轮密钥加）操作。3．在最后一轮中依次进行SubBytes、ShiftRows和AddRoundKey操作。4．得到密文C。AES（Rijndael）结构AES的数据结构在我们的例子中，加密算法的输入分组和解密算法的输出分组均为128位输入分组时以字节为单位的正方形矩阵描述的该分组被复制到state数组，这个数组在加密或解密的每个阶段都会被改变。在执行了最后的阶段后，state被复制到输出矩阵。128位的密钥也是用以字节为单位的矩阵描述的。然后这个密钥被扩展成为一个以字为单位密钥序列数组；每个字由四个字节组成，128位的密钥最终扩展为44字的序列。AES的数据结构AES结构AES结构的一个显著特征是它不是Feistel结构。在Fiestel结构里，数据分组中的一半被用来修改数据分组中的另一半，然后交换两部分。然而Rijndael在内的两个AES最终候选算法没有使用Feistel结构，而是每一轮都使用代换和混淆并行地处理整个数组分组输入的密钥被扩展成由44个32位字所组成的数组w[i]。从图中可以看出在每轮加解密过程中有4个字（128位）的密钥是作为该轮的密钥AES结构该结构由四个不同的阶段组成，包括一个混淆和三个替换：字节替换行移位列混淆：一个利用在域GF（28）上的算术特性的代换算法简单，仅仅在轮密钥加阶段中使用密钥。每个阶段均可逆。对字节替换，行移位和列混淆，在解密算法中用与他们相对应的逆函数与大多数分组密码一样，解密算法按逆序方式利用了扩展密钥AES分组AES替换移位列混淆列混合变换MixColumns()对一个状态逐列进行变换，它将一个状态的每一列视为有限域GF(28)上的一个多项式。在列混合变换中，每一列所表示的多项式将乘以一个固定的多项式C(x)，

C(x)={03}x3+{01}x2+{01}x

+{02}对应4字节向量为(03010102)，模多项式为(x4+1)。87F24D976E4C90EC46E74AC3A68CD8954740A34C37D4709F94E43A42EDA5A6BC轮密钥加AES密钥扩展KeyExpansion（密钥扩展）

将输入的密钥扩展为11组128位密钥组，其中第0组为输入密钥本身

其后第n组第i列为第n-1组第i列与第n组第i-1列之和（模2加法也就是异或，1<=i<=3）对于每一组第0列即i=0，有特殊的处理将前一列即第n-1组第3列（i=3）的4个字节循环左移1个字节，并对每个字节进行字节替代变换SubBytes将第一行（即第一个字节）与轮常量rc[n]相加

最后再与前一组该列相加

i=0i=1i=2i=3RotWordSubWord第3章分组密码3.6分组密码的工作模式

3.6.1电子密码本模式（ECB）特点：(1)

一种最简易的工作方式；(