初等數(shù)論ppt第三章簡化剩余類歐拉函數(shù)ppt課件.ppt

《初等數(shù)論ppt第三章簡化剩余類歐拉函數(shù)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第三章(2)簡化剩余類、歐拉函數(shù)及其應(yīng)用、RSA復(fù)習(xí)剩余類及完全剩余系§3簡化剩余系與歐拉函數(shù)§4歐拉定理.費馬定理及應(yīng)用公鑰密碼體制36RSA算法概況MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman等[1978,1979]發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，稱作MIT體制，后來被廣泛稱之為RSA體制。它既可用于加密、又可用于數(shù)字簽字。RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。37算法描述－密鑰產(chǎn)生獨立地選取兩大素數(shù)p和q(各100～200位十進(jìn)制數(shù)字)計算n=p×q，其歐拉函數(shù)值?(n)=(p－1)(q

2、－1)隨機(jī)選一整數(shù)e，1?e

3、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≡mmodn39選p=7，q=17。求n=p×q=119，φ(n)=(p-1)(q-1)=96。取e=5，滿足1

4、程得密文為c≡195mod119≡2476099mod119≡66解密為6677mod119≡19例題40用RSA算法加密與解密的過程：例：明文=“RSAALGORITHM”(1)明文用數(shù)字表示空白=00，A=01,B=02,…,Z=26(兩位十進(jìn)制數(shù)表示)1819010001120715180920081300(2)利用加密變換公式C=memodr,即C=18191223mod2867=27562756200105420669234704081815p=47,q=61,?(n)=2760時，d=167n=2867e=122341RSA

5、算法實現(xiàn)如何判定一個給定的大整數(shù)是素數(shù)？已知d如何計算e，使e*d≡1modΦ(n)？如何計算C≡Memodn或M≡Cdmodn？42Miller-Rabin素性檢驗算法43求模逆元的擴(kuò)展歐幾里德算法44求模冪的模重復(fù)平方計算法求am，其中a，m是正整數(shù)：將m表示為二進(jìn)制形式bkbk-1…b0，m=bk2k+bk-12k-1+…+b12+b045RSA的快速實現(xiàn)加密很快，指數(shù)小解密比較慢，指數(shù)較大利用中國剩余定理CRT，CRT對RSA解密算法生成兩個解密方程（利用M=Cdmodpq）即:M1=Mmodp=(Cmodp)dmod(p-1)

6、modpM2=Mmodq=(Cmodq)dmod(q-1)modq解方程M=M1modpM=M2modq具有唯一解（利用CRT）46RSA的安全性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到2048bit之間4748RSA的安全性

7、p-q

8、要大p-1,q-1都應(yīng)有大的素因子。e

9、/4,則d能被容易的確定。49作業(yè)6P601,3P641,2