AES内部加密原理

0x01 AES概述

高级加密标准（Advanced Encryption Standard，缩写：AES），在密码学中又称Rijndael加密法，是美国联邦*采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPS PUB 197，并在2002年5月26日成为有效的标准。2006年，高级加密标准已然成为对称**加密中最流行的算法之一。

在这里需要指出的一点就是秘钥长度为128bit的Rijndael加密法被称为标准AES，说起AES，我们一般认为它的的秘钥长度为128bit。

AES要加密的明文数据必须为128bit，不足的会填充。秘钥长度为128bit、192bit、256bit。AES加密包含很多轮的操作，每轮又包含四层（最后一轮只有三层）。

AES输入输出参数

Key length (秘钥长度)	Number of rounds (轮数)	Number of key（子秘钥个数）
128bit	10	11
192bit	12	13
256bit	14	15

0x02内部结构

• Byte Substitution layer （字节替换层）
• Diffusion layer （混淆层）
  • ShiftRows Sublayer （行移位子层）
  • MixColumn Sublayer （列混合子层）
• Key Addition layer （子秘钥相加层）

为了理解数据在AES中是如何移动的，我们假设这样一个state（状态矩阵）：

将128bit的明文数据想象为一个4*4的矩阵，矩阵中A0~A15是16个字节。

Byte Substitution layer （字节替换层）

该层包含有一个S-Boxes ，它有三个特点：

1. 唯一且非线性
2. 双射的（唯一可逆）
3. 任何输入值都不等于输出值

这层软硬件实现都很简单，查表替换即可。

例如：输入值Ai=(C2)hex经过S-Box字节替换得到输出值（25）hex

S((C2)hex)=(25)hex

Diffusion layer （扩散层）

不像S-Box，混淆层表现一种线性操作，

DIFF(A) + DIFF(B) = DIFF(A + B)

该层包含两个子层：

• ShiftRows Sublayer （行移位子层）：在一个字节层上置换数据
• MixColumn Sublayer （列混合子层）：结合（混合）四个字节块的矩阵操作

ShiftRows Sublayer （行移位子层）

查找替换表

输入矩阵：

输出矩阵：

注意：这里的shift是循环左移。

MixColumn Sublayer （列混合子层）

• 混合状态矩阵（state）每一列的线性操作

• 主扩散元素

• 每4字节一列乘以一个4*4混合矩阵，如：
  
  这里01、02、03是十六进制表示法。

• 所有的运算都是在GF(2^8)上进行。

系数在GF(2^8)上的多项式

•在AES的列混合操作中，将4个字节构成的向量看成系数在GF(28)上的次数小于4的多项式 。

• 多项式的加法：

  就是对应系数相加；换句话说，多项式的加法就是4字节向量的逐比特异或

• 多项式的乘法 ：

  必须要取模m(x)=$x^4$x4+1，这样使得次数小于4的多项式的乘积仍然是一个次数小于4的多项式

将多项式的模m(x)=$x^4$x4+1乘运算记为⊗，设

a(x)= $a_3x^3$a3​x3+$a_2x^2$a2​x2+$a_1x$a1​x+$a_0$a0​

b(x)= $b_3x^3$b3​x3+$b_2x^2$b2​x2+$b_1x$b1​x+$b_0$b0​

记

c(x)= a(x)⊗b(x)=$c_3x^3$c3​x3+$c_2x^2$c2​x2+$c_1x$c1​x+$c_0$c0​(mod$x^4$x4 +1)

由于$x^j$xj mod ($x^4$x4+1)=$x^{j mod 4}$xjmod4(j > 4)，所以

即：

$c_0$c0​=$a_0b_0$a0​b0​⊕$a_3b_1$a3​b1​⊕$a_2b_2$a2​b2​⊕$a_1b_3$a1​b3​

$c_1$c1​= $a_1b_0$a1​b0​⊕$a_0b_1$a0​b1​⊕$a_3b_2$a3​b2​⊕$a_2b_3$a2​b3​

$c_2$c2​= $a_2b_0$a2​b0​⊕$a_1b_1$a1​b1​⊕$a_0b_2$a0​b2​⊕$a_3b_3$a3​b3​

$c_3$c3​= $a_3b_0$a3​b0​⊕$a_2b_1$a2​b1​⊕$a_1b_2$a1​b2​⊕$a_0b_3$a0​b3​

列混合的数学本质

将状态矩阵的每列视为系数在GF($2^8$28)上的一元三次多项式，再与一个固定的系数在GF($2^8$28)上的一元三次多项式a(x)进行模$x^4$x4+1乘法

​ a(x) = $03x^3$03x3+$01x^2$01x2+$01x$01x+02

a(x)是模$x^4$x4+1可逆的多项式（即a(x)是与$x^4$x4+1互素的），否则列混合变换就是不可逆的。

举例：

B=（25,25,…,25）

在GF($2^8$28)上只需要计算02•25和03•25，

$25_{hex}$25hex​化为多项式为$x^5$x5+$x^2$x2+1

所以：

02•25=x•($x^5$x5+$x^2$x2+1)=$x^6$x6+$x^3$x3+$x^1$x1

03•25=(x+1)•($x^5$x5+$x^2$x2+1)=$x^6$x6+$x^5$x5+$x^3$x3+$x^2$x2+$x^1$x1+1

01•25 = $x^5$x5+ $x^2$x2 +1

01•25 = $x^5$x5+ $x^2$x2 +1

02•25 =$x^6$x6+ $x^3$x3 +$x^1$x1

03•25 =$x^6$x6+$x^5$x5 +$x^3$x3+$x^2$x2+$x^1$x1+1

$C_i$Ci​ = $x^5$x5 +$x^2$x2 +1

所以输出的tate是C=(25,25,…,25)

xtime()运算

xtime()运算用于快速计算在GF($2^8$28)的乘法运算。

例如：0x57 • 0x13

0x57=${(01010111)}_2$(01010111)2​=$x^6$x6+$x^4$x4+$x^2$x2+x+1

0x13=${(00010011)}_2$(00010011)2​=$x^4$x4+x+1

使用xtime()运算求上式：

xtime(0x57)：01010111 (最高位为0，直接左移，低位补0) 得到x•0x57=1010 1110

10101110 (最高位为1，左移后与0x1B异或) 得到$x^2$x2•0x57=0100 0111

01000111 (最高位为0，直接左移，低位补0) 得到$x^3$x3•0x57=1000 1110

10001110 (最高位为1，左移后与0x1B异或) 得到$x^4$x4•0x57=0000 0111

所以：

0x57•0x13=0x57•($x^4$x4+x+1)
=${(0000 0111)}_2$(00000111)2​+${(1010 1110)}_2$(10101110)2​+${(01010111)}_2$(01010111)2​
=${(1111 0110)}_2$(11110110)2​
=$x^7$x7+$x^6$x6+$x^5$x5+$x^4$x4+$x^2$x2+x