1、12024-3-192024-3-191112024-3-192024-3-1911主要内容：分组密码的基本概念 对称密码基本原理 数据标准加密（DES）高级加密标准(AES)对称密码体制工作模式 对称密码应用第三章第三章 分组密码算法分组密码算法22024-3-192024-3-19222024-3-1923.4AES（高级数据加密标准）32024-3-192024-3-19332024-3-19342024-3-192024-3-19442024-3-194 Rijndael 算法是由两位算法是由两位比利比利时的密码时的密码专家专家发明的，它运算速度很发明的，它运算速度很快快而而且所且所需
2、需的内的内存存不多，这个算法非常可不多，这个算法非常可靠；靠；Rijndael 算法的算法的设设计计策略策略是是宽轨迹策略宽轨迹策略,是是针针对对差差分分分分析析和线性分和线性分析析提提出来的，是一个分组出来的，是一个分组迭迭代密码，代密码，具具有可变的分组长度和密钥长度；有可变的分组长度和密钥长度；Rijndael 汇聚汇聚了安全性能、效了安全性能、效率、率、可实现性和可实现性和灵灵活活性等性等优点优点52024-3-192024-3-19552024-3-195 62024-3-192024-3-19662024-3-196 Rijndael密码设计原则密码设计原则 72024-3-192
3、024-3-197772024-3-192024-3-1977 不可约多项式不可约多项式:一个多项式f(x)称为是不可约的，如果不存在多项式f1(x),f2(x)Zpx，满足f(x)=f1(x)f2(x)，其中deg(f1)0和deg(f2)0,也即f1(x),f2(x)不能是常数。对于非空集合元素对于非空集合元素F，若在，若在F中定义了加和乘两种运算，且满足下述公理：中定义了加和乘两种运算，且满足下述公理：（1）F关于加法构成交换群。其加法恒等元记为关于加法构成交换群。其加法恒等元记为0。（2）F中非零元素全体对乘法构成交换群。其乘法恒等元（单位元）记为中非零元素全体对乘法构成交换群。其乘法
4、恒等元（单位元）记为1。（3）加法和乘法间有如下分配律：）加法和乘法间有如下分配律：a(b+c)=ab+ac (b+c)a=ba+ca 则称则称F为一个域。为一个域。若若F中的元素个数有限，称中的元素个数有限，称F为有限域为有限域(Finite Field)。有限域也叫伽罗瓦。有限域也叫伽罗瓦(Galois Field)域。域。82024-3-192024-3-1988Zpx/f(x)是域当且仅当f(x)是不可约的，也就是说，如果如果f(x)是不可约的是不可约的，则所有属于，则所有属于Zpx的多项式，在的多项式，在mod f(x)后的余式，组成的集合构成一个域后的余式，组成的集合构成一个域。反
5、之也成立。例如：计算Z2x/x3+x+1,可得所有余式构成八个元素的集合0,1,x,x+1,x2,x2+1,x2+x,x2+x+1,这个集合构成一个，加法单位元为0，乘法单位元为1。这八个域元素的系数为这八个域元素的系数为:(000,001,010,011,100,101,110,111)很容易知道，很容易知道，1,x,x+1,x2,x2+1,x2+x,x2+x+1模模x3+x+1就是自身。就是自身。下面是进一步的例子：下面是进一步的例子：例如求例如求x3 mod x3+x+1,因为因为x3+x+10 mod x3+x+1,故故x3x3+x3+x+1x+1 mod x3+x+1。又如求又如求x
6、4 mod x3+x+1，注意到注意到x4=x3 x，故故x4(x+1)x mod x3+x+1x2+x.92024-3-192024-3-199992024-3-192024-3-1999 在在AES中选择的不可约多项式是中选择的不可约多项式是p(x)=x8+x4+x3+x+1，余式的次数，余式的次数至多是至多是7次，共次，共28=256个多项式，这个多项式，这256个余式构成了一个有限域。个余式构成了一个有限域。字节字节b用二进制表示为用二进制表示为b=b7b6b5b4b3b2b1b0为有限域为有限域GF(28)上的域元素，上的域元素，若用多项式表示，若用多项式表示，bi可看作是多项式的系
7、数，可看作是多项式的系数，bi0,1，则字节，则字节b对应多项对应多项式为：式为：例如：字节例如：字节57（十六进制数）对应的二进制为（十六进制数）对应的二进制为，为，为GF(28)上域元素，字节上域元素，字节57对应的多项式为对应的多项式为。AES计算是在一个特别的有限域完成的。计算是在一个特别的有限域完成的。102024-3-192024-3-191010102024-3-192024-3-191010 GF(28)上两个域元素的和对应的多项式仍然是一个次数不超过上两个域元素的和对应的多项式仍然是一个次数不超过7的多项式，的多项式，其多项式系数等于两个元素对应多项式系数的模其多项式系数等于
8、两个元素对应多项式系数的模2加，即域元素对应二进制按位加，即域元素对应二进制按位异或运算。异或运算。例如例如:57+83=D4，用多项式表示为用多项式表示为:(x6+x4+x2+x+1)+(x7+x+1)x7+x6+x4+x2(modp(x)112024-3-192024-3-191111用二进制表示为：01010111 10000011=11010100由于每个元素的加法逆元等于自己，所以有限域减法和加法相同。要计算GF(28)上域元素的乘法，必须先确定一个GF(2)上的8次不可约多项式；GF(28)上两个元素的乘积就是这两个多项式的模乘。在Rijndael密码中，这个8次不可约多项式确定为
9、：它的十六进制表示为。例如，5783=C1可表示为多项式乘法：122024-3-192024-3-191212即：即：是普通多项式乘法，但系数运算可看作比特的乘法和异或运算，即看作域0,1上的运算。()()()()()mod()c xa xb xa xb xp x01223344556677)(axaxaxaxaxaxaxaxa01223344556677)(bxbxbxbxbxbxbxbxb01223344556677)(cxcxcxcxcxcxcxcxc843()1p xxxxx132024-3-192024-3-191313132024-3-192024-3-1913132024-3-1
10、913 （01110011）（10010101）所以所以，（，（01110011）（）（10010101）（）（01110000）)1(1)(247456xxxxxxx1222232345678910111213xxxxxxxxxxxxx1238910111213xxxxxxxxx)()1)(1(4563482345xxxxxxxxxxx142024-3-192024-3-191414142024-3-192024-3-1914142024-3-191488843843mod()mod(1)()1xp xxxxxxp xxxxx )()(01223344556677axaxaxaxaxaxax
11、axxax876543276543210()mod()a xa xa xa xa xa xaxa xp x07axaxaxaxaxaxaxaxax0213243546576)(.)0()(0123456aaaaaaaxax17a888437mod()mod()()1a xp xxp xp xxxxx152024-3-192024-3-191515152024-3-192024-3-1915152024-3-1915)(xax)1(34xxx)(0213243546576xaxaxaxaxaxaxa(00011011)(xax)0(0123456aaaaaaa上述过程称之为x乘法，其定义为:如果
12、b7=0，求模结果不变，由此得出x（十六进制数02）乘b(x)为对b(x)在字节内左移一位（最后一位补0）。若b7=1，则再与1B（其二进制为00011011）做逐比特异或来实现，而任意常数乘法可以通过对中间结果相加实现。162024-3-192024-3-191616162024-3-192024-3-191616 b70举例举例172024-3-192024-3-191717172024-3-192024-3-191717 02 D4=(0000 0010)(1101 0100)=(x)(x7+x6+x4+x2)(modp(x)=x8+x7+x5+x3(modp(x)(x4+x3+x+1)
13、+x7+x5+x3(modp(x)x7+x5+x4+x+1(modp(x)多项式多项式映射为二进制即为：映射为二进制即为：()由上面的规则：由上面的规则：因为因为b71，故（，故（1010 1000）再与（）再与（0001 1011）异或得（）异或得（1011 0011）b71举例举例182024-3-192024-3-191818182024-3-192024-3-191818例例3：求：求5713 192024-3-192024-3-191919202024-3-192024-3-192020 ,0,|.1a bbqabqbaabb a 设设是是任任意意两两个个整整数数,其其中中如如果果存
14、存在在一一个个整整数数 使使得得等等式式成成立立,则则称称或或者者 被被 整整除除,记记作作整整除除定定义义 如如果果 不不能能整整除除则则记记作作,|.baba 因因数数如如果果则则 叫叫做做 的的而而 叫叫做做 的的倍倍数数|,.b abaab写写成成或或/.aa bb此此时时 可可q补充补充212024-3-192024-3-192121,|,(mod),(mod).ma bmababmabmmabm 给给 定定 一一 个个 正正 整整 数数如如 果果 对对 于于 整整 数数有有则则叫叫记记 作作否否 则则叫叫 做做 模模定定 义义作作不不 同同 余余 记记1 1 ，做做 模模同同 余余
15、,7|291,291(mod17).因因 所所以以 例例 7|235,235(mod7).因因 所所以以 ,(mod),.1ma babmkabkm 设设 是是一一个个正正整整数数,是是两两个个整整 数数,则则的的是是存存在在整整数数使使 定定理理要要条条件件得得充充补充补充222024-3-192024-3-192222|0.b aabr被被 除除所所得得的的余余数数推推论论 补充补充232024-3-192024-3-192323232024-3-192024-3-1923234、最大公因数 1212,(2),|(1,2,),.1nknaaanndakndaaa 设设是是个个 整整 数数若
16、若 整整数数则则 称称是是的的 一一 个个 定定公公 因因 数数义义 121212,(,).nnnaaaaaaaaa 若若不不 全全 为为 零零,则则 整整 数数的的所所 有有 公公 因因 数数 中中 最最 大大 的的 一一 个个 公公 因因 数数 叫叫 做做记记 作作最最 大大 公公 因因 数数.1212,(,)1,nnaaaaaa 互互素素特特 别别当当时时称称或或 互互 质质.1212120,(),;(2)|,|.nnnda aad|a d|ad|ae a e|ae|ae d 是是的的最最大大公公因因数数1 1 若若则则最最大大公公因因数数可可描描述述为为:补充补充242024-3-19
17、2024-3-1924245、扩展的欧几里得除法、扩展的欧几里得除法 01,.a bra rb设设是是任任意意两两个个正正整整数数 记记反反复复运运用用欧欧几几里里得得除除法法:补充补充252024-3-192024-3-192525补充补充262024-3-192024-3-1926261nnnrr q 0112,rr qr1223,rr qr211,nnnnrrqr在在广广义义欧欧几几里里得得除除法法中中,由由3221,nnnnrrqr211,nnnnrrqr 1322,nnnnrrrq3122,rrr q2011rrr q(,)satba b1232,nnrrr rs t逐逐次次消消去去
18、可可找找到到整整数数使使得得补充补充272024-3-192024-3-192727 18591 1573286157352862862 143143解解 因因(,)143.s=t=sa+tb=a b 所所以以有有整整数数5,6,5,6,使使得得 1573528615735(18591 1573143)于于是是 1573528628618591431 1573 5(1859)6 1573 1859,1573,(,)1.0abs tsatba b 设设求求整整数数使使得得 例例例282024-3-192024-3-192828 设m是正整数，a是整数，如果存在a,使得aa 1(mod m)成立，
19、则a叫模m的可逆元，a 叫a模m的逆元。例如，设m为11，则8模11的逆元为7，因为871(mod11)当a和m互素的情况下，即（a,m）=1,则a的模m的逆元总是存在的，且可以用下面的辗转相除法()求得。例如，知道89是素数，求60模89的逆元，可以用下面方法。89=160+29 60=229+2 29=142+1则1=29-142=29-14(60-229)=2929-1460=(89-60)29-1460=8929-6043292024-3-192024-3-192929 上页等式两端同时mod89得：60(-43)1 mod 89 故60模89的逆元为-43，为方便记为最小非负数，因为
20、-4346 mod89，故一般说60模89的逆元为46。因此，求a(x)模p(x)的乘法逆元转化为求两个多项式b(x)和c(x)，使得满足 b(x)a(x)+p(x)c(x)=1，即满足a(x)b(x)1 mod p(x)，因此b(x)是a(x)模p(x)的乘法逆元。GF(28)上域元素的乘法逆元上域元素的乘法逆元302024-3-192024-3-193030302024-3-192024-3-193030 求求GF(28)上域元素上域元素F5(十六进制十六进制)的乘法逆元。的乘法逆元。（1）F 5 用 对 应 二 进 制 为用 对 应 二 进 制 为 1 1 1 1 0 1 0 1，则 用
21、 多 项 式 表 示 为，则 用 多 项 式 表 示 为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)采用多项式的扩展欧几里得算法按照如下步骤计算：采用多项式的扩展欧几里得算法按照如下步骤计算：312024-3-192024-3-193131312024-3-192024-3-193131322024-3-192024-3-193232322024-3-192024-3-193232-课堂作业课堂作业1 1：请使用有限域请使用有限域GFGF（2828）上的字
22、节运算方法计算：）上的字节运算方法计算：（1 1）1616进制的进制的“12”12”与与“59”59”的加法，即计算的加法，即计算“12+59”12+59”的值；的值；（2 2）1616进制的进制的“12”12”与与“59”59”的乘法，即计算的乘法，即计算“1259”1259”的值。的值。332024-3-192024-3-1933332024-3-1933 Rijndael 是一种灵活的算法，加密明文分组块的长度可变、密钥长度也可变的是一种灵活的算法，加密明文分组块的长度可变、密钥长度也可变的分组密码。分组长度、密钥长度彼此独立地确定为分组密码。分组长度、密钥长度彼此独立地确定为128、1
23、92、256比特，因而比特，因而Rijndael算法可以算法可以 9种不同的版本，而迭代次数与明文分组块的大小和密钥有关（如种不同的版本，而迭代次数与明文分组块的大小和密钥有关（如下表）。下表）。轮数（Round）分组长度128bit分组长度192bit分组长度256bit密钥128比特101214密钥192比特121214密钥256比特141414对于对于AES，只用了第一列，即明文长度固定为，只用了第一列，即明文长度固定为128比特比特342024-3-192024-3-1934342024-3-1934 Rijndael算法不像算法不像DES算法，采用包含置换操作的典型的算法，采用包含置
24、换操作的典型的Feistel轮结构，而是轮结构，而是进行多轮的替换、列混合和密钥加操作，因此进行多轮的替换、列混合和密钥加操作，因此Rijndael本质上是采用代替本质上是采用代替/置换网置换网络的对称分组密码体制。络的对称分组密码体制。AES和和Rijndael密码算法并不完全一样，密码算法并不完全一样，AES算法限定了明文分组大小为算法限定了明文分组大小为128比特，而密钥长度可为比特，而密钥长度可为128、192、256比特，因而实际上比特，因而实际上AES有三个版本：有三个版本：AES-128、AES-192、AES-256，相应的迭代轮数为相应的迭代轮数为10轮、轮、12轮、轮、14
25、轮。轮。AES算法是算法是Rijndael算法的子集，但实际应用中，术语算法的子集，但实际应用中，术语AES和和Rijndael视为等视为等价，可以交替使用。价，可以交替使用。AESAES加密过程是在一个加密过程是在一个4 44 4的字节矩阵上运作，这个矩阵又称为的字节矩阵上运作，这个矩阵又称为“体（体（statestate）”或者或者“状态状态”，其初值就是一个明文区块（，其初值就是一个明文区块（矩阵中一个元素单位大小就是明文区块矩阵中一个元素单位大小就是明文区块中的一个中的一个ByteByte（8 8比特）比特）。加密时，明文块与子密钥首先进行一次轮密钥加，然）。加密时，明文块与子密钥首先
26、进行一次轮密钥加，然后各轮后各轮AESAES加密循环（除最后一轮外）均包含加密循环（除最后一轮外）均包含4 4个步骤，其结构如下页图所示。个步骤，其结构如下页图所示。352024-3-192024-3-1935352024-3-1935 1.字节代替（字节代替（SubBytes）：）：通过一个非线性的替换函数，用查找表的方式把每个通过一个非线性的替换函数，用查找表的方式把每个字节替换成对应的字节。字节替换成对应的字节。2.行移位（行移位（ShiftRows）：）：将矩阵中的每个横列进行循环式移位。将矩阵中的每个横列进行循环式移位。3.列混合（列混合（MixColumns）：）：为了充分混合矩阵
27、中各个直行的操作。这个步骤使为了充分混合矩阵中各个直行的操作。这个步骤使用线性转换来混合每行内的四个字节。用线性转换来混合每行内的四个字节。362024-3-192024-3-1936362024-3-1936 4.轮密钥加（轮密钥加（AddRoundKey）：）：矩阵中的每一个字节都与该次循环的子密钥矩阵中的每一个字节都与该次循环的子密钥（round key）做做XOR逻辑运算；每个子密钥由密钥生成方案产生。逻辑运算；每个子密钥由密钥生成方案产生。最后一个加密循环中没有列混合（最后一个加密循环中没有列混合（MixColumns）步骤，而以另一个轮密钥加步骤，而以另一个轮密钥加（AddRoun
28、dKey）取代。取代。大多数大多数AES计算是在由不可约多项式计算是在由不可约多项式x x8 8+x+x4 4+x+x3 3+x+1+x+1构造的有限域上完成的。构造的有限域上完成的。AES的加密过程演示的加密过程演示372024-3-192024-3-1937372024-3-19373.4.4 基本变换基本变换 AES算法每次明文分组以及每次变换的中间结果分组称为算法每次明文分组以及每次变换的中间结果分组称为（State）。）。用以字节（用以字节（8比特位）为基本构成元素的矩阵阵列来表示，该阵列有比特位）为基本构成元素的矩阵阵列来表示，该阵列有4行，行，即每列为即每列为32比特，因而比特，
29、因而为分组长度除以为分组长度除以32，通常记为，通常记为Nb。列数：列数：Nb=分分组长度（比特）组长度（比特）32 Rijndael算法列数算法列数Nb可以取的值为可以取的值为4,6,8,对应的分组长度为对应的分组长度为128,192,256 比特。比特。而而AES算法的分组长度固定为算法的分组长度固定为128比特，比特，以字节为基本单位转换为状态字节，以字节为基本单位转换为状态字节，依顺序依顺序 a00,a10,a20,a30,a01,a23,a33，前前4个字节组成第个字节组成第1列，后四个字节组成第列，后四个字节组成第2列，列，依次类推，依次类推，AES算法明文分组可以构成一个算法明文
30、分组可以构成一个44的的字节字节矩阵，如下页图所示，矩阵，如下页图所示，加密加密结束时，输出也是从状态字节中按相同的顺序提取。结束时，输出也是从状态字节中按相同的顺序提取。382024-3-192024-3-1938382024-3-1938 AESAES算法加密和解密过程中密码密钥（算法加密和解密过程中密码密钥（Cipher KeyCipher Key）同样以字节为基本单位同样以字节为基本单位转换，因而依顺序转换，因而依顺序 k k0000,k,k1010,k,k2020,k,k3030,k,k0101,k k2323,k,k3333,，为类似地用一个为类似地用一个4 4行的矩阵行的矩阵阵列
31、来表示，前阵列来表示，前4 4个字节组成第个字节组成第1 1列，后四个字节组成第列，后四个字节组成第2 2列，依次类推，列数记列，依次类推，列数记为为N Nk k。N Nk k=密钥长度（比特）密钥长度（比特）3232392024-3-192024-3-1939392024-3-1939 RijndaelRijndael算法和算法和AESAES算法的密码密钥的列数算法的密码密钥的列数N Nk k可以取的值为可以取的值为4 4、6 6、8,8,对应的密对应的密钥长度为钥长度为128128、192192、256256bitsbits，因而密码密钥构成一个因而密码密钥构成一个4 4 4 4、4 4
32、6 6、4 4 8 8的密钥字节的密钥字节矩阵。如下图所示，矩阵。如下图所示，192192比特密钥的密码密钥矩阵，比特密钥的密码密钥矩阵，N Nk k为为6 6。402024-3-192024-3-1940402024-3-1940 下面我们以一个下面我们以一个128位块为例，介绍位块为例，介绍AES加密算法基本变换的具体过程。加密算法基本变换的具体过程。若示例块是由若示例块是由0和和1组成的，输入的组成的，输入的128位块为位块为10000000 01011110 01101010 00110110 01010011 00100101 00111010 01100110 01100011 0
33、0110101 01101001 00000011 00100000 01101100 00101000 00000110 为了表达简洁，下面的为了表达简洁，下面的AES算法基本变换的中间结果都用算法基本变换的中间结果都用16进制来表示。则进制来表示。则128比特二进制示例块用比特二进制示例块用16进制表示则对应为进制表示则对应为 80 5E 6A 36 53 25 3A 66 63 35 69 03 20 6C 28 06(如下表如下表 所示所示)。412024-3-192024-3-1941412024-3-1941 在进行在进行AES加密算法过程中，首先把输入明文加密算法过程中，首先把输
34、入明文128比特示例块比特示例块80 5E 6A 36 53 25 3A 66 63 35 69 03 20 6C 28 06按照按照AES算法规则构成一个构成一个算法规则构成一个构成一个4 4的字节矩的字节矩阵阵，如下图所示。，如下图所示。1字节代替（字节代替（SubBytes）Rijndael算法的字节变换（算法的字节变换（SubBytes）使用一个使用一个S盒（不像盒（不像DES算法使用算法使用8个个S盒）进行非线性置换。如下页表所示，它将输入或中间态的每一个字节通过一个盒）进行非线性置换。如下页表所示，它将输入或中间态的每一个字节通过一个简单的查表操作，映射为另外一个字节。简单的查表操
35、作，映射为另外一个字节。422024-3-192024-3-1942422024-3-1942 映射方法：输入字节前映射方法：输入字节前4位指定位指定S盒的行值，后盒的行值，后4位指定位指定S盒的列值。有行和列所确盒的列值。有行和列所确定定S盒位置的元素作为输出（如下页图所示）。盒位置的元素作为输出（如下页图所示）。例如输入字节例如输入字节“03”，行值为，行值为0，列值，列值为为3；根据上表可以查得第；根据上表可以查得第0 0行第行第3 3列对应的值为列对应的值为 “7B”，输出字节为输出字节为“7B”。432024-3-192024-3-1943432024-3-1943 例如，输入矩阵（
36、用例如，输入矩阵（用16进制表示）进入进制表示）进入S盒替换操作，则相应的输出如下所示：盒替换操作，则相应的输出如下所示：442024-3-192024-3-1944442024-3-1944 其实其实S盒是一个复杂的代数结构，盒是一个复杂的代数结构，S盒的设计是有一定限制条件的，其中的一盒的设计是有一定限制条件的，其中的一些限制条件是：它应当是可逆的，不能存在这种情况：行些限制条件是：它应当是可逆的，不能存在这种情况：行i列列j位置上的值为位置上的值为ij。实际实际Rijndael的的S盒字节替代操作它包括两个代数变换：盒字节替代操作它包括两个代数变换：452024-3-192024-3-1
37、945452024-3-1945 上面仿射变换用矩阵可以表示如下：上面仿射变换用矩阵可以表示如下：下面以输入下面以输入“F5F5”为示例来说明为示例来说明S S盒替代操作它包括两个变换，不通过查盒替代操作它包括两个变换，不通过查S S盒表，而通过盒表，而通过代数计算求解。代数计算求解。首先求解首先求解“F5F5”由由f(x)=xf(x)=x8 8+x+x4 4+x+x3 3+x+1+x+1构造构造GF(2GF(28 8)有限域上的乘法逆元，然后进行上式的有限域上的乘法逆元，然后进行上式的变换。变换。462024-3-192024-3-1946462024-3-1946 1）其输入十六进制）其输
38、入十六进制“F5”对应二进制为对应二进制为“11110101”，多项式为，多项式为(x7+x6+x5+x4+x2+1)，求其模求其模f(x)=x8+x4+x3+x+1的逆，即求的逆，即求b(x)：(x7+x6+x5+x4+x2+1)b(x)1(mod f(x)通过多项式欧几里得扩展算法，求解得：通过多项式欧几里得扩展算法，求解得：(x7+x6+x5+x4+x2+1)(x6+x2+x)1 mod(x8+x4+x3+x+1)即：即：(x7+x6+x5+x4+x2+1)模模(x8+x4+x3+x+1)的乘法逆元为的乘法逆元为x6+x2+x，即即 F5的乘法逆元为的乘法逆元为46。2 2）十六进制十六
39、进制4646其二进制为其二进制为0100011001000110，进行第，进行第2 2步的仿射变换，代入矩阵步的仿射变换，代入矩阵运算运行：运算运行：即二进制结果为即二进制结果为1110011011100110，对应十六进制结果为，对应十六进制结果为“E6E6”，与查表与查表S S盒替代操作结盒替代操作结果一样。果一样。472024-3-192024-3-1947472024-3-19472行移位（行移位（ShiftRows）在在RijndaelRijndael算法中，行移位操作作用于算法中，行移位操作作用于S S盒的输出。盒的输出。其中，状态阵列的其中，状态阵列的4 4个行循环以字节为基本单
40、位进行左移，而每个行循环以字节为基本单位进行左移，而每1 1行循环做移的偏行循环做移的偏移量是由明文分组的大小和所在行数共同确定，即列数移量是由明文分组的大小和所在行数共同确定，即列数N Nb b和行号确定。和行号确定。设状态阵列的每行用设状态阵列的每行用C Ci i来表示，那么每行偏移量如下表所示：来表示，那么每行偏移量如下表所示：AESAES算法中算法中N Nb b为为4 4，即第，即第1 1行循环左移行循环左移0 0字节，第二行循环左移字节，第二行循环左移1 1字节，第三行循环字节，第三行循环左移左移2 2字节，第四行循环左移字节，第四行循环左移3 3字节，如下页图字节，如下页图。从该图
41、中可以看出，这使得列完全进。从该图中可以看出，这使得列完全进行了重排。行了重排。482024-3-192024-3-1948482024-3-1948 例如，输入矩阵（用例如，输入矩阵（用16进制表示）进入行移位操作，则相应的输出如下所示：进制表示）进入行移位操作，则相应的输出如下所示：492024-3-192024-3-1949492024-3-19493列混合（列混合（MixColumns）列混合操作可以将输入的状态矩阵的每列看作是有限域列混合操作可以将输入的状态矩阵的每列看作是有限域GF(2GF(28 8)上的多项式上的多项式b(x)b(x)，与多项式与多项式s(x)=03 xs(x)=
42、03 x3 3+01 x+01 x2 2+01 x+02+01 x+02相乘然后模相乘然后模x x4 4+1+1，其中多项式的系数其中多项式的系数为有限域为有限域GF(2GF(28 8)的运算。的运算。其方法为其方法为 令令c(x)=s(x)c(x)=s(x)b(x)mod b(x)mod（x x4 41 1），），因而列混合是可以表示为因而列混合是可以表示为矩阵相乘来实现，进行移位后的矩阵与固定矩阵（十六进制表示）相乘，如下所矩阵相乘来实现，进行移位后的矩阵与固定矩阵（十六进制表示）相乘，如下所示：示：502024-3-192024-3-1950502024-3-1950 列混合操作如下图所
43、示：列混合操作如下图所示：例如，输入矩阵（用例如，输入矩阵（用1616进制表示）进入列混合操作，则相应的输出如下所示：进制表示）进入列混合操作，则相应的输出如下所示：512024-3-192024-3-1951512024-3-1951 例如：第例如：第1 1行行0202，0303，0101，0101与第与第1 1列列 E6,1BE6,1B，5050，1818相乘，其中符号相乘，其中符号“*”和和“”分别为有限域分别为有限域GF(2GF(28 8)的乘法和加法运算，具体操作如下：的乘法和加法运算，具体操作如下：可以看到通过列混合操作第可以看到通过列混合操作第1 1列包含字节为列包含字节为B2B
44、2、3838、7575、4A4A，经过这些操作明经过这些操作明文经过几轮迭代后高度打乱了，同时还保证输入和输出之间关联很少了。文经过几轮迭代后高度打乱了，同时还保证输入和输出之间关联很少了。522024-3-192024-3-1952522024-3-19524轮密钥加（轮密钥加（AddRoundKey）最后一阶段是将列混合的状态矩阵与子密钥进行最后一阶段是将列混合的状态矩阵与子密钥进行XORXOR逻辑运算（子密钥是从初逻辑运算（子密钥是从初始密钥派生而来的），始密钥派生而来的），即将轮密钥与状态按比特异或即将轮密钥与状态按比特异或。轮密钥是通过密钥调度过程。轮密钥是通过密钥调度过程从密码密钥
45、中得到的，轮密钥长度等于分组长度。如下图，这完成了算法的一次迭从密码密钥中得到的，轮密钥长度等于分组长度。如下图，这完成了算法的一次迭代。代。532024-3-192024-3-1953532024-3-1953 例如，输入状态矩阵和子密钥矩阵（用例如，输入状态矩阵和子密钥矩阵（用1616进制表示）进入轮密钥加操作，则进制表示）进入轮密钥加操作，则相应的输出如下所示：相应的输出如下所示：542024-3-192024-3-1954542024-3-1954552024-3-192024-3-195555加密算法的描述及实现加密算法的描述及实现 Rijndael解密算法用伪C语言表示如下：Rij
46、ndael-Chiper(bytein4*Nb,byteout4*Nb,wordwNb*Nr+1)Beginbytestate4,Nbstate=inAddRoundKey(State,w0,Nb-1)forround=1step1toNr-1SubBytes(state)ShiftRows(state)MixColumn(state)AddRoundKey(State,wround*Nb,(round+1)*Nb-1)EndforSubBytes(state)ShiftRows(state)AddRoundKey(State,wNr*Nb,(round+1)*Nb-1)Out=stateen
47、d-加密的具体过程：加密的具体过程：首先将明文分组复制到矩阵首先将明文分组复制到矩阵中中，经过初始轮密钥加后，经过初始轮密钥加后，在执行在执行Nr-1次轮变次轮变换来转变状态矩阵换来转变状态矩阵，最后一轮与前，最后一轮与前Nr-1轮不同轮不同之处在于这一轮没有列混合变换；之处在于这一轮没有列混合变换；最后将状态最后将状态矩阵中的各个字节按顺序输出就得到密文分组。矩阵中的各个字节按顺序输出就得到密文分组。562024-3-192024-3-1956562024-3-19563.4.5 密钥扩展密钥扩展 Rijndael算法的密钥按照矩阵的列进行分组，密钥比特的总数等于明文分组长度乘以轮数加1，即
48、分组长度（轮数Round1）。例如当明文分组长度为128bits和轮数Round为10时，轮密钥长度为128(101)1408bits，则需要添加40个新列来进行扩充；当明文分组为128bits和轮数Round为12时，轮密钥长度为128(121)1664bits，则需要添加46个新列来进行扩充。Rijndael算法由于密码密钥Nk列数的不同，其密钥扩展算法有所不同。572024-3-192024-3-1957572024-3-1957下面以密钥长度下面以密钥长度128比特为例比特为例，Nk=4,其密钥扩展示意图如下图。其密钥扩展示意图如下图。首先初始密钥按照矩阵列进行分组，前首先初始密钥按照
49、矩阵列进行分组，前4列初始密钥计为列初始密钥计为K0,K1,K2,K3，那么那么新的列如下递归：新的列如下递归：（1 1）如果）如果K Ki i中，中，i i不是不是4 4的倍数，那么的倍数，那么i i列由如下等式确定：列由如下等式确定：NK=4的密钥扩展示意图的密钥扩展示意图 582024-3-192024-3-1958582024-3-1958 其中其中TKTKi-1i-1 是是K Ki-1i-1的一种转换形式，按以下方式实现：的一种转换形式，按以下方式实现：循环地将循环地将K Ki-1i-1的元素左移位，每次一个字节，如的元素左移位，每次一个字节，如 abcd abcd 变成变成bcda
50、bcda 将这将这4 4个字节作为个字节作为S S盒的输入，输出新的盒的输入，输出新的4 4个字节个字节efghefgh 计算一轮的常量计算一轮的常量 r(i)=Rcon(j/Nr(i)=Rcon(j/NK K)这样生成转换后的列：这样生成转换后的列：e XOR r(i),f,g,he XOR r(i),f,g,h (2)(2)如果如果K Ki i中，中，i i是是4 4的倍数，那么的倍数，那么i i列由如下等式确定：列由如下等式确定：K Ki i=K Ki-4i-4 XOR XOR TKTKi-1i-1 实例：实例：设初始种子密钥为设初始种子密钥为 K0=75 35 6B 99，K1=05
