信息安全導(dǎo)論-5密碼學(xué)數(shù)學(xué)基礎(chǔ)省公開課一等獎全國示范課微課金獎?wù)n件

信息安全導(dǎo)論第五講密碼學(xué)技術(shù)中數(shù)學(xué)基礎(chǔ)華中科技大學(xué)圖象所信息安全研究室Dr.ZuxiWang2025/2/211第1頁密碼學(xué)是研究密碼系統(tǒng)或通信安全一門學(xué)科，分為密碼編碼學(xué)和密碼分析學(xué)。密碼編碼學(xué)是使得消息保密學(xué)科，從事此行稱為密碼編碼者。密碼分析學(xué)（密碼破譯學(xué)）是研究加密消息破譯學(xué)科，從事此行稱為密碼分析者。精于此道人被稱為密碼學(xué)家，當(dāng)代密碼學(xué)家通常是理論數(shù)學(xué)家。2025/2/212第2頁密碼學(xué)是一門交叉學(xué)科，它很大程度上是應(yīng)用數(shù)學(xué)學(xué)科。密碼學(xué)中包括數(shù)論、代數(shù)、概率論、組合數(shù)學(xué)、計算復(fù)雜理論等各種數(shù)學(xué)知識。還包括信息論學(xué)科知識。密碼學(xué)所包括知識十分遼闊，這里僅介紹部分數(shù)學(xué)基本知識。2025/2/213第3頁數(shù)論基礎(chǔ)素數(shù)同余、模運算中國剩下定理Euclean算法Fermat定理、Euler定理素性檢驗因子分解離散對數(shù)2025/2/214第4頁整除、素數(shù)記整數(shù)集合Z={…,-3,-2,-1,0,1,2,3,…}整除設(shè)a,b∈Z，a≠0，假如存在m∈Z，使得b=ma，則稱a整除b，以a|b表示，a是b一個因子或約數(shù)。假如沒有任何m，使得b=ma，則稱a不能整除b,記a?b，此時有a=mb+r且0<r<b。素數(shù)(質(zhì)數(shù))

整數(shù)p>1被稱為素數(shù)是指p因子僅有1，-1，p，-p。不然，稱為合數(shù)。2025/2/215第5頁整除基本性質(zhì)a|a;b≠0，b|0;Ifa|b,b|c,thena|c;ifa|1,thena=±1;ifa|b,andb|a,thena=±b;ifb|gandb|h,thenb|(mg+nh),foranyintegersmandn注意:ifa=0modn,thenn|a2025/2/216第6頁互素與最大條約數(shù)最大條約數(shù)（最大公因子）：若a,b,c∈Z，假如c∣a，c∣b，稱c是a和b條約數(shù)。正整數(shù)d稱為a和b最大條約數(shù)(記d=gcd(a,b)或(a,b))

，假如它滿足:d是a和b條約數(shù)。對a和b任何一個條約數(shù)c有c∣d。等價定義形式是：

gcd(a,b)=max{k:k∣a，k∣b}若gcd(a,b)=1，稱a與b是互素。2025/2/217第7頁最小公倍數(shù)最小公倍數(shù)a,b倍數(shù)中最小者稱為a,b最小公倍數(shù)，記為：lcm(a,b)a,b不全為0，有ab=gcd(a,b)·lcm(a,b).注意：對有限個整數(shù)a1,a2,…,an,也可定義最大條約數(shù)gcd(a1,a2,…,an)和最小公倍數(shù)lcm(a1,a2,…,an).2025/2/218第8頁帶余除法帶余除法：

a∈Z,m>0，可找出兩個唯一確定整數(shù)q和r使a=qm+r,0≤r<m。(若r=0則m∣a）

q和r這兩個數(shù)分別稱為以m去除a所得到商數(shù)和余數(shù).記：q=adivm或[a/m],r=amodm。存在x,y，gcd(a,b)＝ax+by假如a=qb+r,則gcd(a,b)=gcd(b,r).gcd(a/gcd(a,b),b/gcd(a,b))=12025/2/219第9頁算術(shù)基本定理下面關(guān)于素數(shù)事實均成立假如p是一個素數(shù)，而且p|ab，則有p|a或p|b；素數(shù)有沒有窮多個；素數(shù)定理:記π(x)為小于x素數(shù)個數(shù)，則有它表明，對于充分大x，能夠用xlnx近似地表示π(x)。算術(shù)基本定理：任何一個不等于0正整數(shù)a都能夠?qū)懗晌ㄒ槐硎臼?，這里P1>P2>P3…>Pt是素數(shù)，其中αi>0整數(shù)。2025/2/2110第10頁當(dāng)前沒有可用于整數(shù)分解有效算法。對于整數(shù)a,b(a,b≥2)，a,b素數(shù)分解式分別為：

，，其中ei，fi≥0,t≥i≥1，則有：2025/2/2111第11頁帶余除法中，a∈Z，m>0，a=qm+r，0≤r<m，r為a除以m余數(shù)或剩下(Residue)，m稱為模數(shù)，所以稱r為a模正整數(shù)m剩下，記r≡amodmm∣(a-b)

a=q1m+r,b=q2m+r。即a和b分別除以m有相同余數(shù)同余稱整數(shù)a模正整數(shù)m同余(數(shù))于整數(shù)b，并寫a≡b（modm）是指m∣(a－b),m稱為模數(shù)。note:ifa=0modm,thenm|a整數(shù)同余式和同余方程2025/2/2112第12頁1、模關(guān)系：相對于某個固定模數(shù)m同余關(guān)系，是指整數(shù)間一個等價關(guān)系。含有等價關(guān)系三點基本性質(zhì)：

自反性：對任意整數(shù)a，有a≡a（modm）

對稱性：若a≡b(modm)，則b≡a（modm）

傳遞性：若a≡b(modm),b≡c(modm),則a≡c(modm)全體整數(shù)集合Z可按模m（m>1）分成一些兩兩不交等價類（剩下類）。2、整數(shù)模m同余類共有m個，他們分別為mk+0,mk+1,mk+2,…mk+(m-1);k∈z，每一個算一類，每一類都能夠選一個代表元，普通選這一類中最小非負整數(shù)。于是稱[0],[1],[2],…[m-1]為標(biāo)準(zhǔn)完全剩下系。其中與m互素剩下類組成模m簡約剩下系。Z模12標(biāo)準(zhǔn)完全剩下系為：[0],[1],[2],[3],[4],[5],[6],[7],[8],[9],[10],[11]2025/2/2113第13頁Modulo7Example...-21-20-19-18-17-16-15-14-13-12-11-10-9-8-7-6-5-4-3-2-10123456

78910111213141516171819202122232425262728293031323334...2025/2/2114第14頁3、模運算：對于某個固定模m同余式能夠象普通等式那樣相加相減和相乘：a(modm)±b(modm)=(a±b)(modm)a(modm)*b(modm)=a*b(modm)例：由同余式演算證實560－1是56倍數(shù)，223－1是47倍數(shù)。解： 注意53=125≡13(mod56)

于是有56≡169≡1(mod56)

對同余式兩邊同時升到10次冪， 即有56∣(560-1)。 其次,注意26=64≡-30(mod47),于是223=(26)3·25=(26·26)26·25

≡900*(-30)*(32)mod(47)≡(7)*(-30)*(32)(mod47)≡1(mod47)

于是有47∣(223-1)2025/2/2115第15頁Modulo8Example2025/2/2116第16頁4、定理：(消去律)對于ab≡ac(modm)來說，若最大公因子gcd(a,m)＝1（即a與m是互素），則b≡c(modm)加法消去律：

a+b≡a+c(modm)，有b≡c(modm).5、一次同余方程ax≡b(modm)，這個方程有沒有解，相當(dāng)于問有沒有那樣一個整數(shù)x，使得對于某個整數(shù)y來說，有ax+my=b

定理：記最大公因子(a,m)=d，則同余方程ax≡b(modm)有解充分必要條件是d∣b。當(dāng)這個條件滿足時，恰有d個模m同余類中整數(shù)是上述方程解。證實：略。（從ax+my=b入手）2025/2/2117第17頁6、整數(shù)環(huán)z模正整數(shù)m得到剩下類集合能夠記為zm(或z/(m)),zm={[0],[1],…,[m-1]}

在3、中已說明zm對剩下類加法，乘法是封閉，可列出它們加乘表。我們稱zm為剩下類環(huán)（或同余類環(huán)）7、在整數(shù)環(huán)z中是沒有零因子，即兩個非零整數(shù)乘積一定不等于0，不過剩下環(huán)則不然。例z12中：[3]*[4]=[12]=[0]說明，zm中元素可分為兩類，一類是零因子，即若α∈zm,α≠[0]，存在β∈zm且β≠[0]，有α*β=[0]，則稱α，β都為zm中零因子。另一類是可逆元，即若α∈zm，存在β∈zm，使α*β=[1]，此時α,β互為各自逆元，記α-1=β；β-1=α2025/2/2118第18頁定理：剩下類環(huán)zm中元素α=[a]為zm可逆元

最大條約數(shù)(a,m)=1要證實這個定理，只需證實以下引理：引理：任意兩個整數(shù)a和b都有一個最大條約數(shù)，這么一個最大條約數(shù)d能夠表示成a,b二數(shù)關(guān)于整系數(shù)線性組合，即有s,t∈z，使d＝sa＋tb。證實：不妨設(shè)b>0，用輾轉(zhuǎn)相除法，先用b去除a，得

a=q1b+r1,0≤r1<b; (1)假如r1=0，停頓，不然再用r1去除b，得

b=q2r1+r2,0≤r2<r1; (2)假如r2=0，停頓，不然再用r2去除r1，得

r1=q3r2+r3;0≤r3<r2; (3)等等，這么一直進行下去，可得一系列關(guān)系式：

rk-3=qk-1rk-2+rk-1,0≤rk-1<rk-2; (k-1) rk-2=qkrk-1+rk,0≤rk<rk-1; (k)2025/2/2119第19頁因為歷次所得余數(shù)

r1>r2>r3>r4>…rk>…≥0是嚴格遞降一串非負整數(shù)，故最終總會出現(xiàn)余數(shù)為0情形：

rk-1=qk+1rk (k+1)所以，進行有限步必停頓，此時d=rk=(a,b)成立，這是因為1).可知rk為a和b條約數(shù)，只要按倒序分析自然有此結(jié)論。2).a和b任何一個條約數(shù)c都是rk約數(shù)，只要按正序分析，自然可知。為證定理后一部分，將式(1)做移項有

r1=s1a+t1b（其中s1=1,t1=-q1）

再將式(2)右端經(jīng)過移項變?yōu)閞2=s2a+t2b這么一直下去，最終得d=rk=s*a+t*b, s,t∈z.2025/2/2120第20頁例子：求(180，252)，并將他表示為180和252這兩個數(shù)一個帶整系數(shù)線性組合。解： 252=1*180+72 (1) 180=2*72+36 (2) 72=2*36 (3)得(180,252)=36，同時有 72=252-1*180 (1

)由(2)得 36=180-2*72 (2

)

將(1

)代入(2

)，即得

36=180-2*(250-180)

=3*180-2*2522025/2/2121第21頁中國剩下定理例子：（孫子算經(jīng)）今有物不知其數(shù)：三三數(shù)之余二；五五數(shù)之余三；七七數(shù)之余二。問物幾何？答曰：二十三。23≡2*70+3*21+2*15(mod105)（口訣：三人同行七十稀，五樹梅花廿一枝，

七子團圓月正半，除百零五便得知。）問，70，21，15怎樣得到？原問題為：求解同余方程組2025/2/2122第22頁注意：若x0為上述同余方程組解，則x0

=x0+105*k(k∈z)也為上述同余方程組解。有意義是，解題口訣提醒我們先解下面三個特殊同余方程組(1) (2) (3) 特殊解 =? =? =?以方程（1）為對象，相當(dāng)于解一個這么同余方程35y≡1(mod3)，為何呢？原因是，從（1）模數(shù)及條件知，x應(yīng)是35倍數(shù)，于是能夠假設(shè)x＝35y，有2025/2/2123第23頁35y≡1(mod3)相當(dāng)于2y≡1(mod3)

解出y=2（mod3）

于是x35*2(mod(3*35))70(mod105)類似地得到（2）、（3）方程模105解21、15。

于是有

得

2025/2/2124第24頁中國剩下定理：設(shè)自然數(shù)m1,m2,…mr兩兩互素，并記M=m1m2…mr，則同余方程組在模M同余意義下有唯一解。2025/2/2125第25頁證實：考慮方程組，

(1<=i<=r)

因為諸mi(1<=i<=r)兩兩互素，這個方程組作變量替換，令x=(M/mi)*y，方程組等價于解同余方程： (M/mi)y≡1(modmi)2025/2/2126第26頁若得到特解yi,只要令

xi=(M/mi)yi則方程組解為

x0=b1x1+b2x2+…+brxr(modM)模N意義下唯一。中國剩下定理用途之一是，它給出了一個方法，使非常大數(shù)對M模運算轉(zhuǎn)化到更小數(shù)上來進行運算，當(dāng)M為150位或150位以上時，這種方法非常有效。2025/2/2127第27頁Euclidean算法依據(jù)(a,b)=(b,amodb)輾轉(zhuǎn)除法是求解兩個整數(shù)最大公因子傳統(tǒng)方法，由此而得歐幾里得算法是一個用于計算兩個整數(shù)最大公因子有效算法。Euclidean算法：輸入a和b，wherea,b∈z,a,b≥0,a≥b.假如b≠0，則依次完成:r←amodb,a←b,b←r,不然返回a.輸出gcd(a,b)=r.2025/2/2128第28頁ExampleGCD(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)2025/2/2129第29頁擴展Euclidean算法經(jīng)擴張Euclidean算法不但能夠被用于計算d=gcd(a,b)，而且能夠找到滿足等式ax+by=d整數(shù)x和y。擴展Euclidean算法：輸入a和b，wherea,b∈z,a,b≥0,a≥b.假如b=0，則:d←a,x←1,y←0,返回(d,x,y).x2←1,x1←0,y2←0,y1←1假如b≠0，則依次完成:q←[a/b],r←a-qb,x←x2-qx1,y←y2-qy1;a←b,b←r,x2←x1,y2←y1,x1←x,y1←yd←a,x←x2,y←y2，返回(d,x,y).Euclidean算法和擴展Euclidean算法時間復(fù)雜度為O((lgn)2).2025/2/2130第30頁Fermat定理和Euler定理Fermat定理：假如p是素數(shù)而且a是正整數(shù),(p,a)=1那么，ap-1≡1(modp)

證實：設(shè)z*p≡{α∈zp∣(α,p)=1}

易見，z*p={1,2,3,…,(p-1)}且因為（a,p）＝1知

az*p={[a],[2a],[3a],…,[(p-1)a]}=z*p，原因是az*p內(nèi)元素兩兩不一樣。他們剛好為1,2,3…,(p－1)一個排列。所以

[a]*[2a]*[3a]*…[(p-1)a]≡1*2*3*…(p-1)(modp)

由（(p－1)！，p）＝1，

所以ap-1≡1(modp)推論：對素數(shù)p，任意正整數(shù)a，有ap≡a(modp).usefulinpublickeyandprimalitytesting2025/2/2131第31頁Euler函數(shù)φEuler函數(shù)φ(n)是這么來定義：

當(dāng)n＝1時,φ(1)＝1；當(dāng)n>1時，它值φ(n)等于比n小而與n互素正整數(shù)個數(shù)。以n＝24為例，比24小而與24互素正整數(shù)為：1,5,7,11,13,17,19,23。所以，我們有φ(24)＝8。若p為素數(shù)，則φ(p)＝p-1。若p，q都為素數(shù)且p≠q，此時有

φ(pq)＝φ(p)φ(q)=(p-1)·(q-1)證實：考慮zpq剩下類集合是{0，1，2，…，（pq-1）},集合中與pq不互素元素子集為{p,2p,…,(p-1)q}和子集{q,2q,…(p-1)q}以及0，于是若設(shè)n＝pq，有φ(n)=pq-[(q-1)+(p-1)+1]=(p-1)(q-1)=φ(p)φ(q).例：φ(21)=φ(3*7)=φ(3)φ(7)=2*6=12.2025/2/2132第32頁若m1,m2互素，則φ(m1m2)＝φ(m1)φ(m2).設(shè)n=p1e1p2e2…prer，其中p1,p2,…,pr為互異素數(shù)，則φ(n)=p1e1-1p2e2-1…prer-1(p1-1)(p2-1)…(pr-1)

=n(1-1/p1)(1-1/p2)(1-1/p3)…(1-1/pr)Euler公式

證實：考慮1/n,2/n,…n/n，然后化簡成既約分數(shù)，分母為d一類分數(shù)有φ(d)個，于是

歐拉定理（Euler）：若整數(shù)a與整數(shù)n互素，則aφ(n)≡1(modn)。證實：設(shè)小于n而和n互素φ(n)個正整數(shù)為

r1,r2,r3…,rφ(n) (1)2025/2/2133第33頁他們是模n兩兩互不一樣余。對每一個定數(shù)i來說，因為a和ri都與n互素，所以(ari,n)=1，所以ari同余于（1）中某個ri’即

ari≡ri’(modn)，1≤i≤φ(n)而且當(dāng)i≠j時有ari

/≡arj(modn).于是,為

置換.所以有由(ri,n)=1,所以

Remarks：1*.n＝p時，(a,p)=1,有ap-1≡1(modp)為Fermat定理！而對任意a，有ap≡a(modp)（Fermat）2*.易見aφ(n)+1≡a(modn)3*.若n=pq，p與q為相異素數(shù)，取0<m<n，若(m,n)=1，有mφ(n)+1≡m(modn)，也即m(p-1)(q-1)+1≡m(modn).2025/2/2134第34頁4*.對于3中，若(m,n)＝p或q，也一樣有mφ(n)+1≡m(modn)5*.由(mφ(n))k≡1k(modn)知

mkφ(n)≡1(modn)，深入

mkφ(n)+1≡m(modn) mk(p-1)(q-1)+1≡m(modn)2025/2/2135第35頁素性檢驗、因子分解在許多加密算法中，需要隨機選擇一個或多個非常大素數(shù)，所以必須確定一個給定大數(shù)是否是素數(shù)。－－素性檢驗(測試)當(dāng)前還沒有簡單有效方法處理該問題。Miller和Rabin提出一個算法，其利用了Fermat定理。該算法產(chǎn)生數(shù)不一定數(shù)素數(shù)，但令人詫異是，其產(chǎn)生數(shù)幾乎能夠必定是素數(shù)。2025/2/2136第36頁素性檢驗、因子分解RSA算法安全性以對大整數(shù)進行素數(shù)分解困難性為基礎(chǔ)，即無法在多項式時間內(nèi)對于一個足夠大整數(shù)進行分解。一旦這個難題被破解，則RSA算法安全性便不復(fù)存在。一些具代表性因子分解算法包含：二次篩法p-1因子分解方法是更為有效橢圓曲線方法基礎(chǔ)數(shù)域篩法等2025/2/2137第37頁強素數(shù)許多密碼算法關(guān)心強素數(shù)。設(shè)n∈Z，p和q是素數(shù)，而且n=pq。當(dāng)p，q滿足以下特征時，稱之為強素數(shù)。①Gcd(p-1,q-1)比較??；②p-1和q-1都有大素因子（分別記為p*和q*）；③p*-1和q*-1都有大素因子；④p+1和q+1都有大素因子；⑤(p-1)/2和(q-1)/2都是素數(shù)。假如素數(shù)p含有特征⑤,則它們一定含有特征③和④.此時，即使采取一些特殊因子分解方法，對整數(shù)n進行因子分解也非常困難。2025/2/2138第38頁為了增加密碼算法安全性，提議使用長度大而且含有隨機性結(jié)構(gòu)強素數(shù)，其中，素數(shù)長度比其結(jié)構(gòu)特點更為主要。不過，從因子算法對整數(shù)進行分解概率角度考慮，強素數(shù)與其它素數(shù)相比并沒有明確優(yōu)勢。2025/2/2139第39頁代數(shù)基礎(chǔ)－－群、環(huán)、域、布爾代數(shù)概述群、環(huán)、域基本概念有限域

GF(pn)多項式算術(shù)布爾代數(shù)與布爾函數(shù)2025/2/2140第40頁概述有限群、有限域、布爾函數(shù)等在密碼技術(shù)和應(yīng)用中越來越主要。cryptographyAES,EllipticCurve,IDEA,PublicKey將從抽象代數(shù)群、環(huán)、域基本概念開始介紹。2025/2/2141第41頁群（Group）代數(shù)系統(tǒng)：一個集合以及定義在其上一組運算一起組成一個代數(shù)系統(tǒng)。群（group）是一個代數(shù)系統(tǒng)<G；*>，它僅有一個二元運算*（因為是代數(shù)系統(tǒng)，所以運算封閉性滿足），并滿足:結(jié)合律: (a*b)*c=a*(b*c)

含有單位元e: e*a=a*e=a

每一元a有逆元a-1: a*a-1=e假如滿足交換律:a*b=b*a

則形成一個交換群(commutativegroup),也叫阿貝爾群(abeliangroup).Remark:在不引發(fā)歧義下，經(jīng)常將運算符號省略。a*b=ab2025/2/2142第42頁

例1<N；+><Z；+><I；·>和<R；·>不是群。

<I；+>、<R；+>和<R-｛0｝；·>都是群。例2設(shè)有Z4=｛0,1,2,3｝，模4加法運算定義為則<Z4;>組成一個群。

012301230123123023013012Examples:2025/2/2143第43頁Examples:<Zm,+>是一個交換群，也叫加群。+是關(guān)于模m加法；<Zm-{0},·>，·是關(guān)于模m乘法。當(dāng)m是素數(shù)時，它組成一個乘法交換群；但當(dāng)m不是素數(shù)時，它不組成群。2025/2/2144第44頁循環(huán)群（CyclicGroup）群元素冪example: a3=a*a*aak=a*a*…*a(k個a相乘，k正整數(shù))要求:e=a0，a-k=a-1*a-1*…*a-1=(a-1)-k(k個a-1相乘，k正整數(shù))對任意整數(shù)m,n,am*an=am+n,(am)n=amn,a-n=(a-1)n=(an)-1.群中任何元都是某個元g冪，稱群為循環(huán)群，g稱為其一個生成元(generator)。i.e.對群中任一元b,存在k,使b=

gk.以g為生成元循環(huán)群記為G=<g>.稱為由g生成循環(huán)群.2025/2/2145第45頁對任意負整數(shù),按照群中逆元表示方法例3

群<I；+>是循環(huán)群，1是生成元，10=0，對任意正整數(shù)n，n=1+1+…+1，按照群中元素冪表示方法n=1n.

例4

例2中群<Z4；

4>是循環(huán)群，1是其生成元，3也是其生成元。因為10=0，11=1，12=1

41=res4(2)=2,13=12

41=2

41=res4(3)=3又30=0，31=3，32=3

43=res4(6)=2,33=32

43=2

43=res4(5)=12025/2/2146第46頁

例5

設(shè)G={a,b,c,e}，*是G上二元運算，

*eabceabcaecbbceacbaeeabc

a*a=b*b=c*c=e*e=e,a*b=b*a=c,b*c=c*b=a，a*c=c*a=b<G；*>是一阿貝爾群，但它不是循環(huán)群，普通稱這個群為Klein四元群。2025/2/2147第47頁群階和元素周期設(shè)<G；*>是一個群，假如G是有限集，則稱<G；*>是有限群，G中元素個數(shù)稱為群<G；*>階；若G是無限集，則稱<G；*>是無限群。設(shè)<G;*>是一個群，a∈G，若存在正整數(shù)r，使得ar=e，則稱元素a含有有限周期。使ar=e成立最小正整數(shù)r稱為a周期。假如對于任何正整數(shù)r，都有ar≠

e，則稱a周期為無限。2025/2/2148第48頁群階和元素周期Examples在群<R-{0};·>中，單位元1周期為1,-1周期為2.（-1）2=（-1）4=（-1）6=…=1群<Z4；

4>中，14=13

41=3

41=res4(4)=0；

21=2，22=2

42=res4(4)=0；34=33

43=1

43=res4(4)=0。

生成元1和3周期均為4，循環(huán)群<Z4；

4>階也為4。循環(huán)群<I；+>生成元1和–1，其周期均為無限，群<I；+>是一個無限階循環(huán)群。2025/2/2149第49頁群部分性質(zhì)消去律：設(shè)<G;*>是一個群，則對任意a,b∈G，（1）存在唯一元素x∈G，使a*x=b；（2）存在唯一元素y∈G，使y*a=b。設(shè)<G;*>是一個群，則對任意a,b,c∈G（1）若a*b=a*c,則b=c；（2）若b*a=c*a，則b=c。2025/2/2150第50頁群部分性質(zhì)求逆:設(shè)<G;*>是一個群，則對任意a,b,a1,a2,…,ak∈G(a*b)-1=b-1*a-1;(a1*a2*…*ak)-1=ak-1*…*a2-1*a1-1.關(guān)于元素周期:群<G;*>中元素

a若含有有限周期r，則當(dāng)且僅當(dāng)k

是r整數(shù)倍時，ak

=e.群中任一元素與它逆元含有相同周期。在有限群<G;*>中，每個元素均含有有限周期，且周期不超出群<G;*>階。結(jié)論對無限群不成立。如群<I；+>.

2025/2/2151第51頁群部分性質(zhì)設(shè)<G;*>是一由元素g生成循環(huán)群，則若g周期為n，則<G;*>是一個階為n有限循環(huán)群；若g周期為無限，則<G;*>是一個無限階循環(huán)群。2025/2/2152第52頁群部分性質(zhì)Examples群<Z4；

4>中單位元0周期是1；1和3周期均為4；2周期為2，群<Z4；

4>階4.設(shè)<G;*>是一個群，且對于任意a,b∈G，有(a*b)2=a2

*b2,則<G;*>是阿貝爾群。設(shè)Z6={0,1,2,3,4,5},

6是模6加法，定義為：a

6b=res6(a+b)，<Z6;6>是一個群。給出其單位元；各元素逆元；各元素周期。2025/2/2153第53頁設(shè)<G;*>是一個群，若<H;*>是<G;*>子代數(shù)，單位元e∈H，且對于任意a∈H，有a-1∈H，則稱<H;*>是<G;*>子群。<G;*>非空子集H關(guān)于G運算*組成子群，必須滿足：封閉性：H關(guān)于

*

封閉，a,b∈H，有a*b∈H;單位元：G單位元e∈H;可逆性：任意a∈H，有a-1∈H.Example:對于任意整數(shù)m，若令I(lǐng)m={mi:i

∈I}.則<Im;+>均組成<I；+>子群。子群（Subgroup）2025/2/2154第54頁若<H;*>是<G;*>子群，則<H;*>也是群。設(shè)<G;*>是一個群，H是G非空子集，若<H;*>也是群，則稱<H;*>是<G;*>子群。（子群等價定義）設(shè)<G;*>是群，H是G非空子集，若(1)對于任意a,b∈H，有a*b∈H；(2)對任意a∈H，有a-1∈H，則<H;*>是<G;*>子群。子群（Subgroup）2025/2/2155第55頁設(shè)<G;*>是群，H是G非空子集，若對于任意a,b∈H，有a*b-1∈H，則<H;*>是<G;*>子群。設(shè)<G;*>是一有限群，若<H;*>是<G;*>子代數(shù)，則<H;*>是<G;*>子群。即：若對于任意a,b∈H，有a*b∈H，則<H;*>是<G;*>子群（H有限且關(guān)于運算封閉就組成子群）。設(shè)<G;*>是一個群，若<H;*>是<G;*>有限子代數(shù)，則<H;*>是<G;*>子群。子群（Subgroup）2025/2/2156第56頁子群（Subgroup）Examples設(shè)<G;*>是一個群，a是G中任一元素，令H是a全部整數(shù)次冪集合，則H對于G運算組成<G;*>子群。顯然<H;*>是由元素a生成一個循環(huán)群。設(shè)<G;*>是一個群，定義G子集H={h:對任意x∈G,h*x=x*h}，H對于運算*組成<G;*>子群。2025/2/2157第57頁陪集（coset）、正規(guī)子群（normalsubgroup）H是G子群，a屬于G，aH={ah|h屬于H}稱為G一個關(guān)于H左陪集（a所在陪集）。一樣Ha組成一個右陪集。對a，aH不一定等于Ha。假如對所以a，都有aH＝Ha，則稱H為G一個正規(guī)子群。稱aH或Ha為陪集。2025/2/2158第58頁拉格朗日(Lagrange)定理陪集定理：G關(guān)于H全部不用左（右）陪集組成G一個分劃。Lagrange定理：群G必為其子群H及其全部不相同陪集直和。推論：有限群階必為其子群階整數(shù)倍。素數(shù)階群只有平庸子群（群本身與單位元）2025/2/2159第59頁群同態(tài)與同構(gòu)h:G1→G2群間一個映射，假如h保持群運算，即：a,bofG，有h(ab)=h(a)h(b)，則稱h為群G1,G2間一個同態(tài)映射，簡稱同態(tài)(homomorphism)。若同態(tài)h同時是一個雙射，那么稱h為一個同構(gòu)映射，簡稱同構(gòu)(isomorphism)

。這是稱兩群G1,G2是同構(gòu)。從代數(shù)結(jié)構(gòu)角度看，同構(gòu)群含有相同代數(shù)結(jié)構(gòu)，被視為同一群。2025/2/2160第60頁商群（Quotientgroup）群G正規(guī)子群H與其全部不相同陪集在陪集乘法意義下組成一個群，稱為G關(guān)于H商群，記為G/H。f:G→G’群間一個同態(tài)映射，kerf＝{g:f(g)=e’,e’為G’單位元}，即kerf為G’單位元e’在G中原象集合。稱kerf為同態(tài)映射f核。同態(tài)基本定理：設(shè)G’為G關(guān)于同態(tài)映射f象，則有：1.kerf是G正規(guī)子群；2.G’與商群G/kerf同構(gòu)。2025/2/2161第61頁變換群（Transformgroup）集合A上若干雙射（一一映射）對于映射復(fù)合運算組成一個群，稱其為A上一個變換群。一個集合A全部一一變換作成一個變換群。任何一個群都與一個變換群同構(gòu)。2025/2/2162第62頁置換群（permutationgroup）有限集A到直身一個雙射稱為A上一個置換。＃A=n，稱A上置換為n階置換。＃A＝n，A上全部n階置換在置換乘積（映射復(fù)合操作）下組成一個群，稱為n階對稱群(Symmetricgroup)，記為Sn。Sn任一子群，都稱為一個置換群。全部n階偶置換（可分解為偶數(shù)個對換乘積置換）組成Sn一個子群，叫交織群(Alternativegroup)，記為An。2025/2/2163第63頁置換群（permutationgroup）對稱群Sn階為n!，交織群An階為n!/2。凱萊(Caylay)定理：每一個有限群均同構(gòu)于由群元素集合上一個置換群（Sn一個子群）(

gG，gf(g),f(g)為G上一個置換，f(g)：gig

gi,全體f(g)組成G上置換群)2025/2/2164第64頁群生成元系G是一個群，S是G一個非空子集S生成子群H:G包含S最小子群,記H＝(S)。S生成子群H由S中元素及逆元任意乘積組成。假如G=(S)，那么稱S為群G一個生成元系(Generatorsystemorgeneratorset)。當(dāng)＃S＝1，S＝{a}，那么S生成G一個循環(huán)子群，(S)＝<a>.群生成元系通常不唯一。2025/2/2165第65頁對稱群生成系對稱群Sn每個元都能夠?qū)懗?12),(13),…,(1n)這n-1個對換（2-循環(huán)置換）中若干個乘積。S={(12),(13),…,(1n)}是Sn一個生成元系。Remark：Sn還有其它生成元系。2025/2/2166第66頁環(huán)（Ring）帶兩個運算（稱加法和乘法）集合<R,+,·>滿足:關(guān)于加法+組成一個abelian群<R,+>，其單位元為‘0’稱為零元；關(guān)于乘法·滿足:乘法封閉律；滿足結(jié)合律；a(bc)=(ab)c對加法分配律:a(b+c)=ab+ac則稱<R,+,·>為一個環(huán)（Ring）假如乘法是交換，則稱環(huán)為交換環(huán)(commutativering)環(huán)中關(guān)于乘法假如有單位元，稱之為環(huán)單位元。2025/2/2167第67頁子環(huán)、理想、剩下類環(huán)<R,+,·>子代數(shù)即為其子環(huán)。R子集關(guān)于R運算依然是環(huán)，稱為R子環(huán)。R子環(huán)I，假如同時關(guān)于乘法還滿足：對R中任意元r，I中任意元a，有ar,ra均仍屬于I.則稱I為一個理想。R理想I，關(guān)于加法組成剩下類集合上關(guān)于模I加法和乘法組成環(huán)，叫R模I剩下類環(huán)。記為R/I.2025/2/2168第68頁環(huán)同態(tài)與同構(gòu)環(huán)同態(tài)與同構(gòu)映射定義類似群同態(tài)與同構(gòu)。兩個環(huán)之間映射假如保持分別保持環(huán)運算，就稱為環(huán)同態(tài)假如同態(tài)是一一映射，就稱為同構(gòu)。類似地有同態(tài)基本定理。2025/2/2169第69頁零因子、整環(huán)若ab=0,但a,b都不是R中零元,

那么a(b)均稱為左(右)零因子.不然，稱為非零因子.無零因子環(huán):假如R中a,b有ab=o,那么必有a=0orb=0.整環(huán)（domain）：交換有單位元無零因子環(huán)，稱為一個整環(huán)。2025/2/2170第70頁Example:整數(shù)集關(guān)于普通加法和乘法組成一個環(huán)且是一個整環(huán).<Zm,+,·>是一個交換環(huán)，稱為模m剩下類環(huán)。當(dāng)m是合數(shù)時，剩下類環(huán)Zm中有零因子，Zm中a，若(a,m)=1,則a有逆元；當(dāng)m是素數(shù)時，剩下類環(huán)Zm是整環(huán)。2025/2/2171第71頁除環(huán)、域一個環(huán)關(guān)于其乘法不一定有單位元，另外其任一元也不一定有乘法逆元。假如一個環(huán)有單位元，而且任一非零元都有逆元，則稱其為一個除環(huán)。所以<R,+,·>是除環(huán)，它最少有一非零元，且<R,+>是加群；<R-{0},·>是群。一個除環(huán)，假如其關(guān)于乘法是交換，則稱其為一個域（Field）。2025/2/2172第72頁有限域（GaloisFields）有限域也叫Galois域，在密碼學(xué)中有主要作用。三個結(jié)論：每個有限域階必為素數(shù)冪。對任意素數(shù)p和正整數(shù)n，存在pn階域。同階有限域必同構(gòu)。于是：在同構(gòu)意義下，pn階有限域有且只有一個，記為GF(pn).尤其地，經(jīng)慣用到有限域:GF(p)－－稱為素域GF(2n)2025/2/2173第73頁GaloisFieldsGF(p)GF(p)是{0,1,…,p-1}上關(guān)于模p加法、乘法組成有限域。P為素數(shù)時，其中任意非零數(shù)都有逆元.2025/2/2174第74頁ExampleGF(7)2025/2/2175第75頁GF(p)中乘法逆元算法經(jīng)過擴展Euclidean算法得到:EXTENDEDEUCLID(m,b)1.(A1,A2,A3)=(1,0,m); (B1,B2,B3)=(0,1,b)2.ifB3=0 returnA3=gcd(m,b);（bmodm沒有逆）3.ifB3=1 returnB3=gcd(m,b);B2=b–1modm4.Q=A3divB3（A3除以B3商）5.(T1,T2,T3)=(A1–QB1,A2–QB2,A3–QB3)6.(A1,A2,A3)=(B1,B2,B3)7.(B1,B2,B3)=(T1,T2,T3)8.goto2GF(pn)中乘法求逆類似（換成關(guān)于多項式除法）2025/2/2176第76頁Inverseof550inGF(1759)2025/2/2177第77頁域上多項式域F上多項式為形如：表示式，其中n∈N,ai∈F,i=1,2,…,n.若an≠0,稱n為該多項式次數(shù),記n=deg(f(x)),并稱an為首項系數(shù),首項系數(shù)為1多項式稱為首1多項式.2025/2/2178第78頁多項式整環(huán)記F[x]為域上全部多項式f(x)組成集合，則F[x]關(guān)于通常多項式加法+和乘法·形成一個整環(huán)，叫域F上（一元）多項式環(huán)。0為其零元，1為其單位元。在F[x]上類似于整數(shù)環(huán)，關(guān)于多項式有商式、余式、整除、互素、最高公因式、最低公倍式等概念。2025/2/2179第79頁多項式帶余除法帶余除法：a(x),b(x)∈F[x],且b(x)≠0,則存在唯一q(x),r(x)∈F[x],使a(x)=q(x)b(x)+r(x),式中deg(r(x))≤deg(b(x)).q(x)稱為商式,r(x)稱為余式也用a(x)modp(x)

表示a(x)除以p(x)余式.稱為a(x)模p(x)，p(x)稱為模多項式。2025/2/2180第80頁不可約多項式若存在q(x),b(x)，deg(q(x))≥1,deg(b(x))≥1，使a(x)=q(x)b(x)，則稱a(x)為可約多項式，不然稱為不可約(既約)多項式。2025/2/2181第81頁多項式運算僅考慮一元多項式可把多項式運算分為三種：使用代數(shù)基本規(guī)則普通多項式運算；系數(shù)運算是模p運算多項式運算，即系數(shù)在Zp中；系數(shù)在Zp中，且多項式被定義為模一個多項式m(x)多項式運算。2025/2/2182第82頁普通多項式運算加法、減法為(相同次項)對應(yīng)系數(shù)加減法乘法為逐項相乘。egletf(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+22025/2/2183第83頁系數(shù)在Zp中多項式運算在普通多項式運算中，全部系數(shù)都取modp運算。尤其是mod2多項式運算ieallcoefficientsare0or1eg.letf(x)=x3+x2andg(x)=x2+x+1f(x)+g(x)=x3+x+1f(x)xg(x)=x5+x22025/2/2184第84頁模多項式運算基于多項式帶余除法:f(x)=q(x)g(x)+r(x)r(x)稱為余式(remainder)記r(x)=f(x)modg(x)定義模g(x)多項式加法、乘法。假如沒有余式，說g(x)整除

f(x)假如g(x)僅有它自己和1為其因式，說g(x)不可約(或既約)多項式(或素多項式)全部多項式在模不可約多項式加法乘法下組成一個域。2025/2/2185第85頁模p(x)剩下類環(huán)F[x]中一個多項式p(x)，(p(x))為由p(x)生成F[x]子環(huán)，它是一個理想(主理想).F[x]/(p(x))形成一個模p(x)剩下類環(huán)。它等同于全部n-1次多項式集合上關(guān)于模p(x)加法乘法運算組成環(huán)。當(dāng)p(x)為不可約多項式時，其形成一個域。2025/2/2186第86頁最大公因式尋找多項式最大公因式c(x)=GCD(a(x),b(x))假如c(x)

是同時整除a(x),b(x)

次數(shù)最高多項式。（等價定義）經(jīng)過擴充Euclidean算法來尋找: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.goto22025/2/2187第87頁模多項式運算、GF(2n)有限域元素個數(shù)必為pn，p為素數(shù)，n為正整數(shù)。p個元素上以模p運算產(chǎn)生一個域,Zp。但含有pn個元素集合上模pn運算卻不一定能產(chǎn)生域。怎樣定義適當(dāng)運算，使之pn個元成域？Zpn關(guān)于模pn運算是不行。2025/2/2188第88頁模多項式運算、GF(2n)S為域Zp上次數(shù)小于等于n-1全部多項式組成。S中共有pn個不一樣多項式。定義適當(dāng)運算，每個這么S都是一個有限域。運算定義為：運算遵照基本代數(shù)規(guī)則中普通多項式運算規(guī)則系數(shù)運算以p為模，即遵照有限域Zp上運算規(guī)則。多項式運算遵照模某個n次既約多項式m(x)運算。S即為一個pn階有限域，在同構(gòu)意義下，即為GF(pn).實際上，S=Zp[x]/(m(x)).2025/2/2189第89頁模多項式運算、GF(2n)P=2時，即為GF(2n).求其中逆元經(jīng)過擴展Euclidean求逆算法（與前面GF(p)中求逆類似，將那里整數(shù)換成Zp上多項式）2025/2/2190第90頁ExampleGF(23)2025/2/2191第91頁計算上考慮GF(2n)中多項式系數(shù)都是0or1,所以任一多項式都能夠由它n個二進制系數(shù)唯一表示。所以GF(2n)中每個多項式都能夠表示成一個n位二進制整數(shù)。兩個多項式加法等同于按位異或(XOR)運算。乘法經(jīng)過左移一位后按位異或來實現(xiàn)重復(fù)取模運算來簡約高次多項式(alsoshift&XOR)2025/2/2192第92頁布爾代數(shù)代數(shù)系統(tǒng)(B;－,,)(這里

和

分別稱并和交運算、－稱為求補運算)假如滿足以下性質(zhì)，稱為一個布爾代數(shù)：對于B中任意元素x,y,z，有：(1)交換律:x

y＝y(tǒng)

x，x

y＝y(tǒng)

x(2)結(jié)臺律:x

(y

z)＝(x

y)

zx

(y

z)＝(x

y)

z(3)等冪律:x

x＝x，x

x＝x(4)吸收律:x

(x

y)＝x，、x

(x

y)＝x2025/2/2193第93頁(5)分配律:x

(y

z)＝(x

y)

(x

z)x

(y

z)＝(x

y)

(x

z)(6)同一律:x

0＝x,x

1＝x(7)零一律:x

1＝1，x

0＝o(8)互補律:x

(－x)=1，x

(－x)＝o(9)對合律:－(－x)＝x(10)德·摩根定律:－(x

y)＝(－x)(－y)－(x

y)＝(－x)(－y)以上這10條性質(zhì)并不都是獨立。實際上，全部其它性質(zhì)都可由其中四條：交換律、分配律、同一律和互補律推導(dǎo)出來。2025/2/2194第94頁如：集合M冪集2M關(guān)于集合并集、交集、補集運算形成一個布爾代數(shù)。有限布爾代數(shù)基域基數(shù)是2冪。2025/2/2195第95頁布爾函數(shù)布爾表示式布爾代數(shù)B上由x1,x2,…,xn產(chǎn)生布爾表示式歸納地定義為B元素以及符號x1,x2,…,xn都是布爾表示式；布爾表示式并、交、補運算還是布爾表示式。布爾函數(shù)假如x1,x2,…,xn被解釋為只能在B中取值變量，則一個由x1,x2,…,xn產(chǎn)生布爾表示式實際上就是一個從Bn到B函數(shù)。2025/2/2196第96頁由x1,x2,…,xn產(chǎn)生布爾表示式有時也稱為B上一個n元布爾函數(shù)。Bn到B函數(shù)不一定是布爾函數(shù)，＃B>2時，必定有不是布爾函數(shù)函數(shù)存在。＃B=2時，Bn到B函數(shù)都是布爾函數(shù)。多重布爾函數(shù)：(f1,f2,…,fm):Bn×Bn×...×Bn到Bm函數(shù)。其中fi是Bn到B布爾函數(shù)。2025/2/2197第97頁GF(2)上布爾函數(shù)GF(2)只有兩個：0，1。關(guān)于這兩個量之間邏輯運算，GF(2)成為布爾代數(shù)。這時，GF(2)

n到GF(2)一個映射就稱為一個n元布爾函數(shù)(因為GF(2)基數(shù)為2)。對于GF(2)中元素，有x

y＝x·yx

y＝x+y+x·y－x=x+1這里+,·分別表示GF(2)中加(異或)、乘(與)運算。2025/2/2198第98頁作為邏輯運算函數(shù)，布爾函數(shù)是研究數(shù)字邏輯電路主要數(shù)學(xué)工具，也是研究以此為基礎(chǔ)一切科學(xué)技術(shù)主要工具，從而也是研究密碼學(xué)和密碼技術(shù)主要工具。不論在流密碼還是在分組密碼中，不論在私鑰還是在公鑰密碼中，布爾函數(shù)都有主要應(yīng)用。2025/2/2199第99頁布爾函數(shù)表示為了方便布爾函數(shù)理論和應(yīng)用，人們在不一樣情況下對布爾函數(shù)采取了不一樣表示方法，主要有：真值表表示法小項表示法多項式表示法walsh譜表示法矩陣表示法等2025/2/21100第100頁布爾函數(shù)研究問題布爾函數(shù)表示布爾函數(shù)研究方法布爾函數(shù)設(shè)計實現(xiàn)布爾函數(shù)性質(zhì)滿足一定性質(zhì)布爾函數(shù)特征刻劃、存在性、結(jié)構(gòu)與計數(shù)布爾函數(shù)不一樣性質(zhì)之間等價、相斥、相容、制約等關(guān)系密碼學(xué)中，布爾函數(shù)一條性質(zhì)反應(yīng)一個安全性能指標(biāo)，當(dāng)不一樣性能指標(biāo)相互制約時，怎樣折衷以提升綜合性能；伴隨技術(shù)發(fā)展和新攻擊方法出現(xiàn)，新性質(zhì)提出和研究等等2025/2/21101第101頁本原根（本原元）由Euler定理有:a?(n)=1modn,GCD(a,n)=1考慮更普通表示形式am=1modn,GCD(a,n)=1則最少有m=?(n)使之成立，但可能有更小m存在一旦冪次到m,a冪便出現(xiàn)周期循環(huán)假如最小m=?(n)，則a稱為n一個本原根(primitiveroot)假如n=p為素數(shù)，則a連續(xù)冪生成模p剩下類群。2025/2/21102第102頁使am=1modn

成立最小正冪m(這里(a,n)=1)為以下之一amodn階a

所屬模n指數(shù)a

所產(chǎn)生周期長。Zp中a，假如a階數(shù)?(n)，在a就是n一個本原根。假如a是n本原根，則其冪a,a2,…,a?(n)是(模n)各不相同，且均與n互素。2025/2/21103第103頁尤其，對素數(shù)p，若a是p本原根，則a,a2,…,ap-1是(模p)各不相同。a是Zp生成元。如：素數(shù)19本原根為2,3,10,13,14,15.并不是全部整數(shù)都有本原根。實際上，只有形為2,4,pb,2pb整數(shù)才有本原根，這里p任何奇素數(shù)，b正整數(shù)。2025/2/21104第104頁離散對數(shù)或指標(biāo)求一個數(shù)模p離散對數(shù)(discretelogarithm)是求冪逆問題即求x使之滿足ax=bmodp記x=logabmodporx=inda,p(b)－－以底a(模p)b指標(biāo)。假如a是一個本原根，則x總存在,不然不一定。x=log34mod13(x使3x=4mod13)不存在而x=log23mod13=4（經(jīng)過列出所以冪便知）2025/2/21105第105頁離散對數(shù)問題模指數(shù)運算被認為是一個單向函數(shù)，即：對于給定整數(shù)n,a和x，輕易經(jīng)過“平方-乘”方法計算出axmodn；不過，對于給定整數(shù)n,a和b，由方程ax=bmodn求解整數(shù)x確是一個難題。有限域Zp上離散對數(shù)問題是：對于給定素數(shù)p，有限域Zp上一個本原元a，Zp中非零元b，求解滿足ax=bmodp整數(shù)x(0≤x≤p-2)，x=logab(modp)(通常記為x=logab)。2025/2/21106第106頁離散對數(shù)計算當(dāng)前還沒有能夠計算離散對數(shù)問題多項式時間算法。對于已知攻擊方法，素數(shù)選取應(yīng)該滿足最少兩個條件：長度大于150位p-1最少有一個大素數(shù)因子窮搜索方法能夠?qū)﹄x散對數(shù)進行求解，但對于足夠大素數(shù)p并不可行，其所需計算時間和存放空間均為O(p).2025/2/21107第107頁離散對數(shù)計算有3個群離散對數(shù)是密碼設(shè)計人員最為關(guān)心。這三個群分別是：素域GF(p)乘法群特征為2有限域GF(2n)上乘法群有限域F上橢圓曲線群EC(F)2025/2/21108第108頁離散對數(shù)計算GF(p)上計算離散對數(shù)問題算法有很各種。平凡算法：經(jīng)過預(yù)計算全部可能ax