《《分组密码体制》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《分组密码体制》PPT课件.ppt（197页珍藏版）》请在三一办公上搜索。
1、第3章 分组密码体制,3.1 分组密码概述3.2 数据加密标准3.3 差分密码分析与线性密码分析3.4 分组密码的运行模式3.5 IDEA3.6 AES算法Rijndael习题,在许多密码系统中，单钥分组密码是系统安全的一个重要组成部分，用分组密码易于构造伪随机数生成器、流密码、消息认证码（MAC）和杂凑函数等，还可进而成为消息认证技术、数据完整性机制、实体认证协议以及单钥数字签字体制的核心组成部分。实际应用中对于分组密码可能提出多方面的要求，除了安全性外，还有运行速度、存储量（程序的长度、数据分组长度、高速缓存大小）、实现平台（硬件、软件、芯片）、运行模式等限制条件。这些都需要与安全性要求之
2、间进行适当的折中选择。,3.1分组密码概述,分组密码是将明文消息编码表示后的数字序列x0,x1,xi,划分成长为n的组x=(x0,x1,xn-1)，各组（长为n的矢量）分别在密钥k=(k0,k1,kt-1)控制下变换成等长的输出数字序列y=(y0,y1,ym-1)（长为m的矢量），其加密函数E：VnKVm，Vn和Vm分别是n维和m维矢量空间，K为密钥空间，如图3.1所示。它与流密码不同之处在于输出的每一位数字不是只与相应时刻输入的明文数字有关，而是与一组长为n的明文数字有关。在相同密钥下，分组密码对长为n的输入明文组所实施的变换是等同的，所以只需研究对任一组明文数字的变换规则。这种密码实质上是
3、字长为n的数字序列的代换密码。,图3.1 分组密码框图,通常取m=n。若mn，则为有数据扩展的分组密码；若mn，则为有数据压缩的分组密码。在二元情况下，x和y均为二元数字序列，它们的每个分量xi，yiGF(2)。本节将主要讨论二元情况。设计的算法应满足下述要求：,分组长度n要足够大，使分组代换字母表中的元素个数2n足够大，防止明文穷举攻击法奏效。DES、IDEA、FEAL和LOKI等分组密码都采用n=64，在生日攻击下用232组密文成功概率为1/2，同时要求23264b=215MB存贮，故采用穷举攻击是不现实的。,密钥量要足够大（即置换子集中的元素足够多），尽可能消除弱密钥并使所有密钥同等地好
4、，以防止密钥穷举攻击奏效。但密钥又不能过长，以便于密钥的管理。DES采用56比特密钥，看来太短了，IDEA采用128比特密钥，据估计，在今后3040年内采用80 比特密钥是足够安全的。,由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，能抗击各种已知的攻击，如差分攻击和线性攻击；有高的非线性阶数，实现复杂的密码变换；使对手破译时除了用穷举法外，无其它捷径可循。,加密和解密运算简单，易于软件和硬件高速实现。如将分组n化分为子段，每段长为8、16或者32。在以软件实现时，应选用简单的运算，使作用于子段上的密码运算易于以标准处理器的基本运算，如加、乘、移位等实现，避
5、免用以软件难于实现的逐比特置换。为了便于硬件实现，加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同而已。这样，加密和解密就可用同一器件实现。设计的算法采用规则的模块结构，如多轮迭代等，以便于软件和VLSI快速实现。此外，差错传播和数据扩展要尽可能地小。,数据扩展。一般无数据扩展，在采用同态置换和随机化加密技术时可引入数据扩展。差错传播尽可能地小。,要实现上述几点要求并不容易。首先，要在理论上研究有效而可靠的设计方法，而后进行严格的安全性检验，并且要易于实现。下面介绍设计分组密码时的一些常用方法。,如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值。为使加密运算
6、可逆（使解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有2n!个。,3.1.1 代换,图3.2表示n=4的代换密码的一般结构，4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特表示。加密映射和解密映射可由代换表来定义，如表3.1所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。（见33页表3.1）,图3.2 代换结构,但这种代换结构在实用中还有一些问题需考虑。如果分组长度太小，如n=4，系统则等价于古典的
7、代换密码，容易通过对明文的统计分析而被攻破。这个弱点不是代换结构固有的，只是因为分组长度太小。如果分组长度n足够大，而且从明文到密文可有任意可逆的代换，那么明文的统计特性将被隐藏而使以上的攻击不能奏效。,然而，从实现的角度来看，分组长度很大的可逆代换结构是不实际的。仍以表3.1为例，该表定义了n=4时从明文到密文的一个可逆映射，其中第2列是每个明文分组对应的密文分组的值，可用来定义这个可逆映射。因此从本质上来说，第2列是从所有可能映射中决定某一特定映射的密钥。这个例子中，密钥需要64比特。一般地，对n比特的代换结构，密钥的大小是n2n比特。如对64比特的分组，密钥大小应是64264=27010
8、21比特，因此难以处理。,实际中常将n分成较小的段，例如可选n=rn0，其中r和n0都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。一般n0都不太大，称每个子代换为代换盒，简称为S盒。例如DES中将输入为48比特、输出为32比特的代换用8个S盒来实现，每个S盒的输入端数仅为6比特，输出端数仅为4比特。,扩散和混淆是由Shannon提出的设计密码系统的两个基本方法，目的是抗击敌手对密码系统的统计分析。如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密
9、钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合。在Shannon称之为理想密码的密码系统中，密文的所有统计特性都与所使用的密钥独立。图3.2讨论的代换密码就是这样的一个密码系统，然而它是不实用的。,3.1.2 扩散和混淆,所谓扩散，就是将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，等价于说密文中每一位均受明文中多位影响。例如对英文消息M=m1m2m3的加密操作其中ord(mi)是求字母mi对应的序号，chr(i)是求序号i对应的字母。这时明文的统计特性将被散布到密文中，因而每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频
10、率也更接近于相等。在二元分组密码中，可对数据重复执行某个置换，再对这一置换作用于一函数，可获得扩散。,分组密码在将明文分组依靠密钥变换到密文分组时，扩散的目的是使明文和密文之间的统计关系变得尽可能复杂，以使敌手无法得到密钥；混淆是使密文和密钥之间的统计关系变得尽可能复杂，以使敌手无法得到密钥。因此即使敌手能得到密文的一些统计关系，由于密钥和密文之间的统计关系复杂化，敌手也无法得到密钥。使用复杂的代换算法可以得到预期的混淆效果，而简单的线性代换函数得到的混淆效果则不够理想。扩散和混淆成功地实现了分组密码的本质属性，因而成为设计现代分组密码的基础。,很多分组密码的结构从本质上说都是基于一个称为Fe
11、istel网络的结构。Feistel提出利用乘积密码可获得简单的代换密码，乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果，Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。,3.1.3 Feistel密码结构,1.Feistel加密结构图3.3是Feistel网络示意图，加密算法的输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第i轮迭代的输入为前一轮输出的函数：其中Ki是第i轮用的子密钥，由加
12、密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。,图3.3 Feistel网络示意图,Feistel网络中每轮结构都相同，每轮中右半数据被作用于轮函数F后，再与左半数据进行异或运算，这一过程就是上面介绍的代换。每轮的轮函数的结构都相同，但以不同的子密钥Ki作为参数。代换过程完成后，再交换左、右两半数据，这一过程称为置换。这种结构是Shannon提出的代换置换网络（substitution-permutation network,SPN）的特有形式。,Feistel网络的实现与以下参数和特性有关：分组大小分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64比
13、特。密钥大小密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或更短的密钥长度是不安全的，通常使用128比特的密钥长度。轮数单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。子密钥产生算法该算法的复杂性越大，则密码分析的困难性就越大。轮函数轮函数的复杂性越大，密码分析的困难性也越大。,在设计Feistel网络时，还有以下两个方面需要考虑：快速的软件实现在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。算法容易分析如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。,2.Feis
14、tel解密结构Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥Ki的次序与加密过程相反，即第1轮使用Kn，第2轮使用Kn-1，最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。,图3.4的左边表示16轮Feistel网络的加密过程，右边表示解密过程，加密过程由上而下，解密过程由下而上。为清楚起见，加密算法每轮的左右两半用LEi和REi表示，解密算法每轮的左右两半用LDi和RDi表示。图中右边标出了解密过程中每一轮的中间值与左边加密过程中间值的对应关系，即加密过程第i轮的输出是LEiREi（表示链接），解密过程第16-i轮相应的输入是RDiLDi。,图3
15、.4 Feistel加解密过程,加密过程的最后一轮执行完后，两半输出再经交换，因此密文是RE16LE16。解密过程取以上密文作为同一算法的输入，即第1轮输入是RE16LE16，等于加密过程第16轮两半输出交换后的结果。下面证明解密过程第1轮的输出等于加密过程第16轮输入左右两半的交换值。,在加密过程中：在解密过程中,所以解密过程第1轮的输出为LE15RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第i轮有因此,以上两式描述了加密过程中第i轮的输入与第i轮输出的函数关系，由此关系可得图3.4右边显示的LDi和RDi的取值关系。最
16、后可以看到，解密过程第16轮的输出是RE0LE0，左右两半再经一次交换后即得最初的明文。,数据加密标准（data encryption standard,DES）是迄今为止世界上最为广泛使用和流行的一种分组密码算法，它的分组长度为64比特，密钥长度为56比特，它是由美国IBM公司研制的，是早期的称作Lucifer密码的一种发展和修改。DES在1975年3月17日首次被公布在联邦记录中，经过大量的公开讨论后，DES于1977年1月15日被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。规定每隔5年由美国国家保密局（national security agency,N
17、SA）作出评估，并重新批准它是否继续作为联邦加密标准。,3.2 数据加密标准,最近的一次评估是在1994年1月，美国已决定1998年12月以后将不再使用DES。1997年DESCHALL小组经过近4个月的努力，通过Internet搜索了31016个密钥，找出了DES的密钥，恢复出了明文。1998年5月美国EFF(electronics frontier foundation)宣布，他们以一台价值20万美元的计算机改装成的专用解密机，用56小时破译了56 比特密钥的DES。美国国家标准和技术协会已征集并进行了几轮评估、筛选，产生了称之为AES(advanced encryption standa
18、rd)的新加密标准。尽管如此，DES对于推动密码理论的发展和应用毕竟起了重大作用，对于掌握分组密码的基本理论、设计思想和实际应用仍然有着重要的参考价值，下面首先来描述这一算法。,图3.5是DES加密算法的框图，其中明文分组长为64比特，密钥长为56比特。图的左边是明文的处理过程，有3个阶段，首先是一个初始置换IP，用于重排明文分组的64比特数据。然后是具有相同功能的16轮变换，每轮中都有置换和代换运算，第16轮变换的输出分为左右两半，并被交换次序。最后再经过一个逆初始置换IP-1（为IP的逆）从而产生64比特的密文。除初始置换和逆初始置换外，DES的结构和图3.3所示的Feistel密码结构完
19、全相同。,3.2.1 DES描述,图3.5 DES加密算法框图,图3.5的右边是使用56比特密钥的方法。密钥首先通过一个置换函数，然后，对加密过程的每一轮，通过一个左循环移位和一个置换产生一个子密钥。其中每轮的置换都相同，但由于密钥被重复迭代，所以产生的每轮子密钥不相同。,1.初始置换DES的置换表见表3.2。（见40页表3.2）表3.2(a)和表3.2(b)分别给出了初始置换和逆初始置换的定义，为了显示这两个置换的确是彼此互逆的，考虑下面64比特的输入M：,M1 M2 M3 M4 M5 M6 M7 M8M9 M10 M11 M12 M13 M14 M15 M16 M17 M18 M19 M2
20、0 M21 M22 M23 M24M25 M26 M27 M28 M29 M30 M31 M32M33 M34 M35 M36 M37 M38 M39 M40M41 M42 M43 M44 M45 M46 M47 M48M49 M50 M51 M52 M53 M54 M55 M56M57 M58 M59 M60 M61 M62 M63 M64,其中Mi是二元数字。由表3.2(a)得X=IP(M)为：M58 M50 M42 M34 M26 M18 M10 M2M60 M52 M44 M36 M28 M20 M12 M4M62 M54 M46 M38 M30 M22 M14 M6M64 M56 M
21、48 M40 M32 M24 M16 M8M57 M49 M41 M33 M25 M17 M9 M1M59 M51 M43 M35 M27 M19 M11 M3M61 M53 M45 M37 M29 M21 M13 M5M63 M55 M47 M39 M31 M23 M15 M7,如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M)，可以看出，M各位的初始顺序将被恢复。,2.轮结构图3.6是DES加密算法的轮结构。,图3.6 DES加密算法的轮结构,首先看图的左半部分。将64比特的轮输入分成各为32比特的左、右两半，分别记为L和R。和Feistel网络一样，每轮变换可由以下公式表示：,其
22、中轮密钥Ki为48比特，函数F(R,K)的计算过程如图3.7所示。轮输入的右半部分R为32比特，R首先被扩展成48比特，扩展过程由表3.2(c)定义，其中将R的16个比特各重复一次。扩展后的48比特再与子密钥Ki异或，然后再通过一个S盒，产生32比特的输出。该输出再经过一个由表3.2(d)定义的置换，产生的结果即为函数F(R,K)的输出。,图3.7 函数F(R,K)的计算过程,F中的代换由8个S盒组成，每个S盒的输入长为6比特、输出长为4比特，其变换关系由表3.3定义，每个S盒给出了4个代换（由一个表的4行给出）。（见42页表3.3）,对每个盒Si，其6比特输入中，第1个和第6个比特形成一个2
23、位二进制数，用来选择Si的4个代换中的一个。6比特输入中，中间4位用来选择列。行和列选定后，得到其交叉位置的十进制数，将这个数表示为4位二进制数即得这一S盒的输出。例如，S1 的输入为011001，行选为01（即第1行），列选为1100（即第12列），行列交叉位置的数为9，其4位二进制表示为1001，所以S1的输出为1001。S盒的每一行定义了一个可逆代换，图3.2（在3.1.1节）表示S1第0行所定义的代换。,3.密钥的产生再看图3.5和图3.6，输入算法的56比特密钥首先经过一个置换运算，该置换由表3.4(a)给出，然后将置换后的56比特分为各为28比特的左、右两半，分别记为C0和D0。在
24、第i 轮分别对Ci-1和Di-1进行左循环移位，所移位数由表3.4(c)给出。移位后的结果作为求下一轮子密钥的输入，同时也作为置换选择2的输入。通过置换选择2产生的48比特的Ki，即为本轮的子密钥，作为函数F(Ri-1,Ki)的输入。其中置换选择2由表3.4(b)定义。（见44页表3.4）,4.解密和Feistel密码一样，DES的解密和加密使用同一算法，但子密钥使用的顺序相反。,为了提高DES的安全性，并利用实现DES的现有软硬件，可将DES算法在多密钥下多重使用。二重DES是多重使用DES时最简单的形式，如图3.8所示。其中明文为P，两个加密密钥为K1和K2，密文为：解密时，以相反顺序使用
25、两个密钥：,3.2.2 二重DES,图3.8 二重DES,因此，二重DES所用密钥长度为112比特，强度极大地增加。然而，假设对任意两个密钥K1和K2，能够找出另一密钥K3，使得,那么，二重DES以及多重DES都没有意义，因为它们与56比特密钥的单重DES等价，好在这种假设对DES并不成立。将DES加密过程64比特分组到64比特分组的映射看作一个置换，如果考虑264个所有可能的输入分组，则密钥给定后，DES的加密将把每个输入分组映射到一个惟一的输出分组。否则，如果有两个输入分组被映射到同一分组，则解密过程就无法实施。对264个输入分组，总映射个数为。,另一方面，对每个不同的密钥，DES都定义了
26、一个映射，总映射数为2561017。因此，可假定用两个不同的密钥两次使用DES，可得一个新映射，而且这一新映射不出现在单重DES定义的映射中。这一假定已于1992年被证明。所以使用二重DES产生的映射不会等价于单重DES加密。但对二重DES有以下一种称为中途相遇攻击的攻击方案，这种攻击不依赖于DES的任何特性，因而可用于攻击任何分组密码。其基本思想如下：,如果有那么（见图3.8）,如果已知一个明文密文对(P,C)，攻击的实施可如下进行：首先，用256个所有可能的K1对P加密，将加密结果存入一表并对表按X排序，然后用256个所有可能的K2对C解密，在上述表中查找与C解密结果相匹配的项，如果找到，
27、则记下相应的K1和K2。最后再用一新的明文密文对(P,C)检验上面找到的K1和K2，用K1和K2对P两次加密，若结果等于C，就可确定K1和K2是所要找的密钥。,对已知的明文P，二重DES能产生264个可能的密文,而可能的密钥个数为2112，所以平均来说，对一个已知的明文，有2112/264=248个密钥可产生已知的密文。而再经过另外一对明文密文的检验，误报率将下降到248-64=2-16。所以在实施中途相遇攻击时，如果已知两个明文密文对，则找到正确密钥的概率为1-2-16。,抵抗中途相遇攻击的一种方法是使用3个不同的密钥做3次加密，从而可使已知明文攻击的代价增加到2112。然而，这样又会使密钥
28、长度增加到563=168比特，因而过于笨重。一种实用的方法是仅使用两个密钥做3次加密，实现方式为加密|解密|加密，简记为EDE(encryptdecryptencrypt)，见图3.9，即：,3.2.3 两个密钥的三重DES,图3.9 两个密钥的三重DES,此方案已在密钥管理标准ANS X.917和ISO 8732中被采用。,三个密钥的三重DES密钥长度为168比特，加密方式为令K3=K2或K1=K2，则变为一重DES。三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用。,3.2.4 三个密钥的三重DES,差分密码分析是迄今已知的攻击迭代密码最有效的方法之一，其基本思想
29、是：通过分析明文对的差值对密文对的差值的影响来恢复某些密钥比特。,3.3 差分密码分析与线性密码分析 3.3.1 差分密码分析,对分组长度为n的r轮迭代密码，两个n比特串Yi和Y*i的差分定义为其中表示n比特串集上的一个特定群运算，表示 在此群中的逆元。由加密对可得差分序列Y0,Y1,Yr其中Y0和Y*0是明文对，Yi和Y*i(1ir)是第i轮的输出，它们同时也是第i+1轮的输入。第i轮的子密钥记为Ki，F是轮函数，且Yi=F(Yi-1,Ki)。,定义3.1 r-轮特征(r-round characteristic)是一个差分序列：0,1,r其中0是明文对Y0和Y*0的差分，i(1ir)是第i
30、轮输出Yi和Y*i的差分。r-轮特征=0,1,r的概率是指在明文Y0和子密钥K1,Kr独立、均匀随机时，明文对Y0和Y*0的差分为0的条件下，第i(1ir)轮输出Yi和Y*i的差分为i的概率。,定义3.2 在r-轮特征=0,1,r中，定义=P(F(Y)=i|Y=i-1)即 表示在输入差分为i-1的条件下，轮函数F的输出差分为i的概率。r-轮特征=0,1,r的概率近似看作。,对r-轮迭代密码的差分密码分析过程可综述为如下的步骤：找出一个(r-1)-轮特征(r-1)=0,1,r-1，使得它的概率达到最大或几乎最大。均匀随机地选择明文Y0并计算Y*0，使得Y0和Y*0的差分为0，找出Y0和Y*0在实
31、际密钥加密下所得的密文Yr和Y*r。若最后一轮的子密钥Kr（或Kr的部分比特）有2m个可能值Kjr(1j2m)，设置相应的2m个计数器j(1j2m)；用每个Kjr解密密文Yr和Y*r，得到Yr-1和Y*r-1，如果Yr-1和Y*r-1的差分是r-1，则给相应的计数器j加1。,重复步骤，直到一个或几个计数器的值明显高于其他计数器的值，输出它们所对应的子密钥（或部分比特）。,一种攻击的复杂度可以分为两部分：数据复杂度和处理复杂度。数据复杂度是实施该攻击所需输入的数据量；而处理复杂度是处理这些数据所需的计算量。这两部分的主要部分通常被用来刻画该攻击的复杂度。,差分密码分析的数据复杂度是成对加密所需的
32、选择明文对(Y0,Y*0)个数的两倍。差分密码分析的处理复杂度是从(Yr-1,Yr,Y*r)找出子密钥Kr（或Kr的部分比特）的计算量，它实际上与r无关，而且由于轮函数是弱的，所以此计算量在大多数情况下相对较小。因此，差分密码分析的复杂度取决于它的数据复杂度。,线性密码分析是对迭代密码的一种已知明文攻击，它利用的是密码算法中的“不平衡（有效）的线性逼近”。设明文分组长度和密文分组长度都为n比特，密钥分组长度为m比特。记明文分组为P1，P2，,Pn，密文分组为C1，C2，Cn，密钥分组为K1，K2，Km。定义。,3.3.2 线性密码分析,线性密码分析的目标就是找出以下形式的有效线性方程：其中1a
33、n,1bn,1cm。如果方程成立的概率p1/2，则称该方程是有效的线性逼近。如果 是最大的，则称该方程是最有效的线性逼近。,设N表示明文数，T是使方程左边为0的明文数。如果TN/2，则令如果TN/2，则令从而可得关于密钥比特的一个线性方程。对不同的明文密文对重复以上过程，可得关于密钥的一组线性方程，从而确定出密钥比特。,研究表明，当 充分小时，攻击成功的概率是这一概率只依赖于，并随着N或 的增加而增加。,如何对差分密码分析和线性密码分析进行改进，降低它们的复杂度仍是现在理论研究的热点，目前已推出了很多改进方法，例如,高阶差分密码分析、截段差分密码分析（truncated differentia
34、l cryptanalysis）、不可能差分密码分析、多重线性密码分析、非线性密码分析、划分密码分析和差分-线性密码分析，再如针对密钥编排算法的相关密钥攻击、基于Lagrange插值公式的插值攻击及基于密码器件的能量分析（power analysis），另外还有错误攻击、时间攻击、Square攻击和Davies攻击等。,分组密码在加密时,明文分组的长度是固定的，而实际应用中待加密消息的数据量是不定的，数据格式可能是多种多样的。为了能在各种应用场合使用DES，美国在FIPS PUS 74和81中定义了DES的4种运行模式，如表3.5所示。这些模式也可用于其他分组密码，下面以DES为例来介绍这4种
35、模式。（见49页表3.5）,3.4 分组密码的运行模式,ECB(electronic codebook)模式是最简单的运行模式，它一次对一个64比特长的明文分组加密，而且每次的加密密钥都相同，如图3.10所示。当密钥取定时，对明文的每一个分组，都有一个惟一的密文与之对应。因此形象地说，可以认为有一个非常大的电码本，对任意一个可能的明文分组，电码本中都有一项对应于它的密文。,3.4.1 电码本（ECB）模式,图3.10 ECB模式示意图,如果消息长于64比特，则将其分为长为64比特的分组，最后一个分组如果不够64比特，则需要填充。解密过程也是一次对一个分组解密，而且每次解密都使用同一密钥。图3.
36、10中，明文是由分组长为64比特的分组序列P1，P2，PN构成，相应的密文分组序列是C1，C2，CN。,ECB在用于短数据（如加密密钥）时非常理想，因此如果需要安全地传递DES密钥，ECB是最合适的模式。ECB的最大特性是同一明文分组在消息中重复出现的话，产生的密文分组也相同。ECB用于长消息时可能不够安全，如果消息有固定结构，密码分析者有可能找出这种关系。例如，如果已知消息总是以某个预定义字段开始，那么分析者就可能得到很多明文密文对。如果消息有重复的元素而重复的周期是64的倍数，那么密码分析者就能够识别这些元素。以上这些特性都有助于密码分析者，有可能为其提供对分组的代换或重排的机会。,为了解
37、决ECB的安全缺陷，可以让重复的明文分组产生不同的密文分组，CBC（cipher block chaining）模式就可满足这一要求。图3.11是CBC模式示意图，它一次对一个明文分组加密，每次加密使用同一密钥,加密算法的输入是当前明文分组和前一次密文分组的异或，因此加密算法的输入不会显示出与这次的明文分组之间的固定关系，所以重复的明文分组不会在密文中暴露出这种重复关系。,3.4.2 密码分组链接（CBC）模式,图3.11 CBC模式示意图,解密时，每一个密文分组被解密后，再与前一个密文分组异或，即（设）因而产生出明文分组。,在产生第1个密文分组时，需要有一个初始向量IV与第1个明文分组异或。
38、解密时，IV和解密算法对第1个密文分组的输出进行异或以恢复第1个明文分组。IV对于收发双方都应是已知的，为使安全性最高，IV应像密钥一样被保护，可使用ECB加密模式来发送IV。保护IV的原因如下：如果敌手能欺骗接收方使用不同的IV值，敌手就能够在明文的第1个分组中插入自己选择的比特值，这是因为：,用X(i)表示64比特分组X的第i个比特，那么，由异或的性质得其中撇号表示比特补。上式意味着如果敌手篡改IV中的某些比特，则接收方收到的P1中相应的比特也发生了变化。,由于CBC 模式的链接机制，CBC模式对加密长于64比特的消息非常合适。CBC模式除能够获得保密性外，还能用于认证。,如上所述，DES
39、是分组长为64比特的分组密码，但利用CFB（cipher feedback）模式或OFB模式可将DES转换为流密码。流密码不需要对消息填充，而且运行是实时的。因此如果传送字母流，可使用流密码对每个字母直接加密并传送。流密码具有密文和明文一样长这一性质，因此，如果需要发送的每个字符长为8比特，就应使用8比特密钥来加密每个字符。如果密钥长超过8比特，则造成浪费。,3.4.3 密码反馈（CFB）模式,图3.12是CFB模式示意图，设传送的每个单元（如一个字符）是j比特长，通常取j=8，与CBC模式一样，明文单元被链接在一起，使得密文是前面所有明文的函数。,图3.12 CFB模式示意图,加密时，加密算
40、法的输入是64比特移位寄存器，其初值为某个初始向量IV。加密算法输出的最左（最高有效位）j比特与明文的第一个单元P1进行异或，产生出密文的第1个单元C1，并传送该单元。然后将移位寄存器的内容左移j位并将C1送入移位寄存器最右边（最低有效位）j位。这一过程继续到明文的所有单元都被加密为止。,解密时，将收到的密文单元与加密函数的输出进行异或。注意这时仍然使用加密算法而不是解密算法，原因如下：设Sj(X)是X的j个最高有效位，那么因此可证明以后各步也有类似的这种关系。CFB模式除能获得保密性外，还能用于认证。,OFB（output feedback）模式的结构类似于CFB，见图3.13。不同之处如下
41、：OFB模式是将加密算法的输出反馈到移位寄存器，而CFB模式中是将密文单元反馈到移位寄存器。,3.4.4 输出反馈(OFB)模式,图3.13 OFB模式示意图,OFB（output feedback）模式的结构类似于CFB，见图3.13。不同之处如下：OFB模式是将加密算法的输出反馈到移位寄存器，而CFB模式中是将密文单元反馈到移位寄存器。,OFB模式的优点是传输过程中的比特错误不会被传播。例如C1中出现1比特错误，在解密结果中只有P1受到影响，以后各明文单元则不受影响。而在CFB中，C1也作为移位寄存器的输入，因此它的1比特错误会影响解密结果中各明文单元的值。,OFB的缺点是它比CFB模式更
42、易受到对消息流的篡改攻击，比如在密文中取1比特的补，那么在恢复的明文中相应位置的比特也为原比特的补。因此使得敌手有可能通过对消息校验部分的篡改和对数据部分的篡改，而以纠错码不能检测的方式篡改密文。,瑞士联邦技术学院来学嘉（X.J.Lai）和J.L.Massey提出的第1版IDEA（international data encryption algorithm，国际数据加密算法）于1990年公布，当时称为PES（proposed encryption standard，建议加密标准）。1991年，在Biham和Shamir提出差分密码分析之后，设计者推出了改进算法IPES，即改进型建议加密标准。
43、1992年，设计者又将IPES改名为IDEA。这是近年来提出的各种分组密码中一个很成功的方案，已在PGP中采用。,3.5 IDEA,算法中明文和密文分组长度都是64比特，密钥长128比特。其设计原理可从强度和实现两方面考虑。1.密码强度算法的强度主要是通过有效的混淆和扩散特性而得以保证。,3.5.1 设计原理,混淆是通过使用以下3种运算而获得，3种运算都有两个16比特的输入和一个16比特的输出：逐比特异或，表示为。模216（即65536）整数加法，表示为，其输入和输出作为16位无符号整数处理。模216+1（即65537）整数乘法，表示为，其输入、输出中除16位全为0作为216处理外，其余都作为
44、16位无符号整数处理。例如这是因为216215 mod(216+1)=215+1。,表3.6给出了操作数为2比特长时3种运算的运算表。在以下意义下，3种运算是不兼容的：（见55页表3.6）3种运算中任意两种都不满足分配律，例如a+（b c）(a+b)(a+c)3种运算中任意两种都不满足结合律，例如a+（b c）(a+b)c,+,3种运算结合起来使用可对算法的输入提供复杂的变换，从而使得对IDEA的密码分析比对仅使用异或运算的DES更为困难。算法中扩散是由称为乘加（multiplication/addition,MA）结构（见图3.14）的基本单元实现的。该结构的输入是两个16比特的子段和两个1
45、6比特的子密钥，输出也为两个16比特的子段。这一结构在算法中重复使用了8次，获得了非常有效的扩散效果。,图3.14 MA结构,2.实现IDEA可方便地通过软件和硬件实现。软件软件实现采用16比特子段处理，可通过使用容易编程的加法、移位等运算实现算法的3种运算。硬件由于加、解密相似，差别仅为使用密钥的方式，因此可用同一器件实现。再者，算法中规则的模块结构，可方便VLSI的实现。,加密过程（如图3.15所示）由连续的8轮迭代和一个输出变换组成，算法将64比特的明文分组分成4个16比特的子段，每轮迭代以4个16比特的子段作为输入，输出也为4个16比特的子段。最后的输出变换也产生4个16比特的子段，链
46、接起来后形成64比特的密文分组。每轮迭代还需使用6个16比特的子密钥，最后的输出变换需使用4个16比特的子密钥，所以子密钥总数为52。图3.15的右半部分表示由初始的128比特密钥产生52个子密钥的子密钥产生器。,3.5.2 加密过程,图3.15 IDEA的加密框图,1.轮结构图3.16是IDEA第1轮的结构示意图，以后各轮也都是这种结构，但所用的子密钥和轮输入不同。从结构图可见，IDEA不是传统的Feistel密码结构。每轮开始时有一个变换，该变换的输入是4个子段和4个子密钥，变换中的运算是两个乘法和两个加法，输出的4个子段经过异或运算形成了两个16比特的子段作为MA结构的输入。MA结构也有
47、两个输入的子密钥，输出是两个16比特的子段。,图3.16 IDEA第1轮的轮结构,最后，变换的4个输出子段和MA结构的两个输出子段经过异或运算产生这一轮的4个输出子段。注意，由X2产生的输出子段和由X3产生的输出子段交换位置后形成W12和W13，目的在于进一步增加混淆效果，使得算法更易抵抗差分密码分析。,算法的第9步是一个输出变换，如图3.17所示。它的结构和每一轮开始的变换结构一样，不同之处在于输出变换的第2个和第3个输入首先交换了位置，目的在于撤销第8轮输出中两个子段的交换。还需注意，第9步仅需4个子密钥，而前面8轮中每轮需要6个子密钥。,图3.17 IDEA的输出变换,2.子密钥的产生加
48、密过程中52个16比特的子密钥是由128比特的加密密钥按如下方式产生的：前8个子密钥Z1，Z2，Z8直接从加密密钥中取，即Z1取前16比特（最高有效位），Z2取下面的16比特，依次类推。然后加密密钥循环左移25位，再取下面8个子密钥Z9，Z10，Z16，取法与Z1，Z2，Z8的取法相同。这一过程重复下去，直到52子密钥都被产生为止。,3.解密过程解密过程和加密过程基本相同，但子密钥的选取不同。解密子密钥U1，U2，U52是由加密子密钥按如下方式得到（将加密过程最后一步的输出变换当作第9轮）：,第i(i=1,9)轮解密的前4个子密钥由加密过程第(10-i)轮的前4个子密钥得出：其中第1和第4个解
49、密子密钥取为相应的第1和第4个加密子密钥的模216+1乘法逆元，第2和第3个子密钥的取法为：当轮数i=2,8时，取为相应的第3个和第2个加密子密钥的模216加法逆元。i=1和9时，取为相应的第2个和第3个加密子密钥的模216加法逆元。第i(i=1,8)轮解密的后两个子密钥等于加密过程第(9-i)轮的后两个子密钥。,表3.7是对以上关系的总结。其中Zj的模216+1乘法逆元为Z-1j，满足（见58页表3.7）ZjZ-1j=1mod(216+1)因216+1是一素数，所以每一个不大于216的非0整数都有一个惟一的模216+1乘法逆元。Zj的模216加法逆元为-Zj，满足：-Zj+Zj=0 mod(
50、216),下面验证解密过程的确可以得到正确的结果。图3.18中左边为加密过程，由上至下，右边为解密过程，由下至上。将每一轮进一步分为两步，第1步是变换，其余部分作为第2步，称为子加密。,图3.18 IDEA加密和解密框图,现在从下往上考虑。对加密过程的最后一个输出变换，以下关系成立：Y1=W81 Z49 Y2=W83+Z50Y3=W82+Z51 Y4=W84Z52解密过程中第1轮的第1步产生以下关系：J11=Y1U1 J12=Y2+U2J13=Y3+U3 J14=Y4U4,将解密子密钥由加密子密钥表达并将Y1，Y2，Y3,，Y4代入以下关系，有J11=Y1Z-149=W81Z49Z-149=W
