第3章分组密码-zhp

第3章分组密码体制3.1分组密码概述3.2数据加密标准3.3差分密码分析与线性密码分析3.4分组密码的运行模式3.5IDEA3.6AES算法——Rijndael习题分组密码的一般模型分组密码是将明文消息编码为二进制序列后，划分成固定大小的块（Block），每块分别在密钥的控制下变换成二进制序列。令明文编码后的二进制序列为x0,x1,…,xi,…，将其划分为若干固定长度的分组（Block，块）。考虑某个分组x=(x0,x1,…,xn-1)。分组在密钥k=(k0,k1,…,kt-1)的控制下变换为长度为q的密文分组y=(y0,y1,…,ym-1

)。其本质是一个从明文空间（长度为p的比特串集合）M到密文空间（长度为q的比特串的集合）C的映射，该映射由密钥确定。如果明文和密文的分组长都为n比特，则明文的每一个分组都有2n个可能的取值。为使加密运算可逆（使解密运算可行），明文的每一个分组都应产生惟一的一个密文分组，这样的变换是可逆的，称明文分组到密文分组的可逆变换为代换。不同可逆变换的个数有2n!个。3.1.1代换

例：当明文分组长度为p时，有多少种明文和密文间的可逆变换（置换）？有个可能的明文，同样有个可能的密文，当密钥确定时，每个明文唯一对应一个密文，这样的可逆变换（置换）共有个。例如，则置换的个数为。

表示n=4的代换密码的一般结构，4比特输入产生16个可能输入状态中的一个，由代换结构将这一状态映射为16个可能输出状态中的一个，每一输出状态由4个密文比特表示。加密映射和解密映射可由代换表来定义，如表3.1所示。这种定义法是分组密码最常用的形式，能用于定义明文和密文之间的任何可逆映射。（见33页表3.1）理想分组密码如果每个密钥定义一个置换，则为理想分组密码（Idealblockcipher）。从实现角度来说，当分组长度大到一定程度时，理想分组密码是在实际当中是不可行的。当分组长度为n时，理想分组密码的密钥长度将n×2

n

比特。例如，当n=64时，需要的密钥长度为,如此长的密钥在实际应用中难以管理和实现。实际中常将n分成较小的段，例如可选n=r·n0，其中r和n0都是正整数，将设计n个变量的代换变为设计r个较小的子代换，而每个子代换只有n0个输入变量。一般n0都不太大， 称每个子代换为代换盒，简称为S盒。

Shannon提出了在设计密码系统时抗击统计分析的两个基本原则，成为分组密码设计的指导原则。它们是扩散（Diffusion）原则和混淆（Confusion）原则。 如果敌手知道明文的某些统计特性，如消息中不同字母出现的频率、可能出现的特定单词或短语，而且这些统计特性以某种方式在密文中反映出来，那么敌手就有可能得出加密密钥或其一部分，或者得出包含加密密钥的一个可能的密钥集合。3.1.2扩散和混淆扩散原则扩散是指明文的每一位（比特）尽可能多地影响密文的比特位，以隐蔽明文的统计特征。密钥的每一位（比特）也尽可能迅速地扩散到较多的密文比特中去。扩散的目的是希望密文中的任一比特都要尽可能与明文、密钥相关联，或者说，明文和密钥中任一比特的变化，都会在某种程度上影响到密文的变化，以防止统计分析攻击。

例如对英文消息M=m1m2m3…的加密操作其中ord(mi)是求字母mi对应的序号，chr(i)是求序号i对应的字母。这时明文的统计特性将被散布到密文中，因而每一字母在密文中出现的频率比在明文中出现的频率更接近于相等，双字母及多字母出现的频率也更接近于相等。在二元分组密码中，可对数据重复执行某个置换，再对这一置换作用于一函数，可获得扩散。混淆原则混淆指在加密变换过程中明文、密钥以及密文之间的关系尽可能地复杂，以使密码分析者（敌手）无法分析出密钥。防密码分析者采用统计分析法进行破译！执行混淆的每一步都必须是可逆的简单的线性函数得到的混淆效果不够理想，通常需要复杂的代换关系（如非线性的函数）达到比较好的混淆效果。 乘积密码指顺序地执行两个或多个基本密码系统，使得最后结果的密码强度高于每个基本密码系统产生的结果. Feistel还提出了实现代换和置换的方法。其思想实际上是Shannon提出的利用乘积密码实现混淆和扩散思想的具体应用。3.1.3Feistel密码结构图3.3Feistel网络示意图1.Feistel加密结构

输入是分组长为2w的明文和一个密钥K。将每组明文分成左右两半L0和R0，在进行完n轮迭代后，左右两半再合并到一起以产生密文分组。其第i轮迭代的输入为前一轮输出的函数：其中Ki是第i轮用的子密钥，由加密密钥K得到。一般地，各轮子密钥彼此不同而且与K也不同。置换代换Feistel网络的实现与以下参数和特性有关：①分组大小:分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64比特。②密钥大小：密钥越长则安全性越高，但加密速度就越慢。现在普遍认为64比特或更短的密钥长度是不安全的，通常使用128比特的密钥长度。③轮数：单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。④子密钥产生算法：该算法的复杂性越大，则密码分析的困难性就越大。⑤轮函数：轮函数的复杂性越大，密码分析的困难性也越大。在设计Feistel网络时，还有以下两个方面需要考虑：①快速的软件实现：在很多情况中，算法是被镶嵌在应用程序中，因而无法用硬件实现。此时算法的执行速度是考虑的关键。②算法容易分析：如果算法能被无疑义地解释清楚，就可容易地分析算法抵抗攻击的能力，有助于设计高强度的算法。2.Feistel解密结构

Feistel解密过程本质上和加密过程是一样的，算法使用密文作为输入，但使用子密钥Ki的次序与加密过程相反，即第1轮使用Kn，第2轮使用Kn-1，……，最后一轮使用K1。这一特性保证了解密和加密可采用同一算法。图3.4Feistel加解密过程在加密过程中：在解密过程中所以解密过程第1轮的输出为LE15‖RE15，等于加密过程第16轮输入左右两半交换后的结果。容易证明这种对应关系在16轮中每轮都成立。一般地，加密过程的第i轮有因此数据加密标准（dataencryptionstandard,DES）是迄今为止世界上最为广泛使用和流行的一种分组密码算法，它的分组长度为64比特，密钥长度为56比特，它是由美国IBM公司研制的，DES于1977年1月15日被正式批准并作为美国联邦信息处理标准，即FIPS-46，同年7月15日开始生效。规定每隔5年由美国国家保密局（nationalsecurityagency,NSA）作出评估，并重新批准它是否继续作为联邦加密标准。3.2数据加密标准251997年开始，RSA公司发起了一个称作“向DES挑战”的竞技赛。用了96天时间，成功地破解了用DES加密的一段信息；一年之后，在第二届赛事上，这一记录41天；1998年7月，“第2-2届DES挑战赛（DESChallengeII-2）”把破解DES的时间缩短到了只需56个小时；1999年1月，“第三届DES挑战赛（DESChallengeIII）”把破解DES的时间缩短到了只需22.5小时。尽管AES取代它成为新的数据加密标准，但使用诸如3重DES等方法加强DES密钥强度仍然不失为一个安全的密码系统。因此，DES算法的基本理论和设计思想仍有重要的参考价值。图3.5DES加密算法框图

1.初始置换将64位明文的位置进行置换，得到一个乱序的64位明文组。而后分成左右两段，每段32位，用L0和R0表示

如下为64比特的输入M：M1M2M3M4M5M6M7M8

M9M10M11M12M13M14M15M16 M17M18M19M20M21M22M23M24

M25M26M27M28M29M30M31M32

M33M34M35M36M37M38M39M40

M41M42M43M44M45M46M47M48

M49M50M51M52M53M54M55M56

M57M58M59M60M61M62M63M64其中Mi是二元数字。经过置换后的数据变为X=IP（M）： M58M50M42M34M26M18M10M2 M60M52M44M36M28M20M12M4 M62M54M46M38M30M22M14M6 M64M56M48M40M32M24M16M8 M57M49M41M33M25M17M9M1 M59M51M43M35M27M19M11M3 M61M53M45M37M29M21M13M5 M63M55M47M39M31M23M15M7如果再取逆初始置换Y=IP-1(X)=IP-1(IP(M))，可以看出，M各位的初始顺序将被恢复。图3.6DES加密算法的轮结构2.轮结构函数F(R,K)的计算过程扩展运算E选择扩展运算E

功能：将一个32位的输入块扩展为48位的输出块，令s表示E原输入数据比特（R）的原下标，则E的输出是将原下标s=0或者1(mod4)的各比特重复一次得到的，即对原第32，1，4，5，8，9，12，13，16，17，20，21，24，25，28，29各位重复一次，实现数据扩展。

将R0进行扩展换位：

E(R0)=100000000001011111111110100000001101010000000110R0=0000000011111111000001101000001133模2加法功能：将E(R)的各个位与密钥k的各位逐位作模2加，以得到输出bi

,具体运算如下：K1=111100001011111001101110011101010010100000110000E(R0)=100000000001011111111110

100000001101010000000110将E(R0)与K1进行异或运算得到A:A=01110000101010011001000011110101111111000011011034S盒代换48-位输入32-位输出S-盒1S-盒2S-盒3S-盒4S-盒5S-盒6S-盒7S-盒8

代换运算由8个不同的代替盒（S盒）完成。每个S盒有6位输入，4位输出。

48位的输入被分为8个6位的分组，每一分组对应一个S-盒代替操作。

经过S盒代换，形成8个4位分组。37

例如，假设S-盒6的输入（即异或函数的第31位到36位）为110011。第1位和最后一位组合形成了11（用来选择Si盒中的行），它对应着S-盒6的第3行。中间的4位组合形成了1001（用来选择Si盒中的列），它对应着S-盒6的第9列。

S-盒6的第3行第9列处的数是14（行列的交叉位置数），，得到输出值为1110。S-盒612，1，10，15，9，2，6，8，0，13，3，4，14，7，5，11，10，15，4，2，7，12，9，5，6，1，13，14，0，11，3，8，

9，14，15，5，2，8，12，3，7，0，4，10，1，13，11，6，

4，3，2，12，9，5，15，10，11，14，1，7，6，0，8，1338

A=011100001010100110010000

111101011111110000110110将结果分为8组：

A1=011100，查S1盒坐标(0，14)，得B1=0；

A2=001010，查S2盒坐标(0，5)，得B2=11；

A3=100110，查S3盒坐标(2，3)，得B3=9；

A4=010000，查S4盒坐标(0，8)，得B4=1；

A5=111101，查S5盒坐标(3，14)，得B5=5；

A6=011111，查S6盒坐标(1，15)，得B6=8；

A7=110000，查S7盒坐标(2，8)，得B7=10；

A8=110110，查S8盒坐标(2，11)，得B8=13；39置换运算P

将八个S盒的输出连在一起生成一个32位的输出，输出结果再通过置换P产生一个32位的输出，可以下表为P盒置换。至此，密码函数F的操作就完成了。40

合并B1B2…B8，得数据B：

B=00001011100100010101100010101101

对B进行P盒置换，得：

X0=11111100000011000100110100100001L0=11111111101110000111011001010111R0=00000000111111110000011010000011

将L0与X0按位异或，形成R1：

R1=00000011101101000011101101110110令L1=R0

=000000001111111100000110100000113.密钥的产生42

DES算法由64位密钥产生16轮的48位子密钥。在每一轮运算过程中，使用不同的子密钥。每一轮子密钥生成过程可以表示如下：64位密钥置换选择1C0(28位)D0(28位)循环左移循环左移C1(28位)D1(28位)置换选择2循环左移循环左移Ci(28位)Di

(28位)置换选择256位k148位ki48位56位压缩置换。将56位输入置换为48位。不考虑每字节的第8位，将64位密钥减至56位。经过置换选择1，各轮循环移动的次数由轮数决定。43具体的子密钥生成过程描述如下：（1）输入的密钥k先经过一个置换（称为“置换选择1”）进行重排。置换结果（56位）被分成两个28位C0与D0,其中C0是置换结果的前28位，而D0是置换结果的后28位。57494133251791585042342618102595143352719113605244366355473931231576254463830221466153453729211352820124

密钥置换PC–144

K=01110011011001010110001101110101

01110010011010010111010001111001K删除第8，16，24，…，64位的奇偶校验位后变成56位的K’K=01110011011001010110001101110101

01110010011010010111010001111001K’=01110010110010011000101110100111001011010001110100111100K‘经过PC-1置换后得到的C0D0（注：通过变换去掉奇偶校验位）：

C0=0000000011111111111111111101D0=000101010100101010100000100145

C0=0000000011111111111111111101

D0=0001010101001010101000001001由于是第一次迭代，故左移1位C0D0，得到C1D1：C1=0000000111111111111111111010D1=0010101010010101010000010010（2）在计算第i轮迭代所需要的子密钥时，首先对Ci-1与Di

-1进行循环左移，分别得到Ci与Di。循环的次数取决于i的值：如果i=1，2，9和16，循环左移的次数是1；否则循环左移的次数等于2。这些经过移位的值将作为下一个循环的输入。46（3）移动后，将两部分合并成56位后通过压缩置换PC–2后得到48位子密钥，即Ki=PC-2(CiDi)。压缩置换如表所示。1417112415328156211023191242681672720132415231374755304051453348444939563453464250362932压缩置换PC–2C1=0000000111111111111111111010

D1=0010101010010101010000010010C1D1在经过PC-2置换后，得到子密钥K1:K1=1111000010111110011011100111010100101000001100004.解密 和Feistel密码一样，DES的解密和加密使用同一算法，但子密钥使用的顺序相反。DES的安全性：互补性弱密钥和半弱密钥密钥搜索差分分析与线性分析二重DES是多重使用DES时最简单的形式，其中明文为P，两个加密密钥为K1和K2，密文为C，解密时，以相反顺序使用两个密钥：3.2.2二重DES 因此，二重DES所用密钥长度为112比特，强度极大地增加。 假设对任意两个密钥K1和K2，能够找出另一密钥K3，使得已经证明多重DES并不等价于使用一个56位密钥的单重DES。二重DES的中途相遇攻击二重DES的密钥长度为112位，密钥量本身可以抵御目前的穷举攻击，但是，二重DES不能抵御中间相遇攻击如果有那么如果已知一个明文密文对(P,C)，攻击的实施步骤：

首先，用256个所有可能的K1对P加密，将加密结果存入一表并对表按X排序；

然后用256个所有可能的K2对C解密，在上述表中查找与C解密结果相匹配的项，如果找到，则记下相应的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。然而，这样又会使密钥长度增加到56×3=168比特，因而过于笨重。 一种实用的方法是仅使用两个密钥做3次加密，实现方式为加密\解密\加密，简记为EDE(encryptdecryptencrypt)，即：3.2.3两个密钥的三重DES图3.9两个密钥的三重DES三个密钥的三重DES密钥长度为168比特，加密方式为令K3=K2或K1=K2，则变为一重DES。三个密钥的三重DES已在因特网的许多应用（如PGP和S/MIME）中被采用。3.2.4三个密钥的三重DES分组密码在加密时,明文分组的长度是固定的，而实际应用中待加密消息的数据量是不定的，数据格式可能是多种多样的。为了能在各种应用场合使用DES，美国在FIPSPUS74和81中定义了DES的4种运行模式，如表3.5所示。这些模式也可用于其他分组密码，下面以DES为例来介绍这4种模式。3.4分组密码的运行模式ECB(electroniccodebook)模式是最简单的运行模式，它一次对一个64比特长的明文分组加密，而且每次的加密密钥都相同。当密钥取定时，对明文的每一个分组，都有一个惟一的密文与之对应。3.4.1电码本（ECB）模式ECB的优点是简单高效，可以实现并行操作。ECB有良好的差错控制，一个密文块（或明文块）的改变，在解密（或加密）时，只会引起相应的明文块（或密文块）的改变，不会影响其他明文块（或密文块）的改变。ECB的最大特性是明文中相同的分组，在密文也是相同的。这也是其缺点，因为这样在加密长消息时，敌手可能得到多个明文密文对，进行已知明文攻击。因此，ECB特别适合加密的数据随机且较短的情形，如加密一个会话密钥。CBC（cipherblockchaining）模式:重复的明文分组产生不同的密文分组。 加密算法的输入是当前明文分组和前一次密文分组的异或，每次加密使用同一密钥。因此加密算法的输入不会显示出与这次的明文分组之间的固定关系，所以重复的明文分组不会在密文中暴露出这种重复关系。3.4.2密码分组链接（CBC）模式

但是，简单的引入反馈，如果两个消息前面部分的明文分组全部相同，则密文也还是会出现相同的前面部分，即密文的不同是从明文中首次出现不同的位置开始的。为了使得加密的结果一开始就出现不同，或者说使得相同的消息也有不同的密文，引入了初始向量（InitialVector,IV）。IV的不同，使得相同的消息有不同的密文。

IV对于收发双方都应是已知的，为使安全性最高，IV应像密钥一样被保护，可使用ECB加密模式来发送IV。保护IV的原因如下：如果敌手能欺骗接收方使用不同的IV值，敌手就能够在明文的第1个分组中插入自己选择的比特值，这是因为： 如上所述，DES是分组长为64比特的分组密码，但利用CFB（cipherfeedback）模式或OFB模式可将DES转换为流密码。流密码不需要对消息填充，而且运行是实时的。因此如果传送字母流，可使用流密码对每个字母直接加密并传送。 流密码具有密文和明文一样长这一性质，因此，如果需要发送的每个字符长为8比特，就应使用8比特密钥来加密每个字符。如果密钥长超过8比特，则造成浪费。3.4.3密码反馈（CFB）模式图3.12CFB模式示意图 解密时，将收到的密文单元与加密函数的输出进行异或。注意这时仍然使用加密算法而不是解密算法，原因如下：设Sj(X)是X的j个最高有效位，那么因此可证明以后各步也有类似的这种关系。CFB模式除能获得保密性外，还能用于认证。OFB（outputfeedback）模式的结构类似于CFB。不同之处如下：OFB模式是将加密算法的输出反馈到移位寄存器，而CFB模式中是将密文单元反馈到移位寄存器。3.4.4输出反馈(OFB)模式图3.13OFB模式示意图 OFB模式的优点是传输过程中的比特错误不会被传播。例如C1中出现1比特错误，在解密结果中只有P1受到影响，以后各明文单元则不受影响。而在CFB中，C1也作为移位寄存器的输入，因此它的1比特错误会影响解密结果中各明文单元的值。 OFB的缺点是它比CFB模式更易受到对消息流的篡改攻击，比如在密文中取1比特的补，那么在恢复的明文中相应位置的比特也为原比特的补。因此使得敌手有可能通过对消息校验部分的篡改和对数据部分的篡改，而以纠错码不能检测的方式篡改密文。 来学嘉（X.J.Lai）和J.L.Massey提出的第1版IDEA（internationaldataencryptionalgorithm，国际数据加密算法）于1990年公布，当时称为PES（proposedencryptionstandard，建议加密标准）。1991年，在Biham和Shamir提出差分密码分析之后，设计者推出了改进算法IPES，即改进型建议加密标准。1992年，设计者又将IPES改名为IDEA。这是近年来提出的各种分组密码中一个很成功的方案，已在PGP中采用。3.5IDEA 算法中明文和密文分组长度都是64比特，密钥长128比特。其设计原理可从强度和实现两方面考虑。1.密码强度算法的强度主要是通过有效的混淆和扩散特性而得以保证。混淆：通过三种运算实现（DES主要靠异或运算及小的非线性S盒代替来实现）按位模2加；模216加法；模216+1乘法整个运算过程全在16位子分组上进行，因此该算法对16位处理器尤其有效。3.5.1设计原理

IDEA算法中扩散是由称为乘加（multiplication/addition,MA）结构的基本单元实现的。该结构的输入是两个16比特的子段和两个16比特的子密钥，输出也为两个16比特的子段。这一结构在算法中重复使用了8次，获得了非常有效的扩散效果。2.实现IDEA可方便地通过软件和硬件实现。①软件实现原则：使用子分组：密码操作应该在对于软件来说很自然的子分组上进行，具有这些特性的子分组包括8,16,32比特，IDEA采用16比特子段处理使用简单操作：密码操作应该容易使用加法、移位等基本操作编程实现，种可以通过使用容易编程的加法、移位等运算实现IDEA的三种运算。②硬件由于加、解密相似，差别仅为使用密钥的方式，因此可用同一器件实现。再者，算法中有规则的模块结构，（IDEA重复使用两种基本的模块化构件：变换子块和加密子块）可方便VLSI的实现。算法描述：分组长度：64比特密钥长度：128比特迭代轮数：8轮（每轮6个子密钥），附加一个输出变换（4个子密钥）子密钥长度：16比特。52个子密钥由128比特初始密钥通过密钥生成算法生成。使用三种基本运算：按位模2加；模216加法；模216+1乘法图3.15IDEA的加密框图图3.16IDEA第1轮的轮结构1.轮结构每轮的开始有一个变换：两个乘法和两个加法输出的4个字段进行异或异或的结果作为MA的输入，MA的输出是两个16比特的子段变换的4个输出与MA的两个输出异或产生本轮的4个输出每一轮的加密顺序：1、X1和第一个子密钥相乘；2、X2和第二个子密钥相加；3、X3和第三个子密钥相加；4、X4和第四个子密钥相乘；5、第1步和第3步的结果相异或；6、第2步和第4步的结果相异或；7、第5步的结果与第5个子密钥相乘；8、第6步与第7步的结果相加9、第8步的结果与第6个子密钥相乘10、第7步与第9步的结果相加11、第1步与第9步的结果相异或12、第3步与第9步的结果相异或13、第2步与第10步的结果相异或14、第2步与第10步的结果相异或IDEA的输出变换：图3.17IDEA的输出变换2.子密钥的产生

加密过程中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个解密子密钥取为相应的第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.18中左边为加密过程，由上至下，右边为解密过程，由下至上。将每一轮进一步分为两步，第1步是变换，其余部分作为第2步，称为子加密。图3.18IDEA加密和解密框图现在从下往上考虑。对加密过程的最后一个输出变换，以下关系成立：Y1=W81⊙Z49Y2=W83+Z50Y3=W82+Z51Y4=W84⊙Z52解密过程中第1轮的第1步产生以下关系：J11=Y1⊙U1J12=Y2+U2J13=Y3+U3J14=Y4⊙U4将解密子密钥由加密子密钥表达并将Y1，Y2，Y3,，Y4代入以下关系，有J11=Y1⊙Z-149=W81⊙Z49⊙Z-149=W81J12=Y2+

-Z50=W83+

Z50+

-Z50=W83J13=Y3+

-Z51=W82+

Z51+

-Z51=W82J14=Y4⊙Z-152=W84⊙Z52⊙Z-152=W84可见解密过程第1轮第1步的输出等于加密过程最后一步输入中第2个子段和第3个子段交换后的值。从图3.16，可得以下关系：W81=I81MAR(I81I83，I82I84)W82=I83MAR(I81I83，I82I84)W83=I82MAL(I81I83，I82I84)W84=I84MAL(I81I83，I82I84)其中MAR(X,Y)是MA结构输入为X和Y时的右边输出，MAL(X,Y)是左边输出。则V11=J11MAR(J11J13,J12J14)=W81MAR(W81W82,W83W84)=I81MAR(I81I83,I82I84)MAR[I81MAR(I81I83,I82I84)I83MAR(I81I83,I82I84),I82MAL(I81I83,I82I84)I84

MAL(I81I83,I82I84)]=I81MAR(I81I83,I82I84)MAR(I81I83,I82I84)=I81类似地，可有V12=I83V13=I82V14=I84所以解密过程第1轮第2步的输出等于加密过程倒数第2步输入中第2个子段和第3个子段交换后的值。同理可证图3.18中每步都有上述类似关系，这种关系一直到V81=I11V82=I13V83=I12V84=I14即除第2个子段和第3个子段交换位置外，解密过程的输出变换与加密过程第1轮第1步的变换完全相同。即除第2个子段和第3个子段交换位置外，解密过程的输出变换与加密过程第1轮第1步的变换完全相同。所以最后可得知，整个解密过程的输出等于整个加密过程的输入。3.6AES算法——Rijndael1997年9月12日，NIST发布了征集算法的正式公告，要求AES具有128比特的分组长度，并支持128、192和256比特的密钥长度，而且要求AES要能在全世界范围内免费使用。 1998年8月12日，在首届AES候选会议（firstAEScandidateconference）上公布了AES的15个候选算法，任由全世界各机构和个人攻击和评论，这15个候选算法是CAST256、CRYPTON、E2、DEAL、FROG、SAFER+、RC6、MAGENTA、LOKI97、SERPENT、MARS、Rijndael、DFC、Twofish、HPC。1999年3月，在第2届AES候选会议（secondAEScandidateconference）上经过对全球各密码机构和个人对候选算法分析结果的讨论，从15个候选算法中选出了5个。 这5个是RC6、Rijndael、SERPENT、Twofish和MARS。2000年4月13日至14日，召开了第3届AES候选会议（thirdAEScandidateconference），继续对最后5个候选算法进行讨论。2000年10月2日，NIST宣布Rijndael作为新的AES。至此，经过3年多的讨论，Rijndael终于脱颖而出。 Rijndael由比利时的JoanDaemen和VincentRijmen设计，算法的原型是Square算法，它的设计策略是宽轨迹策略（widetrailstrategy）。宽轨迹策略是针对差分分析和线性分析提出的，它的最大优点是可以给出算法的最佳差分特征的概率及最佳线性逼近的偏差的界；由此，可以分析算法抵抗差分密码分析及线性密码分析的能力。

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

3.6.1AES的数学基础和设计思想将b7b6b5b4b3b2b1b0构成的字节b看成系数在{0,1}中的多项式b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0例如：十六进制数‘57’对应的二进制为01010111，看成一个字节，对应的多项式为x6+x4+x2+x+1。

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(2)上的一个8次不可约多项式的多项式乘法。对于AES这一8次不可约多项式为：

m(x)=x8+x4+x3+x+1用十六进制表示为{11B}。

【例】计算：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进制表示)以上定义的乘法满足交换律，且有单位元‘01’。另外，对任何次数小于8的多项式b(x)，可用推广的欧几里得算法得b(x)a(x)+m(x)c(x)=1即a(x)·b(x)=1modm(x)，因此a(x)是b(x)的乘法逆元。再者，乘法还满足分配律：a(x)·(b(x)+c(x))=a(x)·b(x)+a(x)·c(x) 256个字节值构成的集合，在以上定义的加法和乘法运算下，有有限域GF(28)的结构。 GF(28)上还定义了一个运算，称之为x乘法，其定义为x·b(x)=b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0

x(modm(x))如果b7=0，求模结果不变，否则为乘积结果减去m(x)，即求乘积结果与m(x)的异或。 由此得出x（十六进制数‘02’）乘b(x)可以先对b(x)在字节内左移一位（最后一位补0），若b7=1，则再与‘1B’（其二进制为00011011）做逐比特异或来实现，该运算记为b=xtime(a)。在专用芯片中，xtime只需4个异或。x的幂乘运算可以重复应用xtime来实现。而任意常数乘法可以通过对中间结果相加实现。例如，‘57’·‘13’可按如下方式实现：‘57’·‘02’=xtime(57)=‘AE’；‘57’·‘04’=xtime(AE)=‘47’；‘57’·‘08’=xtime(47)=‘8E’；‘57’·‘10’=xtime(8E)=‘07’；‘57’·‘13’=‘57’·(‘01’‘02’‘10’)=‘57’‘AE’‘07’=‘FE’。2.系数在GF(28)上的多项式 4个字节构成的向量可以表示为系数在GF(28)上的次数小于4的多项式。多项式的加法就是对应系数相加；换句话说，多项式的加法就是4字节向量的逐比特异或。

多项式的乘法运算必须要取模M(x)=x4+1，这样使得次数小于4的多项式的乘积仍然是一个次数小于4的多项式，将多项式的模乘运算记为，设a(x)=a3x3+a2x2+a1x+a0，b(x)=b3x3+b2x2+b1x+b0，c(x)=a(x)b(x)=c3x3+c2x2+c1x+c0。由于xjmod(x4+1)=x

j

mod4，所以c0=a0b0a3b1a2b2a1b3；c1=a1b0a0b1a3b2a2b3；c2=a2b0a1b1a0b2a3b3；c3=a3b0a2b1a1b2a0b3。可将上述计算表示为 注意到M(x)不是GF(28)上的不可约多项式（甚至也不是GF(2)上的不可约多项式），因此非0多项式的这种乘法不是群运算。不过在Rijndael密码中，对多项式b(x)，这种乘法运算只限于乘一个固定的有逆元的多项式a(x)=a3x3+a2x2+a1x+a0。 定理3.1系数在GF(28)上的多项式a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当矩阵在GF(28)上可逆。 证明：a3x3+a2x2+a1x+a0是模x4+1可逆的，当且仅当存在多项式h3x3+h2x2+h1x+h0(a3x3+a2x2+a1x+a0)(h3x3+h2x2+h1x+h0)=1mod(x4+1)

因此有(a3x3+a2x2+a1x+a0)(h2x3+h1x2+h0x+h3)=xmod(x4+1)(a3x3+a2x2+a1x+a0)(h1x3+h0x2+h3x+h2)=x2mod(x4+1)(a3x3+a2x2+a1x+a0)(h0x3+h3x2+h2x+h1)=x3mod(x4+1)将以上关系写成矩阵形式即得（证毕）c(x)=xb(x)定义为x与b(x)的模x4+1乘法，即c(x)=xb(x)=b2x3+b1x2+b0x+b3。其矩阵表示中，除a1=‘01’外，其他所有ai=‘00’，即 因此，x（或x的幂）模乘多项式相当于对字节构成的向量进行字节循环移位。3.设计思想 Rijndael密码的设计力求满足以下3条标准：①抵抗所有已知的攻击。②在多个平台上速度快，编码紧凑。③设计简单。

AES算法的轮函数是由3个不同的可逆均匀变换组成的，称它们为3个“层”。 为实现宽轨迹策略，轮函数3个层中的每一层都有它自己的功能：线性混合层：确保多轮之上的高度扩散；非线性层：将具有最优的“最坏情况非线性特性”的S盒并行使用；

密钥加层：单轮子密钥简单地异或到中间状态上，实现一次性掩盖。 Rijndael是一个迭代型分组密码，其分组长度和密钥长度都可变，各自可以独立地指定为128比特、192比特、256比特。3.6.2算法说明1.状态、种子密钥和轮数 类似于明文分组和密文分组，算法的中间结果也须分组，称算法中间结果的分组为状态，所有的操作都在状态上进行。状态可以用以字节为元素的矩阵阵列表示，该阵列有4行，列数记为Nb，Nb等于分组长度除以32。 种子密钥类似地用一个以字节为元素的矩阵阵列表示，该阵列有4行，列数记为Nk，Nk等于分组长度除以32。 有时可将这些分组当作一维数组，其每一元素是上述阵列表示中的4字节元素构成的列向量，数组长度可为4、6、8，数组元素下标的范围分别是0~3、0~5和0~7。4字节元素构成的列向量有时也称为字。AES分组长度、密钥长度、轮数的关系2.轮函数 Rijndael的轮函数由4个不同的计算部件组成，分别是：字节代换（ByteSub）行移位（ShiftRow）列混合（MixColumn）密钥加（AddRoundKey）（1）字节代换运算它用S盒把每个字节aij非线性地变换为另一个字节bij,有效地实现每个字节数据中各位的混淆。(1)代数转换（ByteSub） 字节代换是一个关于字节的非线形变换，独立地对状态的每个字节进行。代换表（即S-盒）是可逆的，由以下两个变换的合成得到：设输入字节为A=(a0a1a2a3a4a5a6a7)，计算Y=ByteSub(A)=?

首先，将字节A看作GF(28)上的元素，映射到自己的乘法逆元，‘00’映射到自己。

X=A-1modm(x)；m(x)=x8+x4+x3+x+1

即A·X≡X·A≡1modm(x)其次，对字节X做如下的（GF(2)上的，可逆的）仿射变换：Y=M·T⊕BMXB上述S-盒对状态的所有字节所做的变换记为ByteSub(State)图3.19字节代换示意图 ByteSub的逆变换由代换表的逆表做字节代换，可通过如下两步实现:首先进行仿射变换的逆变换再求每一字节在GF(28)上逆元。(2)行移位（ShiftRow） 行移位是将状态阵列的各行进行循环移位，不同状态行的位移量不同。第0行不移动，第1行循环左移C1个字节，第2行循环左移C2个字节，第3行循环左移C3个字节。位移量C1、C2、C3的取值与Nb有关，由表3.10给出。 行移位运算记为ShiftRow(State) ShiftRow的逆变换是对状态阵列的后3列分别执行相反方向的移位操作！特点：行移位将某个字节从一列移到另一列中，这种变换确保了某列中的4字节被扩展到4个不同的列。（3）列混合变换（MixColumn）

在列混合变换中，将状态阵列的每个列视为GF(28)上的多项式，再与一个固定的多项式c(x)进行模x4+1乘法。当然要求c(x)是模x4+1可逆的多项式

c(x)=‘03’x3+‘01’x2+‘01’x+‘02’列混合运算也可写为矩阵乘法。设b(x)=c(x)a(x)，则 列混合运算的逆运算是类似的，即每列都用一个特定的多项式d(x)相乘。d(x)满足(‘03’x3+‘01’x2+‘01’x+‘02’)d(x)=‘01’由此可得d(x)=‘0B’x3+‘0D’x2+‘09’x+‘0E’逆变换为：(4)密钥加（AddRoundKey） 密钥加是将轮密钥简单地与状态进行逐比特异或。轮密钥由种子密钥通过密钥编排算法得到，轮密钥长度等于分组长度Nb。密钥加运算的逆运算是其自身。综上所述，组成Rijndael轮函数的计算部件简捷快速，功能互补。轮函数的伪C代码如下：Round(State,RoundKey){ByteSub(State);ShiftRow(State);MixColumn(State);AddRoundKey(State,RoundKey)}结尾轮的轮函数与前面各轮不同，将MixColumn这一步去掉，其伪C代码如下：FinalRound(State,RoundKey){ByteSub(State);ShiftRow(State);AddRoundKey(State,RoundKey)}在以上伪C代码记法中，State、RoundKey可用指针类型，函数Round、FinalRound、ByteSub、ShiftRow、MixColumn、AddRoundKey都在指针State、RoundKey所指向的阵列上进行运算。3.密钥编排 密钥编排指从种子密钥得到轮密钥的过程，它由密钥扩展和轮密钥选取两部分组成。其基本原则如下：轮密钥的比特总数等于分组长度乘以轮数加1；种子密钥被扩展成为扩展密钥；轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，如此下去。(1)密钥扩展 扩展密钥是以4字节字为元素的一维阵列，表示为W[Nb*(Nr+1)]，其中前Nk个字取为种子密钥，以后每个字按递归方式定义。扩展算法根据Nk≤6和Nk>6有所不同。①当Nk≤6时，扩展算法如下KeyExpansion(byteKey[4*Nk],W[Nb*(Nr+1)]){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<Nb*(Nr+1);i++){ temp=W[i-1]; if(i%Nk==0) temp=SubByte(RotByte(temp))^Rcon[i/Nk]; W[i]=W[i-Nk]^temp;}} 其中Key[4*Nk]为种子密钥，看作以字节为元素的一维阵列。函数SubByte()返回4字节字，其中每一个字节都是用Rijndael的S盒作用到输入字对应的字节得到。函数RotByte()也返回4字节字，该字由输入的字循环移位得到，即当输入字为(a,b,c,d)时，输出字为(b,c,d,a)。 可以看出，扩展密钥的前Nk个字即为种子密钥，之后的每个字W[i]等于前一个字W[i-1]与Nk个位置之前的字W[i-Nk]的异或；不过当i/Nk为整数时，须先将前一个字W[i-1]经过以下一系列的变换：1字节的循环移位RotByte→用S盒进行变换SubByte→异或轮常数Rcon[i/Nk]。②当Nk>6时，扩展算法如下：KeyExpansion(byteKey[4*Nk],W[Nb*(Nr+1)]){ 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<Nb*(Nr+1);i++){ temp=W[i-1]; if(i%Nk==0) temp=SubByte(RotByte(temp))^Rcon[i/Nk]; elseif(i%Nk==4) temp=SubByte(temp); W[i]=W[i-Nk]^temp;}}Nk>6与Nk≤6的密钥扩展算法的区别在于：当i为Nk的4的倍数时，须先将前一个字W[i-1]经过SubByte变换。以上两个算法中，Rcon[i/Nk]为轮常数，其值与Nk无关，定义为（字节用十六进制表示，同时理解为GF(28)上的元素）：(2)轮密钥选取轮密钥i（即第i个轮密钥）由轮密钥缓冲字W[Nb*i]到W[Nb*(i+1)]给出，如图3.23所示。图3.23Nb=6且Nk=4时的密钥扩展与轮密钥选取147密钥扩展的具体步骤：（1）初始密钥直接被复制到数组W[i]的前4个字节中，得到W[0],W[1],W[2],W[3](2)对W数组中下标不为4的倍数的元素，只是简单地异或，即W[i]=W[i-1]⊕W[i-4](i不为4的倍数）（3）对w数组中下标为4的倍数的元素，在使用上式进行异或前，需对w[i-1]进行一系列处理，即依次进行RotByte(对输入字节循环左移一个字节)、SubByte(对输入用S盒进行字节代换)，再将得到的结果与Rcon[i/4](轮常量)做异或运算。148例：明文信息：3243f6a8885a308d313198a2e0370734

加密密钥:2b7e151628aed2a6abf7158809cf4f3c加密密钥为128位，轮数Nr=10加密过程：（1）10轮迭代前，先把原明文写成如下形式（表1）,本轮密钥写成如表2形式328831e0435a3137f6309807a88da2342b28ab097eaeF7cf15d2154f16a6883c表1表2

进行轮密钥加变换操作后产生一个结果，作为10轮迭代的第一轮输入。轮密钥加变换操作如下：每个字节相应异或，32：001100102b：00101011异或结果：00011001即19，所以第一个字节为19，其他字节依次类推，因此第一轮的轮开始状态为（表3）：19a09ae93df4c6f8e3e28d48be2b2a08表3149

（2）轮循环

①进行第一轮的“字节代换”操作要查S盒，每个字节依次置换，结果如表4

置换方法：前4位为S盒行值，低4位为S盒列值，如19为S盒中第1行第9列的值即d4。d4e0b81e27bfb44111985d52aef1e530表4

②然后按照行移位变换原则进行操作，结果如表5d4e0b81ebfb441275d52119830aef1e5表5③列混合变换利用公式完成，结果为表604e0482866cbf8068119d326e59a7a4c表6(3)密钥扩展：①W[0]=2b7e1516、w[1]=28aed2a6、w[2]=abf71588、w[3]=09cf4f3c用初始密钥填充。②接着求w[4]，下标为4的倍数，则在异或之前对w[i-1]也就是w[3]处理，w[4]的产生过程如下图所示：150w[4]=a0fafe17w[5]=w[4]⊕w[1]=88542cb1w[6]=w[5]⊕w[2]=23a33939w[7]=w[6]⊕w[3]=2a6c7605w[4],w[5],w[6],w[7]即为新一轮的密钥③把新一轮的密钥和表6做轮密钥加变换，得到的结果如表7做为第2轮迭代的输入。（4）依次迭代下去，直到第10轮迭代结束。最后的结果即产生的密文为表8所示即：3925841d02dc09fbdc118597196a0b32W[3]=09cf4f3ccf4f3c09RotByte()操作8a84eb01SubByte()操