最近需要細節看一下AES演算法的底層設計，S盒不能只通過查表來實現了。
隨便在中文世界裡面搜尋了下S盒的生成，發現講得真是非常複雜，大多數也都是用C/C++程式碼來實現的，直接看程式碼也無法很快get到點。最後發現還是去看維基最為清楚。
GF(28)有限域
簡單回顧一下以前的知識。
AES中使用的有限域可以有以下幾個步驟來生成：
- 首先有GF(p)形成的有限域（p要求是素數）。
- 有係數為GF(p)中元素的的多項式環GF(p)[X] 。
- 有其對於某不可約多項式 P生成的雙邊理想的商環 GF(p)[X]/P 。
- 這個商環又是有限域了。
在這個過程中，選取合適的多項式P=x8+x4+x3+x+1，使得商環中的元素（也是多項式）最大order是7，p取2 （係數就只能是0或者1了）。
這樣，就可以用8-bit的位元組來進行表示了，即常見表示GF(28)。
此後所有AES中操作的最小單位就是這個位元組（多項式）了。
各種運算
這樣就比較好理解，為什麼初學AES時，裡面的加減乘除操作，有些實現得不可思議地簡單，有些又實現得很奇怪。
- 加減操作（ +/−），由於繼承了GF(2)的特性，實現起來都是按位異或。
- 乘法操作（×），由於涉及到了商環，因此會進行多項式模，所以就會需要在特定條件下異或一個常數。
另外在生成S盒的時候，還會有冪次和取逆。
- 冪次（gn），可以簡單利用快速冪實現。
- 取乘法逆元（g−1），有g×g254=g255=1，得到g×g254=1。如此一來，乘法逆元也可以用冪次的方法得到。（快速冪的實現也使得在不特別考慮效能的情況下夠用了）
S盒的具體生成
簡單來說，S盒的變換是一個仿射變換和取乘法逆元的疊加。其中仿射變換可以寫為元素的多個迴圈移位的異或。
對於正向的S盒，是先求逆，再進行變換。
s=b⊕(b⋘1)⊕(b⋘2)⊕(b⋘3)⊕(b⋘4)⊕6316
對於逆向的S盒，是先變換，再求逆。
b=(s⋘1)⊕(s⋘3)⊕(s⋘6)⊕516
其中，b=s−1。
實現
然後就是簡單實現了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #lang rosette/safe
;; Element datatype
(define u8? (bitvector 8))
(define (u8 i) (bv i 8))
;; Field Operations
(define (gf+ a b)
(bvxor a b))
(define (gf* a b)
(define (iter a b p)
(if (or (bvzero? a) (bvzero? b)) p
(let ([p_ (if (bvzero? (lsb b)) p
(bvxor a p))]
[a_ (if (bvzero? (msb a))
(bvshl a one)
(bvxor (u8 #x1b)
(bvshl a one)))]
[b_ (bvlshr b one)])
(iter a_ b_ p_))))
(iter a b zero))
(define (gf^n a n)
(define (iter acc a n)
(cond [(bvzero? n) acc]
[(bvzero? (lsb n)) (iter acc (gf* a a) (bvlshr n one))]
[else (iter (gf* acc a) (gf* a a) (bvlshr n one))]))
(iter one a n))
(define (gf^-1 a)
(gf^n a (u8 254)))
;; Sbox
(define (affine q l)
(foldl bvxor zero
(map (lambda (x) (bvrol q (u8 x))) l)))
(define (sbox i)
(let [(b (gf^-1 i))]
(bvxor (affine b '(0 1 2 3 4)) (u8 #x63))))
(define (sbox^-1 i)
(let [(s (bvxor (affine i '(1 3 6)) (u8 #x05)))]
(gf^-1 s)))
|