現(xiàn)代密碼學(xué)課件第10講-公鑰密碼

公鑰密碼數(shù)論簡介公鑰密碼體制的基本概念RSA算法橢圓曲線密碼體制2023/10/81公鑰密碼數(shù)論簡介2023/10/81數(shù)論簡介2023/10/82數(shù)論簡介2023/10/82模運算設(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稱為這個同余類的代表元素

2023/10/83模運算設(shè)n是一正整數(shù),a是整數(shù),若2023/10/83模運算同余的性質(zhì)若n|(a-b)，則a≡bmodn(amodn)≡(bmodn),則a≡bmodna≡bmodn，則b≡amodna≡bmodn，b≡cmodn，則a≡cmodn求余運算amodn將a映射到集合{0,1,…,n-1},求余運算稱為模運算2023/10/84模運算同余的性質(zhì)2023/10/84模運算模運算的性質(zhì)[(amodn)+(bmodn)]modn=(a+b)modn[(amodn)-(bmodn)]modn=(a-b)modn[(amodn)×(bmodn)]modn=(a×b)modn2023/10/85模運算模運算的性質(zhì)2023/10/85模運算例：Z8={0,1,2,3,4,5,6,7},模8加法和乘法＋01234567001234567112345670223456701334567012445670123556701234667012345770123456×012345670000000001012345672024602463036147254040404045052741636064206427076543212023/10/86模運算例：Z8={0,1,2,3,4,5,6,7},模8加法模運算若x+y=0modn,y為x的加法逆元。每一元素都有加法逆元若對x，有xy=1modn，稱y為x的乘法逆元。在上例中，并非所有x都有乘法逆元定義Zn={0,1,..,n-1}為模n的同余類集合。2023/10/87模運算若x+y=0modn,y為x的加法逆元。每一元素模運算Zn上模運算的性質(zhì)交換律（x+w)modn=(w+x)modn(x×w)modn=(w×x)modn結(jié)合律[(x+w)+y]modn=[x+(w+y)]modn[(x×w)×y]modn=[x×(w×y)]modn分配律[w×(x+y)]modn=[w×x+w×y)]modn2023/10/88模運算Zn上模運算的性質(zhì)2023/10/88模運算單位元(0+w)modn=wmodn(1×w)modn=wmodn加法逆元：對w∈Zn,有z∈Zn，滿足w+z=0modn,z為w的加法逆元，記為z=-w。加法的可約律(a+b)≡(a+c)modn,則b≡cmodn對乘法不一定成立，因為乘法逆元不一定存在。2023/10/89模運算單位元2023/10/89模運算定理:設(shè)a∈Zn,gcd(a,n)=1,則a在Zn有逆元證明思路：用反證法證明a和Zn中任何兩個不同的數(shù)相乘結(jié)果都不相同從1得出a×Zn=Zn,因此存在x∈Zn,使a×x=1modn設(shè)p為素數(shù)，Zp中每一個非零元素都與p互素，因此有乘法逆元，有乘法可約律(a×b)=(a×c)modn,b=cmodn2023/10/810模運算定理:設(shè)a∈Zn,gcd(a,n)=1,則a在Zn有逆費爾瑪定理和歐拉定理費爾瑪定理

若p是素數(shù)，a是正整數(shù)且gcd(a,p)=1，則ap-1≡1modp證明：gcd(a,p)=1,則a×Zp=Zp,a×(Zp-{0})=Zp-{0}{amodp,2amodp,…,(n-1)amodp}={0,1,…,p-1}(amodp)×(2amodp)×…×(n-1)amodp=(p-1)!modp(p-1)!×ap-1=(p-1)!modp(p-1)!與p互素，所以乘法可約律，ap-1=1modp2023/10/811費爾瑪定理和歐拉定理費爾瑪定理2023/10/811費爾瑪定理和歐拉定理歐拉函數(shù)設(shè)n為一正整數(shù)，小于n且與n互素的正整數(shù)的個數(shù)稱為n的歐拉函數(shù)，記為j(n)定理：若n是兩個素數(shù)p和q的乘積，則j(n)＝j(luò)(p)j(q)=(p-1)(q-1)歐拉定理若a和n互素,則aj(n)=1modn2023/10/812費爾瑪定理和歐拉定理歐拉函數(shù)2023/10/812素性檢驗引理：如果p為大于2的素數(shù)，則方程x2≡1modp的解只有和x≡1和x≡-1證明:

x2≡1modp

x2-1≡0modp(x+1)(x-1)≡0modp所以,p|(x+1)或p|(x-1)或p|(x+1)且p|(x-1)存在k,j，x+1=kp,x-1=jp2=(k-j)p,這是不可能的。引理的逆命題：若方程x2≡1modp有唯一解x不為+1或-1，p不是素數(shù)2023/10/813素性檢驗引理：如果p為大于2的素數(shù)，則方程x2≡1mod素性檢驗Miller-Rabin素性概率檢測法n為待檢測數(shù)，a為小于n的整數(shù)，將n-1表示為二進制形式bkbk-1…b0,d賦初值為1，算法核心如下

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不是素數(shù),若返回True,有可能是素數(shù)。2023/10/814素性檢驗Miller-Rabin素性概率檢測法2023/10素性檢測For循環(huán)結(jié)束,有d≡an-1modn.由費爾瑪定理,若n為素數(shù),d為1.所以d≠1，則d不是素數(shù)n-1≡-1modn,所以x≠1和x≠n-1指x2≡1modn有非±1的根,n不是素數(shù)該算法對s個不同的a，重復(fù)調(diào)用，如果每次都返回true，則n是素數(shù)的概率大于等于1-2-s2023/10/815素性檢測For循環(huán)結(jié)束,有d≡an-1modn.由費爾瑪歐幾里德算法求兩個正整數(shù)的最大公因子兩個正整數(shù)互素，可以求一個數(shù)關(guān)于另一個數(shù)的乘法逆元性質(zhì):對任意非負整數(shù)a和正整數(shù)b,有

gcd(a,b)=gcd(b,amodb)證明：a=kb+r≡rmodbamodb=a-kb設(shè)d|a,d|b,所以d|kb.由d|a和d|kb，得d|(amodb)故d是b和amodb的公因子。a,b以及b,amodb公因子集合相同，故最大公因子也相同2023/10/816歐幾里德算法求兩個正整數(shù)的最大公因子2023/10/816Euclid(f,d)f>d1.Xf;Yd;2.IfY=0thenreturnX=gcd(f,d)3.R=XmodY4.X=Y;5.Y=R6.Goto2歐幾里德算法例:gcd(55,22)=gcd(22,11)=gcd(11,0)=112023/10/817Euclid(f,d)f>d歐幾里德算法例:gcd(55歐幾里德算法求乘法逆元若gcd(a,b)=1,b在模a下有乘法逆元(設(shè)b<a)。即存在x<a,bx≡1modaExtendedEuclid(f,d)(f>d)1.（X1X2X3)(1,0,f);(Y1Y2Y3)(0,1,d);2.IfY3=0,thenreturnX3=gcd(f,d);noinverse;3.IfY3=1,thenreturnX3=gcd(f,d);Y2=d-1modf;4.Q=X3div

Y3;5.(T1T2T3)(X1-QY1,X2-QY2,X3-QY3);6.(X1X2X3)(Y1Y2Y3);7.(Y1Y2Y3)(T1T2T3);8.Goto22023/10/818歐幾里德算法求乘法逆元2023/10/818中國剩余定理如果已知某個數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就可以重構(gòu)這個數(shù)定理(中國剩余定理)：設(shè)m1,m2,…,mk是兩兩互素的正整數(shù)，則一次同余方程組對模M有唯一解

2023/10/819中國剩余定理如果已知某個數(shù)關(guān)于一些量量互素的數(shù)的同余類集，就中國剩余定理中國剩余定理可以將一個很大的數(shù)x表示為一組較小的數(shù)(a1,…ak)例：x≡1mod2,