Then Notes 隨筆

Galois Field 有限體

Introduction

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

加法、減法

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

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

f(x)=x6+x4+x2+x+1f(x) = x^6 + x^4 + x^2 + x + 1

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

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

f(x)+g(x)=(x6+x4+x2+x+1)+(x7+x+1)=(x7+x6+x4+x2)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)(10000011)=(11010100)(01010111) \oplus (10000011) = (11010100)

乘法

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

m(x)=x8+x4+x3+x+1m(x) = x^8 + x^4 + x^3 + x + 1

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

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

x8modm(x)=[m(x)x8]=x4+x3+x+1x^8 \bmod m(x) = [m(x) - x^8] = x^4 + x^3 + x + 1

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

f(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0f(x) = b_7x^7 + b_6x^6 + b_5x^5 + b_4x^4 + b_3x^3 + b_2x^2 + b_1x + b_0

將它乘以 xx 後會得出:

x×f(x)=(b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x)modm(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)

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

x×f(x)=(b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x)+(x4+x3+x+1)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)

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

x×f(x)={(b6b5b4b3b2b1b00),if b7=0(b6b5b4b3b2b1b00)(00011011),if b7=1x \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)))));
}

參考資料