密碼學中的一些數學基礎

聲明：本篇博文的內容摘自於《密碼編碼學與網絡安全》這本書。

羣、環和域都是數學理論中的一個分支，即抽象代數或稱爲近世代數的基本元素。在抽象代數中，我們關心的是其元素能進行代數運算的集合，也就是說，我們可以通過很多種方法，使集合上的兩個元素組合得到集合中的第三個元素。這些運算方法都遵守特殊的規則，而這些規則又能確定集合的性質。根據約定，集合上元素的兩種主要運算符號與普通數字的加法和乘法所使用的符號是相同的。然而，我們必須指出，在抽象代數中，我們並不僅僅限於普通的算術操作。

羣

羣G，有時記爲{G, . },是定義了一個二元運算的集合，這個二元運算可表示爲 . ,G中的每一個序偶(a,b)通過運算生成G中的元素(a.b)，並滿足以下公理：
（A1）封閉性：如果a和b都屬於G，則a.b也屬於G。
（A2）結合律：對於G中任意a，b，c，都有(a.b).c=a.(b.c)成立。
（A3）單位元：G中存在一個元素e，對於G中任意元素a，都有a.e=e.a=a。
（A4）逆元：對於G中任意元素a，G中都存在一個元素a’，使得下式成立：a.a’=a’.a=e
如果一個羣的元素是有限的，則該羣稱爲有限羣，並且羣的階就等於羣中元素的個數。否則，稱該羣爲無限羣。
一個羣如果還滿足以下條件，則稱爲交換羣：
（A5）交換律：對於G中任意的元素a，b，都有a.b=b.a成立。

循環羣

我們在羣中定義求冪運算爲重複運用羣中的運算，如a³=a.a.a。而且，我們定義a⁰=e作爲單位元；並且a^-n=(a’)ⁿ,其中a’是a在羣內的逆元算。如果羣G中的每一個元素都是一個固定元素a(a屬於G)的冪a^k(k爲整數)，則稱羣G是循環羣。我們認爲元素a生成了羣G，或者說a是羣G的生成元。循環羣總是交換羣，它可能是有限羣或無限羣。

環

環R，有時記爲{R,+,x},是一個有兩個二元運算的集合，這兩個二元運算分別稱爲加法和乘法，且對於R中的任意元素a，b，c滿足以下公理。
（A1～A5）R關於加法是一個交換羣；也就是說，R滿足從A1到A5的所有原則。對於此種情況下的加法羣，我們用0表示其單位元，-a表示a的逆元。
（M1）乘法的封閉性：如果a和b都屬於R，則ab也屬於R。
（M2）乘法的結合律：對於R中的任意元素a，b，c，有a(bc)=(ab)c成立。
（M3）分配律：對於R中的任意元素a,b,c，下面兩個式子總成立:
a(b+c)=ab+ac (a+b)c=ac+bc
本質上說，環就是一個集合，我們可以在其上進行加法、減法[a-b=a+(-b)]和乘法而不脫離該集合。
環如果還滿足以下條件，則稱爲交換環。
（M4）乘法的交換律：對於R中任意元素a,b,有ab=ba成立。
下面，我們定義整環，它是滿足以下公理的交換環：
（M5）乘法單位元：在R中存在元素1，使得對於R中的任意元素a，有a1=1a=a成立。
（M6）無零因子：如果有R中元素a,b,且ab=0，則必有a=0或b=0。

這裏簡單總結一下，羣是定義了一個二元運算的集合而環是定義了兩個二元運算的集合。循環羣是由一個元素生成的集合。

域

域F，有時記爲{F，+，x}，是有兩個二元運算的集合，這兩個二元運算分別稱爲加法和乘法，且對於F中的任意元素a,b,c 滿足以下公理：
（A1～M6）F是一個整環；也就是說F滿足從A1到A5以及從M1到M6的所有原則。
（M7）乘法逆元：對於F中的任意元素a（除0以外），F中都存在一個元素a^-1使得下式成立：
aa^-1=(a^-1)a=1;

注意：乘法逆元是域中的概念。
本質上說，域就是一個集合，我們可以在其上進行加法、減法、乘法和除法而不脫離該集合。除法又按以下規則來定義：a/b=a(b^-1)。

有限域GF( p )

無限域在密碼學中沒有特別的意義，然而，有限域卻在許多密碼學算法中扮演着重要的角色。有限域的階（元素的個數）必須是一個素數的冪pⁿ,n爲正整數。階爲pⁿ的有限域一般記爲GF(pⁿ),GF代表Galois域，以第一位研究有限域的數學家的名字命名。我們在此要關注兩種特殊的情形：n=1時的有限域GF(p),它和n>1的有限域相比有着不同的結構。

階爲p的有限域

模算術是一種整數算術，它將所有整數約減爲一個固定的集合[0，1，… ，n-1]，其中n爲某個整數。任何這個集合外的整數通過除以n取餘數的方式約減到這個範圍內。
在此之前先複習一下模運算：

模數

如果a是整數，n是正整數，則我們定義a模n是a除以n所得的餘數。整數n稱爲模數。因此，對於任意整數a，我們總可以寫出
a=qn+r 0<=r

同餘的性質

模運算有如下性質：
（1）如果n|(a-b),那麼a與b模n同餘。
（2）a與b模n同餘隱含b與a模n同餘。
（3）a與b模n同餘並且b與c模n同餘，那麼隱含a與c模n同餘。

運算(mod n)將所有的整數映射到集合{0,1,…,(n-1)}

模運算的性質

定義比n小的非負整數集合爲Z_n：
Z_n={0,1,…,(n-1)}這個集合被稱爲剩餘類集，或模n的剩餘類。更準確地說，Z_n中每一個整數都代表一個剩餘類，我們可以將模n的剩餘類表示爲[0],[1],[2],…,[n-1]，其中
[r]={a:a是一個整數，a同餘r(mod n)}

比如模4的剩餘類爲：
[0]={…,-16,-12,-8,-4,0,4,8,12,16,….}
[1]={…,-15,-11,-7,-3,1,5,9,13,17,…}
在剩餘類的所有整數中，我們通常用最小非負整數來代表這個剩餘類。尋找與k是模n同餘的最小非負整數的過程，稱爲模n的k約化。

Z_n（是有乘法單位元的交換環）中整數運算的性質：
交換律：（w+x）mod n =(x+w) mod n (w * x) mod n =(x * w) mod n
結合律：[(w+x)+y] mod n=[w+(x+y)] mod n [(w*x)y] mod n=[w(x*y)] mod n
分配律：[w*(x+y)] mod n=[(w*x)+(w*y)] mod n
單位元：(0+w) mod n =w mod n (1*w) mod n=w mod n
加法逆元(-w):對於Z_n中的任意w，存在一個z使得w+z同餘0 mod n。

令a與n互素，如果(a*b)同餘(a*c)(mod n),那麼b同餘c (mod n) 。

對於任何一般的模數n，如果a和n有任何公因子的話，用乘數a依次作用於0到n-1的所有整數將不會產生一個完整剩餘類集。一般來說，如果一個整數與n互素，那麼它在Z_n中有一個乘法逆元。
給定一個素數p，元素個數爲p的有限域GF(p)被定義爲整數{0,1,…,p-1}的集合Z_p,其運算爲模p的算術運算。

在GF(p)中求乘法逆元

當p值較小時，求GF(p)中元素的乘法逆元很容易。你只需構造一個乘法表，所要的結果可以從中直接讀出。但是，當p值比較大時，這種方法是不切實際的。

如果a和b互素，則b有模a的乘法逆元。也就是說，如果gcd(a,b)=1，那麼b有模a的乘法逆元。即對於正整數b

多項式運算

單變元多項式運算分爲三種：
1.使用代數基本規則的普通多項式運算。
2.係數運算是模p運算的多項式運算，即係數在GF(p)中。
3.係數在GF(p)中，且多項式被定義爲模一個n次多項式m(x)的多項式運算。

普通多項式運算

一個n次多項式(n>=0)的表達形式如下：
f(x)=a_nxⁿ+a_n-1x^n-1+….+a_ixⁱ+a₁x+a₀
其中a_i是某個指定數集S中的元素，該數集稱爲係數集，且a_n!=0。我們稱f(x)是定義在係數集S上的多項式。

零次多項式稱爲常數多項式，僅僅是係數集裏的一個元素。如果a_n=1,那麼對應的n次多項式就被稱爲首1多項式。

多項式運算包含加法、減法和乘法，這些運算是把變量x當做集合S中的一個元素來定義的。除法也以類似的方式定義，但這時要求S是域。這些域包括
實數域、有理數域和素數p的域Z_n。注意整數集並不是域，也不支持多項式除法運算。

係數在Z_p中的多項式運算

現在我們考慮這樣的多項式，它的係數是域F的元素。我們稱其爲域F上的多項式。這種情況下，容易看出這樣的多項式集合是一個環，稱爲多項式環。也
就是說，如果我們把每個不同的多項式視爲集合中的元素，這個集合是一個環。
對域上的多項式進行多項式運算時，除法運算是可能的。注意這並不是說能進行整除。這裏要注意不同的域上的除法的運算規則不同。如果試圖在非域係數集
上進行多項式除法，我們會發現除法運算並不總是有定義的。即使係數集是一個域，多項式除法也不一定是整除。一般說來，除法會產生一個商式和一個餘式。
對於域上的多項式，給定n次多項式f(x)和m(m<=n)次多項式g(x),如果用g(x)除f(x)，我們得到一個商q(x)和一個餘數r(x),滿足如下關係式：
f(x)=q(x)g(x)+r(x)
各多項式的次數爲： Degree f(x)=n Degree g(x)=m Degree q(x)=n-m Degree r(x)<=m-1.
如果允許餘數，我們說域上多項式除法是可以的。

域F上的多項式f(x)被稱爲不可約的（既約的)當且僅當f(x)不能表示爲兩個多項式的積[兩個多項式都在F上，次數都低於f(x)的次數]。與整數相似，一個不可約多項式也被稱爲素多項式。約的時候注意多項式整除的意義，在不同的域上運算是不一樣的。

求最大公因式

我們可以通過定義最大公因式來擴展域上的多項式運算和整數運算之間的相似性。如果
(1)c(x)能同時整除a(x)和b(x)
(2)a(x)和b(x)的任何公共因式都是c(x)的因式。
就稱多項式c(x)爲a(x)和b(x)的最大公因式。

本節我們討論了一般多項式的算術。在一般多項式算術裏，變量不予賦值，即我們不給多項式的變量賦值。相反，運用代數的一般規則對多項式進行算術操作(加、減、乘、除)。除非係數是域的元素，否則多項式除法是不行的。

有限域 GF(2ⁿ)

有限域的元素個數必須爲pⁿ,其中p爲素數，n爲正整數。注意到，當n>1時，pⁿ上的多項式在模pⁿ運算時並不能產生一個域。

實際上所有的加密算法(包括對稱密鑰和公開密碼算法)都涉及整數集上的算術運算。如果某種算法使用的運算之一是除法，那麼我們就必須使用定義在域上的運算。爲了方便使用和提高效率，我們希望這個整數集中的數與給定的二進制位數所能表達的信息一一對應而不出現浪費。也就是說，我們希望這個整數集的範圍從0到2_n-1,這樣正好對應一個n位的字。

我們要尋找一個包含2ⁿ個元素的集合，其上定義了加法和乘法使之成爲一個域。我們給集合的每一個元素賦值爲0～2ⁿ-1之間的唯一整數。請記住我們不會用模算術，因爲那樣不能構成域。我們將會用多項式算術來構造我們需要的域。

多項式模運算

設集合S由域Z^p上次數小於等於n-1的所有多項式組成。每一個多項式具有如下形式：
f(x)=a_n-1x^n-1+a_n-2x^n-2+…..+a₁x+a₀
其中，a_i在集合{0,1,…,p-1}上取值。S中共有pⁿ個不同的多項式。如果定義了合適的運算，那麼每一個這樣的集合S都是一個
有限域。定義由如下幾條組成：
（1）該運算遵循代數基本規則中的普通多項式運算規則及如下兩條限制。
（2）係數運算以p爲模，即遵循有限域Z_p上的運算規則。
（3）如果乘法運算的結果是次數大於n-1的多項式，那麼必須將其除以某個次數爲n的既約多項式m(x)並取餘式。對於多項式f(x),這個餘數
可表示爲r(x)=f(x) mod m(x)。
高級加密標準(AES)使用有限域GF(2⁸)上的運算，其中既約多項式m(x)=x⁸+x⁴+x³+x+1.
和簡單模運算類似，多項式模運算中也有剩餘類集合的概念。設m(x)爲n次多項式，則模m(x)剩餘類集合有pⁿ個元素，其中每個元素
都可以表示成一個m次多項式( m

求乘法逆元

正如Euclid算法可以用來求兩個多項式的最大公因式，擴展Euclid算法則可以用來求一個多項式的乘法逆元。如果多項式b(x)的次數小於a(x)的次數
且gcd[a(x),b(x)]=1，那麼該算法能求出b(x)以a(x)爲模的乘法逆元。若a(x)爲既約多項式，即除了本身與1之外沒有其他因式，則始終有gcd[a(x),b(x)]=1.
算法的描述方式和整數情形的擴展Euclid算法一樣。給定兩個多項式a(x)和b(x)，其中a(x)的次數大於b(x)的次數。我們希望解如下方程獲得v(x),w(x)以及
d(x),其中d(x)=gcd[a(x),b(x)] : a(x)v(x)+b(x)w(x)=d(x) 如果d(x)=1,則w(x)是b(x)模a(x)的乘法逆。

計算上的考慮

GF(2ⁿ)中的多項式
f(x)=a_n-1x^n-1+a_n-2x^n-2+…+a₁x+a₀
可以由它的n個二進制係數(a_n-1a_n-2…a₀) 唯一地表示。因此GF(2ⁿ)中的每個多項式都可以表示成
一個n位的二進制整數。

加法

我們發現這裏的多項式加法是將相應的係數分別相加，而對於Z₂上的多項式，加法其實就是異或(XOR)運算。所以，GF(2_n)中的
兩個多項式加法等同於按位異或運算。

乘法

簡單的異或運算不能完成GF(2ⁿ)上的乘法。但是可以使用一種相當直觀且容易實現的技巧。
一般地，在GF(2ⁿ)上對於n次多項式p(x)，有xⁿ mod p(x) =p(x)-xⁿ。

在GF(2)中，模2的加法和減法是等價的，加法等價於XOR運算，乘法等價於邏輯與運算。

現在考慮GF(2⁸)上的多項式f(x)=b₇x⁷+b₆x⁶+b₅x⁵+b₄x⁴+b₃x³+b₂x²+b₁x+b₀，將它乘以x，可得
x*f(x)=(b₇x⁸+b₆x⁷+b₅x⁶+b₄x⁵+b₃x⁴+b₂x³+b₁x²+b₀x) mod m(x)
如果b₇=0,那麼結果就是一個次數小於8的多項式，已經是約化後的形式，不需要進一步計算。如果b₇=1，那麼可以使用xⁿ mod p(x) =p(x)-xⁿ進行模m(x)的約化：
x*f(x)=(b₆x⁷+b₅x⁶+b₄x⁵+b₃x⁴+b₂x³+b₁x²+b₀x) +(x⁴+x³+x+1)
這表明乘以x(即00000010)的運算可以通過左移一位後再根據條件按位異或(00011011)來實現。總結爲如下的公式：

乘以x的更高次冪可以通過重複使用上式來實現。這樣一來，GF(2⁸)上的乘法可以用多箇中間結果相加的方法實現。

使用生成元

定義有限域GF(2ⁿ)的另一種等價方式有時更方便，它使用相同的不可約多項式。首先，我們需要兩個定義：階爲q的有限域F的生成元是一個元素，記爲g，該元素的前q-1個冪構成了F的所有非零元素，即域F的元素爲0，g⁰, …. ,g^q-2。
考慮由多項式f(x)定義的域F，如果F內的一個元素b滿足f(b)=0，則稱b爲多項式的f(x)的根。（這裏注意不是要求這個方程的數值解，只是處理多項式算術） 最後，可以證明一個不可約多項式的根g是這個不可約多項式定義的有限域的生成元。

通常，對於由不可約多項式f(x)生成的域GF(2ⁿ),有gⁿ=f(g)-gⁿ。計算gⁿ⁺¹ 到g^2n-2的值。域的元素對應g的方冪：g⁰到g^2n-2,另外再加上0元素。域元素的乘法用等式g^k=g^{k mod (2n-1)}進行，k爲任意整數。

寫在最後

這篇文章的內容摘自《密碼編碼學與網絡安全》這本書，最後，我要強調的是GF(2⁸)有限域的運算一定要搞懂，因爲在寫AES算法以及調試AES算法時我們會用到。