应用密码学第三章分组密码体制

应用密码学第三章分组密码体制 3.1分组密码概述

分组密码是一种广泛使用的对称密码。和对称密码中的序列密码(流密码streamcipher)不同，分组密码在加密过程中不是将明文按字符逐位加密，而是首先要将待加密的明文进行分组，每组的长度相同，然后对每组明文分别加密得到密文。分组密码系统采用相同的加密密钥和解密密钥，这是对称密码系统的显著特点。例如将明文分为m块：P0，P1，P2，…，Pm-1，每个块在密钥作用下执行相同的变换，生成m个密文块：C0,C1,C2,…,Cm-1，每块的大小可以是任意长度，但通常是每块的大小大于等于64位（块大小为1比特位时，分组密码就变为序列密码）。如图3－1所示是通信双方最常用的分组密码基本通信模型。图3－1分组密码基本通信模型图

在图3－1中，参与通信的实体有发送方Alice、接收方Bob。而攻击者是在双方通信中试图攻击发方或者收方信息服务的实体，攻击者经常也称为敌人、对手、搭线者、窃听者、入侵者等，并且攻击者通常企图扮演合法的发送方或者接收方。

由图3－1所示，一个分组密码系统(BlockCipherSystem，简称BCS）可以用一个五元组来表示：BCS={P,C,K,E,D}。其中，P、C、K、E、D分别代表明文空间、密文空间、密钥空间、加密算法、解密算法。

设X={x0,x1,…,xn-2,xn-1}为一组长度为n的明文块，在密钥K={k0,k1,…,kt-1}的加密作用下得到密文块Y={y0,y1,…,ym-2,ym-1}，其中xi,yj,kr∈GF(2)，且0≤i≤n-1,0≤j≤m-1,0≤r≤t-1若n=m，明文块长度等于密文块长度，称之为无数据扩展和压缩的分组密码；若n>m，明文块长度大于密文块长度，称之为有数据压缩的分组密码；若n<m，明文块长度小于密文块长度，称之为有数据扩展的分组密码。为了保证分组密码的安全强度，设计分组密码时应遵循如下的基本原则：

（1）分组长度足够长，防止明文穷举攻击，例如DES（DataEncryptionStandard）、IDEA（InternationalDataEncryptionAlgorithm）等分组密码算法，分组块大小为64bit，在生日攻击下用232组密文，破解成功的概率为0.5，同时要求232×64bit=215MB大小的存储空间，故在目前环境下采用穷举攻击DES、IDEA等密码算法是不可能的；而AES明文分组为128bit，同样在生日攻击下用264组密文，破解成功的概率为0.5，同时要求存储空间大小为264×128bit=248MB，所以采用穷举攻击AES算法在计算上就更不可行。

(2)密钥量足够大，同时需要尽可能消除弱密钥的使用，防止密钥穷举攻击，但是由于对称密码体制存在密钥管理问题，密钥也不能过大。

（3）密钥变换足够复杂，能抵抗各种已知攻击，如差分攻击、线性攻击、边信道攻击等，即使得攻击者除了穷举攻击外找不到其它有效的攻击方法。

（4）加密和解密的运算简单，易于软硬件高速实现。

（5）数据扩展足够小，一般无数据扩展。

（6）差错传播尽可能小，加密或解密某明文或密文分组出错，对后续密文解密的影响也尽可能小。

3.2分组密码的原理

20世纪40年代末，ClaudeShannon（香农）在遵循Kerckhoff(柯克霍夫)原则前提下，提出了设计密码系统的两个基本方法——扩散和混淆，目的是抗击攻击者对密码系统的统计分析。

（1）扩散：将明文的统计特性散布到密文中去，实现方式是使得明文的每一位影响密文中多位的值，等价于密文中每一位均受明文中多位的影响。在分组密码中，对数据重复执行某个置换，再对这一置换作用于一函数，可获得扩散。

（2）混淆：使密文和密钥之间的统计关系变得尽可能复杂，使得攻击者无法得到密文和密钥之间的统计，从而攻击者无法得到密钥。

1．代替—置换网络

1949年，ClaudeShannon（香农）在他的论文中提出了一种乘积密码，实现混淆和扩散。乘积密码通常伴随一系列置换与代替操作，常见的乘积密码是迭代密码。许多分组密码重复一个或几个步骤：代替然后换位，之后再代替，再换位等，并且每个步骤的过程都由密钥来控制。目前的大多数分组密码同时使用代替-置换网络以达到混淆和扩散的目标。

代替-置换网络是由多重代替变换(S)和置换变换（P）构成，如图3－2所示，S代替操作起到混淆的作用，P置换操作起到扩散的作用。图3－2一个代替—置换网络图

2．Feistel密码结构

最典型的乘积密码是在1973年由Feistel提出的，整个处理过程包括多轮的代替和置换操作，主密钥分为一个子密钥集，每轮使用一个子密钥。在每轮中，明文被分为左右两部分,分别记为L0和R0，两部分分别进行交换，其中一个部分与子密钥混合，进行相应变换。在进行完n轮迭代之后，左右两半合并在一起再产生密文。Feistel加密法的其中一轮的操作如图3－3所示。图3－3

Feistel一轮的加密每轮迭代运算的逻辑关系可表示如下：其中,Ki表示第i轮用的子密钥，Li表示第i轮的左半部，Ri表示第i轮的右半部，F表示轮函数。图3－4为Feistel网络示意图。图3－4

Feistel网络结构示意图

Feistel网络中除了最后一轮，每轮结构相同，每轮右半部分在子密钥控制下数据先进入轮函数F，然后与左半部分异或得到下一轮的右半部分，而下一轮的左半部分直接为上一轮的右半部分。最后一轮的结构则是上一轮右半部分在子密钥控制下数据先进入轮函数F，然后与左半部分异或得到下一轮的左半部分，而右半部分是上一轮的右半部分。

Feistel网络结构已成为现代对称密码体制结构的基础，如DES算法设计就是最典型的Feistel结构，那么在采用Feistel网络结构设计分组密码的过程中，为了保证分组密码的安全性，与分组密码算法原则非常类似，Feistel网络结构的实现与以下参数和特性有关：

（1）分组大小。分组越大则安全性越高，但加密速度就越慢。分组密码设计中最为普遍使用的分组大小是64bit。

（2）密钥大小。密钥越长则安全性越高，但加密速度就越慢。现在通常使用128bit的密钥长度。

（3）轮数。单轮结构远不足以保证安全性，但多轮结构可提供足够的安全性。典型地，轮数取为16。

（4）子密钥产生算法。该算法的复杂性越大，则密码分析的困难性就越大。

（5）轮函数。轮函数的复杂性越大，密码分析的困难性也越大。

3.Feistel解密结构

如图3－5所示，左边为Feistel加密过程，右边为Feistel解密过程。从图中可以看出，Feistel解码过程所在的变换与加密过程完全一样，只是算法的输入不一样。加密输入的数据为明文，子密钥的顺序为K1,K2,…,Kr-1，Kr,而Feistel解密过程输入的数据为密文，子密钥的顺序与加密过程刚好相反，为Kr,Kr-1,…,K2,K1。因此采用Feistel网络结构设计分组密码算法，加解密可采用同一种算法。图3－5

Feistel加解密过程

DES算法概述

数据加密标准（DataEncryptionStandard，DES）是由美国IBM公司于20世纪70年代中期的一个密码算法（LUCIFER算法）发展而来的，在1977年1月15日，美国国家标准局（NBS）正式公布实施，并得到了ISO的认可。在过去近20多年的时间里，DES被广泛应用于美国联邦和各种商业信息的安全保密工作中，经受住了各种密码分析和攻击，体现出了令人满意的安全性。但随着密码分析技术和计算能力的提高，1994年，美国决定1998年12月以后不再使用DES算法，目前DES算法已被更为安全的Rijndael算法取代。虽然这样，但是目前还无法将DES加密算法彻底地破解掉，而且DES算法的加解密过程非常快，仍是目前使用最为普遍的对称密码算法。在国内，随着三金工程尤其是金卡工程的启动，DES算法在POS、ATM、磁卡及智能卡(IC卡)、加油站、高速公路收费站等领域被广泛应用，以此来实现关键数据的保密，如信用卡持卡人的PIN码加密传输，IC卡与POS机之间的双向认证、金融交易数据包的MAC校验等，均用到DES算法。3.3数据加密标准

DES算法是一种采用传统的代替和置换操作加密的分组密码，明文以64比特为分组，密钥长度为64比特，有效密钥长度为56比特，其中加密密钥有8比特是奇偶校验，DES算法的加密和解密用的是同一算法，它的安全性依赖于所用的密钥。它首先把需要加密的明文划分为每64比特二进制的数据块，用56比特有效密钥对64比特二进制数据块进行加密，每次加密可对64比特的明文输入进行16轮的替换和移位后，输出完全不同的64比特密文数据。由于DES算法仅使用最大为64比特的标准算术和逻辑运算，运算速度快，密钥产生容易，适合于在当前大多数计算机上用软件方法实现，同时也适合于在专用芯片上实现。

DES算法描述

DES算法的加密过程首先对明文分组进行操作，需要加密的明文分为固定大小为64比特的块。图3－6是DES算法的加密流程，图的左边是一个64比特的明文分组块的加密处理过程，右边为密钥扩展处理过程。图3－6

DES加密算法流程（右边矩形框内虚线为子密钥生成过程）

1. 初始置换（IP）

首先输入的64比特的明文块为，按照初始置换(IP)表进行置换，DES的初始置换表如图3－7所示。图3－7初始置换表如图3－7可以看出，输入的m1m2…m64经过初始置换表输出m58m50…m8m57m49…m7，即把明文块按照序号顺序产生一个8×8矩阵，然后根据初始置换矩阵进行变换。

2．轮结构经过DES算法第一阶段的初始置换得到64比特的块为：，然后分为两部分，前32位为左半部分，记为L0，后32位为右半部分，记为R0。如图3－8所示，DES算法的轮结构和Feistel轮结构一样，分为左右两部分各32比特在每一轮中被独立处理。具体过程为：下一轮左半部分的32比特Li等于上一轮右半部分32比特Ri-1；而下一轮右半部分的32比特Ri的计算则先由上一轮右半部分Ri-1和轮密钥Ki输入到F函数中（图3－9）进行变换，变换的结果再与上一轮左半部分Li进行异或运算，得到Ri。因此每一轮变换可由下面公式表示：图3－8DES算法的一轮结构变换图图3－9

F函数的计算过程下面将给出DES算法的一轮结构变换的具体计算过程。首先根据F函数计算过程给出右半部的变换过程（图3－9）。若右半部分R0，则进行E盒变换，将32比特扩展为48比特，E盒扩充方式如图3－10所示。具体变换过程为把输入32比特按照8行4列方式依次排列，形成一个8×4的矩阵，然后E盒扩展之后输出为8×6矩阵。图3－10扩展E盒变换在我们的示例中输入R0，按照图3－10所示的E盒变换之后为：E盒变换之后的48比特输出为：100000000001011111111110100000001101010000000110根据示意图3－9，下一步的操作是E盒的输出48比特作为输入与子密钥进行异或（XOR）操作，若子密钥48比特为：，则操作如下：输入：100000000001011111111110100000001101010000000110密钥：001111011000111111001101001101110011111101001000输出：101111011001100000110011101101111110101101001110输出新的48比特将作为S盒的输入，进入S盒变换，48比特压缩为32比特，如图3－9所示。S盒的安全性能是保证DES算法安全性的源泉，DES算法总共有8种不同的S盒，其定义见图3－11，每个S盒接收6位的输入，输出4位。一个S盒有16列和4行，它的每个元素是4位，通常用十进制表示。每个S盒的使用方法为：S盒接收到6比特的输入，其中第1个比特和最后1比特构成的2位二进制为该S盒的行号，中间的4位二进制为该S盒的列号，然后由该S盒的定义表根据行号和列号查表得到对应的值（一般为十进制），该值就是S盒变换的输出，并转化为二进制。具体变换过程为：若输入为第i个S盒的6比特为Bi=b1b2…b6，然后计算r=2·b1+b6，c=23·b2+22·b3+2·b4+b5，r、c分别为Si盒中的行号和列号，则输出块为Si盒中相应列号和行号的对应值。例如B1=101111，输入第1个S盒，S1(101111)计算为r=3，c=7，对应十进制7，即二进制0111。图3－11

DES算法的S盒图3-12P盒的置换

P盒置换输出：其左半部分的32比特为上一轮右半部分的32比特，L1=R0，而下一轮右半部为经过P盒作用之后输出32比特与左半部分L0的32位进行异或，得到右半部分最终的R1的32比特：XOR01000100001000001001111010011111111111111011100001110110010101110000000011111111000001101000001110111011100110001110100011001000

经过一轮完整变换之后，左半部分L1，右半部分R1，作为下一轮的输入，总共有16轮的运算。

3.逆初始置换（IP-1）

DES算法进行完16轮运算之后，需要进行逆初始置换，逆初始置换正好为初始置换的逆，若一个矩阵进行初始置换之后输出，再进行一次逆初始置换的输出结果为初始矩阵。

假若经过16轮加密之后，输入逆初始置换的64比特的块为，按照逆初始置换(IP)表进行置换，DES的初始置换表如图3－13所示。图3－13逆初始置换表按照图3－13中逆初始置换表操作如下：逆初始置换输出为，按照序号排出8×8的列。经过逆初始置换之后的64比特块为：，即密文C。

根据上面实例可知，DES算法的加密流程可以分为下面四个阶段：设输入64比特的明文块记为m1m2…m64，初始64比特密钥记为K0=k1k2…k64，密钥扩展之后的轮密钥分别记为K1,K2,…,K15,K16，算法描述如下：

(1)(L0,R0)←IP(m1m2…m64)，首先通过一个初始置换IP（如图3－7），把64比特明文块重排，然后将明文分组成左半部分和右半部分，各为32比特，即L0=m58m50…m8，R0=m57m49…m7。

(2)然后进行16轮完全相同的运算（图3－8），i从1到16，通过F函数（图3－9），数据与轮密钥结合，分别计算出Li和Ri，其中F函数计算可记为：其中E表示E盒变换（图3－10），S表示S盒变换（图3－11），P表示P盒变换（图3－12），具体变换过程如下所示：①T←E(Ri)，即将右半部的32比特的Ri=r1r2…r32输入E盒扩展为48比特，记为T。②T′←T+Ki，将得到的48比特的字串T与子密钥Ki异或得到T′，然后将T′平分为8个块，分别记为B1,…,B8，即为T′=(B1,…,B8)，每个块Bi为6比特。F(Ri-1,Ki)=P(S(E(Ri-1)Ki))③T″←(S1(B1),S2(B2),…,S8(B8))，将8个B1,…,B8比特块分别进行S盒变换（图3－11），将输入的48比特压缩为32比特输出，记为T″，其中每个S盒变换可记为Si(Bi)，具体变换过程参见下面的轮结构描述。

④T←P(T″)，T″作为输入，进行P盒置换输出，记为T’’’。

⑤Li←Ri-1,Ri←T’’’Li-1，输出的左半部Li为上一轮右半部Ri-1，而输出的右半部Ri为T与上一轮左半部Li-1进行异或操作。+

(3)b1b2…b64←(R16,L16)，经过上面16轮变换之后，把最后分组(L16,R16)进行交换，得到(R16,L16)作为输出。

(4)C←IP-1(b1b2…b64)，将第(3)步的输出进行IP逆置换最后得到密文C（图3－13）。

4．子密钥产生过程描述

子密钥产生过程的输入，为用户持有的64比特初始密钥，但若用户只提供56比特（通常是用ASCII码表示的7个字母的单词作为密钥）。其余8比特由算法提供，分别放在8、16、24、32、40、48、56和64位上（位的序号为8的倍数）。因此初始密钥中每8位的密钥包含用户提供的7位和DES确定的1位。DES算法添加的位称为奇偶校验位，即每8位的密钥块中都有奇数个奇偶校验（1的个数为奇数）。用户将初始密钥64位输入到子密钥产生流程中，首先经过密钥置换PC－1，将初始密钥的8个奇偶较验位去掉。留下真正的56比特初始密钥。接着，分为两个28比特分组C0及D0，再分别经过一个循环左移函数，每一半左移1或2位（每个阶段情况不同），连接成56比特数据，再按密钥置换PC－2做重排，进行压缩，抛弃8位后，便可输出子密钥的48比特，作为F函数的密钥输入部分。该过程如图3－14所示。图3－14

DES的轮密钥的产生

要注意的是，密钥置换PC－1的输入为64比特，输出为56比特；而密钥置换PC－2的输入和输出分别为56比特和48比特。

在我们所用示例中用户初始输入的56比特有效密钥为：。

分别在8、16、24、32、40、48、56和64位上插入DES算法提供的8位，变成64比特密钥为，然后作为选择置换PC－1的输入，按照下面的置换表进行重新编排和压缩，编排方式如图3－15所示。图3－15置换选择PC－1输入：PC－1输出：置换选择PC－1输出的56比特分为两半，前28比特为C0，后半部分的28比特为D0。然后根据左循环移位函数进行左循环移位1或2位，各轮移位位数如表3－1所示。表3－1循环左移位

根据表3-1所示，C0及D0分别左循环1位得到C1=1101100100110010001101110111D1=0110100010110001000111001101，然后C1和D1连接56位为11011001001100100011011101110110100010110001000111001101作为置换选择PC-2的输入，进行重新编排和压缩，输出48位，得到子密钥K1，而C1和D1作为下一轮子密钥的输入。置换选择PC-2的编排和压缩规则如图3-16所示。图3-16置换选择PC-2通过PC－2置换选择输出的就是DES第1轮的子密钥K1，为，作为DES算法轮结构变换F函数的输入。在分组密码算法中可以看出，密钥随着明文的每一轮变换而变换。DES算法有16轮运算，子密钥也有16个。

DES的各种变形算法

1.二重DES

二重DES算法是DES各种变形算法中最简单的形式，对明文加密不是使用一个密钥，而是采用两个互不相同的密钥K1和K2进行连续加密，因此二重DES的有效密钥长度实际为112比特，比起一重DES的56比特的有效密钥长度，其强度极大的增强。其加密和解密过程如图3－17所示。图3－17二重DES设二重DES两加密密钥分别为K1和K2，则首先用密钥K1对明文P进行加密，然后再用密钥K2进行加密，其密文为：解密时，首先用K2进行解密，然后再用K1进行解密，密钥顺序正好与加密密钥顺序相反，即

2.三重DES

在二重DES的基础上，又提出了三重DES算法。3DES的使用有如下四种不同模式：

（1）DES－EEE3模式。如图3－18所示，使用三个互不相同的密钥，实现方式为加密－加密－加密，密钥分别为K1、K2、K3，其密文为：解密时，密钥顺序正好与加密密钥顺序相反，即图3－18三重DES－EEE3模式（2）DES－EDE3模式。如图3－19所示，使用三个互不相同的密钥，依次采用加密－解密－加密算法，密钥分别为K1、K2、K3，其密文为：解密时，密钥顺序正好与加密密钥顺序相反，依次采用解密－加密－解密的顺序，即图3－19三重DES－EDE3模式（3）DES－EEE2模式，如图3－20所示，使用两个互不相同的密钥K1、K2，实现方式为加密－加密－加密算法，其中第1次和第3次加密采用相同的密钥，分别为K1=K3，其密文为：解密时，密钥顺序正好与加密密钥顺序相反，即图3－20三重DES－EEE2模式（4）DES－EDE2模式，如图3－21所示，使用两个互不相同的密钥K1、K2，实现方式为加密－解密－加密算法，简记为EDE。此方案已在密钥管理标准和ISO8732中被采用。密钥分别为K1=K3，其密文为：解密时，密钥顺序正好与加密密钥顺序相反，依次采用解密－加密－解密的顺序，即四种不同三重DES算法中，前两种模式的密钥长度为168比特，而后两种模式的密钥长度为112比特，已在因特网的许多应用（如PGP和S/MIME）中被采用。

3.4高级加密标准(AES)

算法中的数学基础知识

1.因子

设a、b是两个整数，b≠0，如果存在整数k，使得a=kb,则称b整除a，记为b|a。否则称b不整除a，记为ba。

一个基本性质是：若b|s、b|t，则对任意整数u、v，有b|us+vt。

证明：由b|s、b|t，则存在整数m、n，使得s=mb,t=nb，则us+vt=umb+vnb=(um+vn)b故b|us+vt。

2.模运算

设n是正整数，a是整数，如果用n去除a，得商为q，余数为r，则可以表示为：us+vt=umb+vnb=(um+vn)b用amodn表示余数r，则r≡a（modn）。例如：令a=17，n=5,则17=3×5+2，r=2≡17mod5

3.同余

设n是正整数，a,b是整数，如果amodn≡bmodn，则称整数a和b模n同余，记为a≡bmodn。

显然，a≡b

（modn），则n|(a-b).

例如：a=17,b=-8,n=5,因为17=3×5+2,-8=-2×5+2,则17mod5≡-8mod5，通常记为：

17≡-8mod5.

4.欧几里德除法

设a、b是整数，则a、b的所有公因数中最大的一个公因数叫做最大公因数，通常记为gcd(a,b)。

例如，12和-18的最大公因数为6，记为gcd(12,-18)=6。

如果两个整数的绝对值都比较小，求它们的最大公因数是比较容易的。如果两个数都比较大，可以用广义欧几里德除法，也称辗转相除法。

在介绍欧几里得除法前，介绍一个关于同余的性质。

对任何非负整数a和非负整数b，设a≥b，a=bq+r，0≤r<|b|，则gcd（a，b）=gcd(b，r)。证明：设gcd（a,b）=d,则d|a,d|b,则d|a-bq即d|r.同理，设gcd(b,r)=k,则k|b,k|r,则k|bq+r,即k|a.所以，结论成立。

例如，96=28×3+12，故gcd(96,28)=gcd(28,12)=4.

又如，88=11×8+0，故gcd(88,11)=gcd(11,0)=11.

欧几里得除法

设a,b＞0,且都为整数，进行下列计算:因为例如，求gcd(182，136)。因此gcd(182,136)=gcd(136,40)=gcd(48,8)=8

5.逆元

设m是正整数，a是整数，如果存在a′，使得a×a′≡1(mod

m)成立，则a叫模m的可逆元，a′叫a模m的逆元。

例如，设m为11，则8模11的逆元为7，因为8×7≡1(mod11)

在a和m互素的情况下，即（a,m）=1,则a的模m的逆元总是存在的，且可以用上面的辗转相除法求得。

例如，我们知道89是素数，求60模89的逆元，可以用下面的方法。89=1×60+2960=2×29+229=14×2+11=29-14×2=29-14×(60-2×29)=29×29-14×60=(89-60)×29-14×60=89×29-60×43则等式两端同时mod89得：60×(-43)≡1(mod89)故60模89的逆元为-43，为方便记为最小非负数，因为-43≡46(mod89)，故一般说60模89的逆元为45。

实际上，这里的逆元通常称为乘法逆元。从后面的学习可以看到，定义不同的运算和单位元，就可能有不同情况下的逆元。

8.有限域

由于有限域涉及的知识比较多，我们按内容的递进关系，分成小的知识点，介绍如下。

（1）有限域的定义

非空集合元素F，若在F中定义了加和乘两种运算，且满足下述公理：

（1）F关于加法构成交换群。其加法恒等元记为0。

（2）F中非零元素全体对乘法构成交换群。其乘法恒等元（单位元）记为1。

（3）加法和乘法间有如下分配律：a×(b+c)=a×b+a×c(b+c)×a=b×a+c×a则称F为一个域。若F中的元素个数有限，称F为有限域(FiniteField)。有限域也叫伽罗瓦(GaloisField)域。

例如，对于非空集合F={0,1,2,3,4,5,6,7,8,9,10}，在mod11的情况下做加法和乘法运算，定义运算规则为：

加法：如果a,b∈F,则

a+b≡r(mod11),r∈F

乘法：如果a,b∈F,则

a×b≡s（mod11）,s∈F

由前面的例题易得，F关于加法构成交换群，其加法恒等元为0；F中非零元素全体对乘法构成交换群，其乘法恒等元为1；分配律也是成立的。故F在mod11的情况下做加法和乘法运算构成有限域。其中：ci=ai+bimodp。在Zp［x］上的乘法也要求系数模p。

在实践中，用得比较多的是Z2［x］。

例如：这8个域元素的系数为(000,001,010,011,100,101,110,111)

6）有限域元素加运算

要计算两个域元素的和，可进行多项式相加（这里是在Z2［x］中的加法，系数是模2加）。例：(x2+1)＋(x2+x+1)=2x2+x+2≡xmod（x3+x+1）

7）有限域元素乘运算

要计算两个域元素的乘积，可进行多项式相乘，并且模x3+x+1约化（即用x3+x+1去除，找出余式）。由于是用一个三次多项式去除，余式的次数至多是2，因此余式是该域中的元素。例如：因此，在Z2［x］中，（x2+1）(x2+x+1)≡x2+xmod（x3+x+1）

AES算法描述

Rijndael是一种灵活的算法，加密明文分组块的长度可变、密钥长度也可变的。分组长度、密钥长度彼此独立地确定为128、192、256比特，因而Rijndael算法可以有9种不同的版本，而迭代次数与明文分组块的大小和密钥有关（如表3－3所示）。表3－3

Rijndael算法不同分组大小和密钥长度的加密轮次Rijndael算法不像DES算法，采用包含置换操作的典型的Feistel轮结构，而是进行多轮的替换、列混合和密钥加操作。AES算法和Rijndael密码算法并不完全一样，AES算法限定了明文分组大小为128比特，而密钥长度可为128、192、256比特，因而实际上AES有三个版本：AES－128、AES－192、AES－256，相应的迭代轮数为10轮、12轮、14轮。AES算法是Rijndael算法的子集，但实际应用中，术语AES和Rijndael视为等价，可以交替使用。

AES算法的加密过程是在一个4×4的字节矩阵上运作，这个矩阵又称为“体（state）”或者“状态”，其初值就是一个明文区块（矩阵中一个元素单位大小就是明文区块中的一个字节（8比特））。加密时，明文块与子密钥首先进行一次轮密钥加，然后各轮AES加密循环（除最后一轮外）均包含4个步骤，其结构如图3－22所示。图3－22

AES算法加密结构

(1)字节代替（SubBytes）：通过一个非线性的替换函数，用查找表的方式把每个字节替换成对应的字节。

(2)行移位（ShiftRows）：将矩阵中的每个横列进行循环式移位。

(3)列混合（MixColumns）：为了充分混合矩阵中各个直行的操作，这个步骤使用线性转换来混合每行内的四个字节。

（4）轮密钥加（AddRoundKey）：矩阵中的每一个字节都与该次循环的子密钥（roundkey）做XOR逻辑运算；每个子密钥由密钥生成方案产生。

最后一个加密循环中省略列混合（MixColumns）步骤，而以另一个轮密钥加（AddRoundKey）取代。例如：字节‘57’（十六进制数）对应的二进制为01010111，为GF(28)上域元素，字节‘57’对应的多项式为x6+x4+x2+x+1。（1）b7＝0实例举例：02·54=(00000010)·(01010100)

=(x)·(x6+x4+x2)

=x7+x5+x3≡x7+x5+x3(modp(x))

=(10101000）由上面的规则：相当于把字节(01010100)左移一位即得（10101000）（最后一位补0）。（2）b7＝1实例举例:02·D4=(00000010)·(11010100)

=(x)·(x7+x6+x4+x2)(modp(x))

=x8+x7+x5+x3(modp(x))≡(x4+x3+x+1)+x7+x5+x3(modp(x))≡x7+x5+x4+x+1(modp(x))多项式x7+x5+x4+x+1映射为二进制即为(10110011)。由上面的规则：先把(11010100)在字节内左移一位即得（10101000）（最后一位补0），因为b7＝1，故（10101000）再与（00011011）异或得（10110011）。

4.GF(28)上域元素的乘法逆元

在有限域GF(28)中，域元素的乘法满足交换律，且有单位元，并且每个域元素都有乘法逆元。在GF(28)中求乘法逆元可利用多项式的扩展的欧几里德算法计算出来。

求次数小于8的非零多项式b(x)的乘法逆元，首先利用多项式的扩展欧几德得算法得出两个多项式a(x)和c(x)，使得满足b(x)a(x)+p(x)c(x)=1，即满足a(x)·b(x)≡1modp(x)，因此a(x)是b(x)的乘法逆元。

例如：求GF(28)上域元素“F5”(十六进制)的乘法逆元。（1）“F5”对应二进制为11111001，则用多项式表示为b(x)=x7+x6+x5+x4+x2+1，然后计算两个多项式a(x)和c(x)满足:(x7+x6+x5+x4+x2+1)·a(x)+p(x)c(x)=1

(2)采用多项式的扩展欧几里得算法按照如下步骤计算：因为(x8+x4+x3+x+1)=(x7+x6+x5+x4+x2+1)(x+1)+x2

(x7+x6+x5+x4+x2+1)=x2(x5+x4+x3+x2+1)+1所以基本变换

AES算法每次明文分组以及每次变换的中间结果分组称为状态（State）。状态用以字节（8比特位）为基本构成元素的矩阵阵列来表示，该阵列有4行，即每列为32比特，因而列数为分组长度除以32，通常记为Nb。Rijndael算法列数Nb可以取的值为4、6、8，对应的分组长度为128、192、256比特。而AES算法的分组长度固定为128比特，以字节为基本单位转换为状态字节，依顺序a00，a10，a20，a30，a01，…，a23，a33，前4个字节组成第1列，后四个字节组成第2列，依次类推，AES算法明文分组可以构成一个4×4的字节矩阵，如图3－23所示，加密结束时，输出也是从状态字节中按相同的顺序提取。图3－23阵列状态

AES算法加密和解密过程中密码密钥（CipherKey）同样以字节为基本单位进行计算，顺序依次为k00，k10，k20，k30，k01，…，k23，k33，…，用一个4行的矩阵阵列来表示，前4个字节组成第1列，后4个字节组成第2列，依次类推，列数记为Nk。密钥Rijndael算法和AES算法的密码密钥的列数Nk可以取的值为4、6、8，对应的密钥长度为128、192、256比特，因而密码密钥构成一个4×4、4×6、4×8的密钥字节矩阵。如图3－24所示为192比特密钥的密码密钥矩阵，其中Nk为6。图3－24密码密钥阵列状态下面我们以一个128位块为例，开始分别介绍AES加密算法基本变换的具体过程。若示例块是由0和1组成的，输入的128位块为10000000010111100110101000110110010100110010010100111010011001100110001100110101011010010000001100100000011011000010100000000110，为了表达简洁，下面的AES算法基本变换的中间结果都用16进制来表示。则128比特二进制示例块用16进制表示则对应为805E6A3653253A6663356903206C2806(如表3-4所示).表3－4

AES算法实例明文分组在进行AES加密算法过程中，首先把输入明文128比特示例块805E6A3653253A6663356903206C2806按照AES算法规则构成一个构成一个4×4的字节矩阵，如图3-25所示。图3－25阵列状态

1．字节变换（SubBytes）

Rijndael算法的字节变换是一个基于S盒（不像DES算法使用8个S盒）的非线性置换。如表3－5所示，它将输入或中间态的每一个字节通过一个简单查表操作，映射为另外一个字节。映射方法是：输入字节前4位指定S盒的行值，后4位指定S盒的列值，行和列所确定S盒位置的元素作为输出（如图3－26），例如输入字节为“03”，行值为0，列值为3，根据表3－5可以得知第0行第3列对应的值为“7B”，输出字节为“7B”。表3－5

S盒（十六进制）图3－26

Rijndael算法字节代替操作例如，输入矩阵（用十六进制表示）进入S盒替换操作，则相应的输出如下所示：S盒字节替代—>在上面的示例中，第1个输入字节为“F5”，它将被S盒中第“F”行、第“5”列的元素“E6”代替，其余的输出也用相同的方法进行代替。上面的仿射变换用矩阵可以表示如下：（3－1）（2）十六进制“46”其二进制为01000110，进行第2步的仿射变换，代入矩阵运算运行：即二进制结果为11100110，对应十六进制结果为“E6”，与查表S盒替代操作结果一样。

2.行移位（ShiftRows）

在Rijndael算法中，行移位操作作用于S盒的输出。其中，状态阵列的4个行循环以字节为基本单位进行左移，而每1行循环左移的偏移量是由明文分组的大小和所在行数共同确定的，即列数Nb和行号确定。设状态阵列的每行用Ci来表示，那么每行偏移量如表3－6所示。图3－27行移位操作例如，输入矩阵（用十六进制表示）进入行移位操作，则相应的输出如下所示：接下来进行列混合操作。

3.列混合（MixColumns）

列混合操作可以将输入的状态矩阵的每列看做是有限域GF(28)上的多项式b(x)，与多项式s(x)=03x3+01x2+01x+02相乘然后模多项式x4＋1，其中多项式的系数为有限域GF(28)的运算。其方法为：令c(x)=s(x)×b(x)mod（x4＋1），因而列混合是可以表示为矩阵相乘来实现的，进行移位后的矩阵与固定矩阵（十六进制表示）相乘，如下所示：图3－28列混合操作例如，输入矩阵（用十六进制表示）进入列混合操作，则相应的输出如下所示：输入矩阵输出矩阵可以看到通过列混合操作第1列包含字节为B2、38、75、4A，经过这些操作明文经过几轮迭代后高度打乱了，同时还使输入和输出之间的关联变了。

4.轮密钥加（AddRoundKey）

最后一阶段是将列混合的状态矩阵与子密钥进行XOR逻辑运算（子密钥是从初始密钥派生而来的），即将轮密钥与状态按比特异或。轮密钥是通过密钥调度过程从密码密钥中得到的，轮密钥长度等于分组长度。如图3－29所示，这便完成了算法的一次迭代。

例如，输入状态矩阵和子密钥矩阵（用十六进制表示）进入轮密钥加操作，则相应的输出如下所示：图3－29轮密钥加密钥扩展

Rijndael算法的密钥同样以字节为基本单位进行计算，用一个4行的矩阵阵列来表示。密钥按照矩阵的列进行分组，密钥比特的总数等于明文分组长度乘以轮数加1，即密钥比特的总数＝分组长度×（轮数Round＋1）。例如当明文分组长度为128比特和轮数Round为10时，轮密钥长度为128×(10＋1)＝1408比特，则需要添加40个新列来进行扩充；当明文分组为128比特和轮数Round为12时，轮密钥长度为128×(12＋1)＝1664比特，则需要添加48个新列来进行扩充。Rijndael算法由于密码密钥Nk列数的不同，其密钥扩展算法有所不同。下面给出Rijndael算法的密钥扩展程序伪代码。若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［］表示初始密钥列向量，W［］表示密钥的列向量，SubBytes为小节的S盒的字节代替（如图3－26），RotWord则是以字节为单位的向左循环移位。而Rcon［i］=(RC［i］，′00′，′00″00′)，RC［0］=′01′，RC［i］=2*(RC［i-1］)，前10轮数RC［i］的值（用十六进制表示）如表3－7所示，对应Rcon［i］（用十六进制表示）如表3－8所示。表3－7

RC［i］表3－8

Rcon［i］图3－30

Nk=4的密钥扩展示意图首先初始密钥按照矩阵列进行分组，前4列初始密钥记为K0，K1，K2，K3，那么新的列Ki递归如下：

（1）如果Ki中，i不是4的倍数，那么i列由如下等式确定：Ki=Ki-4XORKi-1

(2)如果Ki中，i是4的倍数，那么i列由如下等式确定：Ki=Ki-4XORT［Ki-1］其中T［Ki-1］是Ki-1的一种转换形式，按以下方式实现：①循环地将Ki-1的元素左移位，每次一个字节，如abcd变成bcda；

②将这4个字节作为S盒的输入，输出新的4个字节efgh；

③计算一轮的常量r(i)=2(i-4)/4；

④这样生成转换后的列：［eXORr(i)，f，g，h］。

第i轮的轮密钥组成了列K4i，K4i+1，K4i+2，K4i+3。

例如：设初始种子密钥为K0=75356B99，K1=05613956，K2=73620531，K3=00550932，下一个子密钥段为K4，由于i是4的倍数，所以K4计算如下：K4=K0XORT(K3)

T(K3)的计算步骤如下：

（1）循环将K3按照字节为单位左移1字节，00550932变成了55093200;

（2）将55093200作为S盒的输入，查表得到输出fc012363;

（3）计算常量Rcon［i］=(RC(j)，00，00，00)，RC(j)=20=01(十六进制)；

（4）将01000000与fc012363f异或运算得fd012363。

因此

T(K3)=fd012363K4=75356B99XORfd012363=883448fa密钥选取非常简单，从扩展密钥中取出轮密钥：第一个轮密钥由扩展密钥的第一个Nb个字（其实就是Nb列），第二个轮密钥由接下来的Nb个字组成，以此类推。其结构如图3－31所示。图3－31轮密钥选择解密过程

AES算法解密过程中的基本运算，除了轮密钥加AddRoundKey与AES加密算法中一样，其它基本运算字节替代（SubBytes）、行移位（ShiftRows）、列混合（MixColumns）都要求逆，解密过程中的基本运算为逆字节替代（InvSubBytes）、逆行移位（InvShiftRows）、逆列混合（InvMixColumns）。下面简要介绍一下解密过程中的基本运算，其解密结构如图3－32所示。图3－32

AES算法解密结构1．逆字节代替（InvSubBytes）

Rijndael算法的逆字节变换（InvSubBytes）是与字节替代一样，它将输入或中间态的每一个字节通过一个简单查表操作，只是查表操作变为查逆S盒，如表3－9所示。映射方法是：输入字节前4位指定逆S盒的行值，后4位指定逆S盒的列值，行和列所确定逆S盒位置的元素作为输出。表3－9逆S盒（十六进制）

同样，Rijndael的逆S盒替代操作也包括两个变换，其变换顺序与S盒刚好相反，先进行仿射变换的逆变换，然后进行求逆运算：

（1）在GF(2)上进行下面的仿射变换，每个字节可以依次记为（b7，b6，b5，b4，b3，b2，b1，b0），依次做下面的仿射变换：其中di是指字节（05=00000101）中的第i位的值。上面逆仿射变换用矩阵可以表示如下：

2.逆行移位（InvShiftRows）

在Rijndael算法中，逆行移位操作与行移位操作相反，行移位操作循环向左移，而逆行移位操作则循环向右移。若AES算法中Nb为4，即第1行循环右移0字节，第2行循环右移1字节，第3行循环右移2字节，第4行循环右移3字节，如图3－33所示。图3－33逆行移位操作

3.逆列混合（InvMixColumns）

逆列混合操作与列混合操作一样，只是多项式不同，则逆列混合操作多项式d(x)=0Bx3+0Dx2+09x+0E相乘然后模x4＋1，因而逆列混合是可以表示为矩阵相乘来实现，输入的矩阵与固定矩阵（十六进制表示）相乘，如下所示：图3－34逆列混合操作具体实例

假设AES加密的明文消息为128比特，密钥为128比特。明文示例块十六进制表示为：805E6A3653253A6663356903206C2806，128比特初始密钥十六进制表示为：。现在我们来跟踪AES加密算法一轮加密过程，以观察所有操作对输出的影响。

首先，128比特的明文块和初始密钥分别依次写成4×4的状态矩阵形式。

明文示例块805E6A3653253A6663356903206C2806依次写成4×4的矩阵形式为：初始密钥也为128比特，十六进制表示为：

75356B99056139567362053100550932

则写成4×4的矩阵形式为：接下来首先明文分组阵列与初始密钥进行一次轮密钥加操作，如下所示：然后进入循环迭代操作，第一步为轮密钥加的输出作为S盒的输入，进行字节替代操作（如图3－26），如下所示：第二步，S盒的输出作为行移位的输入，进入行移位操作（如图3－27），如下所示：第三步，列混合（MixColumn）（如图3－28），在GF(28)域上进行如下矩阵运算：第四步，列混合的输出与子密钥进行轮密钥加，在这之前先进行密钥扩展，得到子密钥。设初始密钥扩展之后下一轮子密钥（K4、K5、K6、K7），如下：故迭代循环操作中第一轮第四步——轮密钥加为：输入 子密钥 输出根据小节密钥扩展算法，如下计算K4：K4=K1⊕SubByte(RotByte(K3))⊕Rcon[1]第一步，对K3执行RotByte(K3)，然后字节替代SubByte(RotByte(K3))。在密钥扩展中，先进行RotByte操作，然后根据S盒表3－4进行替代。如下所示：明文矩阵初始密钥输出矩阵第二步，K4=K0SubByte(RotByte(K3))Rcon［1］，其中Rcon［1］值如表3－8所示。第三步，计算K5、K6、K7。

3.5

SMS4密码算法

SMS4描述

继美国将Rijndael算法作为高级加密标准(AES)、欧洲将Camellia等算法作为NESSIE分组加密标准之后，中国国家密码管理局于2006年1月6日发布第7号公告，将我国无线局域网产品的加密算法确定为SMS4算法。这是国内官方公布的第一个商用密码算法。本算法是一个分组算法。该算法的分组长度为128比特，密钥长度为128比特。加密算法与密钥扩展算法都采用32轮非线性迭代结构。解密算法与加密算法的结构相同，只是轮密钥的使用顺序相反，解密轮密钥是加密轮密钥的逆序。

1．基本运算

SMS4算法采用以下基本运算：

表示32bit异或

<<<I表示32比特t循环左移i位图3－35

SMS4轮函数计算图3－36非线性变换τS盒的置换规则：输入的前4位为行号，后4位为列号，行列交叉点处S盒列表中的数据为输出（如表3－10），例如输入“ef”，则行号为“e”，列号为“f”，根据表3－10，于是S盒的输出值为“84”，即Sbox（ef）=84。

3)线性变换L

非线性变换τ的输出是线性变换L的输入，如图3－37所示，设输入为B∈Z322，输出为C∈Z322，这里，图3－37线性变换L表3－10

SMS4算法S盒（十六进制）算法流程图3－38SMS4加密算法流程图3-39SMS4密钥扩展算法流程图具体实例

以下为本算法ECB工作方式的运算实例，用以验证密码算法实现的正确性。其中，数据采用十六进制表示。

实例一：对一组明文用密钥加密一次。

明文:0123456789abcdeffedcba9876543210

加密密钥:0123456789abcdeffedcba9876543210

实例二：利用相同加密密钥对一组明文反复加密1000000次。

明文:0123456789abcdeffedcba9876543210

加密密钥:0123456789abcdeffedcba9876543210

密

文:595298c7c6fd271f0402f804c33d3f66 3.6其他典型的对称密码体制简介

RC6对称密码体制

RC6是AES候选算法之一，是由Rivest、Robshaw、Sidney和Yin提交的，它可能是最简单的AES算法，RC6是RC5的进一步改进。它的明文分组块大小为128比特，密钥可以为128、192或256比特，共进行20轮的加密。

RC6整个加密过程需要44个子密钥，这些密钥都是从初始的128比特密钥通过一系列复杂运算而生成的。初始128比特密钥分成四个32位字，存放在L(0)，L(1)，L(2)，L(3)[JP]四个寄存器数组中，而44个子密钥存放在S(0)，S(1)，…，S(43)44个寄存器数组中。首先对S(0)，S(1)，…，S(43)进行初始化，密钥生成算法中需要使用两个自然常数，一个是e(自然对数的基数)，另一个是ø（黄金分割率），则子密钥扩展算法如下：S[0]=b7e1519B(十六进制)Fori=1to43，doS[i]:=S[i-1]×9e3779B9(十六进制)A=B=i=j=0Fork=1to132，doA=S(i)=[S(i)+A+B]<<<3A=L(j)=[L(j)+A+B]<<<(A+B)i=(i+1)mod44j=(j+1)mod44

RC6加密算法作为AES候选算法，首先将128比特的明文分组划分成4个32比特的块，分别存放在A、B、C、D中，44个子密钥为S(0)，S(1)，…，S(43)，其加密算法如下所示：B=B+S[0]D=D+S[1]fori=1to20do{t=(B×(2B+1))<<<5u=(D×(2D+1))<<<5A=((At)<<<u)+S[2i]C=((Cu)<<<t)+S[2i+1]

(A,B,C,D)=(B,C,D,A)}A=A+S[42]C=C+S[43]注：算法中“+”、“-”、“×”符号表示模2w的加、减、乘运算（w表示字，即232），而符号“<<<”、“”分别表示循环左移和异或操作。(A，B，C，D)=(B，C，D，A)表示赋值操作即A=B、B=C、C=D、D=A。

RC6算法20轮的加密操作中，包括了XOR逻辑运算、移位、模2w的加、减、乘运算。第i轮操作如图3－40所示。图3－40

RC6一轮加密结构其中F盒执行一个乘法和加法操作，具体定义如下：t=(B×(2B+1))<<<5u=(D×(2D+1))<<<5

RC6解密过程与加密过程不同，但是基本操作类似，也非常简单。同样首先将解密的128比特的密文分成4个32比特的A、B、C、D块和44个子密钥作为输入，具体解密算法如下： C=C-S[43]

A=A-S[42]

fori=20downto1do

{(A,B,C,D)=(D,A,B,C)

u=(D×(2D+1))<<<5

t=(B×(2B+1))<<<5

C=((C-S[2i+1])>>>t)^u

A=((A-S[2i])>>>u)^t

}

D=D-S[1]

B=B-S[0]

Twofish对称密码体制

Twofish是Counterpane公司向NIST提交的一种满足AES要求的加密算法，设计者为Schneier。Twofish采用128比特数据块(128bitblock)，128、192、256比特可变长度密钥。Twofish算法是进入NIST第二轮5种加密算法中的一种，它同时具有RC6和Rijndael[JP]的某些特性，与DES算法一样，使用了16轮的Feistel结构来加密明文，并应用了一些特殊的操作，例如与密钥相关的S盒和矩阵相乘操作等，下面简单介绍一下Twofish加密算法。

Twofish加密过程中需要40个子密钥，由初始密钥通过复杂的密钥生成算法而生成。其中子密钥既要用于Feistel结构的各轮F盒中，也用于生成与密钥相关的S盒，因而S盒具有动态特性，使得攻击者无法预先分析，增强了算法的安全性。

Twofish加密算法与RC6算法类似，需初始密钥128比特，也即16字节。然后将这16字节分为4组，每组32比特，即4字节。在循环之前首先对这4组数据分别用K0、K1、K2、K3进行异或操作，称之为inputwhitening，然后对异或后的数据分组进行计算。计算后将1-3、2-4组的数据对换，如此循环15次，再将1-3、2-4对换一次。对这4组数据分别用K4、K5、K6、K7异或操作，称之为outputwhitening。最后将这4组数据组合成16字节的数据，也就是最后的密文，长度跟加密前的明文一样，同样是128比特。也是首先将明文分为4个32位的块，每一轮加密操作都要进行一次XOR逻辑运算、单个位的移位、一个特殊的函数f以及密钥生成。其中单轮加密如图3－41所示。图3－41

Twofish单轮加密操作

3.7对称密码体制的工作模式

ECB电子码本模式

ECB（ElectronicCodeBook）模式亦即电子码本模式，是最简单的模式，直接利用加密算法分别对分组数据组加密。明文分成64比特的分组进行加密，必要时填充，每个分组用同一密钥加密，同样的明文分组得到相同的密文。

图3－42演示了这种操作模式。图3－42

ECB加密/解密运行模式假