AES算法的数学基础
1．GF(2)域上的多项式
在有限域GF(28)中的元素操作运算可采用几种不同的方法来表示，AES算法主要选择传统的多项式表示法进行的。因为不同的表示对GF（28）的运算复杂度是有影响的。
一个由b7b6b5b4b3b2b1b0组成的字节b可表示成系数为[0, 1]的二进制多项式
b7x7 + b6x6 + b5x5 + b4x4 + b3x3 + b2x2 + b1x1 + b0
例如：十六进制数“6B”对应的二进数为01101011，作为一个字节对应于多项式为：
x6 + x5 + x3 + x + 1
1．1．多项式加法
在GF（28）上的加法定义为二进制多项式的加法，其系数满足模2加（即异或）。例如：“6B”和“71”的和为：6B + 71 = 1A，或采用多项式记法:
(x6 + x5 + x3 + x + 1) + (x6 + x5 + x4 +1) = x4 + x3 + x
显然，多项式加法与以字节为单位的比特异或结果是一致的。
1．2．多项式的乘法
在GF（28）上的乘法（用符节“.”表示）定义为二进制多项式的乘积以8次不可约多项式为模的积，此8次不可约多项式为：
m(x) = x8 + x4 + x3 + x + 1
十六进制为“11B”，二进制表示为100011011，此乘法在GF（28）上满足结合律，且有一个本原元（“01”），例如：
（x6 + x5 + x3 + x + 1）·（x6 + x5 + x4 + 1）
= x12 + x8 + x6 + x5 + x4 + x + 1(mod m(x))
= x7 + x6 + x + 1
或者：6B·71 = C3
显而易见，模的结果是一个低于8阶的多项式，与加法不同的是，乘法并不是在字节上的简单运算。
1．3．函数xtime()
函数xtime()定义为GF（28）上的x·b(x)，若b7 = 0，则字节b左移一位；若b7 = 1，则字节b左移一位，再异或“1B”。
设b（x）为GF（28）域中次数小于8的多项式，由欧几里德扩充算法知，存在a(x)和c(x)，满足：
a(x)b(x) + c(x)m(x) = 1 ( 2 – 1 )
因此有： a(x)b(x)mod m(x) = 1 ( 2 – 2 )
或： a(x)b(x) = 1 mod(m(x)) ( 2 – 3 )
由此，我们可以获得b(x)的逆元：b-1(x) = a(x) mod m(x)
假设：b(x) = b7x7 + b6x6 + x5b5 + b4x4 + b3x3 + b2x2 + b1x1 + b0
若把b(x)乘上x，得到：x·b(x) = b7x8+ b6x7 + x5b6 + b4x5 + b3x4 + b2x3 + b1x2 + b0x
相乘的结果再与m(x)相模的结果有如下规律性：
若b7 = 0， 则(b(x)·x) mod m(x) = b(x) · x
若b7 = 0， 则(b(x)·x) mod m(x) = (b(x)·x) ⊕m(x)
由此，(b(x)·x) mod m(x)可以被认为是先进行字节的左移操作，根据移位结果对该字节与“1B”(m(x))进行条件异或运算不了。 这种类型的操作记为：b = xtime()。
例如：计算63·17 = 58
计算步骤如下：
63·17 = 63·（01 + 02 + 04 + 10）= 63·01 + 63·02 + 63 ·04 + 63·10
63·01 = xtime(63) = C6；（01100011， b7=0， 左移一位）
63·02 = xtime(C6) = 97；（11000110，b7=1，左移一位，异或1B）
63·04 = xtime(97) = 35；（10010111，b7=1，左移一位，异或1B）
63·10 = xtime(35) = 6A；(00110101，b7=0，左移一位)
所以，63·17 = 63·01 + 63·02 + 63 ·04 + 63·10
= 63 + C6 + 97 + 6A
=58
这样，通过分解可将复杂的相乘操作转化为简单的移位和异或操作。
2．GF（28）域上的多项式
在有限域GF（28）上的多项式系统定义为取自GF（28）元素的多项式，则一个4字节的字对应于一个次数小于4的多项式。
2．1．加法运算
GF（28）上的多项式的加法定义为对应项系数相加，即两个带有系数的多项式之各等于相应系数之和的多项式，在GF（28）上的和运算等于异或运算。
2．2．乘法运算
带有系数的多项式相乘与不带系数的多项式相乘相比，稍为复杂一些。设在GF（28）上有两个多项式：
a(x) = a3x3 + a2x2 + a1x + a0
b(x) = b3x3 + b2x2+ b1x + b0
两者关于模x4+1的乘积为：c(x) = a(x) ⊕ b(x) = c3x3 + c2x2 + c1x + c0
其中系数由下面4个式子得到：
c0 = a0b0⊕a3b1⊕a2b2⊕a1b3
c1 = a1b0⊕a0b1⊕a3b2⊕a2b3
c2 = a2b0⊕a1b1⊕a0b2⊕a3b3
c3 = a3b0⊕a2b1⊕a1a2⊕a0b3
很显然，一个固定多项式a(x)与多项式b(x)相乘所构成的运算可以用矩阵乘法表述：
c0 a0 a3 a2 a1 b0
c1 a1 a0 a3 a2 b1
c2 = a2 a1 a0 a3 b2
c3 a3 a2 a1 a0 b3
其中的矩阵是一个循环矩阵。应当注意，M(x) = x4 + 1 不是GF(28)上的不可约多项式（也不是GF（2）上的不可约多项式），因为x4 + 1 = (x +1)(x3 + x2 + x +1)。所以，被一个固定多项式相乘的乘法不一定是可逆的。在AES算法中，乘法算法只限于乘一个固定的有逆元的多项式a3x3 +b2x2 +b1x + b0才能进行乘法，从而保证乘法的可逆性。
2 分组密码的设计原则
分组密码的设计就是找到一种算法，能在密钥的控控制下从一个足够大且足够好的置换子集中简单而迅速的选出一个置换，用来对当前输入的明文进行加密交换。一般地，分组密码的设计准则包括安全性准则和实现性准则两种。前者主要研究如何设计安全算法，分组长度和密钥长度，后者主要讨论如何提高算法的执行速度。
2.1 安全性原则
关于实用密码的两个一般的设计原则是Shannon提出混乱原则和扩散原则。
1．混乱原则：人们所设计的密码应使得密钥和明文以及密文之间的信赖关系相当复杂以至于这种信赖性对密码分析者来说是无法利用。
2．扩散原则：人们所设计密码应使得密钥的每一位数字影响密文的多位数字以防止对密钥进行逐段破译，而且明文的每一位数字也影响密文的多位数字以便隐藏明文数字的统计性性。
影响现代分组密码安全性的因素很多，主要取决于密码算法、分组长度和密钥长度，相应的安全性设计准则也包括三类：
1． 密码算法的设计准则
1) 算法可以公开：密码体制的安全性应当仅依赖于对密钥的保密，而不应基于对算法的保密，这既是数据加密算法标准化所必需要求的，同时也是网络保密通信赖以生存的基础。
2) 混乱原则：密码算法应当保证密钥，明文和密文的依赖关系相当复杂，以至于这种依赖性对密码分析者来说使无法利用的。
3) 扩散原则：人们所设计的密码应使得密钥的每一位数字影响密文的许多位数字，以便隐藏明文数字的统计特性。
4) 能抵抗差分分析和线性分析：为使密码算法能抵抗差分分析，通常选取具有“本原转移概率矩阵”的markov 型密码，通过对一个“弱”密钥函数进行多次迭代，而得到一个“强密码”，为使密码算法抵抗线性分析，通常要求算法中包含高度非线性密码函数。
5) 没有弱密钥：当弱密钥或半弱密钥的个数较少时，它们对体制本身的安全性影响不在，在算法设计中稍作处理就可避免，而且随即选取一个密钥是弱密钥的概率随密钥空间的增大而趋于0。
2． 密钥长度的设计准则
为使密码算法能抵抗对密钥强力攻击，必须保证密钥长度尽可能大，比如，
在近几年来新出现的各种算法，密钥长度都已经要求至少128bits。
3． 分组密码长度
为阻止对分组密码进行统计分析，分组长度必须足够大，由于分组密码是一种简单代换密码，而明文有一定的多余度，因此理论上可以对密文进行频率统计分析。当分组长度很大时，这种分析需要大量的密文数据，使得计算上不可行。
此外还有一个重要的设计原理：密码体制必须能抵抗现有的所有攻击方法。
2.2 实现准则
分组密码可以用软件和硬件来实现。硬件实现的优点是可获得高速率，而软件实现的优点是灵活性强、代价低。
软件实现的设计原则是加密和解密过程区别应该在密钥的使用方式不同，以便同样的器件既可用来加密，又可以用来解密。尽量使用规则结构，因为密码应有一个标准的组件结构，以便能适应于用超大规模集成电路实现。
3.AES基于java的算法的具体实现
3.1 AES算法的整体结构
3.2 AES算法描述与实现
3.2.1 状态矩阵、密钥、轮数
1．描述
AES算法是一个分组长度和密钥长度都可变的迭代加密算法，分组长度和密钥长度分可以128bits、192bits、256bits。在加密过程中，每个数据分组都要进行多次变换操作，每次操后的中间结果称为状态（State），它可以用一个4行、Nb（Nb的值等于数据块长度除以32）列的矩阵来表示状态，矩阵中的每一个元素为一个字节。AES加解密时，先将a0,a1,a2…a15复制到状态数组；加密过程都对这个状态进行技术处理；等待加解密过程处理结束，再将状态数组复制到b0,b1, b2…b15。最后得到加解密的输出结果。操作映射过程如下：
其中密钥的设计类似二维字节数组，共4行，Nk列，且Nk等于密钥长度除32，如表5-8所示，AES使用了轮变换，算法变换的轮数Nr由Nb和Nk共同决定，具体如下表所示：
Nr取决于Nb和Nk变化
|
Nr
|
Nb = 4
|
Nb = 6
|
Nb = 8
|
|
Nk=4
|
10
|
12
|
14
|
|
Nk=6
|
12
|
12
|
14
|
|
Nk=8
|
14
|
14
|
14
|
2．在java中实现得到算法变换的轮数Nr的代码如下：
/**
* 这个方法是用来得到加密轮数
* @param Nb以32bit为单位的待加密明文的长度
* @param Nk是初始密钥的长度
* @return 返回加密轮数（Nr）
*/
public int GetRounds(int Nb, int Nk) {
switch (Nb) {
case 4:
switch (Nk) {
case 4:
return 10;
case 6:
return 12;
case 8:
return 14;
default:
return 0;
}
case 6:
switch (Nk) {
case 4:
case 6:
return 12;
case 8:
return 14;
default:
return 0;
}
case 8:
switch (Nk) {
case 4:
case 6:
case 8:
return 14;
default:
return 0;
}
default:
return 0;
}
