網(wǎng)絡(luò)信息安全課件第四章

2023/6/231/51本章要點(diǎn)域是一些元素的集合，其上定義了兩個(gè)算術(shù)運(yùn)算(加法和乘法)，具有常規(guī)算術(shù)性質(zhì)，如封閉性、結(jié)合律、交換律、分配律、加法逆和乘法逆等。模算術(shù)是一種整數(shù)算術(shù)，它將所有整數(shù)約減為一個(gè)固定的集合[0,1,…,n-1]，n為某個(gè)整數(shù)。任何這個(gè)集合外的整數(shù)通過(guò)除以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ù)來(lái)定義。階為pn，n>1的有限域可由多項(xiàng)式算術(shù)來(lái)定義。本文檔共52頁(yè)；當(dāng)前第1頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐042/514.1群,環(huán)和域Groups,Rings,andFields群G,記作{G,?},定義一個(gè)二元運(yùn)算?的集合，G中每一個(gè)序偶(a,b)通過(guò)運(yùn)算生成G中元素(a?b)，滿足下列公理：(A1)封閉性Closure:如果a和b都屬于G,則a?b也屬于G.(A2)結(jié)合律Associative:對(duì)于G中任意元素a,b,c，都有a?(b?c)=(a?b)?c成立(A3)單位元Identityelement:G中存在一個(gè)元素e，對(duì)于G中任意元素a，都有a?e=e?a=a成立(A4)逆元Inverseelement:對(duì)于G中任意元素a,G中都存在一個(gè)元素a’，使得a?a’=a’?a=e成立本文檔共52頁(yè)；當(dāng)前第2頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐043/51群、有限群和無(wú)限群用Nn表示n個(gè)不同符號(hào)的集合，{1,2,…,n}.n個(gè)不同符號(hào)的一個(gè)置換是一個(gè)Nn到Nn的一一映射。定義Sn為n個(gè)不同符號(hào)的所有置換組成的集合。Sn中的每一個(gè)元素都代表集合{1,2,…,n}的一個(gè)置換，容易驗(yàn)證Sn是一個(gè)群：A1：如果π,ρ∈Sn，則合成映射π?ρ根據(jù)置換π來(lái)改變?chǔ)阎性氐拇涡蚨纬桑?，{3,2,1}?{1,3,2}={2,3,1},顯然π?ρ∈SnA2：映射的合成顯而易見(jiàn)滿足結(jié)合律A3：恒等映射就是不改變n個(gè)元素位置的置換，對(duì)于Sn，單位元是{1,2,…,n}A4：對(duì)于任意π∈Sn，抵消由π定義置換的映射就是π的逆元，這個(gè)逆元總是存在，例如：{2,3,1}?{3,1,2}={1,2,3},有限群FiniteGroup和無(wú)限群InfiniteGroup：如果一個(gè)群的元素是有限的，則該群稱為有限群，且群的階等于群中元素的個(gè)數(shù)；否則稱為無(wú)限群本文檔共52頁(yè)；當(dāng)前第3頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐044/51交換群和循環(huán)群交換群AbelianGroup：還滿足以下條件的群稱為交換群(又稱阿貝爾群)(A5)交換律Commutative：對(duì)于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，或者說(shuō)a是群G的生成元。本文檔共52頁(yè)；當(dāng)前第4頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐045/51環(huán)(Rings)環(huán)R,由{R,+,x}表示,是具有加法和乘法兩個(gè)二元運(yùn)算的元素的集合，對(duì)于環(huán)中的所有a,b,c,都服從以下公理：(A1-A5),單位元是0，a的逆是-a.(M1),乘法封閉性,如果a和b屬于R,則ab也屬于R(M2),乘法結(jié)合律,對(duì)于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),無(wú)零因子,如果R中有a,b且ab=0,則a=0orb=0.滿足M4的是交換環(huán)；滿足M5和M6的交換環(huán)是整環(huán)本文檔共52頁(yè)；當(dāng)前第5頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐046/51域(Fields)域F,可以記為{F,+,x},是有加法和乘法的兩個(gè)二元運(yùn)算的元素的集合，對(duì)于F中的任意元素a,b,c,滿足以下公理：(A1-M6),F是一個(gè)整環(huán)(M7),乘法逆元,對(duì)于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有乘法逆元，其他元素都無(wú)乘法逆元本文檔共52頁(yè)；當(dāng)前第6頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐047/51群、環(huán)和域的關(guān)系本文檔共52頁(yè)；當(dāng)前第7頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐048/514.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=3本文檔共52頁(yè)；當(dāng)前第8頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐049/51因子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,則對(duì)任何整數(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|a本文檔共52頁(yè)；當(dāng)前第9頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0410/51同余(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*7a≡nb

當(dāng)且僅當(dāng)amodn=bmodn如果a是整數(shù)，n是正整數(shù)，定義a除以n所得之余數(shù)為a模n。對(duì)于任意整數(shù)a，我們總可寫出：a=?a/n」xn+(amodn)11mod7=4; -11mod7=3如果(amodn)=(bmodn),則稱整數(shù)a和b是模n同余，表示為a≡bmodn或a≡nb73≡4mod23； 21≡-9mod10本文檔共52頁(yè)；當(dāng)前第10頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0411/51同余的性質(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

本文檔共52頁(yè)；當(dāng)前第11頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0412/51(a1opa2)modn=[(a1modn)]op(a2modn)]modn①反身性：a=amodn②對(duì)稱性：若a=bmodn，則b=amodn③傳遞性:若a=bmodn且b=cmodn，則a=cmodn④如果a=bmodn且c=dmodn，則

a+c=(b+d)modna-c=(b-d)modna?c=(b?d)modn⑤(a+b)modn=(amodn+bmodn)modn(a-b)modn=(amodn-bmodn)modn(a?b)modn=(amodn?bmodn)modn

模算術(shù)運(yùn)算本文檔共52頁(yè)；當(dāng)前第12頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0413/51

(a+b)modn=(amodn+bmodn)modn

證明：定義(amodn)=ra,(bmodn)=rb于是存在整數(shù)j,k使得a=ra+jn,b=rb+kn.那么(a+b)modn=(ra+jn+rb+kn)modn=(ra+rb+(k+j)n)modn=(ra+rb)modn=[(amodn)+(bmodn)]modn

模算術(shù)運(yùn)算本文檔共52頁(yè)；當(dāng)前第13頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0414/51本文檔共52頁(yè)；當(dāng)前第14頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0415/51加法逆元和乘法逆元加法逆元(-w)對(duì)每一個(gè)w∈Zn，存在一個(gè)z，使得w+z≡0modn，則z即為加法逆元-w乘法逆元(w-1)對(duì)每一個(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互素。本文檔共52頁(yè)；當(dāng)前第15頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0416/51剩余集(Residues)定義比n小的非負(fù)整數(shù)集合為Zn：Zn

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

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

CompleteSetofResiduesmodn如果對(duì)每個(gè)整數(shù)a，在集合{r1,r2,…,rn}中恰有一個(gè)余數(shù)ri,使得a=rimodn,則稱{r1,r2,…,rn}為模n的完全剩余集，{0,1,…,n-1}形成模n的完全剩余集。

模算術(shù)的性質(zhì)本文檔共52頁(yè)；當(dāng)前第16頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0417/51模算術(shù)的性質(zhì)(2)模n的縮剩余集(ReducedsetofResiduesmodn)完全剩余集的一個(gè)子集，指的是集合中的元素都和n互素例:n=10，模n的完全剩余集是{0,1,2,…,9}，縮剩余集是{1,3,7,9}本文檔共52頁(yè)；當(dāng)前第17頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0418/51數(shù)論的一個(gè)最基本的技巧是Euclid算法，求兩個(gè)正整數(shù)的最大公約數(shù)gcd(a,n),greatestcommondivisor對(duì)于任何非負(fù)的整數(shù)a和n，gcd(a,n)=gcd(nmoda,a)假設(shè)我們有整數(shù)a,b使得d=gcd(a,b)。假設(shè)a≥b>0，現(xiàn)在用b除a，由除法可得到a=q1b+r10≤r1<b如果恰巧r1=0，則b|a且d=gcd(a,b)=b。但是如果r1≠0,我們說(shuō)d|r1。這基于除法的基本性質(zhì)：由d|a和d|b可以推出d|(a-q1b)，即d|r1。現(xiàn)在假設(shè)有任意的整數(shù)c整除b和r1.因此c|(q1b+r1)=a。因此c同時(shí)整除a和b，必須有c≤d，而d是a和b的最大公因子。因此d=gcd(b,r1)。4.3歐幾里得算法EuclidAlgorithm本文檔共52頁(yè)；當(dāng)前第18頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0419/51a=q1b+r10≤r1<b假設(shè)r1≠0.因?yàn)閎>r1，可以用r1除b，應(yīng)用除法有b=q2r1+r20≤r2<r1如前所述，如果r2=0，則d=r1.如果r2≠0，則d=gcd(r1,r2)。繼續(xù)除法過(guò)程直到余數(shù)為0，比如說(shuō)在第(n+1)階段有rn整除r(n-1)。結(jié)果為如下的方程系統(tǒng)：4.3歐幾里得算法EuclidAlgorithm本文檔共52頁(yè)；當(dāng)前第19頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分使d等于gcd(a,b),根據(jù)gcd的定義，有d|a和d|b成立。對(duì)于任意正整數(shù)b,a可以表示為如下形式：a=kb+r≡r(modb)amodb=r其中k,r為整數(shù)。因此，對(duì)某個(gè)整數(shù)k,有(amodb)=a-kb.因?yàn)閐|b，所以有d|kb；又因?yàn)閐|a，所以有d|(amodb).這說(shuō)明d是b和(amodb)的公因子。反之，如果d是b和(amodb)的公因子，那么d|kb并且由此可知d|[kb+(amodb)],即d|a.因此，a和b的公因子的集合與b和(amodb)的公因子的集合相等。gcd(a,b)=gcd(b,amodb)2023/6/2320/41本文檔共52頁(yè)；當(dāng)前第20頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0421/51Example:

求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)=2本文檔共52頁(yè)；當(dāng)前第21頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0422/51對(duì)于給定的整數(shù)a和b，擴(kuò)展的Euclid算法不僅計(jì)算出最大公因子d，而且還有另外的整數(shù)x和y，它們滿足如下方程：ax+by=d=gcd(a,b)用擴(kuò)展的Euclid算法計(jì)算(x,y,d).假設(shè)在每一步驟i都可以找到xi和yi滿足ri=axi+byi。4.3擴(kuò)展的Euclid算法本文檔共52頁(yè)；當(dāng)前第22頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0423/51從原始的Euclid算法知該過(guò)程當(dāng)余數(shù)為0時(shí)結(jié)束，求得a和b的最大公因子為d=gcd(a,b)=rn.我們也決定了4.3擴(kuò)展的Euclid算法本文檔共52頁(yè)；當(dāng)前第23頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0424/514.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)最簡(jiǎn)單的有限域是GF(2)，它的代數(shù)運(yùn)算簡(jiǎn)述如下：+01x01w-ww-100100000110101111

加乘求逆本文檔共52頁(yè)；當(dāng)前第24頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0425/51GaloisFieldsGF(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ù)都有乘法逆元對(duì)每一個(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è)有限域。本文檔共52頁(yè)；當(dāng)前第25頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0426/51本文檔共52頁(yè)；當(dāng)前第26頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0427/51計(jì)算乘法逆元素Computingmultiplicativeinverses

axmodn=1,x=a-1=? 給定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,則對(duì)于每個(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ì)算乘法逆元素本文檔共52頁(yè)；當(dāng)前第27頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0428/51例如: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說(shuō)明，當(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ò)展來(lái)求逆。計(jì)算乘法逆元素本文檔共52頁(yè)；當(dāng)前第28頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0429/51如果a和b互素，則b有模a的乘法逆元。也就是說(shuō)，如果gcd(a,b)=1,那么b有模a的乘法逆元。即對(duì)于正整數(shù)b<a,存在b-1<a使bb-1=1moda.如果a是素?cái)?shù)并且b<a，則顯然a和b互素，且最大公因子為1.我們已經(jīng)證明過(guò)該式可以用擴(kuò)展Euclid算法來(lái)解：ax+by=d=gcd(a,b)如果gcd(a,b)=1,則有ax+by=1.[(axmoda)+(bymoda)]moda=1moda0+(bymoda)=1如果bymoda=1，則y=b-1.擴(kuò)展的Euclid算法求逆本文檔共52頁(yè)；當(dāng)前第29頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0430/514.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，對(duì)應(yīng)的n次多項(xiàng)式就稱為首1多項(xiàng)式本文檔共52頁(yè)；當(dāng)前第30頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0431/51普通多項(xiàng)式運(yùn)算加或減就是相應(yīng)系數(shù)的加減，乘則要用到所有系數(shù)Ex.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,……x本文檔共52頁(yè)；當(dāng)前第31頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0432/51本文檔共52頁(yè)；當(dāng)前第32頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0433/51系數(shù)在Zp中的多項(xiàng)式運(yùn)算在計(jì)算每個(gè)系數(shù)的值時(shí)需要做模運(yùn)算可以模任何素?cái)?shù)p，但是我們更感興趣的是模2的運(yùn)算也就是說(shuō)所有的系數(shù)不是0就是1比如，令f(x)=x3+x2,g(x)=x2+x+1

則f(x)+g(x)=x3+x+1f(x)xg(x)=x5+x2本文檔共52頁(yè)；當(dāng)前第33頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0434/51本文檔共52頁(yè)；當(dāng)前第34頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0435/51多項(xiàng)式的模運(yùn)算多項(xiàng)式可以寫成如下形式:f(x)=q(x)g(x)+r(x)其中，r(x)就可被看作是余數(shù)r(x)=f(x)modg(x)如果沒(méi)有余數(shù)，就稱g(x)可以整除f(x)如果g(x)除了1和它自身以外沒(méi)有其他公因式，就稱它是不可約多項(xiàng)式或素多項(xiàng)式irreducibleorprime本文檔共52頁(yè)；當(dāng)前第35頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0436/51求多項(xiàng)式的最大公因式可以為多項(xiàng)式求解最大公因式如果c(x)是可以整除a(x)和b(x)最大公因式，則c(x)=GCD(a(x),b(x))可以用Euclid’sAlgorithm來(lái)求解多項(xiàng)式最大公因式:gcd[a(x),b(x)]=gcd[b(x),a(x)modb(x)]=gcd[r1(x),b(x)modr1(x)]=gcd[r2(x),r1(x)modr2(x)]……本文檔共52頁(yè)；當(dāng)前第36頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0437/51求多項(xiàng)式的最大公因式本文檔共52頁(yè)；當(dāng)前第37頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0438/51求多項(xiàng)式的最大公因式本文檔共52頁(yè)；當(dāng)前第38頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0439/51求多項(xiàng)式的最大公因式本文檔共52頁(yè)；當(dāng)前第39頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0440/514.6有限域GF(2n)所有加密算法都涉及到整數(shù)集上的算術(shù)運(yùn)算，如果用到除法，必須使用定義在域上的運(yùn)算。整數(shù)集里的數(shù)與給定的二進(jìn)制位數(shù)所能表達(dá)的信息一一對(duì)應(yīng)，即整數(shù)集的范圍從0到2n-1，正好對(duì)應(yīng)一個(gè)n位的字。將一個(gè)整數(shù)集不平均地映射到自身的算法用于加密時(shí)可能要弱于一個(gè)提供一一映射的算法，因此，有限域GF(2n)對(duì)加密算法是很有吸引力的。所以要尋找一個(gè)包含2n個(gè)元素的集合，其上定義了加法和乘法使之成為一個(gè)域，給集合的每個(gè)元素賦值為0到2n-1之間的唯一整數(shù)，用多項(xiàng)式算術(shù)來(lái)構(gòu)造所需的域?？梢允褂脭U(kuò)展的歐幾里德算法來(lái)為集合中的元素找到逆元。本文檔共52頁(yè)；當(dāng)前第40頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0441/51本文檔共52頁(yè)；當(dāng)前第41頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0442/51多項(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+1本文檔共52頁(yè)；當(dāng)前第42頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0443/51多項(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)并取余式。對(duì)于多項(xiàng)式f(x)，這個(gè)余數(shù)可表示為r(x)=f(x)modm(x)和簡(jiǎn)單模運(yùn)算類似，多項(xiàng)式模運(yùn)算也有剩余類集合的概念。設(shè)m(x)為n次多項(xiàng)式，則模m(x)剩余類集合有pn個(gè)元素，每個(gè)元素都可以表示成一個(gè)m次多項(xiàng)式(m<n)以m(x)為模的剩余類[x+1]由所有滿足a(x)≡(x+1)(mod(x))的多項(xiàng)式a(x)組成。也就是說(shuō)，剩余類[x+1]中的所有多項(xiàng)式a(x)滿足等式a(x)modm(x)=x+1。本文檔共52頁(yè)；當(dāng)前第43頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0444/51多項(xiàng)式模運(yù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所示。本文檔共52頁(yè)；當(dāng)前第44頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0445/51加法運(yùn)算，例如100+010=110，這等價(jià)于x2+x。本文檔共52頁(yè)；當(dāng)前第45頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0446/51多項(xiàng)式模運(yùn)算對(duì)于乘法運(yùn)算，例如：100×010=011，這等價(jià)于x2×x=x3，約減后為x+1。本文檔共52頁(yè)；當(dāng)前第46頁(yè)；編輯于星期日\(chéng)23點(diǎn)3分2023/6/23現(xiàn)代密碼學(xué)理論與實(shí)踐0447/51求乘法逆元擴(kuò)展的歐幾里德算法可以用來(lái)求一個(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)