megrxu

AES S 盒的生成

Mar 23, 2021  「Cryptography」  

最近需要細節看一下 AES 演算法的底層設計,S 盒不能只通過查表來實現了。

隨便在中文世界裡面搜尋了下 S 盒的生成,發現講得真是非常複雜,大多數也都是用 C/C++ 程式碼來實現的,直接看程式碼也無法很快 get 到點。最後發現還是去看維基最為清楚。

$\mathrm{GF}(2^8)$ 有限域

簡單回顧一下以前的知識。 AES 中使用的有限域可以有以下幾個步驟來生成:

  • 首先有 $\mathrm{GF}(p)$ 形成的有限域($p$ 要求是素數)。
  • 有係數為 $\mathrm{GF}(p)$ 中元素的的多項式環 $\mathrm{GF}(p)[X]$ 。
  • 有其對於某不可約多項式 $P$ 生成的雙邊理想商環 $\mathrm{GF}(p)[X]/P$ 。
  • 這個商環又是有限域了。

在這個過程中,選取合適的多項式 $P = x^8 + x^4 + x^3 + x + 1$,使得商環中的元素(也是多項式)最大 order 是 7,$p$ 取 2 (係數就只能是 0 或者 1 了)。

這樣,就可以用 8-bit 的位元組來進行表示了,即常見表示 $\mathrm{GF}(2^8)$。 此後所有 AES 中操作的最小單位就是這個位元組(多項式)了。

各種運算

這樣就比較好理解,為什麼初學 AES 時,裡面的加減乘除操作,有些實現得不可思議地簡單,有些又實現得很奇怪。

  • 加減操作( $+/-$),由於繼承了 $\mathrm{GF}(2)$ 的特性,實現起來都是按位異或。
  • 乘法操作($\times$),由於涉及到了商環,因此會進行多項式模,所以就會需要在特定條件下異或一個常數。

另外在生成 S 盒的時候,還會有冪次和取逆。

  • 冪次($g^n$),可以簡單利用快速冪實現。
  • 取乘法逆元($g^{-1}$),有 $g \times g^{254} = g^{255} = 1$,得到 $g \times g^{254} = 1$。如此一來,乘法逆元也可以用冪次的方法得到。(快速冪的實現也使得在不特別考慮效能的情況下夠用了)

S 盒的具體生成

簡單來說,S 盒的變換是一個仿射變換和取乘法逆元的疊加。其中仿射變換可以寫為元素的多個迴圈移位的異或。

對於正向的 S 盒,是先求逆,再進行變換。

$$ s=b\oplus (b\lll 1)\oplus (b\lll 2)\oplus (b\lll 3)\oplus (b\lll 4)\oplus 63_{16} $$

對於逆向的 S 盒,是先變換,再求逆。

$$ b=(s\lll 1)\oplus (s\lll 3)\oplus (s\lll 6)\oplus 5_{16} $$

其中,$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)))