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)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。