《现代密码学》学习笔记——第三章 分组密码 [二] AES

版本密钥长度分组长度迭代轮数AES-1284410AES-1926412AES-2568414

一、AES的整体结构

二、轮函数

（1）字节代换（SubByte）
（2）行移位（ShiftRow）
（3）列混合（MixColumn）
（4）密钥加（AddRoundKey）

1.字节代换

  字节代换是非线性变换，独立地对状态的每个字节进行。代换表（S-Box）是可逆的。
  将明文字节Ai看作GF(28)上的元素，映射到自己的乘法逆元，’00’映射到自己。（可以通过矩阵计算得出）B′
对字节B′i做仿射变换得到密文Bi

2.行移位

  将状态阵列的各行进行循环移位，不同用的状态行的位移量不同。第0行不移动，第1行循环左移C1个字节，第二行循环左移C2个字节，第三行循环左移C3个字节。

3.有限域上的字节运算

  GF(28) 上的元素表示方法:
    字节表示 Byte: a7a6a5a4a3a2a1a0
    多项式表示 s(x)： s(x) =a7x7+a6x6+a5x5+a4x4+a3x3+a2x2+a1x+ a0

（1）28有限域上的加法运算
例：0x57 + 0x83 = ?
0x57表示16进制的57，表示成二进制为：01010111
0x83表示16进制的83，表示成二进制为：10000011
相加相当于对两个数做异或运算，01010111 ⊕ 10000011 = 11010100 = 0xD4

原式 =(0x7 + 1x6 + 0x5 + 1x4 + 0x3 + 1x2 + 1x + 1) + ( 1x7 + 0x6 + 0x5 + 0x4 + 0x3 + 0x2 + 1x + 1 )

= ( x6 + x4+ x2 + x + 1 ) + ( x7 + x + 1 )

=x7 + x6 + x4+ x2

（2）28有限域上的乘法运算
例：0x57 × 0x83 = ?
0x57表示16进制的57，表示成二进制为：01010111
0x83表示16进制的83，表示成二进制为：10000011
mod m(x)= x8+x4+x3+x+1

原式 =[(0x7 + 1x6 + 0x5 + 1x4 + 0x3 + 1x2 + 1x + 1) × ( 1x7 + 0x6 + 0x5 + 0x4 + 0x3 + 0x2 + 1x + 1 )] mod (x8+x4+x3+x+1)

= [( x6 + x4+ x2 + x + 1 ) × ( x7 + x + 1 )] mod (x8+x4+x3+x+1)

= [( x6× x7 + x4× x7 + x2× x7 + x × x7 + 1 × x7 ) + ( x6× x + x4× x + x2× x + x × x + 1 × x ) + ( x6× 1 + x4× 1 + x2× 1 + x × 1 + 1 × 1 )] mod (x8+x4+x3+x+1)

= [( x13 + x11 + x9 + x8 + x7 ) + ( x7 + x5 + x3 + x2 + x ) + (x6 + x4 + x2+ x + 1)] mod (x8+x4+x3+x+1)

= [x13 + x11 + x9 + x8+ x6 + x5 + x4 + x3 + 1] mod (x8+x4+x3+x+1)

x5m(x) = x5( x8+x4+x3+x+1) = x13 +x9 +x8+x6+x5

原式= (x11 + x4 + x3 + 1) mod (x8+x4+x3+x+1)

x3m(x) = x3( x8+x4+x3+x+1) = x11 +x7 +x6+x4+x3

原式= ( x7 + x6 + 1) mod (x8+x4+x3+x+1) [一直做到原式中的最高次数低于8]

0x57 × 0x83 = x7 + x6 + 1

( x7 + x6 + 1)对应二进制为1100 0001，即：0×C1

（3）28有限域上的x乘法运算
  定义为x·b(x) = b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+ b0x（mod m(x)）
  如果b7=0，求模结果不变，否则为乘积结果减去m(x)，即求乘积结果与m(x)的异或。由此得出x(十六进制02)乘b(x)可以先对b(x)在字节内左移一位(最后一位补0)，若b7=1 则再与1B(其二进制为0001 1011)做逐比特异或来实现，该运算记为b= xtime(a)。在专用芯片中，xtime只需4个异或。x的幂乘运算可以重复应用xtime来实现。而任意常数乘法可以通过对中间结果相加实现。
例：用x乘法实现0×57·13
0×57的二进制表示为：01010111
  57 · 02 = xtime(57) = AE （将57的二进制形式01010111左移一位再补0得到10101110，也就是十六进制的AE）
  57 · 03 = 57·(02+01) = 57· 02+57·01 = 0×AE+0×57=10101110+01010111=111111001=0×F9
  57 · 04 = AE·02 = xtime(AE) = 47（将AE的二进制形式10101110左移一位再补0得到01011100，然后将其与1B也就是00011011异或，得到01000111，也就是0×47）
  57 · 08 = 47·02 = xtime(47) = 8E
  57 · 10 = 8E·02 = xtime(8E) = 07
  57 · 13 = 57 ·(01 ⊕ 02 ⊕ 10)=57⊕ AE⊕ 07=FE

（4）系数在GF(28)上的mod（x4+1）的乘法
  4个字节构成的向量可以表示为系数在GF(28)上的次数小于4的多项式。多项式的加法就是对象系数相加，换句话说，也就是4字节向量逐比特异或。
a(x) = a3x3+a2x2+a1x+ a0
b(x) = b3x3+b2x2+b1x+ b0
c(x) = a(x) ⊕ b(x) = c3x3+c2x2+c1x + c0

c0 = a0b0 ⊕ a3b1⊕ a2b2⊕ a1b3
c0 = a1b0 ⊕ a0b1⊕ a3b2⊕ a2b3
c0 = a2b0 ⊕ a1b1⊕ a0b2⊕ a3b3
c0 = a3b0 ⊕ a2b1⊕ a1b2⊕ a0b3

例：b(x)=01x2
  a(x)=03x3+01x2+01x+02
  c(x)=a(x) ⊕ b(x)

解：a3=03,a2=02,a1=01,a0=02

4.列混合

  列混合即是用一个常矩阵乘以第二步变换后的矩阵，以达到矩阵中每一个元素都是该元素原所在列所有元素的加权和。列混合的定义是：MixColumn(State)是将状态矩阵的每一列看成GF( 28 ) 上的一个多项式，且与一个固定的多项式c (x) = { 03 } x 3 + { 01 } x2 + { 01 } x + { 02 }相乘后模x4+1

  对于上面的矩阵，我们有b(0) = 02a0 +03a1+01a2+01a3，这里的02要转成“系数在GF(28)上的mod（x4+1）的乘法”，同理03和01也要转成“系数在GF(28)上的mod（x4+1）的乘法”，利用其中运算规则进行计算。

5.密钥加

三、AES算法的密钥编排算法

  密钥编排是指从种子密钥得到轮函数的过程，AES的密钥编排由密钥扩展和轮轮密钥选取两部分组成，其基本原则如下：
（1）轮密钥的总比特数等于轮数加1再乘分组长度，如128比特的明文经过10轮加密，总共需要（10+1）*128 = 1408比特的密钥。
（2）种子密钥被扩展成为扩展密钥。
（3）轮密钥从扩展密钥中取，其中第1轮轮密钥取扩展密钥的前Nb个字，第2轮轮密钥取接下来的Nb个字，以此类推。

1.当i=4，4%4=0时（128比特的时候是4个字，Nk=4）

2.当i=5，5%4≠0时（Nk=4）

四、AES的解密变换

AES解密运算是加密运算的逆运算，其中轮函数的逆为：
（1）ByteSub的逆变换由代换表的逆表做字节代换，也可通过如下两步实现: 首先进行仿射变换的逆变换，再求每一字节在GF(28)上逆元。
（2）行移位运算的逆变换是循环右移，位移量与左移时相同。
（3）列混合运算的逆运算是类似的，即每列都用一个特定的多项式d(x)相乘, d(x)满足
  （03x3+01x2+01x+02)*d(x)=01
由此可得
  d(x)=0Bx3+0Dx2+09x+0E
（4） 密钥加运算的逆运算是其自身。