數學中,有限體 (Finite Field) 或伽羅瓦體 (Galois Field),是指包含有限個元素的「體」(field 也有人譯為「域」)。在密碼學裡面,常常會出現基於有限體 $GF(2^n)$ 觀念的計算。

加法、減法

在 $GF(2^n)$ 中,加法與減法其實就是 $\text{xor}$ (互斥或) 運算,因為在 $\bmod 2$ 下,加法與減法是等價的:

  • 1 + 1 = 1 - 1 = 0
  • 1 + 0 = 1 - 0 = 1
  • 0 + 1 = 0 - 1 = 1

例如,考慮有限體 $GF(2^8)$ 中的兩個多項式:

$$ f(x) = x^6 + x^4 + x^2 + x + 1 $$

$$ g(x) = x^7 + x + 1 $$

試求 $f(x) + g(x)$

$$ f(x) + g(x) = (x^6 + x^4 + x^2 + x + 1) + (x^7 + x + 1) = (x^7 + x^6 + x^4 + x^2) $$

用二進位運算來表示的話,則為:

$$ (01010111) \oplus (10000011) = (11010100) $$

乘法

在 $GF(2^n)$ 裡,乘法可以用一些特殊技巧來運算,這裡以 AES 加密運用到的

$$ m(x) = x^8 + x^4 + x^3 + x + 1 $$

為多項式的有限體 $GF(2^8)$ 來舉例,此類計算技巧可以推廣到其他有限體 $GF(2^n)$ 中。

首先,我們要瞭解以下等式是成立的:

$$ x^8 \bmod m(x) = [m(x) - x^8] = x^4 + x^3 + x + 1 $$

現在我們考慮有限體 $GF(2^8)$ 中的多項式:

$$ f(x) = b_7x^7 + b_6x^6 + b_5x^5 + b_4x^4 + b_3x^3 + b_2x^2 + b_1x + b_0 $$

將它乘以 $x$ 後會得出:

$$ x \times f(x) = (b_7x^8 + b_6x^7 + b_5x^6 + b_4x^5 + b_3x^4 + b_2x^3 + b_1x^2 + b_0x) \bmod m(x) $$

這裡我們會發現,如果 $b_7 = 0$,那麼乘出來的結果必定是一個次數小於 8 的多項式,就不用再特別計算;但若 $b_7 = 1$,則可以透過下式做 $\bmod m(x)$ 的運算:

$$ x \times f(x) = (b_6x^7 + b_5x^6 + b_4x^5 + b_3x^4 + b_2x^3 + b_1x^2 + b_0x) + (x^4 + x^3 + x + 1) $$

於是,乘以 $x$ (即 $00000010$) 的運算,是可以透過向左 shift 一個 bit 後,視條件是否需要再 $\text{xor } 00011011$(即 $x^4 + x^3 + x + 1$)

$$ x \times f(x) = \begin{cases} (b_6b_5b_4b_3b_2b_1b_00), & \text{if } b_7 = 0 \\ (b_6b_5b_4b_3b_2b_1b_00) \oplus (00011011), & \text{if } b_7 = 1 \end{cases} $$

乘法實作程式

推導出上式後,我們便可以重複使用它來藉此實現更高次方的乘法!

static uint8_t xtime(uint8_t x)
{
  return ((x << 1) ^ ((x >> 7) * 0x1b));
  // (x >> 7) => b7
  // 0x1b => 00011011
}

static uint8_t multiply(uint8_t x, uint8_t y)
{
  return (((y & 1) * x) ^
    ((y>>1 & 1) * xtime(x)) ^
    ((y>>2 & 1) * xtime(xtime(x))) ^
    ((y>>3 & 1) * xtime(xtime(xtime(x)))));
}

參考資料