第3章分组密码体制



3．1概述

设明文消息编码表示后的二元数字序列为M={x0，x1,…,xk，…}。分组密码首先将M划分成长为m的组块Bi=(xi×m，xi×m+1,…,xi×m+m-1)(长为m的向量)的集合，然后各组分别在密钥K的控制下变换成长度为n的组块Ci=(yi×n，yi×n+1,…,yi×n+n-1)(长为n的向量)。若n>m，则为有数据扩展的分组密码； 若n<m，则为有数据压缩的分组密码； 若n=m，则为无数据扩展和压缩的分组密码，通常研究的是最后这种情况。

通常记EK(·)为密钥为K时的加密函数，称EK(·)的逆函数为密钥为K时的解密函数，记为DK(·)。分组密码的数学模型如图3．1所示。



图3．1分组密码的数学模型


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

3．2分组密码的设计原则与评估
3．2．1分组密码的设计原则
分组密码的设计就是找到一种算法，能在密钥控制下从一个足够大且足够“好”的置换子集合中简单而迅速地选出一个置换，用来对当前输入的明文进行加密变换。一个好的分组密码应该既难破译又容易实现。加密函数Ek(·)和解密函数Dk(·)都必须是容易计算的，但是要从方程y=Ek(x)或x=Dk(y)中解出密钥k应该是一个困难问题。分组密码的设计原则可以分为安全性原则和实现原则。

1． 针对安全性的一般设计原则

分组长度和密钥长度： 当明文分组长度为n位时，至多需要2n个明文—密文对就可以破解该密码。同理，当密钥长度为n位时，对一个截获的密文，至多需要试验2n个密钥就可以破解所使用的密钥。因此从安全性角度来考虑，明文分组长度和密钥长度应尽可能大。

扰乱原则： 又称混淆原则，是指人们所设计的密码应使得密钥和明文、密文之间的依赖关系足够复杂，以至于这种依赖性对密码分析者来说是无法利用的。

扩散原则： 人们所设计的密码应使得密钥的每一位影响密文的许多位，以防止对密钥进行逐段破译； 而且明文的每一位也应影响密文的许多位，以便隐藏明文的统计特性。

另外还有一个重要的设计原理： 密码体制必须能抵抗现有的所有攻击方法。

2． 针对实现的设计原则

分组密码可以用软件或硬件来实现。硬件实现的优点是可获得高速率，而软件实现的优点是灵活性强、代价低。基于软件和硬件的不同性质，分组密码的设计原则可根据预定的实现方法来考虑。

软件实现的设计原则： 使用子块和简单的运算。密码运算在子块上进行，要求子块的长度能自然地适应软件编程，如64、128和256位等(想想看为什么)。在软件实现中，按位置换是难于实现的，因此应尽量避免使用。子块所进行的密码运算应该是一些易于软件实现的，最好是标准处理器所具有的基本指令，如加法、乘法和移位等。

应用密码学(第3版)

第3章分组密码体制

硬件实现的设计原则： 加密和解密的相似性，即加密和解密过程的区别应该仅仅在于密钥的使用方式不同，以便同样的器件既可用来加密，又可用来解密； 尽量使用规则结构，因为密码应有一个标准的组件结构以便其能适于用超大规模集成电路实现。

3．2．2分组密码的评估

对分组密码的评估主要有3个方面：安全性；性能；算法和实现特性。

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

算法性能主要包括在各种平台上的计算效率和对存储空间的需求。计算效率主要是指算法在用软硬件实现时的执行速度。

算法和实现特性主要包括： 灵活性、硬件和软件适应性、算法的简单性等。算法的灵活性是指可以满足更多应用的需求，例如： (1)密钥和分组长度可以进行调整； (2)在许多不同类型的环境中能够安全、有效地实现； (3)可以为序列密码、HASH函数等的实现提供帮助； (4)算法必须能够用软件和硬件两种方法实现。另外，算法设计应相对简单也是一个评估因素。

3．3分组密码的基本设计结构

分组密码算法各不相同，但有些重要的结构在很多分组密码算法中都会有所应用。当今绝大多数的分组密码都是乘积密码。所谓乘积密码，就是以某种方式连续使用两个或多个密码，以使得所得到的最后结果或乘积比使用其中任意一个密码都更强。乘积密码通常伴随一系列置换与代换操作，常见的乘积密码是迭代密码，即对同一个密码进行迭代使用。下面首先介绍分组密码设计所使用的四种常用结构，然后再介绍基本结构的细化。

3．3．1Feistel结构

Feistel结构是Horst FeistelHorst Feistel，德国密码学家，曾在IBM公司从事密码设计工作，是最早研究分组密码设计和理论的非政府研究人员之一。于1973年在设计Lucifer分组密码时发明的，随着分组密码算法DES(Data Encryption Standard)的使用而流行。许多分组密码算法采用了Feistel结构，以下会对其中部分算法进行介绍。



图3．2Feistel结构的第i轮

Feistel结构是典型的迭代密码，图3．2是其一轮的结构示意图。对一个分组长度为2n位的r轮Feistel型密码，其加密过程如下： 

(1) 给定明文P，记P=L0R0，这里L0是P的最左边n位，R0是P的最右边n位。

(2) 进行r轮完全相同的运算，如第i(1≤i ≤r)轮的运算如下： 
Li=Ri-1
Ri=Li-1F(Ri-1,Ki)
这里的F是轮函数，K1，K2，…，Kr是由种子密钥生成的子密钥。

(3) 输出密文C=RrLr。


Feistel结构保证了加密过程的可逆性，因为： 
Ri-1=Li
Li-1=Ri F(Li,Ki)
再注意到，Feistel结构在加密的最后一轮略去“左右交换”，可以看出Feistel结构的解密与加密是完全一样的，除了所使用的子密钥的顺序正好相反。 

“加解密相似”是Feistel型密码在实现上的优点。但另一方面，Feistel型密码的扩散要慢一些。例如，算法至少需要两轮才能改变输入的每一位。这导致Feistel型密码的轮数较多，一般大于或等于16。

3．3．2SPN结构


SPN(SubstitutionPermutation Network)结构也是一种特殊的迭代密码，著名分组密码算法AES(Advanced Encryption Standard)就是基于此结构。


图3．3SPN型密码的一轮加密过程

SPN结构分为两层： 第一层为S层，也称为替换层，主要起扰乱的作用； 第二层为P层，也称为置换层，主要起扩散的作用。

在这种密码的每一轮中，首先输入被作用于一个由密钥控制的可逆函数S，然后再被作用于一个置换(或一个可逆的线性变换)P。SPN结构如图3．3所示，其中Xi表示第i轮的输出，也就是第i+1轮的输入。 

SPN结构和Feistel结构相比，可以得到更快的扩散，但是SPN密码的加解密通常不相似。

3．3．3Feistel结构的变种

在基本Feistel结构的基础上，又发展出多种衍生结构，如三类广义Feistel 结构、收缩 Feistel 结构、扩张 Feistel 结构等［2］［11］。以下介绍三类Feistel结构变种。

Type1型广义Feistel结构继承了Feistel结构加解密相似的特点。该结构提出后受到了广泛的关注，CAST256算法就采用了Type1型广义Feistel结构。该结构的表达式为
gi(Xi,1,Xi,2，…，Xi,d)=Fi(Xi,1Ki)Xi,2,Xi,3，…，Xi,d,Xi,1，若1≤i<r；Xi,1,Fi(Xi,1Ki)Xi,2,Xi,3，…，Xi,d，若i=r
以四路Type1结构为例，其结构如图3．4所示。

Type2型广义Feistel结构同样继承了Feistel结构加解密相似的优点。CIEFIA算法就采用了Type2型广义Feistel结构。同样，Type2型广义Feistel结构由图3．5通过r轮迭代得到，最后一轮取消拉线变换。




图3．4四路Type1结构




图3．5四路Type2结构



设第i圈从左向右数的第j个轮函数为Fi,j(1≤j≤d/2)，轮子密钥为Kij∈{0,1}n/d，第i圈的d个输入分别为Xi,1,Xi,2，…,Xi,d∈{0,1}n/d。每一圈的函数表达式为
gi(Xi,1,Xi,2，…，Xi,d)=
(Fi,1(Xi,1Ki,1)Xi,2,Xi,3,Fi,2(Xi,3Ki,2)Xi,4,…,
Fi,d2Xi,d-1Ki,d2Xi,d,Xi,1),若1≤i<r; (Xi,1,Fi,1(Xi,1Ki,1)Xi,2,Xi,3,Fi,2(Xi,3Ki,2)Xi,4,…,
Fi,d2Xi,d-1Ki,d2Xi,d),若i=r


图3．6四路Type3结构

Type3型广义Feistel结构与Type1型和Type2型广义Feistel结构一样，其与Type1型和Type2型最大的区别为每圈的圈函数中含有的非线性轮函数数目。Type1型广义Feistel结构每圈有一个非线性轮函数，Type2型广义Feistel结构每圈有d/2个非线性轮函数，Type3型广义Feistel结构每圈有d-1个非线性轮函数。Type3型广义Feistel结构如图3．6所示。

设第i圈从左向右数的第j个轮函数为Fi,j(1≤j≤d/2)，轮子密钥为Ki,1，Ki,2，…，Ki,d-1∈{0,1}n/d，第i圈的d个输入分别为Xi,1,Xi,2，…,Xi,d∈{0,1}n/d。第i圈的函数表达式如下： 
gi(Xi,1,Xi,2，…,Xi,d)=
(Fi,1(Xi,1Ki,1)Xi,2,Fi,2(Xi,2Ki,2)Xi,3,…,
Fi,d-1(Xi,d-1Ki,d-1)Xi,d-1,Xi,1),若1≤i<r; 
(Xi,1,Fi,1(Xi,1Ki,1)Xi,2,Fi,2(Xi,2Ki,2)Xi,3,…,
Fi,d-1(Xi,d-1Ki,d-1)Xi,d-1),若i=r
3．3．4LaiMassey结构

LaiMassey结构由Serge VaudenaySerge Vaudenay，法国密码学家，于2006年当选国际密码学研究协会理事。提出，该结构由模加、减运算和一个正型置换σ构建而成。实际上，LaiMassey结构出自Lai来学嘉，上海交通大学教授，中国密码学家。和James Lee MasseyJames Lee Massey，信息理论家和密码学家，苏黎世联邦理工学院数字技术名誉教授。在1990年共同提出的IDEA分组密码算法［13］，在当时被称为PES(Proposed Encryption Standard，推荐加密标准)。2000年，Vaudenay提取出IDEA中的结构来构建一般化的密码模型［3］，并且用原设计者的名字为之命名。LaiMassey结构虽然不如Feistel结构著名，但其优点为实现代价低，运算速度快。LaiMassey结构的运算有群中加和减，这里仅仅对运算的情况进行介绍。LaiMassey结构如图3．7所示。



图3．7LaiMassey结构

令x∈{0,1}2n，F为轮函数，定义基本LaiMassey结构LMp(x,y)∈P2n如下： 
LMp(x,y)=(xF(Δ,K),yF(Δ,K)),
其中Δ=xy
因为x0y0=x1y1，任意轮的LM结构都不具有伪随机性。这个问题可以通过对左侧的输入加入一个σ函数，对x做一个简单变换来解决。例如，σ(xL,xR)=(xR,xLxR)并且LaiMassey结构中的模运算也统一为异或运算时，有
LMp(x,y)=((σ(xRFR(Δ,K))‖(xLxRFR(Δ,K)FL(Δ,K)),yF(Δ,K))
LaiMassey结构是一个典型的密码结构，被广泛应用于算法领域，其中包括分组密码算法IDEA和FOX［3］等。由Vaudenay等人对LaiMassey结构的分析结果可知，加入了上述变换的四轮LaiMassey结构在传统的安全性假设下可以实现强伪随机性，而三轮LaiMassey结构只能具有伪随机性［12］。

3．3．5基本设计结构的细化

实际上，在设计现代分组密码算法时，很多时候会基于多种结构，这些结构会进一步考虑其中涉及的子模块函数所使用的结构，从而得到具体细化的整体结构。其中，通常把Feistel结构和SPN结构结合起来，就可以得到一些细化的分组密码算法的整体结构［4］： 

（1） FeistelFeistel结构： 算法整体结构是Feistel结构，轮函数F也采用Feistel结构。特别地，三轮Feistel结构具有伪随机性。

（2） FeistelSPN结构： 算法整体结构是Feistel结构，轮函数F釆用SPN结构。

（3） SPNFeistel结构： 算法的整体结构是SPN结构，轮函数F中嵌套Feistel结构。

除此之外，还有其他一些设计结构，如SPNSPS结构(其中SPS是指SubstitutionPermutationSubstitution函数)、将广义Feistel结构和SPN结构结合的GFNSPN结构等。

3．4数据加密标准DES

1972年，美国国家标准局(NBS)制定了一个保护计算机和通信开发计划，准备开发一个标准的密码算法，来规范密码技术应用的混乱局面。要求这个算法能够被测试和验证，不同设备间可以互操作，且实现成本低。

1973年5月15日，NBS在《联邦记事》上发布了征集保密传输存储系统中计算机数据密码算法的请求及相关的技术、经济和兼容性要求如下： 

(1) 算法具有较高的安全性，安全性仅依赖于密钥，不依赖于算法； 

(2) 算法完全确定，且易于理解； 

(3) 算法对任何用户没有区别，适合于各种用途； 

(4) 实现算法的电子器件必须很经济； 

(5) 算法必须能够验证和出口。

但是，由于公众此前对密码知识的缺乏，所以，虽反响强烈，但提交的方案均不理想。

1974年8月27日，NBS再次发布征集公告，第一次IBM公司提交了一个良好的候选算法。该算法是Luciffer密码算法的改进，由Feistel于1971年设计。1975年3月17日，NBS在《联邦记事》上公布了这一算法的细节，随后发表通知，征求公众的评论。

尽管受到了强烈的批评和责难，1976年11月23日，这一算法还是被采纳为联邦标准，并授权在非密级的政府通信中使用。该标准的正式文本FIPS PUB46(DES)在1977年1月15日公布，其他文件如FIPS PUB81(DES工作方式)、FIPS PUB74(DES实现和使用指南)、FIPS PUB112(DES口令加密)、FIPS PUB113(DES计算机数据监别)等联邦信息处理标准也相继于20世纪80年代初公布。1981年，美国国家标准研究所(ANST)批准DES作为私营部门的数据加密标准，称为DEA，相关文件如ANSI X3．92(DEA)、ANSI X3．106(DEA工作方式)、ANSI X3．105(网络加密标准)等相继公布。

3．4．1算法描述

DES是一种明文分组为64位、有效密钥为56位、输出密文为64位的，具有16轮迭代的分组对称密码算法。DES由初始置换、16轮迭代和初始逆置换组成。

1． DES的基本运算

1) 初始置换IP和初始逆置换IP-1

表3．1和表3．2分别给出了初始置换IP和初始逆置换IP-1。从表中容易看出这两个置换是互补的。


表3．1初始置换IP



585042342618102

605244362820124
续表


625446383022146

645648403224168

57494133251791

595143352719113

615345372921135

635547393123157




表3．2初始逆置换IP-1



408481656246432

397471555236331

386461454226230

375451353216129

364441252206028

353431151195927

342421050185826

33141949175725


2) E扩展运算

E扩展运算是扩位运算，将32位扩展为48位，用方阵形式可以容易地看出其扩展位，其中中间四列为原始输入数据，如表3．3所示。


表3．3E扩展运算



3212345

456789

8910111213

121314151617

161718192021

202122232425

242526272829

28293031321


3) S盒运算

S盒运算由8个S盒函数构成，如下：
S(x1x2…x48)=S1(x1…x6)‖S2(x7…x12)‖…‖S8(x43…x48)
其中，每一个S盒都是6位的输入、4位的输出。Si(h1…h6)的值对应表3．4的si中(h1h6)2行和(h2h3h4h5)2列上的值，其中(h1h6)2和(h2h3h4h5)2为二进制表示，即，Si(h1…h6)=si((h1h6)2，(h2h3h4h5)2)。


表3．4S盒运算




0123456789101112131415

S1
01441312151183106125907

10157414213110612119538

24114813621115129731050

31512824917511314100613


S2
01518146113497213120510

13134715281412011069115

20147111041315812693215

31381013154211671205149


S3
01009146315511312711428

11370934610285141211151

21364981530111212510147

31101306987415143115212


S4
07131430691012851112415

11381156150347212110149

21069012117131513145284

33150610113894511127214


S5
02124171011685315130149

11411212471315015103986

24211110137815912563014

31181271142136150910453


S6
01211015926801334147511

11015427129561131401138

29141552812370410113116

34321295151011141760813


S7
04112141508133129751061

11301174911014351221586

21411131237141015680592

36111381410795015142312


S8
01328461511110931450127

11151381037412561101492

27114191214206101315358

32114741081315129035611



4) P置换

P置换是对8个S盒的输出进行变换，可以扩散单个S盒的效果，如表3．5所示。


表3．5P置换



167202129122817

11523265183110

282414322739

19133062211425


2．  DES结构

DES是一个16轮的Feistel型密码，它的分组长度为64位，密钥长度为56位。在进行16轮加密之前，先对明文做一个固定的初始置换IP，IP(M)=L0R0。在16轮加密之后，对比特串L16 R16换位为R16L16后做逆置换IP-1来给出密文C，如图3．8所示。DES的一轮加密如图3．9所示。




图3．8DES的总体结构





图3．9DES的轮函数



其中 f 函数为f(R，Ki)=P(S(KiE(R)))，如图3．10所示。



图3．10DES的f函数


3．4．2密钥扩展算法

DES的每一轮都使用不同的、从算法密钥K导出的48位子密钥Ki(也称轮密钥)。密钥是一个64位的分组，但是其中8位用于奇偶校验，所以密钥的有效位只有56位。子密钥的生成过程如下： 

(1) 给定一个64位的密钥K，删掉8个校验位并利用一个固定的置换PC1(见表3．6)来置换剩下的56位，记PC1(K)=C0D0，这里C0是PC1(K)的前28位，D0是后28位。

(2) 对每一个i（1≤i≤16），计算
Ci=LSi(Ci-1)
Di=LSi(Di-1)
Ki=PC2(CiDi)
其中LSi表示一个或两个位置的左循环移位，LSi的具体取值见表3．7； PC2是另一个固定置换，如表3．8所示。密钥方案的计算过程如图3．11所示。


表3．6置换选择PC1



5749413325179

1585042342618

1025951433527

1911360524436

63554739312315

7625446383022

1466153453729

211352820124




表3．7LSi的取值



轮数(i)12345678910111213141516

LSi1122222212222221




表3．8置换选择PC2



1417112415328

15621102319124

2681672720132

4152313747553040

5145334844493956

3453464250362932





图3．11子密钥生成算法


3．4．3三重DES算法

DES运用了置换、替代、代数等多种密码技术，算法结构紧凑，条理清楚，而且加密与解密算法类似，便于工程实现。

然而，从DES诞生之日起，人们就对它的安全持怀疑态度，并展开了激烈的争论，主要表现在以下几点。

1. S盒的设计准则

这个问题涉及美国国家安全局(NSA)，他们修改了IBM公司的S盒。虽然修改后的S盒满足IBM公司关于S盒的设计原则，但是，人们还是怀疑NSA在S盒中嵌入了陷门，使得NSA可以借助于这个陷门及56位的短密钥解密DES。

在1990年以前，S盒的设计准则一直没有公布，直到差分密码分析方法发表后才公布。公布的S盒设计准则如下。

P1： S盒的每一行是整数0，1，…，15的一个置换； 

P2： 没有一个S盒是它输入的线性或仿射函数； 

P3： 改变S盒的一个输入位至少会引起两位输出的改变； 

P4： 如果固定输入的最左边和最右边的2位，变换中间4位，则每个可能的4位输出只能得到一次； 

P5： 如果两个输入仅中间2位不同，则它们的输出至少有2位不同； 

P6： 对任何一个S盒，如果两个输入的前两位不同，而最后两位相同，则两个输出一定不同； 

P7： 对任何一个S盒，如果固定一个输入位保持不变而使其他5位输入变化，观察一个固定输出位的值，使这个输出位为D的输入的数目与使这个输出位为I的输入的数目总数接近相等； 

P8： 在有相同且非零的差分的32对输入中，至多有8对具有相同的输出差分。

但是，S盒的设计准则还没有完全公开，我们仍然不知道S盒的构造中是否使用了进一步的设计准则，这也使得人们的猜测无法消除。

2. 56位有效密钥太短

对DES的批评中，最中肯的是关于DES密钥长度的争议。实际上，在IBM公司最初向NSA提交的方案当中，密钥的长度为112位，但在DES成为一个标准时，密钥被削减至56位。

56位的密钥确实太短，下面两个事件很有说服力。

(1) 分布式穷举攻击： 1997年1月28日，美国数据安全公司RSA在Internet上开展了一项名为“秘密密钥挑战”的竞赛，悬赏一万美元来破解一段DES密文，得到了许多网络用户的积极响应。美国科罗拉多州的程序员R．Verser设计了一个可以通过互联网分段运行的密钥搜索程序，组织了一个称为DESCHALL的搜索行动，成千上万志愿者加入该计划中。第96天，即竞赛发布后的第140天，1997年6月17日晚上，美国盐湖城的M．Sanders成功找到了密钥并解密出明文。

(2) 专用搜索机： 1998年5月，美国电子边境基金会宣布已将一台价值20万美元的计算机改装成专用设备，仅用56小时就破译了DES。这更加直接地说明了56位密钥太短，彻底宣布了DES的终结。

3. 弱密钥和半弱密钥

如果对于初始密钥k，生成的16个子密钥都相同，则称k是弱密钥。显然，DESk(DESk(x))=x。在DES中有4个弱密钥。如果有一对密钥k1、k2，使得: DESk2(DESk1(x))=DESk1(DESk2(x))=x，则称k1、k2是(互逆的)半弱密钥。在DES中有12个半弱密钥。

虽然DES存在弱密钥，但这并不是较大的安全问题。弱密钥与半弱密钥的数量与密钥总量相比是微不足道的。如果随机地选择密钥，那么选中这些弱密钥或半弱密钥的概率可以忽略不计。而且，也可以在密钥产生时进行检查，确保不使用弱密钥或半弱密钥作为DES的密钥。

4. 代数结构存在互补对称性

由DES中函数f的结构可知： 
f(Ri-1,Ki)=f(Ri-1,Ki)
其中表示K的按位取反。再考虑DES的结构，有: 
DES()=DESK(M)
这种特性称为互补对称性。

由于互补对称性，攻击者在进行穷举攻击时仅需试验所有256个密钥的一半。

为了提高DES算法的安全性，人们提出了DES的许多改进方案。其中，称为三重DES的多重加密算法是DES的一个重要的改进算法。多重加密使用同一算法，在多重密钥的作用下，多次加密同一个明文分组。在多重密钥彼此不同且独立的情况下，多重加密对提高密码的安全性有所帮助。

三重DES最主要的一般结构如图3．12所示。



图3．12三重DES最主要的一般结构


即三重DES的加密过程为
C=EK3(DK2(EK1(M)))
解密过程为
M=DK1(EK2(DK3(C)))
再根据K1是否等于K3，可以把三重DES分为两个密钥和三个密钥两种类型。能不能使用二重DES来代替两个密钥的三重DES呢？答案是否定的，因为存在一种简单的攻击方式使得二重DES的有效密钥长度远远小于112，具体原因请读者自己思考。

三重DES的主要优点是密钥长度增加到112或168位，可以有效抵抗DES面临的穷举搜索攻击。其主要缺点是： (1)由于三重加密，处理速度相对较慢； (2)分组长度仍为64位，就效率和安全性而言，与密钥的增长不相匹配，分组长度应更长。

3．5高级加密标准AES

在DES的安全性难以保证的情况下，1997年1月2日，美国国家标准与技术研究所(NIST)开始了征集DES替代者的工作。该替代者称为高级加密标准，即AES。制定AES的主要目标是确保信息可实现100年的安全性，即加密后的密文在100年内不会被破解，因此其安全性与运算效率需在三重DES之上。1997年9月12日，NIST发布了征集算法的正式公告，要求AES具有128位的分组长度，并支持128、192和256位的密钥长度，而且要求AES能在全世界范围内免费使用。

在截至1998年6月15日提交的21个算法里，有15个满足所有的必备条件并被接纳为AES的候选算法。NIST在1998年8月20日的“第一次AES候选大会”上公布了15个AES的候选算法。1999年3月“第二次AES候选大会”举行，1999年8月，5个候选算法入围了决赛： MARS、RC6、Rijndael、Serpent和Twofish。

2000年4月举行了“第三次AES候选大会”。2000年10月2日，Rijndael被选择为AES。2001年2月28日，NIST宣布关于AES的联邦信息处理标准的草案可供公众讨论。2001年11月26日，AES被采纳为标准，并在2001年12月4日的联邦记录中作为FIPS197公布。

AES的征集过程以其公开性和国际性而闻名。第二次候选算法大会和官方请求公众评审，为候选算法的意见反馈、公众讨论与分析提供了足够的机会，而且这一过程为置身其中的每一个人所称道。15个AES候选算法的作者代表着不同国家： 澳大利亚、比利时、加拿大、哥斯达黎加、法国、德国、以色列、日本、韩国、挪威、英国及美国，这正表明了AES的国际性。最终被选为AES的Rijndael算法就是由两位比利时研究者J．Daemen和V．Rijmen提出的。

AES的候选算法根据以下三条主要原则进行评判： 

(1) 安全性； 

(2) 代价； 

(3) 算法与实现特性。

其中，算法的“安全性”无疑是最重要的，因为一个算法如果被发现不安全就不会再被考虑。“代价”指的是各种实现的计算效率(速度和存储需求)，包括软件实现、硬件实现和智能卡实现。“算法与实现特性”包括算法的灵活性、简捷性及其他因素。最后，五个入围最终决赛的算法都被认为是安全的。Rijndael之所以当选是由于它集安全性、高性能、高效率、可实现性及灵活性于一体，被认为优于其他四个算法。

3．5．1AES算法的数学基础
1． 有限域GF(28)
AES把1字节看成在有限域GF(28)上的一个元素，并采用多项式表示域中的元素。对于1字节b，其二进制表示为b7b6b5b4b3b2b1b0，可以把b看成系数在{0，1}中的多项式： 
b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0
例如，十六进制数{57}(二进制表示为“01010111”)该字节对应于如下多项式： 
x6+x4+x2+x+1

下面给出一些例子来说明GF(28)中的运算。

(1) 加法。

在多项式表示中，两个元素的和是一个多项式，其系数是两个元素的系数模2加(即异或)。

例如，{57}和{83}的和为{57}+{83}={D4}，或者采用其多项式记法如下: 
(x6+x4+x2+x+1)+(x7+x+1)=x7+x6+x4+x2
显然，该加法与简单的以字节为单位的按位异或是一致的。

(2) 乘法。

在多项式表示的域中，有限域GF(28)中的乘法就是两个多项式模一个特定的、次数为8的不可约多项式的乘积。对于AES，这个不可约多项式称为m(x)，且由下式给出： 
m(x)=x8+x4+x3+x+1
或由十六进制的{11B}表示。

例如，{57}×{83}={C1}，因为
(x6+x4+x2+x+1)(x7+x+1)
=x13+x11+x9+x8+x6+x5+x4+x3+1
(x13+x11+x9+x8+x6+x5+x4+x3+1) mod m(x)
=(x13+x11+x9+x8+x6+x5+x4+x3+1) mod (x8+x4+x3+x+1)
=x7+x6+1
(3) x乘法。

如果用多项式x乘以b(x)，有
b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x
将上面的结果进行模m(x)化简就得到x·b(x)。如果b7=0，则这一化简是恒等运算，即为b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x； 如果b7=1，则必须减掉m(x)。由此得出x乘法可以用字节内左移操作和紧接着的一个与{1B}的有条件的按位异或操作来实现，故x乘法的实现效率非常高，该运算记为xtime(b)。

可以利用x乘法来加快GF(28)中任意两个元素的乘法。

【例3．1】计算{57}×{13}。

解： 因为
{57}×{13}={57}×({01}+{02}+{10})={57}×{01}+{57}×{02}+{57}×{10}
{57}×{02}=xtime({57})={AE}
{57}×{10}=xtime(xtime(xtime(xtime({57}))))
=xtime(xtime(xtime({AE})))
=xtime(xtime({47}))
=xtime({8E})={07}
所以
{57}×{13}={57}×{01}+{57}×{02}+{57}×{10}={57}+{AE}+{07}={FE}
2． GF(28)域上的多项式

一个字(4字节)可以看作是GF(28)域上的多项式，每个字对应一个次数小于4的多项式。

多项式对应的系数简单相加可以实现多项式的相加。由于GF(28)中的加法为位异或，因此，两个字的加法是一个简单的按位异或。

乘法则比较复杂。假设有GF(28)上的两个多项式： a(x)=a3x3+a2x2+a1x+a0和b(x)=b3x3+b2x2+b1x+b0，它们的乘积c(x)=a(x)b(x)如下： 
c(x)=c6x6+c5x5+c4x4+c3x3+c2x2+c1x+c0
其中
c0=a0b0
c1=a1b0a0b1c2=a2b0a1b1a0b2c3=a3b0a1b2a2b1a0b3c4=a3b1a2b2a1b3c5=a3b2a2b3c6=a3b3
显然，c(x)不能再被表示为4字节。通过模一个4次多项式c(x)进行化简，这样，乘法的结果可以化简为一个次数小于4的多项式。

在AES中，使用的模数多项式为M(x)=x4+1。由于
xj mod (x4+1)=xj mod 4
记a(x)b(x) mod (x4+1)的结果为d(x)=a(x)b(x)，设d(x)=d3x3+d2x2+d1x+d0，则有
d0=a0b0a3b1a2b2a1b3d1=a1b0a0b1a3b2a2b3d2=a2b0a1b1a0b2a3b3d3=a3b0a2b1a1b2a0b3
其矩阵表示为
d0d1d2d3=a0a3a2a1a1a0a3a2a2a1a0a3a3a2a1a0b0b1b2b3

注意： 模M(x)=x4+1不是GF(28)上的不可约多项式，因为M(x)=x4+1=(x+1)(x3+x2+x+1)。因此，与一个固定多项式相乘的乘法将不一定是可逆的。

在AES中，这里选择了一个具有逆元的固定多项式进行这样的乘法，从而保证了乘法的可逆性。

3．5．2算法的总体描述

AES的分组长度为128位，有三种可选的密钥长度，即128位、192位和256位。AES是一个迭代型密码，轮数Nr依赖于密钥长度。如果密钥长度为128位，则Nr=10； 如果密钥长度为192位，则Nr=12； 如果密钥长度为256位，则Nr=14。AES的密钥长度与加解密轮数之间的对照如表3．9所示。


表3．9AES的密钥长度与加解密轮数的对照表



算法名称密钥长度加解密轮数(Nr)

AES12812810

AES19219212

AES25625614


AES中的操作都是以字节为基础的，所有用到的变量都由适当数量的字节组成。中间变量State用如下4×4字节矩阵表示： 



s0,0s0,1s0,2s0,3

s1,0s1,1s1,2s1,3

s2,0s2,1s2,2s2,3

s3,0s3,1s3,2s3,3


下面给出AES加密过程的总体描述： 

(1) 给定一个明文M，将State初始化为M，并将轮密钥与State异或(称为AddRoundKey)；  

(2) 对前Nr-1轮中的每一轮，用S盒进行一次替换操作(称为SubBytes)，对替换的结果State做行移位操作(称为ShiftRows)，再对State做列混合变换(MixColumns，也称为列混淆变换)，然后进行AddRoundKey操作； 

(3) 在最后一轮中依次进行SubBytes、ShiftRows和AddRoundKey操作； 

(4) 将State定义为密文C。

AES的加密过程可用如下伪代码描述：

AESCipher(byte in［16］, byte out［16］, word w［4*(Nr+1)］)

//in［］、out［］和w［］分别表示AES加密的输入、输出和子密钥

{

byte state ［4,4］;  //中间变量



state = in; //用以列为顺序的输入来初始化中间变量，即state［r, c］=in［r+4c］, 0<=r、c<4

AddRoundKey (state, w［0, 3］);



//前Nr－1轮加密

for(int round = 1; round < Nr-1; round++)

{

SubBytes (state);

ShiftRows (state);

MixColumns (state);

AddRoundKey (state, w［4*round, 4*round+3］);

}



//最后一轮加密

SubBytes (state)；

ShiftRows (state)；

AddRoundKey (state, w［4*Nr, 4*Nr+3］)；



out = state；

}

AES的解密算法与加密算法有较大的不同，它的伪代码描述如下：

AESDecipher(byte in［16］, byte out［16］, word w［4*( Nr+1)］)

{

byte state［4, 4］;



state = in;

AddRoundKey(state, w［4*Nr, 4*Nr＋3］);



//前Nr-1轮解密

for(int round=Nr-1; round>0; round--)

{

InvShiftRows(state);

InvSubBytes(state);

AddRoundKey(state, w［4*round, 4*round＋3］);

InvMixColumns(state);

} 

//最后一轮解密

InvShiftRows(state);

InvSubBytes(state);

AddRoundKey(state, w［0, 3］);

}

容易看出，AES的解密过程使用了四种逆变换，即InvSubBytes(·)、InShiftRows(·)、InvMixColumns(·)和AddRoundKey(·)(AddRoundKey的逆变换是它自身)，以相反的顺序对由密文映射得到的状态矩阵进行变换。另外，AES的解密过程使用的子密钥与加密过程相同，但使用的顺序相反。下面介绍算法中的基本变换。

3．5．3算法的基本变换
1．  字节替换变换(SubBytes)
字节替换操作使用一个S盒对State的每字节都进行独立的替换。表3．10给出了AES的S盒。


表3．10AES的S盒



Y

X
0123456789abcdef

0637c777bf26b6fc53001672bfed7ab76

1ca82c97dfa5947f0add4a2af9ca472c0

2b7fd9326363ff7cc34a5e5f171d83115

304c723c31896059a071280e2eb27b275

409832c1a1b6e5aa0523bd6b329e32f84

553d100ed20fcb15b6acbbe394a4c58cf

6d0efaafb434d338545f9027f503c9fa8

751a3408f929d38f5bcb6da2110fff3d2

8cd0c13ec5f974417c4a77e3d645d1973

960814fdc222a908846eeb814de5e0bdb

ae0323a0a4906245cc2d3ac629195e479

be7c8376d8dd54ea96c56f4ea657aae08

cba78252e1ca6b4c6e8dd741f4bbd8b8a

d703eb5664803f60e613557b986c11d9e

ee1f8981169d98e949b1e87e9ce5528df

f8ca1890dbfe6426841992d0fb054bb16



与DES的S盒相比，AES的S盒能进行代数上的定义，而且不是像DES的S盒那样比较明显的“随机”代换。

S盒按如下方式构造： 

(1) 行x、列y的字节值初始化为十六进制的{xy}；

(2) 把S盒中的每字节映射为在有限域GF(28)中的逆，{00}不变；

(3) 把S盒中的每字节转换为二进制表示(b7，b6，b5，b4，b3，b2，b1，b0)，然后进行如下的仿射变换：
b′0b′1b′2b′3b′4b′5b′6b′7=10001111
11000111
11100011
11110001
11111000
01111100
00111110
00011111b0b1b2b3b4b5b6b7+11000110
【例3．2】这里用一个小例子来说明S盒的构造算法。以十六进制的{53}开始，二进制表示为01010011，它表示有限域GF(28)中的元素为
x6+x4+x+1
它在有限域GF(28)中的乘法逆元素为
x7+x6+x3+x
因此，在二进制下有

(b7，b6，b5，b4，b3，b2，b1，b0)=(1,1,0,0,1,0,1,0)

下面计算
b′0=(b0+b4+b5+b6+b7+1) mod 2
=(0+0+0+1+1+1) mod 2
=1
同理，可计算其他位，结果为
(b′0，b′1，b′2，b′3，b′4，b′5，b′6，b′7)=(1,1,1,0，1,1,0,1)
以十六进制表示就是{ED}，故S盒中的第5行、第3列中的元素为{ED}，即SubBytes({53})={ED}。

2． 行移位变换(ShiftRows)

State的第一行保持不变，第二行循环左移1字节，第三行循环左移2字节，第四行移行循环左移3字节，如图3．13所示。



图3．13行移位变换


3． 列混合变换(MixColumns)

列混合变换对State中的每列进行独立的操作，它把每列都看成GF(28)中的一个四项多项式s(x)，再与GF(28)上的固定多项式 a(x)={03}x3+{01}x2+{01}x+{02}进行模x4+1的乘法运算。如对第c列(0≤c≤3)，其对应的GF(28)中的多项式为sc(x)=s0,c+s1,cx+s2,cx2+s3,cx3，则列混合变换后为s′c(x)=sc(x)a(x)。其矩阵乘法表示如下： 
s′0，c
s′1，c
s′2，c
s′3，c=02030101
01020301
01010203
03010102s0，c
s1，c
s2，c
s3，c
其中0≤c≤3。

解密变换中涉及的三种基本变换如下。

4． InvSubBytes变换

InvSubBytes变换是字节替换变换(SubBytes)的逆变换，即先用到了仿射变换的逆变换，再计算GF(28)中的乘法逆。逆S盒对状态矩阵中的每字节进行逆变换。InvSubBytes变换可以通过如表3．11所示的逆S盒实现。


表3．11AES解密过程中的逆S盒



Y

X
0123456789abcdef

052096ad53036a538bf40a39e81f3d7fb

17ce339829b2fff87348e4344c4dee9cb
续表


Y

X
0123456789abcdef
2547b9432a6c2233dee4c950b42fac34e

3082ea16628d924b2765ba2496d8bd125

472f8f66486689816d4a45ccc5d65b692

56c704850fdedb9da5e154657a78d9d84

690d8ab008cbcd30af7e45805b8b34506

7d02c1e8fca3f0f02c1afbd0301138a6b

83a9111414f67dcea97f2cfcef0b4e673

996ac7422e7ad3585e2f937e81c75df6e

a47f11a711d29c5896fb7620eaa18be1b

bfc563e4bc6d279209adbc0fe78cd5af4

c1fdda8338807c731b11210592780ec5f

d60517fa919b54a0d2de57aaf93c99cef

ea0e03b4dae2af5b0c8ebbb3c83539961

f172b047eba77d626e169146355210c7d



5． InvShiftRows变换

InvShiftRows变换是行移位变换(ShiftRows)的逆变换，即对状态矩阵的各行按相反的方向进行循环移位操作。因此，状态矩阵各行的移位情况如下：  第一行保持不变；  第二行循环右移1字节； 第三行循环右移2字节； 第四行循环右移3字节。

6． InvMixColumns变换

InvMixColumns变换是列混合变换(MixColumns)的逆变换。InvMixColumns同样逐列处理状态矩阵，它把每一列都当作系数GF(28)有限域上的四项多项式。

与MixColumns变换对应，InvMixColumns变换把列多项式与多项式a(x)相对于模多项式x4+1的逆a-1(x)相乘，即
a-1(x)={0b}·x3+{0d}·x2+{09}·x+{0e}
设列多项式为sc(x)=s0,c+s1,cx+s2,cx2+s3,cx3，0≤c≤3，InvMixColumns变换可改写为如下的矩阵形式： 
s′0,cs′1,cs′2,cs′3,c=0e0b0d09090e0b0d0d090e0b0b0d090es0,cs1,cs2,cs3,c，0≤c≤3
3．5．4密钥扩展算法

轮密钥是由密钥经过一个扩展算法产生的，其长度由加解密轮数决定，具体地说，轮密钥有(分组长度)×(Nr+1)位。例如，AES128的加解密轮数为10，则轮密钥共有128×(10+1)=1408 位。

密钥扩展算法以一个字(即4字节)为基本单位，其伪代码描述如下： 

KeyExpansion(byte key［4*Nk］, word w［4*(Nr+1)］, Nk)

// key［］表示初始密钥，w［］表示扩展后的密钥，Nk为密钥长度(以字为单位)

{	

word temp;

//扩展密钥的前Nk个字是初始密钥

for (i=0;i< Nk;i++)

//把四个单字节按照从高位到低位的顺序表示为一个字

w［i］ = (key［4*i］, key［4*i+1］, key［4*i+2］, key［4*i+3］);

for(i = Nk; i<4*( Nr+1); i++)

{

temp = w［i-1］;

if (i % Nk == 0)

temp = SubWord(RotWord(temp)) ^ Rcon［i/ Nk］;

else if(Nk ==8 && (i % Nk == 4))

temp = SubWord(temp);

w［i］ = w［i - Nk］ ^ temp;

}

}

密钥扩展算法中包括两个函数RotWord和SubWord。RotWord(B0，B1，B2，B3)对输入的4字节进行循环左移操作，即
RotWord(B0，B1，B2，B3)=(B1，B2，B3，B0)
SubWord(B0，B1，B2，B3)对输入的4字节分别使用S盒的替换操作SubBytes。Rcon［i］=(RC［i］,'00','00'，'00')，RC［i］的所有可能值(用十六进制表示)如表3．12所示。实际上，RC［i］的值为有限域GF(28)中的多项式xi-1的十六进制表示。


表3．12RC［·］



i1234567891011

RC［i］01020408102040801B366c


可以看到，扩展密钥的最前面Nk个字是直接由输入的密钥填充的，而后面的每个字w［i］则主要由前面的字w［i-1］与Nk个位置之前的字w［i- Nk］进行异或运算得到。 

3．6国密分组密码算法SM4
3．6．1算法的总体描述
SM4分组密码算法［5］是我国无线局域网标准WAPI中所使用的密码标准，该算法采用非平衡Feistel 结构（一种基本Feistel结构的变种），分组长度为128位，密钥长度为128位。加密算法与密钥扩展算法均采用非线性迭代结构。加密运算和解密运算的算法结构相同，解密运算的轮密钥使用顺序与加密运算相反。

SM4分组密码算法的加密密钥长度为128位，表示为MK=(MK0,MK1,MK2,MK3)，其中MKi(i=0，1,2,3)为32位。轮密钥表示为(rk0,rk1,…,rk31)，其中rki(i=0,1,…，31)为32位。轮密钥由加密密钥生成。FK=(FK0,FK1,FK2,FK3)为系统参数，CK=(CK0,CK1,…,CK31)为固定参数，用于密钥扩展算法，其中FKi(i=0,1,…，3)，CKi(i=0,1,…，31)均为32位。

SM4加密算法由32次迭代运算和1次反序变换R组成。设明文输入为(X0,X1,X2,X3)∈(Z322)4，密文输出为(Y0,Y1,Y2,Y3)∈(Z322)4,轮密钥为rki∈Z322，i=0,1,…，31。加密算法的运算过程如下： 

(1) 首先执行32次迭代运算： 
Xi+4=F(Xi,Xi+1,Xi+2,Xi+3,rki)，i=0,1,…,31
其中F为轮函数。

(2) 对最后一轮数据进行反序变换如下： 
(Y0,Y1,Y2,Y3)=R(X32,X33,X34,X35)=(X35,X34,X33,X32)
SM4的加密和解密算法的变换结构相同，不同的只有轮密钥的使用顺序，解密时反序使用轮密钥。

轮函数F的细节如下。

设输入为(X0,X1,X2,X3)∈(Z322)4，轮密钥为rk∈Z322，则轮函数F为
F(X0,X1,X2,X3,rk)=X0T(X1X2X3rk)
其中，T： Z322→Z322是一个可逆变换，由非线性变换τ和线性变换L复合而成，即T(·)=L(τ(·))。

非线性变换τ由4 个并行的S盒(见表3．13)构成，设输入为A=(a0,a1,a2,a3)∈(Z82)4，非线性变换τ的输出为B=(b0,b1,b2,b3)∈(Z82)4，即
(b0,b1,b2,b3)=τ(A)=(Sbox(a0),Sbox(a1),Sbox(a2),Sbox(a3))



表3．13SM4加密过程的S盒



0123456789ABCDEF

0D690E9FECCE13DB716B614C228FB2C05

12B679A762ABE04C3A44132649860699

29C4250F491EF987A33540B43ECFAC62

3E4B31CA9C908E89580DF94F758F3FA6

44707A7FCF37317BA83593C19E6854FA8

5686B81B27164DA8BF8EB0F4B70569D35

61E240E5E6358D1A225227C3B01217887

7D40046579FD327524C3602E7A0C4C89E

8EBF8AD240C738B5A3F7F2CEF96115A1

9E0AE5DA49B341A55A933230F58CB1E3

A1DF6E22E8266CA60C02923AB0534E6F

BD5DB3745DEFD8E2F03FF6A7266C5B51

C8D1BA92BBDDBC7F11D95C411F105AD8

D0AC13188A5CD7BBD2D74D012B8E5B4B0

E8969974A0C96777E65B9F109C56EC684

F18F07DEC3ADC4D2079EE5F3EDCB3948


设S盒的输入为EF，则经S盒运算的输出结果为第E行、第F列的值，即Sbox(EF)=0x84。

L是线性变换，非线性变换τ的输出是线性变换L的输入。设输入为B∈Z322，则： 
C=L(B)=B(B<<<2)(B<<<10)(B<<<18)(B<<<24)
其中，<<<i表示32位循环左移i位； Zn2表示长度为n的二进制序列集合。

3．6．2密钥扩展算法

本算法的轮密钥由加密密钥通过密钥扩展算法生成。设加密密钥为MK，MK=(MK0,MK1,MK2,MK3)∈(Z322)4。

轮密钥生成方法如下： 
K0=MK0FK0
K1=MK1FK1
K2=MK2FK2
K3=MK3FK3
rki=Ki+4T′(Ki+1Ki+2Ki+3CKi)，i=0,1,2,…,31
式中： T′是将合成置换T 的线性变换L替换为L′(B)=B(B<<<13)(B<<<23)。

系统参数FK的取值如下： 
FK0=(A2B1BAC6)
FK1=(56AA3350)
FK2=(677D9197)
FK3=(B27022DC)
固定参数CK的取值方法如下： 

设cki,j为CKi的第j字节(i=0,1,…,31; j=0,1,2,3)，即CKi=(cki,0,cki,1,cki,2,cki,3)∈(Z82)4，则cki,j=(4i+j)×7(mod 256)。

固定参数CKi(i=0,1,2,…,31)的具体取值如下： 
00070E15，1C232A31，383F464D，545B6269，
70777E85，8C939AA1，A8AFB6BD，C4CBD2D9，
E0E7EEF5，FC030A11，181F262D，343B4249，
50575E65，6C737A81，888F969D，A4ABB2B9，
C0C7CED5，DCE3EAF1，F8FF060D，141B2229，
30373E45，4C535A61，686F767D，848B9299，
A0A7AEB5，BCC3CAD1，D8DFE6ED，F4FB0209，
10171E25，2C333A41，484F565D，646B7279
解密密钥同加密密钥，解密使用的轮密钥由解密密钥生成，生成方法同加密过程的轮密钥生成方法。

3．7轻量级分组密码

本节将介绍轻量级分组密码算法的相关内容。所谓轻量级分组密码算法是指相对于传统的分组密码算法（如DES和AES）来说算法结构简单，在硬件实现和运行功耗上有明显优势的一类分组密码算法。轻量级分组密码算法更适合于资源受限的应用场景（如物联网相关的应用场景）。下面将具体介绍两种著名的轻量级分组密码算法PRESENT［6］和CLEFIA［7］，这两个算法均已入选国际标准化组织（ISO）的轻量级分组密码标准。

3．7．1PRESENT密码算法

在2007年的密码硬件和嵌入式系统国际会议上，丹麦密码学家Bogdanov、Kundsen等公布了PRESENT算法［6］，该算法属于超轻量级加密算法。所谓分组密码算法的量级，主要通过其硬件实现时的复杂程度来衡量。PRESENT算法与其他一些轻量级分组密码算法相比，有着最简单的硬件实现，因此它被称为超轻量级密码算法。PRESENT算法为SPN结构，分组长度为64位，密钥长度有80位和128位两种，


图3．14PRESENT加密算

法的结构

两种均为31轮。硬件实现80位密钥的PRESENT算法仅需要约1570个与非门。该算法在功耗方面也有很优秀的表现： 在物联网的低耗节点中，80位的密钥能够提供足够的安全性，至于128位的密钥可以用在安全性要求更高的场景。PRESENT面向硬件设计，因此硬件性能良好，但软件性能一般，甚至较差。

PRESENT加密算法的结构如图3．14所示。算法先将轮函数迭代31次，轮函数包括轮密钥加(addRoundKey)、非线性置换S层(sBoxLayer)、线性置换P层(pLayer)，再经过一次轮密钥加运算后得到密文。

设64 位的明文P=p63p62p61p60…p0，其中p0表示最低位，p63表示最高位。轮函数各步操作如下： 

① 轮密钥加。完成64位中间状态与64位轮密钥的异或运算。

② 设S 层(见表3．14)输入W=w63w62w61…w0，输出V=v63v62v61…v0，则有： 
v63v62v61v60=S(v63v62v61v60)
v59v58v57v56=S(v59v58v57v56)
…
v3v2v1v0=S(v3v2v1v0)
③ P 层将输入的每一位映射到输出的另一位，取值如表3．15所示。


表3．14PRESENT算法的S层



x0123456789ABCDEF

S(x)C56B90AD3EF84712




表3．15P层真值表



i0123456789101112131415

P(i)0163248117334921834503193551

i16171819202122232425262728293031

P(i)4203652521375362238547233955

i32333435363738394041424344454647

P(i)824405692541571026425811274359

i48495051525354555657585960616263

P(i)12284460132945611430466215314763


解密时先将解密轮函数迭代31次，再经过一次轮密钥加，得到明文。与加密不同的方面如下： 

① 解密轮函数依次是： 轮密钥加、线性置换逆P层、非线性置换逆S层； 

② 轮密钥加实现中间状态与轮密钥的异或，轮密钥的使用顺序与加密时相反，依次是rk32,rk31,…,rk2，最后一步轮密钥加使用rk1； 

③ 逆P层的表达式为
P-1(i)=(4i)%63,i≠6363,i=63
④ 逆S层依次将连续4位经过逆S层,逆S层的取值如表3．16所示。


表3．16PRESENT运算的逆S层



x0123456789ABCDEF

S-1(x)5E28C12DB463079A


密钥扩展算法

设80位的种子密钥为K=k79k78k77…k0，最左边的64位作为第一轮的轮密钥，即rk1=k79k78k77…k16，接着循环执行如下步骤31 次，每次将最左边64位作为轮密钥。

① 循环左移61位，即
k79k78k77…k0←k18k17k16…k19
② 将最左边4位经过S层，即
k79k78k77k76←S(k79k78k77k76)
③ 将轮常量i和k19k18k17k16k15异或，即
k19k18k17k16k15←ik19k18k17k16k15

轮常量依次是1、2、3、…、31。

3．7．2CLEFIA密码算法

CLEFIA［7］是由SONY公司研制开发的一种分组加密算法，该算法被用来保护SONY公司的音乐和图像等数字内容，以及进行“高级”版权的保护与认证。CLEFIA算法在2007年的快速软件加密国际会议上公布。SONY公司称CLEFIA算法可以抵抗“现有的密码破解手段”，他们希望这种新技术可以应用到软件和AV硬件中。

CLEFIA算法由数据处理部分和密钥扩展部分组成。它的基本结构是一种广义的Feistel结构,由四条输入分支组成。每一轮中有两个F函数，每个F函数使用两个不同的S盒以及两个不同的扩散矩阵。密钥扩展部分与数据处理部分共享Feistel结构，从而使得CLEFIA只需要较小的硬件和软件规模。

CLEFIA算法支持128位的分组长度，密钥长度可选128/192/256位。密钥长度是128位、192位和256位时，加密轮数分别是18轮、22轮和26轮。下面以128位密钥为例对CLEFIA算法进行详细介绍，如图3．15所示。



图3．15CLEFIA加密算法的结构


设P=(P0,P1,P2,P3)和C ∈ {0，1}128分别为128位的明文和密文，其中Pi,Ci∈{0,1}32(0≤i<4)为32位的分支； Ki∈{0,1}32(0≤i<2r)为轮密钥，WK0,WK1,WK2,WK3∈{0,1}32为白化密钥。ｒ轮CLEFIA算法加密过程如下。

① 初始白化层T=(T0，T1，T2，T3)=(P0，P1WK0，P2，P3WK1)为第一轮的输入。

② r轮轮变换。设T(i-1)=(T(i-1)0，T(i-1)1，T(i-1)2，T(i-1)3) 为第i轮的输入，则第i轮的输出为
T(i)=(T(i)0，T(i)1，T(i)2，T(i)3) 
=(F0(T(i-1)0,K2i-2)T(i-1)1，T(i-1)2，F1(T(i-1)2,K2i-1)T(i-1)3，T(i-1)0)
③ 末尾白化层。密文C=(C0，C1，C2，C3)=(T(r)3，T(r)0WK2，T(r)1，T(r)2WK3)。

上述F0和F1是两个非线性可逆函数，F0定义如下。

① 轮密钥加： 计算A=T(i-1)0K2i-2； 

② 非线性变换A=(A0，A1，A2，A3)，其中Ai∈{0,1}8(0≤i≤3)，计算B0=S0(A0)，B1=S1(A1)，B2=S0(A2)，B3=S1(A3)； 

③ 线性变换： 计算D=M0(B0，B1，B2，B3)T。

其中，S0和S1是两个非线性Ｓ盒，M0为一个4×4的矩阵。非线性函数Ｆ1的定义与F0类似，只需将其中的S0和S1的位置互换，将M0变为M1即可。M0和M1的十六进制表示如下： 
M0=0x010x020x040x06
0x020x010x060x04
0x040x060x010x02
0x060x040x020x01
M1=0x010x080x020x0a
0x080x010x0a0x02
0x020x0a0x010x08
0x0a0x020x080x01
矩阵与向量的乘法定义在有限域GF(28)上，其本原多项式为z8+z4+z3+z2+1。容易验证矩阵M0和M1都是自逆的，即M0=M-10，M1=M-11。

CLEFIA算法的解密过程与加密过程类似，如图3．16所示。



图3．16CLEFIA解密算法的结构


密钥扩展算法

CLEFIA的密钥扩展算法可分为两部分： 首先由种子密钥SK生成L，然后由SK和L扩展得到子密钥WK与K，其中生成L的结构与其密钥长度有关。因此，首先定义两种整体结构GFN4,r及GFN8,r(GFNd,r表示含有d个32位的分支和r轮迭代)： 当密钥长度为128位时，密钥扩展算法的结构为GFN4,r，与图3．15中的结构相同； 当密钥长度为192/256位时，密钥扩展算法的结构为GFN8,r，如图3．17所示。



图3．17GFN8,10结构


当密钥长度为128位时的密钥扩展算法步骤如下： 

① L←GFN4,12(CON1280,CON1281,…，CON12823,SK); 

② WK0|WK1|WK3|WK4←SK; 

③ For i=0 to i=8

{

T=L(CON12824+4i|CON12824+4i+1|CON12824+4i+2|CON12824+4i+3);

L←∑(L); 

当i是奇数时，T←TSK;

K4i|K4i+1|K4i+2|K4i+3←T;

}

算法在步骤①中用到了24个32位常数CON128i(0≤i<24)； 然后由L和SK生成子密钥Ki(0≤i<36)和WKi(0≤i<4)，其中用到了36个32位常数CON128i(24≤i<60)。

当密钥长度为192位或者256位两种情况下，密钥扩展算法是比较相似的，不同之处仅在于所用的常数数量不同： 192位的情况下使用了76个32位常数CON192i，256位密钥的情况下使用了92个32位常数CON256i。用k表示密钥长度，下面是密钥长度为192和256位的密钥扩展算法的步骤： 

① 当k=192时，SKL←SK0|SK1|SK2|SK3，SKR←SK4|SK5|SK0|SK1； 

当k=256时，SKL←SK0|SK1|SK2|SK3，SKR←SK4|SK5|SK6|SK7； 

② 令SKL=SKL0|SKL1|SKL2|SKL3，SKR←SKR0|SKR1|SKR2|SKR3，

LL|LR←GFN8,10(CON(k)0,CON(k)1,…，CON(k)39,SKL0,…，SKL3,SKR0,…，SKR3); 

③ WK0|WK1|WK3|WK4←SKLSKR; 

④ For i=0 to i=10(当k=192)或i=12(当k=256)

{ 

当i mod 4=0或1：

T=LL(CON(k)40+4i|CON(k)40+4i+1|CON（k）40+4i+2|CON（k）40+4i+3);

LL←∑(LL); 

当i是奇数时，T←TSKR

当i mod 4=2 或3:

T=LR(CON(k)40+4i|CON（k）40+4i+1|CON(k)40+4i+2|CON(k)40+4i+3);

LR←∑(LR);

当i是奇数时，T←TSK;

K4i|K4i+1|K4i+2|K4i+3←T;

}

关于密钥扩展算法中涉及的常数CON(k)i，在文献［7］中有详细的介绍，此处不再赘述。

3．8分组密码的工作模式

本节将介绍分组密码的工作模式。由于前述章节介绍的分组密码算法一次只能处理单块数据，因此，引入分组密码的工作模式可以用于处理多个数据块。这里需要注意的是，只有使用了“合适的”分组密码工作模式，才能基于具体的分组密码算法设计出能实现数据机密性的对称加密方案。下面将具体介绍五种典型的分组密码工作模式，即电子密码本模式、密码分组链接模式、密码反馈模式、输出反馈模式和计数器模式。

3．8．1电子密码本模式(ECB)

电子密码本模式(Electronic Codebook Mode，ECB)是最简单的模式，它直接利用加密算法分别对每个明文分组使用相同密钥进行加密。设明文分组序列为M=M1M2…Mn，相应的密文分组序列为C=C1C2…Cn，则
Ci=Ek(Mi),i=1,2,…,n
对于长度大于b位的报文，整个加密前需要把这个报文分成b位的分组，如果必要的话对最后一个分组进行填充。使用“密码本”这个术语的原因是对每个b位的明文分组都有一个唯一的密文，因此可以想象一个巨大的密码本，其中对每一个可能的b位明文项，都有一个密文项与之对应。

在ECB模式下，加密算法的输入是明文，算法的输出将直接作为密文进行输出，不进行任何形式的反馈，每个明文分组的处理是相互独立的，这种方式也是分组密码工作的标准模式。

ECB模式的主要缺点是由于没有任何形式的反馈，相同的明文加密后将产生相同的密文，这样在处理具有固定数据结构的明文数据时容易暴露明文数据的固有格式。例如某些格式化的报文，除了作业号、通信地址、发报时间、密级等数据位置固定外，明文数据也非常有规律，这些常用的数据通常加密后在密文的同一个位置出现，密码分析者就可能得到许多明文密文对，从而为分析、破译密码提供线索。

同时，由于ECB模式下各个报文分组之间是相互独立的，这样，如果攻击者有能力对报文进行分组的插入与删除，就可以进行主动攻击，带来安全风险。另外，ECB模式无法纠正传输中的同步差错，如果在传输中增加或丢失一位或多位数据，将导致密文分组的对齐错误，这样，整个密文序列都将不能正确地解密。

3．8．2密码分组链接模式(CBC)

在密码分组链接模式(Cipher Block Chaining Mode，CBC模式)中，加密算法的输入是当前的明文分组Mi和上一次产生的密文分组Ci-1的异或，其输出为密文分组Ci，即
C0=IV
Ci=Ek(MiCi-1),1≤i≤n
相应的解密规则为
C0=IV
Mi=Dk(Ci)Ci-1,1≤i≤n
CBC模式的工作示意图如图3．18所示。



图3．18CBC模式的工作示意图


IV被用来和解密算法的输出进行异或，以产生第一个明文分组。因此，IV必须被发送方和接收方双方所知，通常作为密文的一部分。IV一般无须保密，但需随消息进行更换。

CBC模式有效地改进了ECB模式的缺点，它能够隐蔽明文的数据模式，相同的明文对应的密文一般是不同的。同时，在一定程度上，它能够有效地抵抗密文传输过程中对数据的篡改，如分组的重放、插入和删除等。

CBC模式由于引进了反馈，当信道噪声等干扰导致密文传输错误时，密文中的一位错误将影响当前分组及下一个分组的解密，但其他分组不受影响，人们把这种错误传播形式称为“有限传播”。请考虑，如果接收方不知道IV，对解密有什么影响？

3．8．3密码反馈模式(CFB)

为了实现更大的灵活性，密码反馈模式(Cipher Feedback Mode，CFB模式)需要引入一个整数参数s，1≤s≤b。需要注意的是，明文不是按b进行分组，而是按s分组，且明文的长度必须是s的倍数。故CFB模式能够通过对参数s的选择来对长度小于b的数据直接进行加密，而CBC模式却做不到。

在s位CFB模式，加密函数的输入是一个b位的移位寄存器，这个移位寄存器被初始化为一个初始向量IV。加密函数处理结果的最高(最左边)s位与明文的第一个分组M1进行异或运算，产生密文分组C1。同时，移位寄存器的值向左移s位，且用C1替换寄存器的最低(最右边)s位。这个过程如此重复，直到完成加密。CFB模式的加解密过程如图3．19所示。



图3．19CFB模式的加解密过程


令函数LSBi(·)表示输入的前i个最低有效位，函数MSBi(·)表示输入的前i个最高有效位。例如，LSB3(111011011)=011，和MSB4(111011011)=1110。则CFB模式的加解密规则如下： 

加密： 
I1=IV
Ij=LSBb-s(Ij-1)‖Cj-1,2≤j≤n
Cj=MjMSBs(EK(Ij)),1≤j≤n
解密： 
I1=IV
Ij=LSBb-s(Ij-1)‖Cj-1,2≤j≤n
Mj=CjMSBs(EK(Ij)),1≤j≤n
CFB模式由于采用密文反馈，若某个密文分组在传输中出现一位或多位的错误，将会引起当前分组和后续部分分组的解密错误。因为只有当错误的密文位从寄存器中移出后，解密才会恢复正常，因此一个密文分组出错会影响后面最多bs个分组的解密(x表示大于或等于x的最小整数)。

3．8．4输出反馈模式(OFB)

在CFB模式中，一位密文的传输错误会影响至少b+1位的明文，这种错误传播的影响对于有些应用来讲太大。对于这些应用来说，可以采用第四种工作模式，即输出反馈模式(Output Feedback Mode，OFB模式)。


在OFB模式中，先产生一个密钥流，然后将其与明文相异或，其加解密过程如图3．20所示。因此，OFB模式实际上就是一个同步流密码，通过反复加密一个初始向量IV来得到密钥流。这种方法有时也叫作“内部反馈”，因为反馈机制独立于明文和密文而存在。



图3．20OFB模式的加解密过程


定义Z0=IV，然后用下述公式计算密钥流Z0Z1…Zn： 
Zi=EK(Zi-1),1≤i≤n
最后用如下简单运算来完成加解密： 

加密： Ci=MiZi(1≤i≤n)

解密： Mi=CiZi(1≤i≤n)

OFB模式要求在密钥相同的情况下，每次加密必须使用不同的IV，否则消息的机密性就得不到保证。

OFB模式具有普通序列密码的优缺点，例如可加密任意长度的数据(即不需要进行分组填充)，不会传播错误，适于加密冗余度较大的数据、语音和图像数据，但对密文的篡改难以检测。

3．8．5计数器模式(CTR)

CBC和CFB等模式都存在这样一个问题： 不能以随机顺序来访问加密的数据，因为当前密文数据块的解密依赖于前面的密文块。而这个问题对于很多应用来说，特别是数据库的应用，是很难接受的。例如，若用CBC模式来加密数据库，则为了访问一个特定的加密字段，就需要解密在它之前的所有数据，这是代价很高的操作。为此又出现了另一种操作模式，即计数器模式(Counter Mode，CTR模式)。

CTR模式不是用加密算法的输出填充寄存器，而是将一个计数器输入寄存器中，其加解密过程如图3．21所示。每一个分组完成加密后，计数器都要增加某个常数，典型常数值是1。其加解密公式如下： 

加密： Ci=MiEK(CTR+i)(1≤i≤n)

解密： Mi=CiEK(CTR+i)(1≤i≤n)

其中，CTR表示计数器的初始值。



图3．21CTR模式的加解密过程


CTR模式的主要优点如下。

(1) 随机访问特性： 可以随机地对任意一个密文分组进行解密，对该密文分组的处理与其他密文分组无关。

(2) 高效率： 能并行处理，即能对多个分组的加解密同时进行处理，而不必等前面分组处理完再开始； 而且，CTR模式最主要和最耗时的处理并不依赖于明文或密文，因此可以提前进行预处理，这也可以极大提高处理效率。因此CTR模式很适合对实时性和速度要求很高的场景。

此外，CTR模式还可以处理任意长度的数据，而且加解密过程仅涉及加密运算，不涉及解密运算，因此不用实现解密算法。

3．9分组密码的基本密码分析方法

本节介绍主流且通用的对分组密码算法的三种分析方法，这些方法的攻击复杂度依赖于所分析密码算法的数学结构，其中差分分析和线性分析方法被认为是现代密码学发展至今极具意义的密码分析方法。

3．9．1差分密码分析 

差分密码分析［4］是Eli BihamEli Biham(1960—)，以色列密码学家，目前是以色列Technion理工学院计算机科学系的教授。和Adi ShamirAdi Shamir(1952—)，RSA算法的发明者之一，差分分析的发明者之一，Eli Biham的博士生导师。在1990年提出的一种分析方法，最初的差分密码分析是针对DES提出的，后来的发展表明差分密码分析几乎适用于所有的分组密码。差分密码分析是迄今为止攻击分组密码算法最有效的分析方法之一。差分分析是一种选择明文攻击方法，它的基本思想是： 首先固定明文的差分，经若干轮后，研究明文差分对密文差分的影响，以此来恢复部分或全部的密钥位。对分组长度为n的r轮迭代密码算法，将两个n位串Xi和X*i的差分定义为
ΔXi=XiX*i
其中： X0和X*0是明文对，Xi和X*i是第i轮的输出，同时也是第i+1轮的输入。若记第i轮的子密钥为Ki，轮函数为F，则Xi=F(Xi-1,Ki)。利用加密算法获得密文对，寻找一个高概率的区分器； 选择具有特定输入差分值a0的明文对(X0,X*0),该明文对在最后一轮的输入差分ΔXr-1以很高的概率为取特定值ar-1； 最后，恢复最后一轮的子密钥。为了叙述方便，定义以下概念。

定义3．1r轮特征Φ是一个差分序列： 
a0,a1,…，ar
其中a0表示明文对X0和X*0的差分，ai(1≤i≤r)表示第i轮Xi和X*i的差分。r轮特征Φ的概率是指在明文对X0和X*0的差分为a0，且明文X0和子密钥K1,K2，…，Kr相互独立且均匀随机的条件下，第i(1≤i≤r)轮输出Xi和X*i的差分为ai的概率。

定义3．2如果明文对X0和X*0的差分为a0，Xi和X*i的差分为ai，1≤i≤r，则称明文对X0和X*0为特征Φ=a0,a1,…,ar的一个正确对； 否则，称为特征的错误对。

用pΦi=P(ΔF(X)=ai|ΔX=ai-1)表示在输入差分为ai-1的条件下，轮函数F的输出差分为ai的概率。通常r轮特征Φ=a0,a1,…，ar的概率用∏ri=1pΦi来近似替代。

对r轮迭代密码算法的差分密码分析的基本过程可总结为如下步骤： 

① 找出一个概率最大的(r-1)轮特征Φ(r-1)=a0,a1,…，ar-1；

② 均匀、随机地选择明文X0，计算出X*0。对2m个最后一轮的子密钥Kr(或Kr的部分)的可能值Kjr，设置相应的2m个计数器，用每个可能值Kjr解密Xr和X*r，得到Xr-1和X*r-1，如果Xr-1和X*r-1的差分是ar-1，则相应的计数器加1； 

③ 反复执行②，若出现一个或几个明显高于其他计数器的值，则输出它们所对应的密钥或部分。

以上只是差分分析的基本原理，在实际应用中，有些步骤可能难以实现。例如，可能由于Kr的选取空间过大，攻击者只能转而选择推测Kr的部分。在1992年的国际密码学会议上，Biham和Shamir改进了之前的攻击方法，对16轮的DES来说，差分攻击的攻击复杂度为247个明文密文对。

3．9．2线性密码分析

线性密码分析［14］最早由松井充松井充(1961—)，日本密码学家，现为三菱电机公司高级研究员。于1993年提出，它起初也是针对DES的一种分析手段。线性密码分析属于已知明文攻击方法，攻击者能获取明文密文对，通过寻找明、密文间的不平衡的线性逼近表达式，从而恢复密钥。在介绍线性分析前，首先介绍线性分析中用到的堆积引理。

堆积引理设Xi(1≤i≤n)是独立的随机变量P(Xi=0)=pi，P(Xi=1)=1-pi,则
P(X1X2…Xi=0)=1/2+2n-1·∏ni=1(pi-1/2)
线性分析的第一步是寻找以下形式的不平衡的线性表达式： 
M［i1,i2，…，ia］C［j1,j2，…，jb］=K［k1,k2，…，kc］
其中用i1,i2，…，ia，j1,j2，…，jb，k1,k2，…，kc表示固定的数据位位置。对随机的明文M和相应的密文C，上述等式成立的概率p≠1/2，将|p-1/2|称为逼近优势，以此来刻画该等式的有效性。为了寻找非平衡的线性表达式，首先计算单个轮函数的输入、输出的线性逼近及其成立的概率，分组密码算法的线性逼近的概率与每一轮的线性逼近的概率有关，由堆积引理来计算明文密文对和密钥的线性逼近的概率。

对r轮迭代密码算法的线性密码分析的基本过程可以总结为以下步骤： 

① 首先找出一个(r-1)轮线性逼近式(α，β)，其中α表示输入掩码，β表示输出掩码，且其偏差|ε(α，β)|较大； 

② 利用区分器的输出，攻击者确定恢复的第r轮子密钥Kr(或Kr的部分)，设攻击的密钥量为h，对每个可能的候选密钥gki，0≤i≤2h-1，设置相应的2h个计数器； 

③ 均匀、随机地选取明文X，在同一个未知密钥k(即在未知的轮密钥k1,k2，…，kr)下加密，获得相应的密文Z； 

④ 对每个密文Z,用第r轮中每个猜测密钥的轮密钥gki对其解密，得到Yr-1，计算αXβYr-1是否为0，若是，则给相应的计算器λi加1； 

⑤ 将2h个计数器中λim-12最大值所对应的密钥gki作为攻击获得的正确密钥值。

差分密码分析和线性密码分析是现代密码学极有意义的成果之一。在这些分析手段的基础上，之后高阶差分密码分析、飞来去器攻击、不可能差分密码分析，以及两者相结合的差分线性分析等相继被提出，这里不再赘述，感兴趣的读者可以在文献［4］中找到这些分析手段的相关原理和具体步骤。

3．9．3中间相遇攻击

1977年，Whitfield DiffieWhitfield Diffie(1944—)，美国著名密码学家，公钥加密的先驱之一。等人提出中间相遇攻击方法［8］，其分析的对象依旧是DES算法。中间相遇攻击大致可分为两部分： 中间相遇阶段通过部分加解密匹配过滤一部分错误密钥，减小密钥空间； 密钥检测阶段穷尽搜索剩余密钥，利用新的明文密文对确定唯一正确的密钥。中间相遇攻击的核心思想是将一个密码算法分为两部分： C=E(k1,k2)(P)=E″k2(E′k1(P))，假设攻击者拥有明文密文对(Pi，Ci)，1≤i≤n，中间相遇攻击的步骤如下： 

① 首先，固定明文Pi的某字节x之外的全部字节，单独取遍字节x的所有可能值。计算C*i=E′k1(Pi)。记录C*i在某个位置s的值y，且将x和y的关系表示为y=f(x)，函数f可以由算法E′和k1决定。

② 对所有可能的k2，计算出C**i=E″-1k2(C*i)，检查位置s的值y′=y是否成立，若不成立，则淘汰相应的k2。

③ 对所有的i，重复上述两步，最终获得正确的密钥。

以使用两个不同密钥的双重DES算法EE2为例，如下： 
EE2(m)=Enck2(Enck1(m))
每个密钥的长度为κ，攻击者首先选择信息m，之后计算出在所有可能的k1下的Enck1(m)，并放入表中； 在得到密文c后，使用所有的k2值对c解密，将得到的结果放入另一个表中。通过寻找两个表中相同的值，可以得到密钥(k1,k2)的可能值。注意，例子中并不是对部分字节固定，而是计算了密钥的所有可能值。这是因为实际应用中需要对内存和时间代价权衡考虑，分析证明，对于双重DES，中间相遇攻击大致需要256+α+3次加/解密操作，以及256-α条用于保存中间信息的内存，α为整数。

基础的中间相遇攻击需要对密钥空间进行独立子集合划分，通常要求加密结构和密钥扩展算法足够简单且扩散速度慢，这种要求在一定程度上限制了中间相遇攻击的应用范围。此后出现的多种改进的中间相遇攻击放宽了对密钥集合划分或筛选条件的限制，例如2008年提出的针对8轮AES256的中间相遇攻击［9］、2014年提出的对AES的安全性分析［10］等都取得了较好的效果。

思考题与习题

31为了保证分组密码算法的安全强度，对分组密码算法的要求有哪些?

32简述分组密码的设计原则。

33什么是SPN网络?

34什么是Feistel密码结构?主要有什么特点？

35什么是分组密码的操作模式?分组密码有哪些主要的操作模式?其工作原理是什么?各有何特点?

36简述DES的加密思想和f函数特性。

37请证明DES结构的互补对称性，即DES()=DESK(M)。

38请用DES的8个S盒对48位串70a990f5fc36进行压缩置换，用十六进制写出每个S盒的输出。

39除三重DES外，还有什么方式可以提高DES的安全性？

310设DES算法的8个S盒都为S1，且R0=FFFFFFFF，K1=555555555555(均为十六进制表示)，求f(R0，K1)。

311对DES和AES进行比较，说明两者的特点和优缺点。

312AES的基本变换有哪些?

313设m=b5c9179eb1cc1199b9c51b92b5c8159d，请给出AES中的字节替换变换SubBytes(m)的输出(用十六进制表示)。

314AES的加密算法和解密算法之间有何不同?

315在CBC模式中，若传输中一个密文字符的中位发生了错误，这个错误将传播多远？

316使用C或者C++语言编程实现SM4在CBC模式和OFB模式下的加解密过程。要求指定明文文件、密钥文件、初始化向量文件的位置和名称，加密完成后密文文件的位置和名称。(加密时先分别从指定的明文文件、密钥文件和初始化向量文件中读取有关信息，然后分别按CBC和OFB模式进行加密，最后将密文(用十六进制表示)写入指定的密文文件。解密过程与此类似。)

317SM4是基于非平衡Feistel结构的国密分组密码算法，PRESENT和CLEFIA是两种可面向硬件环境的轻量级分组密码算法，试从算法结构上分析和比较这三种分组密码算法。

318差分密码分析和线性密码分析是针对分组密码算法的两种密码分析方法，请简述这两种方法的基本思想。