密码学中的数学基础2 伽罗华域(Galois Field)上的四则运算
1)域的概念
參考《密碼編碼學(xué)與網(wǎng)絡(luò)安全》這書的有限域一章。形象地說,域有這樣一個性質(zhì):在加法和乘法上具有封閉性。也就是說對域中的元素進(jìn)行加法或乘法運(yùn)算后的結(jié)果仍然是域中的元素。有一點(diǎn)要注意,域里面的乘法和加法不一定是我們平常使用的乘法和加法。可以把C語言中的與運(yùn)算和異或運(yùn)算分別定義成加法和乘法。但習(xí)慣上,仍然使用符號+ 和 * 表示加法和乘法運(yùn)算。
2)域中單位元和逆元兩個概念
加法和乘法運(yùn)算都有對應(yīng)的單位元(這兩個單位元一般不同,但都用符號e表示)。單位元就像線性代數(shù)的單位矩陣。一個矩陣乘以單位矩陣等于本身。對應(yīng)地,在域中的單位元有:對于加法單位元,所有元素加上單位元e,等于其本身。對應(yīng)乘法單位元,所有元素乘上單位e,等于其本身。
逆元就像數(shù)學(xué)上的倒數(shù),兩個元素互為對方的逆元。如果元素a和b互為加法逆元,那么就有 a + b = e。若互為乘法逆元,那么就有a * b = e。如果元素a在域中找不到另外一個元素b,使得a+b=e(a*b=e),那么a就沒有加法(乘法)逆元。
逆元有什么用呢?其實逆元是用于除法運(yùn)算的。小學(xué)的時候老師都會教:除于一個分?jǐn)?shù)就等于乘以該分?jǐn)?shù)的倒數(shù)(分?jǐn)?shù)的倒數(shù)就是該分?jǐn)?shù)的乘法逆元)。所以要想除于某個數(shù),可以乘以該數(shù)的逆元。
一個集合有加法單位元和乘法單位元,以及每一個元素都對應(yīng)有加法逆元和乘法逆元,是成為域的必要條件。需要注意:即使集合里面有元素0,并且0沒有對應(yīng)的乘法逆元,那么該集合也可能是一個域。因為并不要求0有乘法逆元。
例子:
一個域的例子就是我們平時熟悉的有理數(shù)集合,相應(yīng)的加法和乘法就是我們平時用的加法和乘法。其中,加法的單位元為0,有理數(shù)a的加法逆元就是其相反數(shù)。因為a + (-a) = 0(單位元)。乘法的單位元為1,a的乘法逆元是其倒數(shù)。因為a * (1/a) = 1。注意這里的元素0并沒有乘法逆元。
有理數(shù)是整數(shù)(正整數(shù)、0、負(fù)整數(shù))和分?jǐn)?shù)的統(tǒng)稱,是整數(shù)和分?jǐn)?shù)的集合。一般用黑體字母Q表示。
3)有限域
有限域,是指域中的元素個數(shù)是有限的。
4)有限域GF(p):
伽羅華域(Galois Field) Évariste Galois ,伽羅華(也譯作伽瓦羅),法國數(shù)學(xué)家,群論的創(chuàng)立者。用群論徹底解決了根式求解代數(shù)方程的問題,而且由此發(fā)展了一整套關(guān)于群和域的理論。
在密碼學(xué)中,有限域GF(p)是一個很重要的域,其中p為素數(shù)。簡單來說,GF(p)就是 mod p,因為一個數(shù) 模p后,結(jié)果在[0, p -1]之間,即該域中有p個元素。對于元素a和b,那么(a+b) mod p和(a*b)mod p,其結(jié)果都是域中的元素。GF(p)里面的加法和乘法都是平時用的加法和乘法。GF(p)的加法和乘法單位元分別是0和1,元素的加法和乘法逆元都很容易理解和求得,這里就不展開講了,《密碼編碼學(xué)與網(wǎng)絡(luò)安全》書中有詳講的。
求乘法逆元的實現(xiàn)代碼如下面所示,具體是使用了類似輾轉(zhuǎn)相除法的方法。
//g_prime就是 GF(p)中的p
int g_prime = 251;
int calculateInverse(int x)
{
int a1 = 1, a2 = 0, a3 = g_prime;
int b1 = 0, b2 = 1, b3 = x;
while( 1 )
{
if( b3 == 0 )
throw std::logic_error("should not be 0");
if( b3 == 1 )
break;
int q = a3 / b3;
int t1 = a1 - q*b1, t2 = a2 - q*b2, t3 = a3 - q*b3;
a1 = b1; a2 = b2; a3 = b3;
b1 = t1; b2 = t2; b3 = t3;
}
return (b2 + g_prime)%g_prime;
}
View Code
為什么p一定要是一個素數(shù)呢?
這是因為當(dāng)p為素數(shù)時,才能保證集合中的所有的元素都有加法和乘法逆元(0除外)。
假如p等于10,其加法和乘法單位元分別是0和1。加法沒有問題,所有元素都有加法逆元,但對于乘法來說,比如元素2,它就沒有乘法逆元。因為找不到一個數(shù)a,使得2*a mod 10等于1。這時,就不能進(jìn)行除于2運(yùn)算了。
對于p等于素數(shù),那么它就能保證域中的所有元素都有逆元。即,對于域中的任一個元素a,總能在域中找到另外一個元素b,使得a*b mod p 等于1。這個是可以證明的,利用反證法和余數(shù)的定義即可證明,不難。
5)有限域GF(2^8):
現(xiàn)在重點(diǎn)講一下GF(2^n),特別是GF(2^8),因為8剛好是一個字節(jié)的比特數(shù)。
前面說到, GF(p),p得是一個素數(shù),才能保證集合中的所有元素都有加法和乘法逆元(0除外)。但我們卻很希望0到255這256個數(shù)字也能組成一個域。因為很多領(lǐng)域需要用到。mod 256的余數(shù)范圍就是0到255,但256不是素數(shù)。小于256的最大素數(shù)為251,所以很多人就直接把大于等于251的數(shù)截斷為250。在圖像處理中,經(jīng)常會這樣做。但如果要求圖像無損的話,就不能截斷。
貌似已經(jīng)到了死胡同,救星還是有的,那就是GF(p^n),其中p為素數(shù)。在這里我們只需令p為2,n為8,即GF(2^8)。
6)多項式運(yùn)算
要弄懂GF(2^n),要先明白多項式運(yùn)算。這里的多項式和初中學(xué)的多項式運(yùn)算有一些區(qū)別。雖然它們的表示形式都是這樣的:f(x) = x^6 + x^ 4 + x^2 + x + 1。下面是它的一些特點(diǎn)。
多項式的系數(shù)只能是0或者1。當(dāng)然對于GF(p^n),如果p等于3,那么系數(shù)是可以取:0, 1, 2的
合并同類項時,系數(shù)們進(jìn)行異或操作,不是平常的加法操作。比如x^4 + x^4等于0*x^4。因為兩個系數(shù)都為1, 進(jìn)行異或后等于0
無所謂的減法(減法就等于加法),或者負(fù)系數(shù)。所以,x^4 – x^4就等于x^4 + x^4。-x^3就是x^3。
看一些例子吧。對于f(x) = x^6 + x^4 + x^2 + x + 1。g(x) = x^7 + x + 1。
那么f(x) + g(x) = x^7 + x^6 + x^4+ x^2 + (1+1)x + (1+1)1 = x^7 + x^6 + x^4 + x^2。f(x) – g(x)等于f(x) + g(x)。
f(x) * g(x) =(x^13 + x^11 + x^9 + x^8 + x^7) + (x^7 + x^5 + x^3 + x^2 + x) + (x^6+ x^4 + x^2 + x + 1) = x^13 + x^11 + x^9 + x^8 + x^6 + x^5+ x^4+ x^3+1。
下圖是除法,除法得到的余數(shù),也就是mod操作的結(jié)果。
7)素多項式(本原多項式):
對于多項式也類似素數(shù),有素多項式。其定義和素數(shù)類似,素多項式不能表示為其他兩個多項式相乘的乘積。
伽羅華域的元素可以通過該域上的本原多項式生成。通過本原多項式得到的域,其加法單位元都是0,乘法單位元是1。
以GF(2^3)為例,指數(shù)小于3的多項式共8個:0, 1, x, x+1, x^2, x^2+1, x^2 + x, x^2+x+1。其系數(shù)剛好就是000,001, 010, 011, 100, 101, 110, 111,是0到7這8個數(shù)的二進(jìn)制形式。多項式對應(yīng)一個值,我們可以稱這個值為多項式值。
GF(2^3)上有不只一個本原多項式,選一個本原多項式x^3+x+1,這8個多項式進(jìn)行四則運(yùn)算后 mod (x^3+x+1)的結(jié)果都是8個之中的某一個。因此這8個多項式構(gòu)成一個有限域。
對于GF(2^3),取素多項式為x^3 + x+1,那么多項式x^2+x的乘法逆元就是x+1。系數(shù)對應(yīng)的二進(jìn)制分別為110和011。此時,我們就認(rèn)為對應(yīng)的十進(jìn)制數(shù)6和3互為逆元。
部分 GF(2^w)域經(jīng)常使用的本原多項式如下:
8)通過本原多項式生成元素
設(shè)P(x)是GF(2^w)上的某一個本原多項式,GF(2^w)的元素產(chǎn)生步驟是:
1、給定一個初始集合,包含0,1和元素x,即{0,1,x};
2、將這個集合中的最后一個元素,即x,乘以x,如果結(jié)果的度大于等于w,則將結(jié)果mod P(x)后加入集合;
3、直到集合有2^w個元素,此時最后一個元素乘以x再mod P(x)的值等于1。
例如,GF(2^4)含有16個元素,本原多項式為P(x)=x^4+x+1,除了0、1外,另外14個符號均由本原多項式生成。
注意到x^14=x^3+1,此時計算x^15=x^14*x=(x^3+1)*x=x^4+x=1,生成結(jié)束。
9)伽羅華域上的運(yùn)算
加法和減法:
加法即異或運(yùn)算
減法即加法
乘法和除法:
伽羅華域上的多項式乘法,其結(jié)果需要mod P(x),可以通過以下方式簡化計算。
首先,考慮x^8,x^8 mod P(x) = P(x) – x^8 = x^4 + x^3 +x^2 +1。
對于一般形式的多項式f(x)=a7*x^7 + a6*x^6 + a5*x^5 + a4*x^4 + a3*x^3 + a2*x^2 + a1*x + a0,乘以x得到
x*f(x) = (a7*x^8 + a6*x^7 + a5*x^6 + a4*x^5 + a3*x^4 + a2*x^3 + a1*x^1 + a0*x) mod P(x)
這時有兩種情況:
1)a7 == 0,此時結(jié)果是一個小于指數(shù)小于8的多項式,不需要取模計算。
2)a7 == 1,則將x^8替換為x^4 + x^3 + x^2 +1,而不用進(jìn)行除法取模計算,結(jié)果為:
x*f(x) = (x^4 + x^3 + x^2 +1) +a6*x^7 + a5*x^6 + a4*x^5 + a3*x^4 + a2*x^3 + a1*x^1 + a0*x
雖然可以通過替換減少除法計算,但還是過于復(fù)雜。尤其是在需要大量運(yùn)算的場合,比如圖像處理。于是牛人提出通過查表來減少計算。
10)查表的原理
首先介紹一個概念,生成元。
生成元是域上的一類特殊元素,生成元的冪可以遍歷域上的所有元素。假設(shè)g是域GF(2^w)上生成元,那么集合{g0 ,g1 ,……,g(2^w-1) } 包含了域GF(2^w)上所有非零元素。
將生成元應(yīng)用到多項式中, GF(2^w)中的所有多項式都是可以通過多項式生成元g通過冪求得。即域中的任意元素a,都可以表示為a = g^k。
GF(2^w)是一個有限域,就是元素個數(shù)是有限的,但指數(shù)k是可以無窮的。所以必然存在循環(huán)。這個循環(huán)的周期是2^w-1(g不能生成多項式0)。所以當(dāng)k大于等于2^w-1時,g^k =g^(k%(2^w-1))。
對于g^k = a,有正過程和逆過程。知道指數(shù)k求a是正過程,知道值a求指數(shù)k是逆過程。
對于乘法,假設(shè)a=g^n,b=g^m。那么a*b = g^n* g^m = g^(n+m)。查表的方法就是根據(jù)a和b,分別查表得到n和m,然后查表g^(n+m)即可。
因此需要構(gòu)造正表和反表,在GF(2^w)域上分別記為gflog和gfilog。gflog是將二進(jìn)制形式映射為多項式形式,gfilog是將多項式形式映射為二進(jìn)制形式。
注意:多項式0,是無法用生成元生成的。g^0等于多項式1,而不是0。
根據(jù)上文的GF(2^4)的元素表示,生成gflog表和gfilog表如下:
查表進(jìn)行乘法和除法運(yùn)算的例子
在GF(2^4)域上的乘法和除法,已知2^w-1 = 2^4 -1 = 15:
乘法:
7 * 9 = gfilog[gflog[7] + gflog[9]] = gfilog[10 + 14]
= gfilog[24 mod 15] =gfilog[9]=10
除法:
13 / 11 = gfilog[gflog[13] - gflog[11]] = gfilog[13 - 7] = gfilog[6] = 12
摘自:
https://blog.csdn.net/shelldon/article/details/54729687
https://blog.csdn.net/luotuo44/article/details/41645597
總結(jié)
以上是生活随笔為你收集整理的密码学中的数学基础2 伽罗华域(Galois Field)上的四则运算的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 买了第三方数据线,如何鉴定是否通过了 M
- 下一篇: php使用strlen()判断中文汉字字