簡化剩余類歐拉函數(shù)rsa省公開課一等獎全國示范課微課金獎

第三章(2)簡化剩下類、歐拉函數(shù)及其應(yīng)用、RSA第1頁復(fù)習(xí)

第2頁第3頁第4頁第5頁第6頁第7頁第8頁第9頁第10頁第11頁第12頁第13頁第14頁第15頁剩下類及完全剩下系第16頁第17頁第18頁第19頁第20頁第21頁第22頁§3簡化剩下系與歐拉函數(shù)

第23頁第24頁第25頁第26頁第27頁第28頁第29頁§4歐拉定理.費馬定理及應(yīng)用

第30頁第31頁第32頁第33頁公鑰密碼體制34第34頁RSA算法概況MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]發(fā)覺了一個用數(shù)論結(jié)構(gòu)雙鑰方法，稱作MIT體制，以后被廣泛稱之為RSA體制。它既可用于加密,又可用于數(shù)字簽字。RSA算法安全性基于數(shù)論中大整數(shù)分解困難性。35第35頁算法描述－密鑰產(chǎn)生獨立地選取兩大素數(shù)p和q(各100～200位十進制數(shù)字)計算n=p×q，其歐拉函數(shù)值

(n)=(p－1)(q－1)

隨機選一整數(shù)e，1

e<

(n)，gcd(

(n),e)=1在模

(n)下，計算e有逆元d=e-1mod

(n)以n，e為公鑰；私鑰為d。(p,q不再需要，能夠銷毀。)

加密將明文分組，各組對應(yīng)十進制數(shù)小于nc=memodn解密

m=cd

modn36第36頁解密正確性證實cd

modn≡med

modn≡m1

modj(n)

modn≡mkj(n)+1modngcd(m,n)=1

mj(n)≡1modn—歐拉定理mkj(n)≡1modnmkj(n)+1≡mmodngcd(m,n)≠1m是p倍數(shù)或q倍數(shù)，設(shè)m=cp，gcd(m,q)=1,

mj(q)≡1modq，

mkj(q)≡1modq，

[mkj(q)]j(p)≡1modqmkj(n)≡1modq，存在一整數(shù)r，使mkj(n)≡1＋rq兩邊同乘m=cp,mkj(n)+1≡m+rcpq=m+rcn,即mkj(n)+1≡mmodn37第37頁選p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，滿足1<e<φ(n)，且gcd(φ(n),e)=1。確定滿足d·e=1mod96且小于96d，因為77×5=385=4×96+1，所以d為77公開鑰為{5，119}，秘密鑰為{77}。設(shè)明文m=19，則由加密過程得密文為c≡195mod119≡2476099mod119≡66解密為6677mod119≡19例題38第38頁用RSA算法加密與解密過程：例：明文=“RSAALGORITHM”(1)明文用數(shù)字表示空白=00，A=01,B=02,…,Z=26(兩位十進制數(shù)表示)

181901000112071518091300(2)利用加密變換公式C=memodr,即C=18191223mod2867=2756

275605420669234704081815p=47,q=61,(n)=2760時，d=167n=2867e=122339第39頁RSA算法實現(xiàn)怎樣判定一個給定大整數(shù)是素數(shù)？已知d怎樣計算e，使e*d≡1modΦ(n)？怎樣計算C≡Memodn或M≡Cdmodn？40第40頁Miller-Rabin素性檢驗算法

41第41頁求模逆元擴展歐幾里德算法

42第42頁求模冪模重復(fù)平方計算法求am，其中a，m是正整數(shù)：將m表示為二進制形式bkbk-1…b0，m=bk2k+bk-12k-1+…+b12+b043第43頁RSA快速實現(xiàn)加密很快，指數(shù)小解密比較慢，指數(shù)較大利用中國剩下定理CRT，CRT對RSA解密算法生成兩個解密方程（利用M=Cdmodpq）即:M1=Mmodp=(Cmodp)dmod(p-1)

modp

M2=Mmodq=(Cmodq)dmod(q-1)modq解方程M=M1modpM=M2modq含有唯一解（利用CRT）44第44頁RSA安全性RSA安全性是基于分解大整數(shù)困難性假定假如分解n=p×q，則馬上取得

(n)=(p－1)(q－1)，從而能夠確定e模

(n)乘法逆d由n直接求

(n)等價于分解nRSA-129歷時8個月被于1996年4月被成功分解，RSA－130于1996年4月被成功分解密鑰長度應(yīng)該介于1024bit