密碼學(xué)中常用數(shù)學(xué)知識(shí)市公開課一等獎(jiǎng)省賽課獲獎(jiǎng)

公鑰密碼密碼學(xué)中慣用數(shù)學(xué)知識(shí)公鑰密碼體制基本概念RSA算法第1頁(yè)4.1.1群、環(huán)、域群<G,*>定義:一些數(shù)字組成集合一個(gè)二元運(yùn)算，運(yùn)算結(jié)果屬于此集合（封閉性）服從結(jié)合律。有單位元，逆元。假如是可交換，則成為Abel群*為乘法時(shí)，稱為乘法群逆元（a-1）*為加法時(shí)，稱為加法群逆元（-a）環(huán)<R,+,*>定義:

Abel群，及一個(gè)乘法運(yùn)算：滿足結(jié)合律與加法分配律

假如加法滿足交換律,則稱交換環(huán)例：整數(shù)modN（foranyN）第2頁(yè)域<F,+,*>定義：

<F,+>是Abel加群環(huán)<F-{0},*>是Abel乘群例：整數(shù)modP（P為素?cái)?shù)）Galois域：假如n是素?cái)?shù)p

，則模運(yùn)算modulop

形成GaloisFieldmodulop

記為：GF(p)

第3頁(yè)4.1.2素?cái)?shù)和互素?cái)?shù)因子：對(duì)整數(shù)b!=0

及a,假如存在整數(shù)m

使得a=mb,稱b整除a,也稱b是a因子。記作b|a

例1,2,3,4,6,8,12,24

整除24素?cái)?shù)：素?cái)?shù):只有因子1和本身1是一個(gè)平凡素?cái)?shù)例2,3,5,7是素?cái)?shù),4,6,8,9,10不是第4頁(yè)200以內(nèi)素?cái)?shù)：2357111317192329313741434753596167717379838997101103107109113127131137139149151157163167173179181191193197199素?cái)?shù)分解：把整數(shù)n寫成素?cái)?shù)乘積分解整數(shù)要比乘法困難整數(shù)n素?cái)?shù)分解是把它寫素?cái)?shù)乘積

eg.91=7×13;3600=24×32×52

第5頁(yè)互素?cái)?shù)：整數(shù)a,b

互素是指它們沒(méi)有除1之外其它因子。

8與15互素

8因子1,2,4,8 15因子1,3,5,15 1是唯一公因子記為：gcd(8,15)=1第6頁(yè)4.1.3模運(yùn)算設(shè)n是一正整數(shù),a是整數(shù),若a=qn+r,0≤r<n,

則amodn=r若(amodn)=(bmodn),稱為a,b模n同余，記為a≡bmodn稱與a模n同余數(shù)全體為a同余類，記為[a]，a稱為這個(gè)同余類代表元素。-21-20-19-18-17-16–15-14-13-12-11-10-9-8-7-6-5-4-3-2-10123456

78910111213141516171819202122232425262728293031323334第7頁(yè)同余性質(zhì)：若n|(a-b)，則a≡bmodn(amodn)≡(bmodn),則a≡bmodna≡bmodn，則b≡amodna≡bmodn，b≡cmodn，則a≡cmodn求余運(yùn)算amodn將a映射到集合{0,1,…,n-1},求余運(yùn)算稱為模運(yùn)算。模運(yùn)算性質(zhì)[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)×(bmodn)]modn=(a×b)modn第8頁(yè)定理:設(shè)a∈Zn,gcd(a,n)=1,則a在Zn有逆元。證實(shí)思緒：用反證法證實(shí)a和Zn中任何兩個(gè)不一樣數(shù)相乘結(jié)果都不相同從1得出a×Zn=Zn,所以存在x∈Zn,使a×x=1modn設(shè)a為素?cái)?shù)，Zp中每一個(gè)非零元素都與a互素，所以有乘法逆元，有乘法可約律

(a×b)=(a×c)modn,b=cmodn定義Zn為小于n全部非負(fù)整數(shù)集合Zn={0,1,2,…,n-1}第9頁(yè)4.1.4費(fèi)爾瑪定理和歐拉定理費(fèi)爾瑪定理：若p是素?cái)?shù)，a是正整數(shù)且gcd(a,p)=1，則ap-1≡1modp證實(shí)：

當(dāng)gcd(a,p)=1,則a×Zp=Zp。又因?yàn)閍×0≡0modp,所以a×(Zp-{0})=Zp-{0}即：{amodp,2amodp,…,(n-1)amodp}={1,…,p-1}(amodp)×(2amodp)×…×(n-1)amodp=(p-1)!ap-1modp所以：(p-1)!ap-1modp

=(p-1)!modp(p-1)!與p互素，所以乘法可約律，ap-1=1modp第10頁(yè)歐拉函數(shù)設(shè)n為一正整數(shù)，小于n且與n互素正整數(shù)個(gè)數(shù)稱為n歐拉函數(shù)，記為φ(n)

歐拉定理若a和n互素,則aφ(n)=1modn例：Φ(6)=2,Φ(7)=6,Φ(8)=4顯然，若n是素?cái)?shù)，Φ(n)=n-1定理：

若n是兩個(gè)素?cái)?shù)p和q乘積，則Φ(n)＝Φ(p)Φ(q)=(p-1)(q-1)例：21=3×7，所以φ(21)=φ(3)×φ(7)=2×6=12第11頁(yè)4.1.5素性檢驗(yàn)愛拉托斯散(Eratosthenes)篩法定理：設(shè)n是正整數(shù)，若對(duì)全部滿足p≤素?cái)?shù)p，都有p|n，則n一定是素?cái)?shù)。對(duì)給定數(shù)檢驗(yàn)其是否為素?cái)?shù)若要找出小于n全部素?cái)?shù)：

先將2到n之間整數(shù)列出，從中刪除小于等于全部素?cái)?shù)倍數(shù)，余下整數(shù)即是所要求素?cái)?shù)。此方法在n很大時(shí)，實(shí)際上是不可行。第12頁(yè)Miller-Rabin素性概率檢測(cè)法引理：假如p為大于2素?cái)?shù)，則方程x2≡1modp解只有和x≡1和x≡-1證實(shí):x2≡1modp

x2-1≡0modp

(x+1)(x-1)≡0modp

所以：p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)

若p|(x+1)且p|(x-1)，則存在k,j，使x+1=kp,x-1=jp

可得：2=(k-j)p,這是不可能。所以：p|(x+1)或p|(x-1)

設(shè)：p|(x+1)，則x+1=kp

x=-1modp

設(shè)：p|(x-1)，則x-1+1=kp

x=1modp引理逆命題：若方程x2≡1modp，有唯一解x不為+1或-1，p不是素?cái)?shù)。例：x2=1(mod8)12=1mod832=1mod852=1mod872=1mod8又5=-3mod8，7=-1mod8，所以方程解為：1，-1，3，-38不是素?cái)?shù)。第13頁(yè)Miller-Rabin素性概率檢測(cè)法n為待檢測(cè)數(shù)，a為小于n整數(shù)，將n-1表示為二進(jìn)制形式bkbk-1…b0,d賦初值為1，算法關(guān)鍵以下：

fori=kdownto0do{xd;d(d×d)modn;ifd=1and(x≠1)and(x≠n-1)thenreturnFalseifbi=1thed(d×a)modn}ifd≠1thenreturnFalse;returnTrue若返回False,n不是素?cái)?shù),若返回True,有可能是素?cái)?shù)。For循環(huán)結(jié)束,有d≡an-1modn。由費(fèi)爾瑪定理,若n為素?cái)?shù),d為1。所以d≠1，則d不是素?cái)?shù)。n-1≡-1modn,所以x≠1和x≠n-1指x2≡1modn有非±1根,n不是素?cái)?shù)。第14頁(yè)4.1.6歐幾里得算法2.兩個(gè)正整數(shù)互素，能夠求一個(gè)數(shù)關(guān)于另一個(gè)數(shù)乘法逆元性質(zhì):

對(duì)任意非負(fù)整數(shù)a和正整數(shù)b,

有g(shù)cd(a,b)=gcd(b,amodb)證實(shí)：

1.求兩個(gè)正整數(shù)最大公因子a=kb+r≡rmodbamodb=a-kb

設(shè)d是a，b公因子，即d|a,d|b,所以d|kb.由d|a和d|kb，得d|(amodb)，故d是b和amodb公因子。

a,b以及b,amodb公因子集合相同，故最大公因子也相同。gcd(55,22)=gcd(22,11)=gcd(11,0)=11gcd(11,10)=gcd(10,1)=1第15頁(yè)Euclid(f,d)f>d1.Xf;Yd;2.IfY=0thenreturnX=gcd(f,d)3.R=XmodY4.X=Y;5.Y=R6.Goto2假定輸入是兩個(gè)正整數(shù)Euclid算法：gcd(55,22)=gcd(22,11)=gcd(11,0)=11gcd(11,10)=gcd(10,1)=1第16頁(yè)歐幾里德算法--求乘法逆元若gcd(a,b)=1,b在模a下有乘法逆元(設(shè)b<a)。即存在x<a,bx≡1moda思緒：求gcd(a,b)，當(dāng)gcd(a,b)=1時(shí)，則返回b逆元。整除中一個(gè)論斷：若gcd(a,b)=d，則存在m,n，使得d=ma+nb。則當(dāng)gcd(a,b)=1時(shí)，有ma+nb=1，即m是a模b逆元，n是b模a逆元。第17頁(yè)ExtendedEuclid(f,d)(f>d)1.（X1X2X3)(1,0,f);(Y1Y2Y3)(0,1,d);2.IfY3=0,thenreturnX3=gcd(f,d);停頓，沒(méi)有逆元;3.IfY3=1,thenreturnX3=gcd(f,d);Y2=d-1modf;4.Q=X3divY3（整數(shù)除）;5.(T1T2T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1X2X3)(Y1Y2Y3);7.(Y1Y2Y3)(T1T2T3);8.Goto2擴(kuò)展歐幾里德算法：求d模f逆元第18頁(yè)例：求解11d(mod51)=1步驟。即求11-1mod51=？循環(huán)次數(shù)QX1X2X3Y1Y2Y3初值--10510111ExtendedEuclid(f,d)(f>d)1.（X1X2X3)(1,0,f);(Y1Y2Y3)(0,1,d);2.IfY3=0,thenreturnX3=gcd(f,d);

停頓，沒(méi)有逆元;3.IfY3=1,thenreturnX3=gcd(f,d);Y2=d-1modf;4.Q=X3divY3（整數(shù)除）;5.(T1T2T3)(X1