| |
有关aes的一些理解
最近很多密码学的书都包含了最新的aes算法，但由于涉及的数学理论比较多，我也只是明白一些能让我实现他的皮毛。
aes比较牛的地方是速度快，而且明文和密钥的长度可以是128,196,256位，并且可以任意组合，明文和密钥的长度不一定是一样长的。由于采用了模块化设计，算法包含4个步骤：1.字节替换；2.行位移；3.列混淆；4.密钥加法，这些步骤循环10轮。最让我恶心的第10轮的又不一样，没有列混淆。
强烈建议大家看作者的英文论文和书，其中讲到了一种32位平台的快速实现方法。这种方法根据每一步的数学原理，将4步和为一步，那一大堆公式推倒我就不在这重复了。这种快速实现方法需要构造8个矩阵（加解密各四个），一般都叫他们tbox。加解密前九轮只需用u替换一下即可，最后一轮还是用sbox做替换，所以这速度是唰唰的快呀~
这样一来，实现aes的关键问题就是怎么构造8个矩阵u。其中涉及多项式即算问题。
（1）多项式加法
多项式加法即按位做异或运算。例如0x57 + 0x83 = 01010111 xor 10000011 = 11010100 = 0xd4。
（2）多项式乘法
gf(2n)中的乘法是多项式的模2乘积通过免去进位，再模一个次数为n的不可约多项式约化得到,不可约多项式我理解的和自然数域中的素数相对应，都是有不可再分解的特点。例如下面gf(23)的例子：
f(x)*g(x) = (x2+x)(x2+x+1) mod (x3+x+1)
= (x4+2x3+2x2+x) mod (x3+x+1) 系数是二的直接约掉，实际上这里是模2加法
= (x4+x) mod (x3+x+1)
= x2+1
rijindael选用8次不可约多项式x8+x4+x3+x+1，可用元组(100011011)或十六进制数0x11b表示。用这个多项式的理由听起来比较有意思，作者说是在一本书上有一堆8次不可约多项式，第一个是0x11b就用它了，ft吧。f(x)乘以x+1(或‘03’)的乘法分解成f(x)*2+1，最后模m(x)约化：
f ^= f << 1; //乘2加1
if(f & 0x100) f ^= 0x11b; //模m(x)约化
在gf(28)中的两个多项式f和h的乘法可通过用对数加速：设g(x)为gf(28)的一个生成多项式，所谓生成多项式就是数组的256个元素的值就是0-255的排列，则存在m和n使得f=gm，h=gn，则f*h=gm+x mod m(x)。有了这个公式我们就可以把多项式乘法转为加法来算，具体说来就是构造对数表和反对数表
对数表的构造：
1. 构造多项式g(x)=x+1的255个幂存入alog表中
alog[0] = 1;
for (i = 1; i < 256; i++)
{
j = (alog[i-1] << 1) ^ alog[i-1]; //x*3=x*2+1
if ((j & 0x100) != 0) // 如果超过255，需要约化
j ^= root;
alog[i] = j;
}
2. 在log表中存放对底g(x)的对数
for (i = 1; i < 255; i++)
log[alog[i]] = i;
再构造alog和log之后，乘法运算可以一步完成alog[ (log[a]+log[b]) % 255 ] 。
实际上实现多项式乘法的方法有很多种，在msdn搜aes可以查到一篇写c#实现的，它的乘法算法也是一种很经典的方法。用对数表的方法好理解，最重要的是查表速度快。
s盒和反向s盒的实现
(1) 初始化s盒，按升序排列的字节表示 gf(28)的所有数，0至255。
(2) 用alog[255-log[x]]，把s盒中每个字节映射为它在gf(28)中的逆。0被映射为0。
(3) 计算那个仿射变换，那个公式很恶心，参看作者的文献。其中的矩阵乘法，可以利用前面des的技巧，把s盒的每个字节按位分离存放在一个256*8的临时矩阵中再计算乘法。
解密用的逆s盒可以用insbox[sbox[i] & 0xff] = i得到。
tbox的构造
for (t = 0; t < 256; t++)
{
s = sbox[t];
tbox1[t] = mul4(s, g[0]);
tbox2[t] = mul4(s, g[1]);
tbox3[t] = mul4(s, g[2]);
tbox4[t] = mul4(s, g[3]);
s = insbox[t];
tbox5[t] = mul4(s, ig[0]);
tbox6[t] = mul4(s, ig[1]);
tbox7[t] = mul4(s, ig[2]);
tbox8[t] = mul4(s, ig[3]);
}
g矩阵可以在文献中查到，ig是g在gf(28)的逆。
在加解密过程中，加密用tbox1-4，解密用tbox5-8，前9轮用t，最后一轮用sbox。但是要注意调用顺序，为了实现列混淆，具体顺序参看那个列混淆的公式。
|
|
