2023/3/91/51本章要點域是一些元素的集合，其上定義了兩個算術運算(加法和乘法)，具有常規算術性質，如封閉性、結合律、交換律、分配律、加法逆和乘法逆等。模算術是一種整數算術，它將所有整數約減為一個固定的集合[0,1,…,n-1]，n為某個整數。任何這個集合外的整數通過除以n取余的方式約減到這個范圍內。兩個整數的最大公因子是可以整除這兩個整數的最大正整數。一個有限域就是有有限個元素的域。可以證明有限域的階(元素個數)一定可以寫作素數的冪形式pn，n為一個整數，p為素數。階為p的有限域可以由模p的算術來定義。階為pn，n>1的有限域可由多項式算術來定義。當前1頁，總共52頁。2023/3/9現代密碼學理論與實踐042/514.1群,環和域Groups,Rings,andFields群G,記作{G,?},定義一個二元運算?的集合，G中每一個序偶(a,b)通過運算生成G中元素(a?b)，滿足下列公理：(A1)封閉性Closure:如果a和b都屬于G,則a?b也屬于G.(A2)結合律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成立當前2頁，總共52頁。2023/3/9現代密碼學理論與實踐043/51群、有限群和無限群用Nn表示n個不同符號的集合，{1,2,…,n}.n個不同符號的一個置換是一個Nn到Nn的一一映射。定義Sn為n個不同符號的所有置換組成的集合。Sn中的每一個元素都代表集合{1,2,…,n}的一個置換，容易驗證Sn是一個群：A1：如果π,ρ∈Sn，則合成映射π?ρ根據置換π來改變ρ中元素的次序而形成，如，{3,2,1}?{1,3,2}={2,3,1},顯然π?ρ∈SnA2：映射的合成顯而易見滿足結合律A3：恒等映射就是不改變n個元素位置的置換，對于Sn，單位元是{1,2,…,n}A4：對于任意π∈Sn，抵消由π定義置換的映射就是π的逆元，這個逆元總是存在，例如：{2,3,1}?{3,1,2}={1,2,3},有限群FiniteGroup和無限群InfiniteGroup：如果一個群的元素是有限的，則該群稱為有限群，且群的階等于群中元素的個數；否則稱為無限群當前3頁，總共52頁。2023/3/9現代密碼學理論與實踐044/51交換群和循環群交換群AbelianGroup：還滿足以下條件的群稱為交換群(又稱阿貝爾群)(A5)交換律Commutative：對于G中任意的元素a,b，都有a?b=b?a成立當群中的運算符是加法時，其單位元是0；a的逆元是-a,并且減法用以下的規則定義：a–b=a+(-b)循環群CyclicGroup如果群中的每一個元素都是一個固定的元素a(a∈G)的冪ak(k為整數)，則稱群G為循環群。元素a生成了群G，或者說a是群G的生成元。當前4頁，總共52頁。2023/3/9現代密碼學理論與實踐045/51環(Rings)環R,由{R,+,x}表示,是具有加法和乘法兩個二元運算的元素的集合，對于環中的所有a,b,c,都服從以下公理：(A1-A5),單位元是0，a的逆是-a.(M1),乘法封閉性,如果a和b屬于R,則ab也屬于R(M2),乘法結合律,對于R中任意a,b,c有a(bc)=(ab)c.(M3),乘法分配律,a(b+c)=ab+acor(a+b)c=ac+bc(M4),乘法交換律,ab=ba，交換環(M5),乘法單位元,R中存在元素1使得所有a有a1=1a.(M6),無零因子,如果R中有a,b且ab=0,則a=0orb=0.滿足M4的是交換環；滿足M5和M6的交換環是整環當前5頁，總共52頁。2023/3/9現代密碼學理論與實踐046/51域(Fields)域F,可以記為{F,+,x},是有加法和乘法的兩個二元運算的元素的集合，對于F中的任意元素a,b,c,滿足以下公理：(A1-M6),F是一個整環(M7),乘法逆元,對于F中的任意元素a(除0以外),F中都存在一個元素a-1,使得aa-1=(a-1)a=1.域就是一個集合，在其上進行加減乘除而不脫離該集合,除法按以下規則定義:a/b=a(b-1).有理數集合,實數集合和復數集合都是域；整數集合不是域，因為除了1和-1有乘法逆元，其他元素都無乘法逆元當前6頁，總共52頁。2023/3/9現代密碼學理論與實踐047/51群、環和域的關系當前7頁，總共52頁。2023/3/9現代密碼學理論與實踐048/514.2ModularArithmetic給定任意正整數n和a，如果用a除以n，得到的商q和余數r滿足如下關系:

a=qn+r0≤r<n;q=?a/n」?x」表示小于等于x的最大整數Eg:11=1x7+4,r=4;-11=(-2)x7+3,r=3當前8頁，總共52頁。2023/3/9現代密碼學理論與實踐049/51因子Divisors如果a=mb,其中a,b,m為整數，則當b≠0時，即b能整除a,或a除以b余數為0,b|a.b是a的一個因子。24的正因子有1,2,3,4,6,8,12和24。以下關系成立如果a|1,則a=±1如果a|b，且b|a,則a=±b任何b≠0能整除0如果b|g，且b|h,則對任何整數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當前9頁，總共52頁。2023/3/9現代密碼學理論與實踐0410/51同余(congruence)給定整數a,b及n≠0,當且僅當a-b=kn時，a與b在模n時同余，記為a≡bmodn或a≡nb Ex:17≡57∵17-7=2*5;53≡711∵53-11=6*7a≡nb

當且僅當amodn=bmodn如果a是整數，n是正整數，定義a除以n所得之余數為a模n。對于任意整數a，我們總可寫出：a=?a/n」xn+(amodn)11mod7=4; -11mod7=3如果(amodn)=(bmodn),則稱整數a和b是模n同余，表示為a≡bmodn或a≡nb73≡4mod23； 21≡-9mod10當前10頁，總共52頁。2023/3/9現代密碼學理論與實踐0411/51同余的性質如果n|(a-b),則a≡bmodn證明:如果n|(a-b),則有(a-b)=kn,k為某些整數，所以a=b+kn。故amodn=(b+kn)除以n的余數

=b除以n的余數

=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

當前11頁，總共52頁。2023/3/9現代密碼學理論與實踐0412/51(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

模算術運算當前12頁，總共52頁。2023/3/9現代密碼學理論與實踐0413/51

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

證明：定義(amodn)=ra,(bmodn)=rb于是存在整數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

模算術運算當前13頁，總共52頁。2023/3/9現代密碼學理論與實踐0414/51當前14頁，總共52頁。2023/3/9現代密碼學理論與實踐0415/51加法逆元和乘法逆元加法逆元(-w)對每一個w∈Zn，存在一個z，使得w+z≡0modn，則z即為加法逆元-w乘法逆元(w-1)對每一個w∈Zp，存在一個z，使得wxz≡1modp，p為素數，w與p互素，則z即為乘法逆元w-1因為w與p互素，如果用w乘以Zp中的所有數模p，得到的余數將以不同次序涵蓋Zp中的所有數，那么至少有一個余數的值為1。因此，在Zp中的某個數與w相乘模p的余數為1,這個數就是w的乘法逆元,w-1某些但非全部整數存在一個乘法逆元就將使模數不再是素數。如果gcd(a,n)=1,則能在Zn中找到b，使得axb≡1modn，則b即為乘法逆元a-1,因為a與n互素。當前15頁，總共52頁。2023/3/9現代密碼學理論與實踐0416/51剩余集(Residues)定義比n小的非負整數集合為Zn：Zn

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

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

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

模算術的性質當前16頁，總共52頁。2023/3/9現代密碼學理論與實踐0417/51模算術的性質(2)模n的縮剩余集(ReducedsetofResiduesmodn)完全剩余集的一個子集，指的是集合中的元素都和n互素例:n=10，模n的完全剩余集是{0,1,2,…,9}，縮剩余集是{1,3,7,9}當前17頁，總共52頁。2023/3/9現代密碼學理論與實踐0418/51數論的一個最基本的技巧是Euclid算法，求兩個正整數的最大公約數gcd(a,n),greatestcommondivisor對于任何非負的整數a和n，gcd(a,n)=gcd(nmoda,a)假設我們有整數a,b使得d=gcd(a,b)。假設a≥b>0，現在用b除a，由除法可得到a=q1b+r10≤r1<b如果恰巧r1=0，則b|a且d=gcd(a,b)=b。但是如果r1≠0,我們說d|r1。這基于除法的基本性質：由d|a和d|b可以推出d|(a-q1b)，即d|r1。現在假設有任意的整數c整除b和r1.因此c|(q1b+r1)=a。因此c同時整除a和b，必須有c≤d，而d是a和b的最大公因子。因此d=gcd(b,r1)。4.3歐幾里得算法EuclidAlgorithm當前18頁，總共52頁。2023/3/9現代密碼學理論與實踐0419/51a=q1b+r10≤r1<b假設r1≠0.因為b>r1，可以用r1除b，應用除法有b=q2r1+r20≤r2<r1如前所述，如果r2=0，則d=r1.如果r2≠0，則d=gcd(r1,r2)。繼續除法過程直到余數為0，比如說在第(n+1)階段有rn整除r(n-1)。結果為如下的方程系統：4.3歐幾里得算法EuclidAlgorithm當前19頁，總共52頁。使d等于gcd(a,b),根據gcd的定義，有d|a和d|b成立。對于任意正整數b,a可以表示為如下形式：a=kb+r≡r(modb)amodb=r其中k,r為整數。因此，對某個整數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/3/920/41當前20頁，總共52頁。2023/3/9現代密碼學理論與實踐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當前21頁，總共52頁。2023/3/9現代密碼學理論與實踐0422/51對于給定的整數a和b，擴展的Euclid算法不僅計算出最大公因子d，而且還有另外的整數x和y，它們滿足如下方程：ax+by=d=gcd(a,b)用擴展的Euclid算法計算(x,y,d).假設在每一步驟i都可以找到xi和yi滿足ri=axi+byi。4.3擴展的Euclid算法當前22頁，總共52頁。2023/3/9現代密碼學理論與實踐0423/51從原始的Euclid算法知該過程當余數為0時結束，求得a和b的最大公因子為d=gcd(a,b)=rn.我們也決定了4.3擴展的Euclid算法當前23頁，總共52頁。2023/3/9現代密碼學理論與實踐0424/514.4有限域GF(p)GaloisFields有限域在密碼學中扮演重要角色有限域的階(元素個數)必須是一個素數的冪pn,n為正整數。元素個數是pn的有限域一般記為GF(pn)，即Galoisfields,模pn.關注兩種特殊情形，n=1時的有限域和p為2時的有限域，即GF(p)和GF(2n)最簡單的有限域是GF(2)，它的代數運算簡述如下：+01x01w-ww-100100000110101111

加乘求逆當前24頁，總共52頁。2023/3/9現代密碼學理論與實踐0425/51GaloisFieldsGF(p)階為p的有限域GF(p)給定一個素數p，元素個數為p的有限域GF(p)被定義為整數{0,1,…,p-1}的集合Zp，其運算為模p的算術運算Zn中的任一整數有乘法逆元當且僅當該整數與n互素，若n為素數，Zn中的所有非零整數都與n互素，因此Zn中所有非零整數都有乘法逆元對每一個w∈Zp，存在一個z，使得w×z≡1modp，則z即為乘法逆元w-1因為w與p互素，如果用w乘以Zp中的所有數模p，得到的余數將以不同次序涵蓋Zp中的所有數，即余數集合是{0,1,…,p-1}的置換形，那么至少有一個余數的值為1。因此，在Zp中的某個數與w相乘模p的余數為1,這個數就是w的乘法逆元，w-1。所以，Zp是一個有限域。當前25頁，總共52頁。2023/3/9現代密碼學理論與實踐0426/51當前26頁，總共52頁。2023/3/9現代密碼學理論與實踐0427/51計算乘法逆元素Computingmultiplicativeinverses

axmodn=1,x=a-1=? 給定a∈[0,n-1],gcd(a,n)=1，若能找到唯一整數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

證明：(略)可以用反證法證明 此性質意味著每一個aimodn(i=0,…,n-1)都是不同的模n剩余，而{aimodn}i=0,1,…,n-1是完全剩余集{0,1,…,n-1}的置換形式計算乘法逆元素當前27頁，總共52頁。2023/3/9現代密碼學理論與實踐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說明，當gcd(a,n)=1時，a一定有一個唯一的逆元素。定理4.1如果gcd(a,n)=1,一定存在整數x,0<x<n，滿足axmodn=1可以用Euclid’s計算最大公約數算法的擴展來求逆。計算乘法逆元素當前28頁，總共52頁。2023/3/9現代密碼學理論與實踐0429/51如果a和b互素，則b有模a的乘法逆元。也就是說，如果gcd(a,b)=1,那么b有模a的乘法逆元。即對于正整數b<a,存在b-1<a使bb-1=1moda.如果a是素數并且b<a，則顯然a和b互素，且最大公因子為1.我們已經證明過該式可以用擴展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.擴展的Euclid算法求逆當前29頁，總共52頁。2023/3/9現代密碼學理論與實踐0430/514.5多項式運算三種多項式運算使用代數基本規則的普通多項式運算系數運算是模p運算的多項式運算，即系數在GF(p)中系數在GF(p)中，且多項式被定義為模一個n次多項式m(x)的多項式運算普通多項式運算一個n次多項式(n>=0)的表達形式如下其中ai是某個指定數集S中的元素，該數集稱為系數集，且an≠0，f(x)是定義在系數集S上的多項式零次多項式稱為常數多項式，是系數集里的一個元素，如果an=1，對應的n次多項式就稱為首1多項式當前30頁，總共52頁。2023/3/9現代密碼學理論與實踐0431/51普通多項式運算加或減就是相應系數的加減，乘則要用到所有系數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當前31頁，總共52頁。2023/3/9現代密碼學理論與實踐0432/51當前32頁，總共52頁。2023/3/9現代密碼學理論與實踐0433/51系數在Zp中的多項式運算在計算每個系數的值時需要做模運算可以模任何素數p，但是我們更感興趣的是模2的運算也就是說所有的系數不是0就是1比如，令f(x)=x3+x2,g(x)=x2+x+1

則f(x)+g(x)=x3+x+1f(x)xg(x)=x5+x2當前33頁，總共52頁。2023/3/9現代密碼學理論與實踐0434/51當前34頁，總共52頁。2023/3/9現代密碼學理論與實踐0435/51多項式的模運算多項式可以寫成如下形式:f(x)=q(x)g(x)+r(x)其中，r(x)就可被看作是余數r(x)=f(x)modg(x)如果沒有余數，就稱g(x)可以整除f(x)如果g(x)除了1和它自身以外沒有其他公因式，就稱它是不可約多項式或素多項式irreducibleorprime當前35頁，總共52頁。2023/3/9現代密碼學理論與實踐0436/51求多項式的最大公因式可以為多項式求解最大公因式如果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)]……當前36頁，總共52頁。2023/3/9現代密碼學理論與實踐0437/51求多項式的最大公因式當前37頁，總共52頁。2023/3/9現代密碼學理論與實踐0438/51求多項式的最大公因式當前38頁，總共52頁。2023/3/9現代密碼學理論與實踐0439/51求多項式的最大公因式當前39頁，總共52頁。2023/3/9現代密碼學理論與實踐0440/514.6有限域GF(2n)所有加密算法都涉及到整數集上的算術運算，如果用到除法，必須使用定義在域上的運算。整數集里的數與給定的二進制位數所能表達的信息一一對應，即整數集的范圍從0到2n-1，正好對應一個n位的字。將一個整數集不平均地映射到自身的算法用于加密時可能要弱于一個提供一一映射的算法，因此，有限域GF(2n)對加密算法是很有吸引力的。所以要尋找一個包含2n個元素的集合，其上定義了加法和乘法使之成為一個域，給集合的每個元素賦值為0到2n-1之間的唯一整數，用多項式算術來構造所需的域。可以使用擴展的歐幾里德算法來為集合中的元素找到逆元。當前40頁，總共52頁。2023/3/9現代密碼學理論與實踐0441/51當前41頁，總共52頁。2023/3/9現代密碼學理論與實踐0442/51多項式模運算設集合S由域Zp上次數小于等于n-1的所有多項式組成，每個多項式具有如下形式：其中，ai在集合{0,1,…,p-1}上取值，S共有pn個不同的多項式當p=3,n=2時，集合中共有32=9個多項式，分別是

0 x 2x1 x+1 2x+12 x+2 2x+2當p=2,n=3時，集合中共有23=8個多項式，分別是 0 x+1 x2+x1 x2 x2+x+1x x2+1當前42頁，總共52頁。2023/3/9現代密碼學理論與實踐0443/51多項式模運算如果定義了合適的運算，那么每個這樣的集合S都是一個有限域，定義由如下幾條組成：該運算遵循基本代數規則中的普通多項式運算規則系數運算以p為模，即遵循有限域Zp上的運算規則如果乘法運算的結果是次數大于n-1的多項式，那么必須將其除以某個次數為n的既約多項式m(x)并取余式。對于多項式f(x)，這個余數可表示為r(x)=f(x)modm(x)和簡單模運算類似，多項式模運算也有剩余類集合的概念。設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。當前43頁，總共52頁。2023/3/9現代密碼學理論與實踐0444/51多項式模運算以n次既約多項式m(x)為模的所有多項式組成的集合滿足圖4.1的所有公理，于是可以形成一個有限域。為構造有限域GF(23)，需要選擇一個3次既約多項式：x3+x2+1或x3+x+1,選擇后者則結果如表4.6所示。當前44頁，總共52頁。2023/3/9現代密碼學理論與實踐0445/51加法運算，例如100+010=110，這等價于x2+x。當前45頁，總共52頁。2023/3/9現代密碼學理論與實踐0446/51多項式模運算對于乘法運算，例如：100×010=011，這等價于x2×x=x3，約減后為x+1。當前46頁，總共52頁。2023/3/9現代密碼學理論與實踐0447/51求乘法逆元擴展的歐幾里德算法可以用來求一個多項式的乘法逆元。如果多項式b(x)的次數小于m(x)且gcd[m(x),b(x)]=1，那么可以求出b(x)以m(x)為模的乘法逆元。擴展的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)]