有关AES的一些理解
最近很多密码学的书都包含了最新的AES算法但由于涉及的数学理论比较多我也只是明白一些能让我实现他的皮毛
AES比较牛的地方是速度快而且明文和密钥的长度可以是位并且可以任意组合明文和密钥的长度不一定是一样长的由于采用了模块化设计算法包含个步骤字节替换行位移列混淆密钥加法这些步骤循环轮最让我恶心的第轮的又不一样没有列混淆
强烈建议大家看作者的英文论文和书其中讲到了一种位平台的快速实现方法这种方法根据每一步的数学原理将步和为一步那一大堆公式推倒我就不在这重复了这种快速实现方法需要构造个矩阵（加解密各四个）一般都叫他们Tbox加解密前九轮只需用U替换一下即可最后一轮还是用Sbox做替换所以这速度是唰唰的快呀~
这样一来实现AES的关键问题就是怎么构造个矩阵U其中涉及多项式即算问题
（）多项式加法
多项式加法即按位做异或运算例如x + x = XOR = = xD
（）多项式乘法
GF(n)中的乘法是多项式的模乘积通过免去进位再模一个次数为n的不可约多项式约化得到不可约多项式我理解的和自然数域中的素数相对应都是有不可再分解的特点例如下面GF()的例子
f(x)*g(x) = (x+x)(x+x+) mod (x+x+)
= (x+x+x+x) mod (x+x+)系数是二的直接约掉实际上这里是模加法
= (x+x) mod (x+x+)
= x+
Rijindael选用次不可约多项式x+x+x+x+可用元组()或十六进制数xB表示用这个多项式的理由听起来比较有意思作者说是在一本书上有一堆次不可约多项式第一个是xB就用它了FT吧f(x)乘以x+(或)的乘法分解成f(x)*+最后模m(x)约化
f ^= f << ;//乘加
if(f & x) f ^= xB; //模m(x)约化
在GF()中的两个多项式f和h的乘法可通过用对数加速设g(x)为GF()的一个生成多项式所谓生成多项式就是数组的个元素的值就是的排列则存在m和n使得f=gmh=gn则f*h=gm+x mod m(x)有了这个公式我们就可以把多项式乘法转为加法来算具体说来就是构造对数表和反对数表
对数表的构造
构造多项式g(x)=x+的个幂存入alog表中
alog[] = ;
for (i = ; i < ; i++)
{
j = (alog[i] << ) ^ alog[i];//x*=x*+
if ((j & x) != )// 如果超过需要约化
j ^= ROOT;
alog[i] = j;
}
在log表中存放对底g(x)的对数
for (i = ; i < ; i++)
log[alog[i]] = i;
再构造alog和log之后乘法运算可以一步完成alog[ (log[a]+log) % ]
实际上实现多项式乘法的方法有很多种在msdn搜AES可以查到一篇写c#实现的它的乘法算法也是一种很经典的方法用对数表的方法好理解最重要的是查表速度快
S盒和反向S盒的实现
() 初始化S盒按升序排列的字节表示 GF()的所有数至
() 用alog[log[x]]把S盒中每个字节映射为它在GF()中的逆被映射为
() 计算那个仿射变换那个公式很恶心参看作者的文献其中的矩阵乘法可以利用前面DES的技巧把S盒的每个字节按位分离存放在一个*的临时矩阵中再计算乘法
解密用的逆S盒可以用inSbox[Sbox[i] & xFF] = i得到
Tbox的构造
for (t = ; t < ; t++)
{
s = Sbox[t];
Tbox[t] = mul(s G[]);
Tbox[t] = mul(s G[]);
Tbox[t] = mul(s G[]);
Tbox[t] = mul(s G[]);
s = inSbox[t];
Tbox[t] = mul(s iG[]);
Tbox[t] = mul(s iG[]);
Tbox[t] = mul(s iG[]);
Tbox[t] = mul(s iG[]);
}
G矩阵可以在文献中查到iG是G在GF()的逆
在加解密过程中加密用Tbox解密用Tbox前轮用T最后一轮用Sbox但是要注意调用顺序为了实现列混淆具体顺序参看那个列混淆的公式
