1、第4章分组密码算法 第4章分组密码算法 4.1基本概念基本概念 4.2DES算法算法 4.3RC4算法算法 4.4AES算法算法 4.5IDEA算法算法 4.6SMS4算法算法 4.7加密模式加密模式 第4章分组密码算法 分组密码是将明文消息编码表示后的数字序列x1,x2,xi,，划分成长为 m 的组 x=(x0,x1,xm-1)，各组(长为 m 的矢量)分别在密钥 k=(k0,k1,kt-1)控制下变换成等长的输出数字序列 y=(y0,y1,yn-1)(长为 n 的矢量)，其加密函数E:VnKVn，Vn是 n 维矢量空间，K为密钥空间，参看图4.1.1 所示。4.1基本概念基本概念 第4章分
2、组密码算法 图4.1.1 分组密码加解密框图 第4章分组密码算法 分组算法与流密码的不同之处在于:输出的每一位数字不是只与相应时刻输入的明文数字有关,而是与一组长为m的明文数字有关。在相同密钥下,分组密码对长为m的输入明文组所实施的变换是等同的,所以只需研究对任一组明文数字的变换规则。这种密码实质上是字长为m的数字序列的代换密码。第4章分组密码算法 参数m和n的取值有以下三种情况:(1)通常取n=m,这种情况下称之为等长加密。(2)当nm时,为有数据扩展的分组密码,称之为扩展加密。(3)当nm时,为有数据压缩的分组密码,称之为压缩加密。这种情况下不能由密文恢复明文,主要用于数据完整性校验等,功
3、能上等同于第7章中的杂凑函数。第4章分组密码算法 密码学安全的分组算法应满足下述要求:(1)分组长度n要足够大,从而使分组代换字母表中的元素个数2n足够大,以防止明文穷举攻击奏效。(2)密钥量要足够大,尽可能消除弱密钥并使所有密钥同样好,以防止密钥穷举攻击奏效。但密钥又不能过长,以利于密钥的管理。从目前的实际情况来看,128bit的密钥长度是足够安全的,且128bit也常被认为是当前安全密钥的底限长度。(3)由密钥确定置换的算法要足够复杂,充分实现明文与密钥的扩散和混淆,没有简单的关系可循,要能抗击各种已知的攻击,如差分攻击和线性攻击等,使对手破译时除了用穷举法外,无其他捷径可循。第4章分组密
4、码算法(4)加密和解密运算简单,易于用软件和硬件高速实现。为了便于硬件实现,加密和解密过程之间的差别应仅在于由秘密密钥所生成的密钥表不同。这样,加密和解密就可用同一器件实现。设计的算法采用规则的模块结构,如多轮迭代等,以便于软件和VLSI快速实现。(5)数据扩展。一般无数据扩展,在采用同态置换和随机化加密技术时可引入数据扩展。(6)差错传播尽可能小。第4章分组密码算法 4.2DES算法算法 4.2.1历史背景历史背景随着计算机通信网的形成与发展,人们要求信息作业标准化。只有标准化,才能真正推动网络的发展和应用普及,便于训练、生产和降低成本。安全保密亦不例外,只有标准化,才能真正实现网络和信息的
5、安全。美国国家标准局(NBS)在1973年5月15日的联邦记录中公布了征求传输和存储数据系统中保护计算机数据的密码算法的建议,并要求NSA(NationalSecurityAgency,美国国家安全局)协助评估加密算法的安全性。此建议公布后,虽然公众反响表示支持这种标准化做法,但未征得可以公开使用的技术。1974年8月27日NBS再次提出公告以征求建议,并进一步阐述了这一需求的迫切性,对建议方案提出了如下要求:第4章分组密码算法(1)算法必须完全确定,而无含糊之处。(2)算法必须有足够高的保护水准,即可以检测到威胁,恢复密钥所必须的运算时间或运算次数足够大。(3)安全性必须只依赖于密钥的保密。
6、(4)对任何用户或产品供应者必须是不加区分的。第4章分组密码算法 4.2.2算法描述算法描述在介绍DES算法之前,我们简单地介绍一下Feistel加密结构。很多分组密码算法从本质上都是基于Feistel网络结构设计的。图4.2.1所示为Feistel网络示意图。第4章分组密码算法 图4.2.1Feistel网络示意图 第4章分组密码算法 加密算法的输入是分组长为2w的明文和一个密钥k,输出是一个长为2w的密文。Feistel的结构定义如图4.2.2所示,其中,ki是第i轮用的密钥。图4.2.2中,加密:Li=Ri-1Ri=Li-1F(Ri-1,Ki)解密:Ri-1=LiLi-1=RiF(Ri-
7、1,Ki)=RiF(Li,Ki)第4章分组密码算法 图4.2.2 Feistel的结构定义如第4章分组密码算法 在给出Feistel的网络定义后,下面介绍DES算法。DES是一种对二元数据进行加密的算法,数据分组长度为64bit(8Byte),密文分组长度也是64bit,没有数据扩展,密钥长度为64bit,其中有8bit奇偶校验,有效密钥长度为56bit。DES的整个体制是公开的,系统的安全性全靠密钥保密。DES算法的构成框图如图4.2.3所示。第4章分组密码算法 图4.2.3DES算法的构成框图 第4章分组密码算法 1.初始置换初始置换IP初始置换将64bit明文的位置进行交换,得到一个乱序
8、的64bit明文组,而后分成两段,每段为32bit,分别以L0和R0表示,如图4.2.4所示。由图4.2.4可知,IP中各列元素的位置号数相差8,实质上,其排列方法为:先将64bit按行排列为88的矩阵,选择其中第2、4、6、8、1、3、5、7列重新排成88矩阵,再将该矩阵顺时针旋转90即得初始置换IP,相当于将原明文的各字节按列读出以构成置换输出。第4章分组密码算法 图4.2.4初始置换IP 第4章分组密码算法 2.逆初始置换逆初始置换IP-1将16轮迭代后给出的64bit组进行置换,得到输出的密文组,如图4.2.5所示。图4.2.5中,输出为矩阵中元素按行读出的结果。第4章分组密码算法 图
9、4.2.5逆初始变换IP-1 第4章分组密码算法 3.乘积变换乘积变换图4.2.6给出了乘积变换的框图,它是DES算法的核心部分,将经过IP置换后的数据分成32bit的左、右两组,在迭代过程中彼此交换位置。每次迭代时只对右边的32bit进行一系列的加密变换,在此轮迭代即将结束时,把左边的32bit与右边得到的32bit逐位模2相加,作为下一轮迭代时右边的段,并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。在每一轮迭代时,右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P。第4章分组密码算法 图4.2.6乘积变换 第4章分组密码算法 1)选择扩展运算E
10、将输入的32bitRi-1扩展成48bit的输出,其变换表在图4.2.7中给出。令s表示E原输入数据比特的原下标,则E的输出是将原下标s0或1(mod4)的各比特重复一次得到的,即对原第32、1、4、5、8、9、12、13、16、17、20、21、24、25、28、29各位都重复一次,亦即第一列和最后一列重复,实现数据扩展。将表中数据按行读出,则得到48bit输出。第4章分组密码算法 图4.2.7选择扩展运算E 第4章分组密码算法 2)密钥加密运算将子密钥产生器输出的48bit子密钥ki与选择扩展运算E输出的48bit数据按位模2相加。第4章分组密码算法 3)选择压缩运算S将前面送来的48bi
11、t数据从左至右分成8组,每组为6bit。而后并行送入8个S盒,每个S盒为一线性代换网络,有4bit输出(6bit输入,其中4bit决定列，2bit决定行;4bit输出对应行和列决定的S盒中的元素)。S1S8盒的选择函数关系如表4.2.1表4.2.8所示。运算S的框图由图4.2.8给出。第4章分组密码算法 表 4.2.1 的 8 个S盒 1s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 2 4 1 14 8
12、 13 6 2 11 15 12 9 7 3 10 5 0 3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13 第4章分组密码算法 2s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 1 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 2 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 3 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9 表表4.2.2 S2盒盒第4章分组密码
13、算法 3s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 1 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 2 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 3 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12 表表4.2.3 S3盒盒第4章分组密码算法 4s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 7 13 14 3 0 6 9 10 1 2 8 5 11 1
14、2 4 15 1 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 2 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14 表表4.2.4 S4盒盒第4章分组密码算法 5s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 1 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 2 4 2 1 11 10 13 7 8 15 9 12 5
15、 6 3 0 14 3 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3 表表4.2.5 S5盒盒第4章分组密码算法 6s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 1 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 2 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 3 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13 表表4.2.6 S6盒盒第4章分组密码算法 表表4.2
16、.7 S7盒盒7s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 2 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 3 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12 第4章分组密码算法 表表4.2.8 S8盒盒8s 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 13 2 8 4 6 15 11 1 10 9 3 1
17、4 5 0 12 7 1 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 3 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11 第4章分组密码算法 图4.2.8选择压缩运算 第4章分组密码算法 第4章分组密码算法 DES所使用的S盒已经是现代几乎所有分组密码算法不可缺少的部件。S盒的作用是获得高非线性度。DES的S盒的设计细节始终没有公布,因此被人们怀疑其存在陷门(即密码设计者为自己预留的破译通道)。这种不透明的设计曾经严重地影响了商用市场。然而,这一缺点却引出
18、了商用分组密码设计的一个准则“透明性”,即密码的使用者能够确知该密码的安全强度。第4章分组密码算法 4)置换运算P对S1S8盒输出的32bit数据进行坐标变换,如图4.2.9所示。置换运算P起混淆的作用。置换运算P输出的32bit数据与左边32bit(Ri-1)按位模2相加,将所得到的32bit作为下一轮迭代用的右边的数字段,并将Ri-1并行送到左边的寄存器作为下一轮迭代用的左边的数字段。第4章分组密码算法 图4.2.9置换运算P 第4章分组密码算法 4.子密钥产生器子密钥产生器将64bit初始密钥经过置换选择PC1、循环移位置换、置换选择PC2给出每次迭代加密用的子密钥ki,参看图4.2.1
19、0。在64bit初始密钥中有8位为校验位,其位置号为8、16、24、32、40、48、56和64,其余56位为有效位,用于子密钥计算。将这56位送入置换选择PC1,参看图4.2.11。图4.2.11中,经过坐标置换后这56位分成两组,每组为28bit,分别送入C寄存器和D寄存器中。在各次迭代中,C和D寄存器分别将存数进行循环左移变换,移位次数见表4.2.9。每次移位以后,将C和D寄存器原存数送给置换选择PC2,见图4.2.12。图4.2.12中,置换选择PC2将C中的第9、18、22、25位和D中的第7、9、15、26位删去,并将其余数字置换位置后送出48bit数字作为第i次迭代时所用的子密钥
20、ki。第4章分组密码算法 图4.2.10子密钥产生器框图 第4章分组密码算法 图4.2.11置换选择PC1 第4章分组密码算法 图4.2.12置换选择PC2 第4章分组密码算法 表表4.2.9循环左移变换循环左移变换 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 循环左移次数 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 第4章分组密码算法 4.2.3加解密过程加解密过程加密过程:L0R0 IP(64 bit 输入码)LiRi-1 i=1,.,16 (421)RiLi-1f(Ri-1,ki)i=1,.,16 (422)64 bit密文IP-1(
21、R16L16)将式(4.2.1)和式(4.2.2)的运算进行16次后就得到密文组。DES的加密运算是可逆的,其解密过程与加密过程类似。第4章分组密码算法 解密过程:R16L16 IP(64 bit密文)Ri-1 Li i=16,.,1 (423)Li-1Rif(Li-1,ki)i=16,.,1 (424)64 bit明文IP-1(R0L0)第4章分组密码算法 4.2.4DES的变型的变型DES的安全性完全依赖于所用的密钥,而其56位密钥已被证明是不安全的。为了提高DES的安全性和适应不同情况的需求,人们设计了多种应用DES的方式,如独立子密钥方式、DESX、CRYPT(3)、S盒可变的DES、
22、RDES、snDESi、xDESi、GDES等,其主要目的是增加DES的密钥长度。为了提高DES算法的安全性,三重DES算法(简称3DES)是经常使用的一种DES变型算法。在3DES中,使用两个或三个密钥对一个分组进行三次加密。使用三个密钥时,第一次使用密钥k1,第二次使用密钥k2,第三次使用密钥k3,参见图4.2.13;使用两个密钥时,第一次使用密钥k1,第二次使用密钥k2,第三次再使用密钥k1,参见图4.2.14。图4.2.13和图4.2.14中,E表示DES加密;D表示DES解密。第4章分组密码算法 图4.2.13三个密钥的3DES原理框图 第4章分组密码算法 三个密钥的3DES可使已知
23、明文攻击的代价达到2112(见杨波编写的现代密码学(第二版)的3.2节)。但是,在这种情况下,其密钥长度为168bit,显得笨重。一种实用的方法就是采用两个密钥进行三次加密,具体实现时采用加密解密加密方式,如图4.2.14所示。第4章分组密码算法 图4.2.14两个密钥的3DES原理框图 第4章分组密码算法 尽管目前国内外已经基本不再简单地使用DES了,但3DES还是比较好的算法,国内许多安全标准在规定对称加密算法时,基本都将3DES作为其中一个选项。这足以说明3DES的安全性还是得到了认可的。但是,我们也要清楚地认识到,3DES的密钥长度是112位,而不是128位。128位是目前普遍认可的安
24、全密码算法的最小密钥长度。是否采用3DES作为分组算法,需要根据应用环境、业务重要性、安全性要求等因素综合考虑。第4章分组密码算法 4.3RC4算法算法 1987年,RonRivest为RSA数据安全公司设计了RC4算法。该算法与众多流密码的算法不同,它更易于用软件实现。正是由于RC4算法具有线性反馈移位寄存器等其他流密码算法所不具有的特性,因此该算法逐渐走入了人们的视野,并受到了广泛的关注。在RC4算法被设计出来之后的一段时间内,设计者未公开该算法的细节。在开始的七年中该算法具有专利,必须在签署保密协议后才能得到其细节。1994年9月,有人把它的源代码以匿名方式张贴在Cypherpunks邮
25、件列表中。该代码迅速被传到Usenet新闻组sci.crypt栏目中,并且通过互联网传遍了全世界的ftp站点。拥有RC4合法拷贝的用户对它进行了完全的验证,自此RC4算法变得众所周知。第4章分组密码算法 其实,RC密码算法有一个系列,它们都是由美国MIT的密码学专家RonRivest教授设计的。其中,RC1未公开发表;RC2是可变密钥长度的分组密码算法;RC3因在开发过程中被攻破而放弃;RC4是可变密钥长度的序列密码算法;RC5是可变参数的分组密码算法;RC6作为AES的候选算法进入了第二轮遴选过程,是5个进入第二轮的候选算法之一。下面主要介绍RC4算法。第4章分组密码算法 4.3.2算法描述
26、算法描述下面我们首先说明该算法中使用的符号所代表的意义:n表示RC4算法中使用的一个字节的长度(可以根据用户需要来定义);N表示长度为n的一个字节能够显示的值的总量,即N=2n;S表示该算法的内部状态,每一个S中有N个nbit长度的值;t表示一个参数,t=0,1,2,;St表示在参数t时的内部状态;it和jt表示参数t时对应的两个指针,它们指向内部状态St中的两个值;Stit表示St中指针指向的值;k表示一个密钥;l是密钥k包含的字节数,即l=k的比特数/n;Zt表示每一个t对应的伪随机数生成器的输出值。第4章分组密码算法 第4章分组密码算法 该算法包含两个部分，伪随机数生成算法 PRGA 和
27、密钥方案算法KSA。PRGA 首先将两个指针 it和 jt初始化为 0，it和 jt作为两个随机变化的指针，然后交换状态 St-1中 it和 jt指向的值，该过程的输出值为 ttttS iS j位置的值，具体过程如下：第4章分组密码算法 初始化:i0=0j0=0生成过程:11ttii 11 ttttjjSi 11 ,ttttttttS iSjS jSi ttttttZS S iS j 第4章分组密码算法 KSA 包含2n步操作，每一步操作与 PRGA 非常相似，该过程将内部状态 S 初始化，并将指针 it和 jt位置设为 0。具体过程如下:初始化初始化:For i=0，1，21n S0i=i
28、j0=0 第4章分组密码算法 操作过程操作过程:For i=0，1，21n 1 mod tttjjS iK il 11 ,ttttttS iSjS jSi 该算法中所有的“+”运算都是模 2n的加法，在每次更新中，除了相互交换的两个字之外，其它的都保持不变，输出的 n 比特字节的序列1()ttZZ。加密时，每个tZ 和长度为 n 的明文异或，产生密文。第4章分组密码算法 4.3.3WEP协议和协议和TKIP协议协议RC4的应用很广,我们这里只介绍影响较大的WEP协议和TKIP协议,希望能够为读者设计安全协议提供一些参考。1.WEP协议协议无线局域网的IEEE802.11标准规定了两部分安全机制
29、:一是访问认证机制;二是数据加密机制(WEP协议,WiredEquivalencyPrivacy)。它们是无线局域网系统中安全机制的主要形态和基础。第4章分组密码算法 1)WEP帧的数据加密过程发送端构造WEP帧的加密过程如图4.3.1所示。WEP机制用加密密钥与初始化向量IV连接产生种子密钥,然后把种子密钥送入伪随机产生器PRNG以产生密钥流,密钥流与明文进行异或生成密文。WEP帧的加密过程如下:(1)消息m通过CRC32循环冗余校验生成校验值ICV,将其记做c(m),将m与c(m)连接生成明文p=(m,c(m)。(2)选择初始化向量IV,将其记做v,将初始化向量与密钥k连接作为种子密钥,种
30、子密钥作为RC4算法的输入生成伪随机密钥流,记为RC4(v,k)。(3)将明文p与伪随机密钥流RC4(v,k)进行异或生成密文,记为cpRC4(v,k)。之后发送端把密文加上初始化向量IV和报头形成WEP帧并进行传输。WEP帧格式如图4.3.2所示。第4章分组密码算法 图4.3.1WEP帧的加密过程第4章分组密码算法 图4.3.2WEP帧格式 第4章分组密码算法 2)WEP帧的数据解密过程接收端WEP帧的解密过程如图4.3.3所示。图4.3.3WEP帧的解密过程 第4章分组密码算法 解密过程如下:(1)把接收到的初始向量v和共享密钥k连接作为种子密钥,种子密钥作为RC4算法的输入生成密钥流RC
31、4(v,k)。(2)将密钥流RC4(v,k)与密文进行异或以生成明文:cRC4(v,k)=(pRC4(v,k)RC4(v,k)=p。(3)计算解密后的消息的ICV,并将其与接收到的ICV进行比较,若相同则接受,若不同则丢弃。第4章分组密码算法 2.TKIP协议协议临时密钥完整性校验协议(TKIP,TemporalKeyIntegrityProtocol)针对WEP的攻击,提出了相应的各种补救措施,并且可以在现有硬件上通过软件升级来实现,能达到在现存资源上可能达到的最大安全性。TKIP是WEP到IEEE802.11(i)的AESCCMP协议的过渡协议。这里简单地给出TKIP的结构框图和WEP封装
32、的内部结构框图。1)TKIP的结构框图图4.3.4所示为TKIP的结构框图,它主要由5部分组成:阶段一密钥混合、阶段二密钥混合、MIC、分段和WEP封装。第4章分组密码算法 图4.3.4TKIP的结构框图 第4章分组密码算法 2)WEP封装的内部结构框图 图4.3.5WEP封装的内部结构框图 第4章分组密码算法 4.4AES算法算法 4.4.1历史背景历史背景DES的安全性一直受到质疑,RSA数据安全公司曾提供10000美元奖金作为悬赏来破译DES。DESCHALL小组经过近四个月的努力,通过Internet搜索了31016个密钥,找出了DES的密钥,恢复出了明文。1998年5月,美国EFF也
33、宣布,他们以一台价值20万美元的计算机改装成的专用解密机,用56小时破译了56bit的DES密钥。因为DES的安全强度不高,所以1997年1月2日美国NIST宣布征集一个新的对称密钥分组密码算法作为取代DES的新的加密标准。这个新的算法被命名为高级加密标准(AES)。1997年9月12日,正式公开征集AES算法,并要求如果算法被选中,则在世界范围内它必须是可以免费获得的。第4章分组密码算法 1998年8月20日,NIST公布了15个AES候选算法。根据第一阶段的分析和评论,NIST从15个算法中选出了5个算法,这5个参加决赛的候选算法是MARS、RC6、Rijndael、Serpent和Two
34、fish。在第二轮评论中,要征询对候选算法的各方面的评论和分析,包括但不限于以下方面:密码分析、知识产权、所有AES决赛候选算法的剖析、综合评价及有关实现问题。2000年5月15日,第二轮公众分析期结束以后,NIST研究了所有可得到的信息,以便于为AES作出选择。2000年10月2日,NIST宣布已经选中了Rijndael并建议作为AES。该算法由比利时密码学家JoanDaemen和VincentRijmen设计。第4章分组密码算法 4.4.2Rijndael密码概述密码概述Rijndael是分组长度和密钥长度均可变的分组密码,密钥长度和分组长度可以独立地指定为128bit、192bit或25
35、6bit。为简化起见,我们只讨论最小(即密钥长度为128bit,分组长度为128bit)时的情形。我们所限定的描述无损于Rijndael密码工作原理的一般性。在这种情况下,128bit的消息(明文、密文)分组被分成16Byte(1Byte是8bit),记为 1510,mmmInputBlock第4章分组密码算法 密钥分组也是这样,即 1510,kkkInputKey内部数据结构的表示是一个44矩阵:1511731410621395112840mmmmmmmmmmmmmmmmInputBlock1511731410621395112840kkkkkkkkkkkkkkkkInputKey第4章分组
36、密码算法 同DES(以及最现代的对称密钥分组密码)一样,Rijndael算法也是由基本的变换单位“轮”多次迭代而成的。在消息分组长度和密钥分组均为128bit的最小情况下,轮数是10。当消息分组长度和密钥长度变大时,轮数也应该相应增加。Rijndael中的轮变换记为 Round(State,RoundKey)这里State是轮消息矩阵,既被看做输入,也被看做输出;RoundKey是轮密钥矩阵,它是由输入密钥通过密钥表导出的。一轮的完成将导致State的元素改变(也就是改变它的状态)。对于加密(解密),输入到第一轮中的State就是明文(密文)消息矩阵InputBlock,而最后一轮中输出的St
37、ate就是密文(明文)消息矩阵InputKey。第4章分组密码算法 轮(除了最后一轮)变换由四个不同的变换组成,这些变换是后面将要介绍的内部函数,即Round(State,RoundKey)SubBytes(State);ShiftRows(State);MixColumns(State);AddRoundKey(State,RoundKey);最后一轮记为 FinalRound(State,RoundKey)第4章分组密码算法 它等于不使用MixColumns函数的Round(State,RoundKey),这类似于DES中最后一轮的情形,即在输出的两半数据分组之间再做一次交换。轮变换是可逆
38、的,以便于解密,相应的逆轮变换分别记为Round-1(State,RoundKey)和FinalRound-1(State,RoundKey)下面描述的四个内部函数都是可逆的。第4章分组密码算法 4.4.3Rijndael密码的内部函数密码的内部函数因为Rijndael密码的四个内部函数都是可逆的,所以为了实现Rijndael的解密,我们只需要在相反的方向使用它们各自的逆就可以了。下面我们仅就加密方向来描述这些函数。Rijndael密码的内部函数是在有限域上实现的,F2上的所有多项式模不可约多项式:bAxy1(4.4.1)这里 10001111110001111110001111110001,
39、11111000011111000011111000011111A01100011b第4章分组密码算法 2.内部函数内部函数ShiftRows(State)ShiftRows(State)函数在State的每行上运算,对于128bit分组长度的情形,它就是下面的变换:0,00,10,20,30,00,10,20,31,01,11,21,31,11,21,31,02,02,12,22,32,22,32,02,13,03,13,23,33,33,03,13,2ssssssssssssssssssssssssssssssss(4.4.2)这个运算实际上是一个换位密码,它只是重排了元素的位置,而不改变
40、元素本身。对于在第i(i=0,1,2,3)行的元素,位置重排就是循环向右移动4-i个位置。既然换位密码仅仅重排行元素的位置,那么这个变换当然是可逆的。第4章分组密码算法 3.内部函数内部函数MixColumns(State)MixColumns(State)函数在State的每列上作用,所以对于式(4.4.2)右边矩阵中的四列State,MixColumns(State)迭代四次。下面只描述了对一列的作用,一次迭代的输出仍是一列。首先,令 0123ssss是式(4.4.2)中右边矩阵中的一列。注意：为了表述清楚，这里我们已经省略了列数。第4章分组密码算法 把这一列表示为3次多项式:012233
41、)(sxsxsxsxs因为s(x)的系数是字节,也就是说它们是F28中的元素,所以这个多项式是在F28上的,因此不是Rijndael中的元素。列s(x)上的运算定义为将这个多项式乘以一个固定的3次多项式c(x),然后模x4+1:)1)(mod()(4xxsxc(4.4.3)这里固定的多项式是:02010103)(23012233xxxcxcxcxcxcc(x)的系数也是F28中的元素(以十六进制表示字节或域元素)。第4章分组密码算法 我们应该注意到,式(4.4.3)中的乘法不是Rijndael域中的运算,c(x)和s(x)甚至不是Rijndael域中的元素,而且因为x4+1在F2上可约(x4+
42、1=(x+1)4),所以式(4.4.3)中的乘法甚至不是任何域中的运算。进行乘法模一个4次多项式的唯一理由是使运算输出一个3次多项式。也就是说,为了获得一个从一列(3次多项式)到另一列(3次多项式)的变换,这个变换可以看做是使用已知密钥的一个多表代换(乘积)密码。第4章分组密码算法 读者可以验证在F2上计算的方程(注意，在这个环中,减法与加法等同):)4(mod4)1(modiixxx因此,在式(4.4.3)的乘积中,xi(i=0,1,2,3)的系数一定是满足j+k=i(mod 4)的cjsk的和(这里j,k=0,1,2,3)。例如,在乘积中x2的系数是:33201102scscscsc因为乘
43、法和加法都在F28中,所以很容易验证,式(4.4.3)中的多项式乘法可由下面的线性代数式给出:003210110321221032332103dccccsdccccsdccccsdccccs012302030101010203010101020303010102ssss (4.4.4)第4章分组密码算法 4.内部函数内部函数AddRoundKey(State,RoundKey)AddRoundKey(State,RoundKey)函数仅仅是逐字节、逐比特地将RoundKey中的元素与State中的元素相加,这里的“加”是F2中的加法(也就是逐比特异或),是平凡可逆的,逆就是自身相“加”。Rou
44、ndKey比特已经被列成表。也就是说,不同轮的密钥比特是不同的,它们由使用一个固定的(非秘密的)“密钥表”方案的密钥导出。第4章分组密码算法 至此,我们已经完成了Rijndael内部函数的描述,因此也完成了加密运算的描述。综上所述,四个内部函数都是可逆的,因此解密仅仅是在相反的方向反演加密,也就是运行AddRoundKey(State,RoundKey)-1、MixColumns(State)-1、ShiftRows(State)-1、SubBytes(State)-1。注意:Feistel密码的加密和解密可以使用同样的电路(硬件)和代码(软件),而Rijndael密码的加密和解密必须分别使用
45、不同的电路和代码。第4章分组密码算法 四个内部函数的功能小结如下:(1)SubBytes的目的是得到一个非线性的代换密码。对于分组密码的抗差分分析来说,非线性是一个重要的性质。(2)ShiftRows和MixColumns的目的是获得明文消息分组中不同位置上的字节的混合。比如,由于在自然语言和商业数据中包含高冗余而导致明文消息在消息空间有一个低熵分布(也就是说,典型的明文集中在整个消息空间中一个较小的子空间中),而消息分组中不同位置上的字节的混合导致消息在整个消息空间中有更广的分布。这本质上就是香农提出的混合特性。(3)AddRoundKey给出了消息分布所需的秘密随机性。这些函数重复多次(对
46、于128bit密钥和数据长度的情形,至少重复10次)以后,就构成了Rijndael密码。第4章分组密码算法 4.4.4快速而安全的实现快速而安全的实现Rijndael的内部函数是非常简单的,它们在很小的代数空间上进行运算,因此可以高效地实现这些内部函数。由对Rijndael内部函数的描述可以看出,只有SubBytes和MixColumns有非平凡的代数运算,因此可以考虑它们的快速实现。第4章分组密码算法 首先,在SubBytes中,利用“查表法”能够有效计算x-1,即可以一次建立一个有28=256个字节对的小表,用来长期使用(也就是说,这个表可以“固化”嵌入硬件或者通过软件实现)。在这个由对组
47、成的表中,零字节与零字节对应,表中的其余255项是(x,x-1)对的255种情况,其中逆在域F28中运算。“查表法”是非常有效的,它还能抗定时分析攻击(TimingAnalysisAttack),这种攻击根据观察不同数据的运算时间差异,就能够暗示出一个运算是在比特0上进行还是在比特1上进行。第4章分组密码算法 因为式(4.4.1)中的矩阵A和向量b是常量,所以“查表法”实际上可以完全包括式(4.4.1)的整个变换。也就是说,256项的表是由(x,y)对组成的,其中x,yF28,而(0,b)是(x,y)的特殊情况。显然,只要使用逆元表就可以得到逆元,因此,SubBytes可以用两个小表来实现,其
48、中每个表有256个字节。第4章分组密码算法 在MixColumns中,F28中元素间的乘法(即c(x)和s(x)系数间的乘法),或者更准确地说,固定矩阵的元素与式(4.4.3)中列向量元素间的乘法,可以通过“查表法”实现,即z=xy(域乘法),这里x01,02,03,yF28。注意,字节01只不过是域中的乘法单位元,即01y=y,因此这个乘法表的实现(无论是在软件中还是在硬件中)只需要2256=512项。由此可知,这个实现不仅很快,而且还能够减少定时分析攻击的危险。式(4.4.4)中的线性代数运算和它的逆也有一个快速的“固化”实现法。第4章分组密码算法 4.4.5AES对应用密码学的积极影响对
49、应用密码学的积极影响AES的引入为应用密码学带来了积极影响。首先,多重加密(例如三重DES)随着AES的出现而成为不必要的了。加长和可变的密钥及128bit、192bit和256bit的数据分组长度为各种应用要求提供了大范围可选的安全强度。由于多重加密要多次使用密钥,那么避免使用多重加密就意味着现实中必须使用的密钥数目的减少,因此可以简化安全协议和系统的设计。第4章分组密码算法 其次,AES的广泛使用促进了同样强度的新的杂凑函数的出现。在某些情形下,分组密码加密算法与杂凑函数密切相关,分组密码加密算法经常被用来作为单向杂凑函数,这已经成为一种标准应用。UNIX操作系统的登录认证协议(即UNIX
50、口令方案的实现中DES函数的典型的“单向变换”用法)就是一个典型的例子。另一个典型例子是利用分组密码加密算法来实现(加密的)单向杂凑函数。现实中,杂凑函数也经常被用作分组密码算法来生成密钥的伪随机数函数,由于AES的密钥可变、加长且数据分组需要类似长度的杂凑函数,又由于平方根攻击,杂凑函数的长度应该是分组密码密钥或数据分组长度的两倍,因此需要与128bit、192bit和256bit的AES长度相匹配的256bit、384bit和512bit输出长度的新的杂凑函数。第4章分组密码算法 另外,像DES标准吸引了许多试图攻破该算法的密码分析家的注意,随之促进了分组密码分析认识水平的发展一样,作为新
