# Introduction
數學中,有限體 (Finite Field) 或伽羅瓦體 (Galois Field),是指包含有限個元素的「體」(field 也有人譯為「域」)。在密碼學裡面,常常會出現基於有限體 GF(2n) 觀念的計算。
# 加法、減法
在 GF(2n) 中,加法與減法其實就是 xor (互斥或) 運算,因為在 mod 2 下,加法與減法是等價的:
- 1 + 1 = 1 - 1 = 0
- 1 + 0 = 1 - 0 = 1
- 0 + 1 = 0 - 1 = 1
例如,考慮有限體 GF(28) 中的兩個多項式:
f(x)=x6+x4+x2+x+1
g(x)=x7+x+1
試求 f(x)+g(x)
f(x)+g(x)=(x6+x4+x2+x+1)+(x7+x+1)=(x7+x6+x4+x2)
用二進位運算來表示的話,則為:
(01010111)⊕(10000011)=(11010100)
# 乘法
在 GF(2n) 裡,乘法可以用一些特殊技巧來運算,這裡以 AES 加密運用到的
m(x)=x8+x4+x3+x+1
為多項式的有限體 GF(28) 來舉例,此類計算技巧可以推廣到其他有限體 GF(2n) 中。
首先,我們要瞭解以下等式是成立的:
x8modm(x)=[m(x)−x8]=x4+x3+x+1
現在我們考慮有限體 GF(28) 中的多項式:
f(x)=b7x7+b6x6+b5x5+b4x4+b3x3+b2x2+b1x+b0
將它乘以 x 後會得出:
x×f(x)=(b7x8+b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x)modm(x)
這裡我們會發現,如果 b7=0,那麼乘出來的結果必定是一個次數小於 8 的多項式,就不用再特別計算;但若 b7=1,則可以透過下式做 mod m(x) 的運算:
x×f(x)=(b6x7+b5x6+b4x5+b3x4+b2x3+b1x2+b0x)+(x4+x3+x+1)
於是,乘以 x (即 00000010) 的運算,是可以透過向左 shift 一個 bit 後,視條件是否需要再 xor 00011011(即 x4+x3+x+1)
x×f(x)=⎩⎨⎧(b6b5b4b3b2b1b00),(b6b5b4b3b2b1b00)⊕(00011011),if b7=0if b7=1
# 乘法實作程式
推導出上式後,我們便可以重複使用它來藉此實現更高次方的乘法!
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)))));
}
# 參考資料