有關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+
可用元組(
)或十六進制數
x
B表示
用這個多項式的理由聽起來比較有意思
作者說是在一本書上有一堆
次不可約多項式
第一個是
x
B就用它了
FT吧
f(x)乘以x+
(或
)的乘法分解成f(x)*
+
最後模m(x)約化
f ^= f <<
; //乘
加
if(f &
x
) f ^=
x
B; //模m(x)約化
在GF(
)中的兩個多項式f和h的乘法可通過用對數加速
設g(x)為GF(
)的一個生成多項式
所謂生成多項式就是數組的
個元素的值就是
的排列
則存在m和n使得f=gm
h=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[b]) %
]
實際上實現多項式乘法的方法有很多種
在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
但是要注意調用順序
為了實現列混淆
具體順序參看那個列混淆的公式
From:http://tw.wingwit.com/Article/program/Java/Javascript/201311/25421.html
