現(xiàn)代密碼學(xué)理論與實(shí)踐第4章有限域

現(xiàn)代密碼學(xué)理論與實(shí)踐

第4章有限域FourthEditionbyWilliamStallingsSlidesby楊壽保syang@http:///~syang2012年9月2022/10/311/51現(xiàn)代密碼學(xué)理論與實(shí)踐04本章要點(diǎn)域是一些元素的集合，其上定義了兩個(gè)算術(shù)運(yùn)算(加法和乘法)，具有常規(guī)算術(shù)性質(zhì)，如封閉性、結(jié)合律、交換律、分配律、加法逆和乘法逆等。模算術(shù)是一種整數(shù)算術(shù)，它將所有整數(shù)約減為一個(gè)固定的集合[0,1,…,n-1]，n為某個(gè)整數(shù)。任何這個(gè)集合外的整數(shù)通過除以n取余的方式約減到這個(gè)范圍內(nèi)。兩個(gè)整數(shù)的最大公因子是可以整除這兩個(gè)整數(shù)的最大正整數(shù)。一個(gè)有限域就是有有限個(gè)元素的域?？梢宰C明有限域的階(元素個(gè)數(shù))一定可以寫作素?cái)?shù)的冪形式pn，n為一個(gè)整數(shù)，p為素?cái)?shù)。階為p的有限域可以由模p的算術(shù)來定義。階為pn，n>1的有限域可由多項(xiàng)式算術(shù)來定義。2022/10/312現(xiàn)代密碼學(xué)理論與實(shí)踐044.1群,環(huán)和域Groups,Rings,andFields群G,記作{G,?},定義一個(gè)二元運(yùn)算?的集合，G中每一個(gè)序偶(a,b)通過運(yùn)算生成G中元素(a?b)，滿足下列公理：(A1)封閉性Closure:如果a和b都屬于G,則a?b也屬于G.(A2)結(jié)合律Associative:對于G中任意元素a,b,c，都有a?(b?c)=(a?b)?c成立(A3)單位元Identityelement:G中存在一個(gè)元素e，對于G中任意元素a，都有a?e=e?a=a成立(A4)逆元Inverseelement:對于G中任意元素a,G中都存在一個(gè)元素a’，使得a?a’=a’?a=e成立2022/10/313現(xiàn)代密碼學(xué)理論與實(shí)踐04群、有限群和無限群用Nn表示n個(gè)不同符號的集合，{1,2,…,n}.n個(gè)不同符號的一個(gè)置換是一個(gè)Nn到Nn的一一映射。定義Sn為n個(gè)不同符號的所有置換組成的集合。Sn中的每一個(gè)元素都代表集合{1,2,…,n}的一個(gè)置換，容易驗(yàn)證Sn是一個(gè)群：A1：如果π,ρ∈Sn，則合成映射π?ρ根據(jù)置換π來改變ρ中元素的次序而形成，如，{3,2,1}?{1,3,2}={2,3,1},顯然π?ρ∈SnA2：映射的合成顯而易見滿足結(jié)合律A3：恒等映射就是不改變n個(gè)元素位置的置換，對于Sn，單位元是{1,2,…,n}A4：對于任意π∈Sn，抵消由π定義置換的映射就是π的逆元，這個(gè)逆元總是存在，例如：{2,3,1}?{3,1,2}={1,2,3},有限群FiniteGroup和無限群InfiniteGroup：如果一個(gè)群的元素是有限的，則該群稱為有限群，且群的階等于群中元素的個(gè)數(shù)；否則稱為無限群2022/10/314現(xiàn)代密碼學(xué)理論與實(shí)踐04交換群和循環(huán)群交換群AbelianGroup：還滿足以下條件的群稱為交換群(又稱阿貝爾群)(A5)交換律Commutative：對于G中任意的元素a,b，都有a?b=b?a成立當(dāng)群中的運(yùn)算符是加法時(shí)，其單位元是0；a的逆元是-a,并且減法用以下的規(guī)則定義：a–b=a+(-b)循環(huán)群CyclicGroup如果群中的每一個(gè)元素都是一個(gè)固定的元素a(a∈G)的冪ak(k為整數(shù))，則稱群G為循環(huán)群。元素a生成了群G，或者說a是群G的生成元。2022/10/315現(xiàn)代密碼學(xué)理論與實(shí)踐04環(huán)(Rings)環(huán)R,由{R,+,x}表示,是具有加法和乘法兩個(gè)二元運(yùn)算的元素的集合，對于環(huán)中的所有a,b,c,都服從以下公理：(A1-A5),單位元是0，a的逆是-a.(M1),乘法封閉性,如果a和b屬于R,則ab也屬于R(M2),乘法結(jié)合律,對于R中任意a,b,c有a(bc)=(ab)c.(M3),乘法分配律,a(b+c)=ab+acor(a+b)c=ac+bc(M4),乘法交換律,ab=ba，交換環(huán)(M5),乘法單位元,R中存在元素1使得所有a有a1=1a.(M6),無零因子,如果R中有a,b且ab=0,則a=0orb=0.滿足M4的是交換環(huán)；滿足M5和M6的交換環(huán)是整環(huán)2022/10/316現(xiàn)代密碼學(xué)理論與實(shí)踐04域(Fields)域F,可以記為{F,+,x},是有加法和乘法的兩個(gè)二元運(yùn)算的元素的集合，對于F中的任意元素a,b,c,滿足以下公理：(A1-M6),F是一個(gè)整環(huán)(M7),乘法逆元,對于F中的任意元素a(除0以外),F中都存在一個(gè)元素a-1,使得aa-1=(a-1)a=1.域就是一個(gè)集合，在其上進(jìn)行加減乘除而不脫離該集合,除法按以下規(guī)則定義:a/b=a(b-1).有理數(shù)集合,實(shí)數(shù)集合和復(fù)數(shù)集合都是域；整數(shù)集合不是域，因?yàn)槌?和-1有乘法逆元，其他元素都無乘法逆元2022/10/317現(xiàn)代密碼學(xué)理論與實(shí)踐04群、環(huán)和域的關(guān)系2022/10/318現(xiàn)代密碼學(xué)理論與實(shí)踐044.2ModularArithmetic給定任意正整數(shù)n和a，如果用a除以n，得到的商q和余數(shù)r滿足如下關(guān)系:

a=qn+r0≤r<n;q=?a/n」?x」表示小于等于x的最大整數(shù)Eg:11=1x7+4,r=4;-11=(-2)x7+3,r=32022/10/319現(xiàn)代密碼學(xué)理論與實(shí)踐04因子Divisors如果a=mb,其中a,b,m為整數(shù)，則當(dāng)b≠0時(shí)，即b能整除a,或a除以b余數(shù)為0,b|a.b是a的一個(gè)因子。24的正因子有1,2,3,4,6,8,12和24。以下關(guān)系成立如果a|1,則a=±1如果a|b，且b|a,則a=±b任何b≠0能整除0如果b|g，且b|h,則對任何整數(shù)m和n有b|(mg+nh)Eg:b=7,g=14,h=63,m=3,n=2,7|14and7|63

求證：7|(3x14+2x63)證明：(3x14+2x63)=7(3x2+2x9)

顯然,7|(7(3x2+2x9))如果a≡0modn，則n|a2022/10/3110現(xiàn)代密碼學(xué)理論與實(shí)踐04同余(congruence)給定整數(shù)a,b及n≠0,當(dāng)且僅當(dāng)a-b=kn時(shí)，a與b在模n時(shí)同余，記為

a≡bmodn或a≡nb Ex:17≡57∵17-7=2*5;53≡711∵53-11=6*7

a≡nb

當(dāng)且僅當(dāng)amodn=bmodn如果a是整數(shù)，n是正整數(shù)，定義a除以n所得之余數(shù)為a模n。對于任意整數(shù)a，我們總可寫出：a=?a/n」xn+(amodn)11mod7=4; -11mod7=3如果(amodn)=(bmodn),則稱整數(shù)a和b是模n同余，表示為a≡bmodn或a≡nb73≡4mod23； 21≡-9mod102022/10/3111現(xiàn)代密碼學(xué)理論與實(shí)踐04同余的性質(zhì)如果n|(a-b),則a≡bmodn證明:如果n|(a-b),則有(a-b)=kn,k為某些整數(shù)，所以a=b+kn。故amodn=(b+kn)除以n的余數(shù)

=b除以n的余數(shù)

=bmodna≡bmodn隱含b≡amodna≡bmodn和b≡cmodn隱含a≡cmodnEx:23≡8(mod5)，因?yàn)?3-8=15=5x3-11≡5(mod8)，因?yàn)?11-5=-16=8x(-2)81≡0(mod27)，因?yàn)?1-0=81=27x3

2022/10/3112現(xiàn)代密碼學(xué)理論與實(shí)踐04(a1opa2)modn=[(a1modn)]op(a2modn)]modn ①反身性：a=amodn②對稱性：若a=bmodn，則b=amodn③傳遞性:若a=bmodn且b=cmodn，則a=cmodn④如果a=bmodn且c=dmodn，則

a+c=(b+d)modna-c=(b-d)modn

a?c=(b?d)modn⑤(a+b)modn=(amodn+bmodn)modn(a-b)modn=(amodn-bmodn)modn(a?b)modn=(amodn?bmodn)modn⑥如果ac=bdmodn且c=dmodn,gcd(c,n)=1,

則a=bmodn證明：留給學(xué)生例：3*2=1*2mod4且2=2mod4,但3≠1mod4，

∵gcd(2,4)≠1模算術(shù)運(yùn)算2022/10/3113現(xiàn)代密碼學(xué)理論與實(shí)踐042022/10/3114現(xiàn)代密碼學(xué)理論與實(shí)踐04加法逆元和乘法逆元加法逆元(-w)對每一個(gè)w∈Zn，存在一個(gè)z，使得w+z≡0modn，則z即為加法逆元-w乘法逆元(w-1)對每一個(gè)w∈Zp，存在一個(gè)z，使得wxz≡1modp，p為素?cái)?shù)，w與p互素，則z即為乘法逆元w-1因?yàn)閣與p互素，如果用w乘以Zp中的所有數(shù)模p，得到的余數(shù)將以不同次序涵蓋Zp中的所有數(shù)，那么至少有一個(gè)余數(shù)的值為1。因此，在Zp中的某個(gè)數(shù)與w相乘模p的余數(shù)為1,這個(gè)數(shù)就是w的乘法逆元,w-1某些但非全部整數(shù)存在一個(gè)乘法逆元就將使模數(shù)不再是素?cái)?shù)。如果gcd(a,n)=1,則能在Zn中找到b，使得

axb

≡1modn，則b即為乘法逆元a-1,因?yàn)閍與n互素。2022/10/3115現(xiàn)代密碼學(xué)理論與實(shí)踐04剩余集(Residues)定義比n小的非負(fù)整數(shù)集合為Zn：Zn

={0,1,…,(n-1)} b是amodn的剩余，如果a=bmodn或

a是bmodn的剩余，如果b=amodn(1)模n的完全剩余集

CompleteSetofResiduesmodn如果對每個(gè)整數(shù)a，在集合{r1,r2,…,rn}中恰有一個(gè)余數(shù)ri,使得a=rimodn,則稱{r1,r2,…,rn}為模n的完全剩余集，{0,1,…,n-1}形成模n的完全剩余集。與同余不同之處：a≡nb,當(dāng)且僅當(dāng)amodn=bmodn

a≡nr，即a=rmodn,不是說amodn=r比如20≡314，得20=14mod3,r=2，但20mod3≠14，而是20mod3=14mod3模算術(shù)的性質(zhì)2022/10/3116現(xiàn)代密碼學(xué)理論與實(shí)踐04模算術(shù)的性質(zhì)(2)模n的縮剩余集(ReducedsetofResiduesmodn)完全剩余集的一個(gè)子集，指的是集合中的元素都和n互素例:n=10，模n的完全剩余集是{0,1,2,…,9}，縮剩余集是{1,3,7,9}2022/10/3117現(xiàn)代密碼學(xué)理論與實(shí)踐04數(shù)論的一個(gè)最基本的技巧是Euclid算法，求兩個(gè)正整數(shù)的最大公約數(shù)gcd(a,n),greatestcommondivisor對于任何非負(fù)的整數(shù)a和n，gcd(a,n)=gcd(nmoda,a)原理是計(jì)算gi+1=gi-1modgi

直到gi=0為止。Algorithmgcd(a,n)begin g0:=n,g1:=a,i:=1 whilegi≠0do begin gi+1=gi-1modgi i:=i+1 endn

gcd:=gi-1end

例如：gcd(22,55)=gcd(55mod22,22)=gcd(11,22)=114.3歐幾里得算法EuclidAlgorithm2022/10/3118現(xiàn)代密碼學(xué)理論與實(shí)踐04Euclid'sGCDAlgorithmEuclid'sAlgorithmtocomputeGCD(a,b):

A?a,B?b若B=0，則返回A=gcd(a,b)R=AmodBA?B,B?R轉(zhuǎn)到2Int

gcd(int

x,inty){

Return(!y)?x:gcd(y,x%y);

}如果a和b只有唯一的正公因子1，則稱整數(shù)a和b是互素的，即gcd(a,b)=12022/10/3119現(xiàn)代密碼學(xué)理論與實(shí)踐04Example:

求gcd(1970,1066)1970=1x1066+904 gcd(1066,904)1066=1x904+162 gcd(904,162)904=5x162+94 gcd(162,94)162=1x94+68 gcd(94,68)94=1x68+26 gcd(68,26)68=2x26+16 gcd(26,16)26=1x16+10 gcd(16,10)16=1x10+6 gcd(10,6)10=1x6+4 gcd(6,4)6=1x4+2 gcd(4,2)4=2x2+0 gcd(2,0) Gcd(1970,1066)=22022/10/3120現(xiàn)代密碼學(xué)理論與實(shí)踐044.4有限域GF(p)GaloisFields有限域在密碼學(xué)中扮演重要角色有限域的階(元素個(gè)數(shù))必須是一個(gè)素?cái)?shù)的冪pn,n為正整數(shù)。元素個(gè)數(shù)是pn的有限域一般記為GF(pn)，即Galoisfields,模pn.關(guān)注兩種特殊情形，n=1時(shí)的有限域和p為2時(shí)的有限域，即GF(p)和GF(2n)最簡單的有限域是GF(2)，它的代數(shù)運(yùn)算簡述如下：+01x01w-ww-100100000110101111

加乘求逆2022/10/3121現(xiàn)代密碼學(xué)理論與實(shí)踐04GaloisFieldsGF(p)階為p的有限域GF(p)給定一個(gè)素?cái)?shù)p，元素個(gè)數(shù)為p的有限域GF(p)被定義為整數(shù){0,1,…,p-1}的集合Zp，其運(yùn)算為模p的算術(shù)運(yùn)算Zn中的任一整數(shù)有乘法逆元當(dāng)且僅當(dāng)該整數(shù)與n互素，若n為素?cái)?shù)，Zn中的所有非零整數(shù)都與n互素，因此Zn中所有非零整數(shù)都有乘法逆元對每一個(gè)w∈Zp，存在一個(gè)z，使得w×z≡1modp，則z即為乘法逆元w-1因?yàn)閣與p互素，如果用w乘以Zp中的所有數(shù)模p，得到的余數(shù)將以不同次序涵蓋Zp中的所有數(shù)，即余數(shù)集合是{0,1,…,p-1}的置換形，那么至少有一個(gè)余數(shù)的值為1。因此，在Zp中的某個(gè)數(shù)與w相乘模p的余數(shù)為1,這個(gè)數(shù)就是w的乘法逆元，w-1。所以，Zp是一個(gè)有限域。2022/10/3122現(xiàn)代密碼學(xué)理論與實(shí)踐042022/10/3123現(xiàn)代密碼學(xué)理論與實(shí)踐04在GF(p)中求乘法逆元如果gcd(m,b)=1，那么b有模m的乘法逆元，歐幾里得算法可被擴(kuò)展如下：求出gcd(m,b)后，當(dāng)gcd為1時(shí)，算法返回b的乘法逆元EXTENDEDEUCLID(m,b)1.(A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);noinverse3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB35.(T1,T2,T3)=(A1–QB1,A2–QB2,A3–QB3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto22022/10/3124現(xiàn)代密碼學(xué)理論與實(shí)踐04在域GF(1759)中求550的乘法逆元2022/10/3125現(xiàn)代密碼學(xué)理論與實(shí)踐04計(jì)算乘法逆元素

Computingmultiplicativeinverses

給定a∈[0,n-1],gcd(a,n)=1，若能找到唯一整數(shù)x∈[0,n-1]，滿足：axmodn=1,則稱a和x互逆 如n=10,a=3,x=7,axmodn=1=3x7mod10n=17,a=5,x=7,axmodn=1=5x7mod17

引理4.1:如果gcd(a,n)=1,則對于每個(gè)i,j,0≤i<j<n,

aimodn≠ajmodn

證明：(略)可以用反證法證明 此性質(zhì)意味著每一個(gè)aimodn(i=0,…,n-1)都是不同的模n剩余，而{aimodn}i=0,1,…,n-1是完全剩余集{0,1,…,n-1}的置換形式計(jì)算乘法逆元素axmodn=1,x=a-1=?2022/10/3126現(xiàn)代密碼學(xué)理論與實(shí)踐04例如:n=5,a=3,gcd(3,5)=1,{0,1,…,n-1}={0,1,2,3,4} 3*0mod5=03*1mod5=33*2mod5=13*3mod5=43*4mod5=2{aimodn}i=0,1,…,n-1={0,3,1,4,2}引理4.1說明,當(dāng)gcd(a,n)=1時(shí),a一定有一個(gè)唯一的逆元素。定理4.1如果gcd(a,n)=1,一定存在整數(shù)x,0<x<n，滿足axmodn=1可以用Euclid’s計(jì)算最大公約數(shù)算法的擴(kuò)展來求逆。計(jì)算乘法逆元素2022/10/3127現(xiàn)代密碼學(xué)理論與實(shí)踐04Algorithminv(a,n)begin g0:=n;g1:=a;u0:=1;v0:=0;u1:=0;v1:=1;i:=1 whilegi≠0do“gi=uin+via” begin y:=gi-1divgi; gi+1:=gi-1–y*gi; ui+1:=ui-1–y*ui; vi+1:=vi-1–y*vi; i:=i+1 end x:=vi-1 ifx>=0,theninv:=x,elseinv:=x+nend

gi=uin+via是循環(huán)變量，當(dāng)gi=0時(shí)gi-1=gcd(a,n)。如果gcd(a,n)=1,則gi-1=1，并且vi-1a–1=ui-1n。因此，vi-1amodn=1,vi-1

＝x，就是a的逆元素。用擴(kuò)展的Euclid算法求逆2022/10/3128現(xiàn)代密碼學(xué)理論與實(shí)踐04例：3xmod7=1，

g0:=n;g1:=a;u0:=1;v0:=0;u1:=0;v1:=1

i gi

ui vi yy:=gi-1divgi;gi+1:=gi-1–y*gi 0 7 1 0ui+1:=ui-1–y*ui;vi+1:=vi-1–y*vi 1 3 0 1 2 2 1 1 -2 330因此得到vi-1=-2，x=-2+7=5。例：5xmod49=1，x=10 i gi

ui vi y 049 1 0 1 5 0 1 9 2 4 1-9 1 3 1-110 440因此得到vi-1=10=x。擴(kuò)展的Euclid算法求逆2022/10/3129現(xiàn)代密碼學(xué)理論與實(shí)踐044.5多項(xiàng)式運(yùn)算三種多項(xiàng)式運(yùn)算使用代數(shù)基本規(guī)則的普通多項(xiàng)式運(yùn)算系數(shù)運(yùn)算是模p運(yùn)算的多項(xiàng)式運(yùn)算，即系數(shù)在GF(p)中系數(shù)在GF(p)中，且多項(xiàng)式被定義為模一個(gè)n次多項(xiàng)式m(x)的多項(xiàng)式運(yùn)算普通多項(xiàng)式運(yùn)算一個(gè)n次多項(xiàng)式(n>=0)的表達(dá)形式如下其中ai是某個(gè)指定數(shù)集S中的元素，該數(shù)集稱為系數(shù)集，且an=0，f(x)是定義在系數(shù)集S上的多項(xiàng)式零次多項(xiàng)式稱為常數(shù)多項(xiàng)式，是系數(shù)集里的一個(gè)元素，如果an=1，對應(yīng)的n次多項(xiàng)式就稱為首1多項(xiàng)式2022/10/3130現(xiàn)代密碼學(xué)理論與實(shí)踐04普通多項(xiàng)式運(yùn)算加或減就是相應(yīng)系數(shù)的加減，乘則要用到所有系數(shù)例如letf(x)=x3+x2+2andg(x)=x2–x+1f(x)+g(x)=x3+2x2–x+3f(x)–g(x)=x3+x+1f(x)xg(x)=x5+3x2–2x+2f(x)/g(x)=x+2,……x2022/10/3131現(xiàn)代密碼學(xué)理論與實(shí)踐042022/10/3132現(xiàn)代密碼學(xué)理論與實(shí)踐04系數(shù)在Zp中的多項(xiàng)式運(yùn)算在計(jì)算每個(gè)系數(shù)的值時(shí)需要做模運(yùn)算可以模任何素?cái)?shù)p，但是我們更感興趣的是模2的運(yùn)算也就是說所有的系數(shù)不是0就是1比如，令f(x)=x3+x2,g(x)=x2+x+1

則f(x)+g(x)=x3+x+1

f(x)xg(x)=x5+x22022/10/3133現(xiàn)代密碼學(xué)理論與實(shí)踐042022/10/3134現(xiàn)代密碼學(xué)理論與實(shí)踐04多項(xiàng)式的模運(yùn)算多項(xiàng)式可以寫成如下形式:f(x)=q(x)g(x)+r(x)其中，r(x)就可被看作是余數(shù)r(x)=f(x)modg(x)如果沒有余數(shù)，就稱g(x)可以整除f(x)如果g(x)除了1和它自身以外沒有其他公因式，就稱它是不可約多項(xiàng)式或素多項(xiàng)式irreducibleorprime算術(shù)模運(yùn)算模一個(gè)不可再分的多項(xiàng)式，結(jié)果形成一個(gè)域2022/10/3135現(xiàn)代密碼學(xué)理論與實(shí)踐04求多項(xiàng)式的最大公因式可以為多項(xiàng)式求解最大公因式如果c(x)是可以整除a(x)和b(x)最大公因式，則c(x)=GCD(a(x),b(x))可以用Euclid’sAlgorithm求解多項(xiàng)式最大公因式:EUCLID[a(x),b(x)]1.A(x)?

a(x);B(x)?

b(x)2.ifB(x)=0returnA(x)=gcd[a(x),b(x)]3.

R(x)=A(x)modB(x)4.

A(x)?

B(x)5.

B(x)?

R(x)6.

goto

22022/10/3136現(xiàn)代密碼學(xué)理論與實(shí)踐044.6有限域GF(2n)所有加密算法都涉及到整數(shù)集上的算術(shù)運(yùn)算，如果用到除法，必須使用定義在域上的運(yùn)算。整數(shù)集里的數(shù)與給定的二進(jìn)制位數(shù)所能表達(dá)的信息一一對應(yīng)，即整數(shù)集的范圍從0到2n-1，正好對應(yīng)一個(gè)n位的字。將一個(gè)整數(shù)集不平均地映射到自身的算法用于加密時(shí)可能要弱于一個(gè)提供一一映射的算法，因此，有限域GF(2n)對加密算法是很有吸引力的。所以要尋找一個(gè)包含2n個(gè)元素的集合，其上定義了加法和乘法使之成為一個(gè)域，給集合的每個(gè)元素賦值為0到2n-1之間的唯一整數(shù)，用多項(xiàng)式算術(shù)來構(gòu)造所需的域?？梢允褂脭U(kuò)展的歐幾里德算法來為集合中的元素找到逆元。2022/10/3137現(xiàn)代密碼學(xué)理論與實(shí)踐042022/10/3138現(xiàn)代密碼學(xué)理論與實(shí)踐04多項(xiàng)式模運(yùn)算設(shè)集合S由域Zp上次數(shù)小于等于n-1的所有多項(xiàng)式組成，每個(gè)多項(xiàng)式具有如下形式：其中，ai在集合{0,1,…,p-1}上取值，S共有pn個(gè)不同的多項(xiàng)式當(dāng)p=3,n=2時(shí)，集合中共有32=9個(gè)多項(xiàng)式，分別是

0 x 2x1 x+1 2x+12 x+2 2x+2當(dāng)p=2,n=3時(shí)，集合中共有23=8個(gè)多項(xiàng)式，分別是 0 x+1 x2+x1 x2 x2+x+1x x2+12022/10/3139現(xiàn)代密碼學(xué)理論與實(shí)踐04多項(xiàng)式模運(yùn)算如果定義了合適的運(yùn)算，那么每個(gè)這樣的集合S都是一個(gè)有限域，定義由如下幾條組成：該運(yùn)算遵循基本代數(shù)規(guī)則中的普通多項(xiàng)式運(yùn)算規(guī)則系數(shù)運(yùn)算以p為模，即遵循有限域Zp上的運(yùn)算規(guī)則如果乘法運(yùn)算的結(jié)果是次數(shù)大于n-1的多項(xiàng)式，那么必須將其除以某個(gè)次數(shù)為n的既約多項(xiàng)式m(x)并取余式。對于多項(xiàng)式f(x)，這個(gè)余數(shù)可表示為r(x)=f(x)modm(x)和簡單模運(yùn)算類似，多項(xiàng)式模運(yùn)算也有剩余類集合的概念。設(shè)m(x)為n次多項(xiàng)式，則模m(x)剩余類集合有pn個(gè)元素，每個(gè)元素都可以表示成一個(gè)pn次多項(xiàng)式(m<n)以n次既約多項(xiàng)式m(x)為模的所有多項(xiàng)式組成的集合滿足圖4.1的所有公理，于是可以形成一個(gè)有限域。為構(gòu)造有限域GF(23),需要選擇一個(gè)3次既約多項(xiàng)式：x3+x2+1和x3+x+1,選擇后者則結(jié)果如表4.6所示。2022/10/3140現(xiàn)代密碼學(xué)理論與實(shí)踐042022/10/3141現(xiàn)代密碼學(xué)理論與實(shí)踐04求乘法逆元擴(kuò)展的歐幾里德算法可以用來求一個(gè)多項(xiàng)式的乘法逆元。如果多項(xiàng)式b(x)的次數(shù)小于m(x)且gcd[m(x),b(x)]=1，那么可以求出b(x)以m(x)為模的乘法逆元。擴(kuò)展的EUCLID[m(x),b(x)]1.[A1(x),A2(x),A3(x)]?[1,0,m(x)];[B1(x),B2(x),B3(x)]?[1,0,b(x)]2.ifB3(x)=0returnA3(x)=gcd[m(x),b(x)];noinverse3.ifB3(x)=1returnB3(x)=gcd[m(x),b(x)];B2(x)=b(x)-1modm(x)4.

Q(x)=quotientofA3(x)/B3(x)5.[T1(x),T2(x),T3(x)]?[A1(x),A2(x)-Q(x)B1(x),A2(x)-Q(x)B2(x),A3(x)-Q(x)B3(x)]6.

[A1(x),A2(x),A3(x)]?[B1(x),B2(x),B3(x)]7.

[B1(x),B2(x),B3(x)]?[T1(x),T2(x),T3(x)]8.

goto

22022/10/3142現(xiàn)代密碼學(xué)理論與實(shí)踐04ExtendedEuclid2022/10/3143現(xiàn)代密碼學(xué)理論與實(shí)踐04計(jì)算上的考慮因?yàn)橄禂?shù)不是0就是1,因此GF(2n)中的每個(gè)多項(xiàng)式都可以表示成一個(gè)n位的二進(jìn)制整數(shù)加法其實(shí)就是異或運(yùn)算XOR,兩個(gè)多項(xiàng)式加法等同于按位異或運(yùn)算