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

網(wǎng)絡(luò)信息安全

Chapter4

FiniteFields2023/7/221標(biāo)題添加點擊此處輸入相關(guān)文本內(nèi)容點擊此處輸入相關(guān)文本內(nèi)容總體概述點擊此處輸入相關(guān)文本內(nèi)容標(biāo)題添加點擊此處輸入相關(guān)文本內(nèi)容2本章要點域是一些元素的集合，其上定義了兩個算術(shù)運算(加法和乘法)，具有常規(guī)算術(shù)性質(zhì)，如封閉性、結(jié)合律、交換律、分配律、加法逆和乘法逆等。模算術(shù)是一種整數(shù)算術(shù)，它將所有整數(shù)約減為一個固定的集合[0,1,…,n-1]，n為某個整數(shù)。任何這個集合外的整數(shù)通過除以n取余的方式約減到這個范圍內(nèi)。兩個整數(shù)的最大公因子是可以整除這兩個整數(shù)的最大正整數(shù)。一個有限域就是有有限個元素的域。可以證明有限域的階(元素個數(shù))一定可以寫作素數(shù)的冪形式pn，n為一個整數(shù)，p為素數(shù)。階為p的有限域可以由模p的算術(shù)來定義。階為pn，n>1的有限域可由多項式算術(shù)來定義。2023/7/2234.1群,環(huán)和域Groups,Rings,andFields群G,記作{G,?},定義一個二元運算?的集合，G中每一個序偶(a,b)通過運算生成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中存在一個元素e，對于G中任意元素a，都有a?e=e?a=a成立(A4)逆元Inverseelement:對于G中任意元素a,G中都存在一個元素a’，使得a?a’=a’?a=e成立2023/7/224群、有限群和無限群用Nn表示n個不同符號的集合，{1,2,…,n}.n個不同符號的一個置換是一個Nn到Nn的一一映射。定義Sn為n個不同符號的所有置換組成的集合。Sn中的每一個元素都代表集合{1,2,…,n}的一個置換，容易驗證Sn是一個群：A1：如果π,ρ∈Sn，則合成映射π?ρ根據(jù)置換π來改變ρ中元素的次序而形成，如，{3,2,1}?{1,3,2}={2,3,1},顯然π?ρ∈SnA2：映射的合成顯而易見滿足結(jié)合律A3：恒等映射就是不改變n個元素位置的置換，對于Sn，單位元是{1,2,…,n}A4：對于任意π∈Sn，抵消由π定義置換的映射就是π的逆元，這個逆元總是存在，例如：{2,3,1}?{3,1,2}={1,2,3},有限群FiniteGroup和無限群InfiniteGroup：如果一個群的元素是有限的，則該群稱為有限群，且群的階等于群中元素的個數(shù)；否則稱為無限群2023/7/225交換群和循環(huán)群交換群AbelianGroup：還滿足以下條件的群稱為交換群(又稱阿貝爾群)(A5)交換律Commutative：對于G中任意的元素a,b，都有a?b=b?a成立當(dāng)群中的運算符是加法時，其單位元是0；a的逆元是-a,并且減法用以下的規(guī)則定義：a–b=a+(-b)循環(huán)群CyclicGroup如果群中的每一個元素都是一個固定的元素a(a∈G)的冪ak(k為整數(shù))，則稱群G為循環(huán)群。元素a生成了群G，或者說a是群G的生成元。2023/7/226環(huán)(Rings)環(huán)R,由{R,+,x}表示,是具有加法和乘法兩個二元運算的元素的集合，對于環(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)2023/7/227域(Fields)域F,可以記為{F,+,x},是有加法和乘法的兩個二元運算的元素的集合，對于F中的任意元素a,b,c,滿足以下公理：(A1-M6),F是一個整環(huán)(M7),乘法逆元,對于F中的任意元素a(除0以外),F中都存在一個元素a-1,使得aa-1=(a-1)a=1.域就是一個集合，在其上進(jìn)行加減乘除而不脫離該集合,除法按以下規(guī)則定義:a/b=a(b-1).有理數(shù)集合,實數(shù)集合和復(fù)數(shù)集合都是域；整數(shù)集合不是域，因為除了1和-1有乘法逆元，其他元素都無乘法逆元2023/7/228群、環(huán)和域的關(guān)系2023/7/2294.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=32023/7/2210因子Divisors如果a=mb,其中a,b,m為整數(shù)，則當(dāng)b≠0時，即b能整除a,或a除以b余數(shù)為0,b|a.b是a的一個因子。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|a2023/7/2211同余(congruence)給定整數(shù)a,b及n≠0,當(dāng)且僅當(dāng)a-b=kn時，a與b在模n時同余，記為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。對于任意整數(shù)a，我們總可寫出：a=?a/n」xn+(amodn)11mod7=4; -11mod7=3如果(amodn)=(bmodn),則稱整數(shù)a和b是模n同余，表示為a≡bmodn或a≡nb73≡4mod23； 21≡-9mod102023/7/2212同余的性質(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)，因為23-8=15=5x3-11≡5(mod8)，因為-11-5=-16=8x(-2)81≡0(mod27)，因為81-0=81=27x3

2023/7/2213(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)modna?c=(b?d)modn⑤(a+b)modn=(amodn+bmodn)modn(a-b)modn=(amodn-bmodn)modn(a?b)modn=(amodn?bmodn)modn

模算術(shù)運算2023/7/2214

(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ù)運算2023/7/22152023/7/2216加法逆元和乘法逆元加法逆元(-w)對每一個w∈Zn，存在一個z，使得w+z≡0modn，則z即為加法逆元-w乘法逆元(w-1)對每一個w∈Zp，存在一個z，使得wxz≡1modp，p為素數(shù)，w與p互素，則z即為乘法逆元w-1因為w與p互素，如果用w乘以Zp中的所有數(shù)模p，得到的余數(shù)將以不同次序涵蓋Zp中的所有數(shù)，那么至少有一個余數(shù)的值為1。因此，在Zp中的某個數(shù)與w相乘模p的余數(shù)為1,這個數(shù)就是w的乘法逆元,w-1某些但非全部整數(shù)存在一個乘法逆元就將使模數(shù)不再是素數(shù)。如果gcd(a,n)=1,則能在Zn中找到b，使得axb≡1modn，則b即為乘法逆元a-1,因為a與n互素。2023/7/2217剩余集(Residues)定義比n小的非負(fù)整數(shù)集合為Zn：Zn

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

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

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

模算術(shù)的性質(zhì)2023/7/2218模算術(shù)的性質(zhì)(2)模n的縮剩余集(ReducedsetofResiduesmodn)完全剩余集的一個子集，指的是集合中的元素都和n互素例:n=10，模n的完全剩余集是{0,1,2,…,9}，縮剩余集是{1,3,7,9}2023/7/2219數(shù)論的一個最基本的技巧是Euclid算法，求兩個正整數(shù)的最大公約數(shù)gcd(a,n),greatestcommondivisor對于任何非負(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,我們說d|r1。這基于除法的基本性質(zhì)：由d|a和d|b可以推出d|(a-q1b)，即d|r1?，F(xiàn)在假設(shè)有任意的整數(shù)c整除b和r1.因此c|(q1b+r1)=a。因此c同時整除a和b，必須有c≤d，而d是a和b的最大公因子。因此d=gcd(b,r1)。4.3歐幾里得算法EuclidAlgorithm2023/7/2220a=q1b+r10≤r1<b假設(shè)r1≠0.因為b>r1，可以用r1除b，應(yīng)用除法有b=q2r1+r20≤r2<r1如前所述，如果r2=0，則d=r1.如果r2≠0，則d=gcd(r1,r2)。繼續(xù)除法過程直到余數(shù)為0，比如說在第(n+1)階段有rn整除r(n-1)。結(jié)果為如下的方程系統(tǒng)：4.3歐幾里得算法EuclidAlgorithm2023/7/2221使d等于gcd(a,b),根據(jù)gcd的定義，有d|a和d|b成立。對于任意正整數(shù)b,a可以表示為如下形式：a=kb+r≡r(modb)amodb=r其中k,r為整數(shù)。因此，對某個整數(shù)k,有(amodb)=a-kb.因為d|b，所以有d|kb；又因為d|a，所以有d|(amodb).這說明d是b和(amodb)的公因子。反之，如果d是b和(amodb)的公因子，那么d|kb并且由此可知d|[kb+(amodb)],即d|a.因此，a和b的公因子的集合與b和(amodb)的公因子的集合相等。gcd(a,b)=gcd(b,amodb)2023/7/2222Example:

求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)=22023/7/2223對于給定的整數(shù)a和b，擴(kuò)展的Euclid算法不僅計算出最大公因子d，而且還有另外的整數(shù)x和y，它們滿足如下方程：ax+by=d=gcd(a,b)用擴(kuò)展的Euclid算法計算(x,y,d).假設(shè)在每一步驟i都可以找到xi和yi滿足ri=axi+byi。4.3擴(kuò)展的Euclid算法2023/7/2224從原始的Euclid算法知該過程當(dāng)余數(shù)為0時結(jié)束，求得a和b的最大公因子為d=gcd(a,b)=rn.我們也決定了4.3擴(kuò)展的Euclid算法2023/7/22254.4有限域GF(p)GaloisFields有限域在密碼學(xué)中扮演重要角色有限域的階(元素個數(shù))必須是一個素數(shù)的冪pn,n為正整數(shù)。元素個數(shù)是pn的有限域一般記為GF(pn)，即Galoisfields,模pn.關(guān)注兩種特殊情形，n=1時的有限域和p為2時的有限域，即GF(p)和GF(2n)最簡單的有限域是GF(2)，它的代數(shù)運算簡述如下：+01x01w-ww-100100000110101111

加乘求逆2023/7/2226GaloisFieldsGF(p)階為p的有限域GF(p)給定一個素數(shù)p，元素個數(shù)為p的有限域GF(p)被定義為整數(shù){0,1,…,p-1}的集合Zp，其運算為模p的算術(shù)運算Zn中的任一整數(shù)有乘法逆元當(dāng)且僅當(dāng)該整數(shù)與n互素，若n為素數(shù)，Zn中的所有非零整數(shù)都與n互素，因此Zn中所有非零整數(shù)都有乘法逆元對每一個w∈Zp，存在一個z，使得w×z≡1modp，則z即為乘法逆元w-1因為w與p互素，如果用w乘以Zp中的所有數(shù)模p，得到的余數(shù)將以不同次序涵蓋Zp中的所有數(shù)，即余數(shù)集合是{0,1,…,p-1}的置換形，那么至少有一個余數(shù)的值為1。因此，在Zp中的某個數(shù)與w相乘模p的余數(shù)為1,這個數(shù)就是w的乘法逆元，w-1。所以，Zp是一個有限域。2023/7/22272023/7/2228計算乘法逆元素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,則對于每個i,j,0≤i<j<n, aimodn≠ajmodn

證明：(略)可以用反證法證明 此性質(zhì)意味著每一個aimodn(i=0,…,n-1)都是不同的模n剩余，而{aimodn}i=0,1,…,n-1是完全剩余集{0,1,…,n-1}的置換形式計算乘法逆元素2023/7/2229例如: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時，a一定有一個唯一的逆元素。定理4.1如果gcd(a,n)=1,一定存在整數(shù)x,0<x<n，滿足axmodn=1可以用Euclid’s計算最大公約數(shù)算法的擴(kuò)展來求逆。計算乘法逆元素2023/7/2230如果a和b互素，則b有模a的乘法逆元。也就是說，如果gcd(a,b)=1,那么b有模a的乘法逆元。即對于正整數(shù)b<a,存在b-1<a使bb-1=1moda.如果a是素數(shù)并且b<a，則顯然a和b互素，且最大公因子為1.我們已經(jīng)證明過該式可以用擴(kuò)展Euclid算法來解：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算法求逆2023/7/22314.5多項式運算三種多項式運算使用代數(shù)基本規(guī)則的普通多項式運算系數(shù)運算是模p運算的多項式運算，即系數(shù)在GF(p)中系數(shù)在GF(p)中，且多項式被定義為模一個n次多項式m(x)的多項式運算普通多項式運算一個n次多項式(n>=0)的表達(dá)形式如下其中ai是某個指定數(shù)集S中的元素，該數(shù)集稱為系數(shù)集，且an≠0，f(x)是定義在系數(shù)集S上的多項式零次多項式稱為常數(shù)多項式，是系數(shù)集里的一個元素，如果an=1，對應(yīng)的n次多項式就稱為首1多項式2023/7/2232普通多項式運算加或減就是相應(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,……x2023/7/22332023/7/2234系數(shù)在Zp中的多項式運算在計算每個系數(shù)的值時需要做模運算可以模任何素數(shù)p，但是我們更感興趣的是模2的運算也就是說所有的系數(shù)不是0就是1比如，令f(x)=x3+x2,g(x)=x2+x+1

則f(x)+g(x)=x3+x+1f(x)xg(x)=x5+x22023/7/22352023/7/2236多項式的模運算多項式可以寫成如下形式: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和它自身以外沒有其他公因式，就稱它是不可約多項式或素多項式irreducibleorprime2023/7/2237求多項式的最大公因式可以為多項式求解最大公因式如果c(x)是可以整除a(x)和b(x)最大公因式，則c(x)=GCD(a(x),b(x))可以用Euclid’sAlgorithm來求解多項式最大公因式: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)]……2023/7/2238求多項式的最大公因式2023/7/2239求多項式的最大公因式2023/7/2240求多項式的最大公因式2023/7/22414.6有限域GF(2n)所有加密算法都涉及到整數(shù)集上的算術(shù)運算，如果用到除法，必須使用定義在域上的運算。整數(shù)集里的數(shù)與給定的二進(jìn)制位數(shù)所能表達(dá)的信息一一對應(yīng)，即整數(shù)集的范圍從0到2n-1，正好對應(yīng)一個n位的字。將一個整數(shù)集不平均地映射到自身的算法用于加密時可能要弱于一個提供一一映射的算法，因此，有限域GF(2n)對加密算法是很有吸引力的。所以要尋找一個包含2n個元素的集合，其上定義了加法和乘法使之成為一個域，給集合的每個元素賦值為0到2n-1之間的唯一整數(shù)，用多項式算術(shù)來構(gòu)造所需的域。可以使用擴(kuò)展的歐幾里德算法來為集合中的元素找到逆元。2023/7/22422023/7/2243多項式模運算設(shè)集合S由域Zp上次數(shù)小于等于n-1的所有多項式組成，每個多項式具有如下形式：其中，ai在集合{0,1,…,p-1}上取值，S共有pn個不同的多項式當(dāng)p=3,n=2時，集合中共有32=9個多項式，分別是

0 x 2x1 x+1 2x+12 x+2 2x+2當(dāng)p=2,n=3時，集合中共有23=8個多項式，分別是 0 x+1 x2+x1 x2 x2+x+1x x2+12023/7/2244多項式模運算如果定義了合適的運算，那么每個這樣的集合S都是一個有限域，定義由如下幾條組成：該運算遵循基本代數(shù)規(guī)則中的普通多項式運算規(guī)則系數(shù)運算以p為模，即遵循有限域Zp上的運算規(guī)則如果乘法運算的結(jié)果是次數(shù)大于n-1的多項式，那么必須將其除以某個次數(shù)為n的既約多項式m(x)并取余式。對于多項式f(x)，這個余數(shù)可表示為r(x)=f(x)modm(x)和簡單模運算類似，多項式模運算也有剩余類集合的概念。設(shè)m(x)為n次多項式，則模m(x)剩余類集合有pn個元素，每個元素都可以表示成一個m次多項式(m<n)以m(x)為模的剩余類[x+1]由所有滿足a(x)≡(x+1)(mod(x))的多項式a(x)組成。也就是說，剩余類[x+1]中的所有多項式a(x)滿足等式a(x)modm(x)=x+1。2023/7/2245多項式模運算以n次既約多項式m(x)為模的所有多項式組成的集合滿足圖4.1的所有公理，于是可以形成一個有限域。為構(gòu)造有限域GF(23)，需要選擇一個3次既約多項式：x3+x2+1或x3+x+1,選擇后者則結(jié)果如表4.6所示。2023/7/2246加法運算，例如100+010=110，這等價于x2+x。2023/7/2247多項式模運算對于乘法運算，例如：100×010=011，這等價于x2×x=x3，約減后為x+1。2023/7/2248求乘法逆元擴(kuò)展的歐幾里德算法可以用來求一個多項式的乘法逆元。如果多項式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.goto22023/7/2249ExtendedEuclid2023/7/2250計算上的考慮因為系數(shù)