《應(yīng)用密碼學(xué)》課件9-非對(duì)稱(chēng)密碼

非對(duì)稱(chēng)密碼體制

（公鑰密碼體制）公鑰密碼體制提出和分類(lèi)公鑰密碼體制概念單陷門(mén)函數(shù)概念RSA算法EIGamal算法橢圓曲線(xiàn)密碼算法密鑰分配：加密者指定一個(gè)密鑰后，必須得想方設(shè)法把密鑰分發(fā)出去給解密者，同時(shí)還得小心翼翼確保密鑰不被泄露。這是對(duì)稱(chēng)密碼算法固有的一個(gè)矛盾，如何解決呢？對(duì)稱(chēng)密碼進(jìn)行密鑰分配的要求：已經(jīng)共享一個(gè)密鑰：利用密鑰分配中心：第一個(gè)密鑰如何獲得和KDC之間的密鑰如何獲得公鑰密碼體制的提出公鑰密碼---密鑰問(wèn)題

使用非對(duì)稱(chēng)密鑰密碼體制進(jìn)行秘密通信時(shí)，假設(shè)一個(gè)網(wǎng)絡(luò)中有n個(gè)用戶(hù)，則需要2n個(gè)密鑰，若n=1000，則2000，則與對(duì)稱(chēng)密碼體制的密鑰500000，密鑰管理的復(fù)雜度大大縮小。非對(duì)稱(chēng)密碼體制密鑰的復(fù)雜度是線(xiàn)性的2n

對(duì)稱(chēng)密碼體制密鑰的復(fù)雜度是平方級(jí)的n(n-1)/2實(shí)際需要－密鑰管理6公鑰加密模型公鑰加密體制的原理密鑰分配Bob（發(fā)送端）Alice（接收端）公開(kāi)的密鑰7

公鑰密碼體制的原理8公鑰加密體制的原理郵箱的例子任何人可以向郵箱投舉報(bào)信用戶(hù)(審計(jì)人員)才能打開(kāi)郵箱，讀信的內(nèi)容9公鑰加密體制的原理公鑰密鑰對(duì)參數(shù)生成需滿(mǎn)足的要求：公開(kāi)密鑰(public-key),可以被任何人知道,用于加密或驗(yàn)證簽名；私鑰(private-key),只能被消息的接收者或簽名者知道,用于解密或簽名；由私鑰及公開(kāi)參數(shù)容易計(jì)算出公開(kāi)密鑰；由公鑰及公開(kāi)參數(shù)推導(dǎo)私鑰是困難的；10定義單向函數(shù)是兩個(gè)集合X、Y之間的一個(gè)映射，使得Y中每一元素y都有惟一的一個(gè)原像x∈X，且由x易于計(jì)算它的像y，由y計(jì)算它的原像x是不可行的.一個(gè)函數(shù)是單向陷門(mén)函數(shù)，是指該函數(shù)是易于計(jì)算的，但求它的逆是不可行的，除非再已知某些附加信息。當(dāng)附加信息給定后，求逆可在多項(xiàng)式時(shí)間完成.單向陷門(mén)函數(shù)11單向陷門(mén)函數(shù)是一族可逆函數(shù)fk，滿(mǎn)足①Y=fk1(X)易于計(jì)算（當(dāng)k1和X已知時(shí)）.②X=f-1k2(Y)易于計(jì)算（當(dāng)k2和Y已知時(shí)）.③X=f-1k2(Y)計(jì)算上是不可行的（當(dāng)Y已知，但k2未知時(shí)）已知K1，計(jì)算出K2是不可行的（當(dāng)K1已知，但k2未知時(shí)）研究公鑰密碼算法就是要找出合適的陷門(mén)單向函數(shù)單向陷門(mén)函數(shù)公鑰密碼體制的發(fā)展歷史Diffie和Hellman公鑰密碼體制的發(fā)展歷史RonaldRivest,AdiShamir,andLenAdleman14RSA算法是1978年由R.Rivest,A.Shamir和L.Adleman提出的一種用數(shù)論構(gòu)造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。它既可用于加密、又可用于數(shù)字簽字。

RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。

RLRivest,AShamir,LAdleman,"OnDigitalSignaturesandPublicKeyCryptosystems",CommunicationsoftheACM,vol21no2,pp120-126,Feb1978RSA算法151.密鑰的產(chǎn)生①選兩個(gè)安全的大素?cái)?shù)p和q。②計(jì)算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿(mǎn)足1<e<φ(n)，且gcd(φ(n),e)=1。④計(jì)算d，滿(mǎn)足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運(yùn)算可知，它的乘法逆元一定存在。(一般公鑰取值為65537（216+1））⑤以{e,n}為公開(kāi)鑰（PK）,{d,n}為秘密鑰（SK）。RSA算法1選取大素?cái)?shù)的方法：隨機(jī)產(chǎn)生一個(gè)大整數(shù)，利用素性檢測(cè)算法判定該整數(shù)是否為素?cái)?shù)2以往素檢測(cè)的算法都是概率性的，即存在一定的錯(cuò)誤概率；32003年，印度人發(fā)表文章“PrimesisinP”，證明了素判定問(wèn)題是一個(gè)多項(xiàng)式時(shí)間問(wèn)題。1）輾轉(zhuǎn)相除法2）利用歐拉定理求e^{φ(

φ(n))}-1思考：分析兩種計(jì)算方法的效率162.加密加密時(shí)首先將明文比特串分組，使得每個(gè)分組對(duì)應(yīng)的十進(jìn)制數(shù)小于n，即分組長(zhǎng)度小于log2n。然后對(duì)每個(gè)明文分組m，作加密運(yùn)算：

c≡memodnRSA算法173.解密對(duì)密文分組的解密運(yùn)算為：m≡cdmodn證明RSA算法中解密過(guò)程的正確性.證明：由加密過(guò)程知c≡memodn，所以cdmodn≡medmodn≡m1

modφ(n)modn≡mkφ(n)+1modnRSA算法18下面分兩種情況：①m與n互素，則由Euler定理得mφ(n)≡1modn,mkφ(n)≡1modn,mkφ(n)+1≡mmodn即cdmodn≡m。②gcd(m,n)≠1，先看gcd(m,n)=1的含義，由于n=pq，所以gcd(m,n)=1意味著m不是p的倍數(shù)也不是q的倍數(shù)。因此gcd(m,n)≠1意味著m是p的倍數(shù)或q的倍數(shù)，不妨設(shè)m=tp，其中t為一正整數(shù)。此時(shí)必有g(shù)cd(m,q)=1，否則m也是q的倍數(shù)，從而是pq的倍數(shù)，與m<n=pq矛盾RSA算法19

由gcd(m,q)=1及Euler定理得mφ(q)≡1modq，所以mkφ(q)≡1modq,［mkφ(q)］φ(p)≡1modq,mkφ(n)≡1modq

因此存在一整數(shù)r，使得mkφ(n)=1+rq，兩邊同乘以m=tp得mkφ(n)+1=m+rtpq=m+rtn即mkφ(n)+1≡mmodn，所以cdmodn≡m.RSA算法RSA保密通信示意圖歐拉(Euler)函數(shù)

設(shè)

(m)為小于或等于m且與m互素的正整數(shù)個(gè)數(shù)，稱(chēng)

(m)為歐拉(Euler)函數(shù)。例如，

(3)＝2，

(5)＝4，

(8)＝4。顯然，當(dāng)p為素?cái)?shù)時(shí)，

(p)＝p－1。關(guān)于歐拉函數(shù)的重要結(jié)論關(guān)于歐拉函數(shù)的重要結(jié)論。若(m1，m2)＝1，則

(m1m2)＝

(m1)

(m2),尤其是當(dāng)m1，m2都為素?cái)?shù)時(shí)，

(m1m2)＝

(m1)

(m2)＝(m1-1)(m2-1).例如，

(15)=

(3)×

(5)=2×4=8.實(shí)際上，這些數(shù)是1，2，4，7，8，11，13，14，共8個(gè)。可以用等差數(shù)列的方式證明當(dāng)m1，m2都為素?cái)?shù)時(shí)的情形歐拉定理

歐拉定理設(shè)n≥2且(a，n)＝1，則a

(n)

1(modn)例如，求132001mod17。因?yàn)?13，17)＝1，所以13

(17)

1(mod17)，因?yàn)?/p>

(17)＝16，即1316≡1(mod17)。而2001＝125×16＋1，132001＝（1316）125·13≡13(mod17)，即被17除得的余數(shù)為13。當(dāng)n為素?cái)?shù)p時(shí)，就是費(fèi)爾馬定理。費(fèi)爾馬定理若p是素?cái)?shù)，(a，p)＝1，則ap-1≡1(modp).RSA算法舉例在RSA算法密鑰產(chǎn)生過(guò)程中，設(shè)p=13，q=23，取公鑰e＝29，則私鑰d可以用歐幾里德擴(kuò)展算法求出。由已知可得n=pq=13*23=299，φ(n)=(p-1)(q-1)=12*22=264。e*d≡1modφ(n)怎么求解264=29*9+329=3*9+23=2+1

1=3-2=3-(29-3*9)=3*10-29=(264-29*9)*10-29=264*10-29*91=-91≡173mod264由歐幾里德擴(kuò)展算法可得：d為173。逆元設(shè)m是正整數(shù)，a是整數(shù)，如果存在a’,使得a×a’≡1(modm)成立，則a叫模m的可逆元，a’叫a模m的逆元。例如，設(shè)m為11，則8模11的逆元為7，因?yàn)?×7≡1(mod11)當(dāng)a和m互素的情況下，即（a,m）=1,則a的模m的逆元總是存在的，且可以用上面的輾轉(zhuǎn)相除法求得。求逆元舉例例如，我們知道89是素?cái)?shù)，求60模89的逆元，可以用下面方法。89=1×60+2960=2×29+229=14×2+1則1=29-14×2=29-14×(60-2×29)=29×29-14×60=(89-60)×29-14×60=89×29-60×43求逆元舉例等式兩端同時(shí)mod89得：60×(-43)≡1mod89故60模89的逆元為-43，為方便記為最小非負(fù)數(shù)，因?yàn)?43≡46mod89，故一般說(shuō)60模89的逆元為46.如何用程序?qū)崿F(xiàn)求逆元？實(shí)際上，這里的逆元通常稱(chēng)為乘法逆元。從后面的學(xué)習(xí)可以看到，定義不同的運(yùn)算和單位元，就可能有不同情況下的逆元。RSA算法舉例（1）加密過(guò)程：設(shè)RSA算法的參數(shù)選擇如上所述，當(dāng)消息m=9所對(duì)應(yīng)的密文的計(jì)算過(guò)程為：929mod299＝211（2）解密過(guò)程：211173mod299≡929例：選p=7，q=17.取e=5，設(shè)明文m=19，求密文c求得n=p×q=119，φ(n)=(p-1)(q-1)=96.取e=5，滿(mǎn)足1<e<φ(n)，且gcd(φ(n),e)=1，計(jì)算滿(mǎn)足d·e=1mod96且小于96的d.因?yàn)?7×5=385=4×96+1，所以d為77，因此公開(kāi)鑰為{5，119}，秘密鑰為{77，119}.設(shè)明文m=19，則由加密過(guò)程得密文為c≡195mod119≡2476099mod119≡66;解密過(guò)程為m≡6677mod119≡19.RSA算法30RSA中的計(jì)算問(wèn)題1.RSA的加密與解密過(guò)程

RSA的加密、解密過(guò)程都為求一個(gè)整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計(jì)算，則中間結(jié)果非常大，有可能超出計(jì)算機(jī)所允許的整數(shù)取值范圍。如上例中解密運(yùn)算6677mod119，先求6677再取模，則中間結(jié)果就已遠(yuǎn)遠(yuǎn)超出了計(jì)算機(jī)允許的整數(shù)取值范圍。而用模運(yùn)算的性質(zhì)：(a×b)modn=[(amodn)×(bmodn)]modn就可減小中間結(jié)果。RSA算法模冪運(yùn)算問(wèn)題31

2.模指數(shù)運(yùn)算的快速算法

例如求x16，直接計(jì)算的話(huà)需做15次乘法。然而如果重復(fù)對(duì)每個(gè)部分結(jié)果做平方運(yùn)算即求x，x2，x4，x8，x16則只需4次乘法。求am可如下進(jìn)行，其中a，m是正整數(shù)：將m表示為二進(jìn)制形式bkbk-1…b0，即m=bk2k+bk-12k-1+…+b12+b0因此bk=0而bk-i=1或者bk-i=0RSA算法模冪運(yùn)算32例：求a1919=1×24+0×23+0×22+1×21+1×20所以

a19=((((a1)2a0)2a0)2a1)2a1練習(xí)：求a7和a8，并統(tǒng)計(jì)快速運(yùn)算法的運(yùn)算次數(shù).

RSA算法平方乘算法/***令m=bk2k+bk-12k-1+…+b12+b0，求am=?***/d=1;fori=kdownto0{d≡(d×d)modn;ifbi=1then{d≡(d×a)modn}}returnd注意：在RSA中，運(yùn)算的形式一般是memodn,則在程序或算法中，所有的乘法或乘方運(yùn)算之后都有一個(gè)模運(yùn)算。練習(xí)題求解1177mod23=？練習(xí)題求解1177mod23=？77=(1001101)2ibidd=1611*11mod23≡115011*11mod23≡6406*6mod23≡133113*13mod23≡88*11mod23≡192119*19mod23≡1616*11mod23≡151015*15mod23≡180118*18mod23≡22*11mod23≡2236

整數(shù)分解問(wèn)題：已知n是兩個(gè)大素?cái)?shù)的乘積，求n的素分解RSA的安全性是基于分解大整數(shù)困難的假定

如果RSA的模數(shù)n被成功地分解為p×q，則獲得φ(n)=(p-1)(q-1)，從而攻擊者能夠從公鑰e解出d，即d≡e-1modφ(n)，攻擊成功.

RSA算法的安全性37

至今還未能證明分解大整數(shù)就是NPC問(wèn)題，也許有尚未發(fā)現(xiàn)的多項(xiàng)式時(shí)間分解算法.

隨著人類(lèi)計(jì)算能力的不斷提高，原來(lái)被認(rèn)為是不可能分解的大數(shù)已被成功分解.例如RSA-129（即n為129位十進(jìn)制數(shù)，大約428個(gè)比特）已在網(wǎng)絡(luò)上通過(guò)分布式計(jì)算歷時(shí)8個(gè)月于1994年4月被成功分解，RSA-130已于1996年4月被成功分解.RSA算法的安全性38

分解算法的進(jìn)一步改進(jìn).過(guò)去分解算法都采用二次篩法,

如對(duì)RSA-129的分解.而對(duì)RSA-130的分解則采用了一個(gè)新算法，稱(chēng)為推廣的數(shù)域篩法，該算法在分解RSA-130時(shí)所做的計(jì)算僅比分解RSA-129多10%.1）在使用RSA算法時(shí)對(duì)其密鑰的選取要特別注意其大小。估計(jì)在未來(lái)一段比較長(zhǎng)的時(shí)期，密鑰長(zhǎng)度介于1024比特至2048比特之間的RSA是安全的.RSA算法的安全性392）|p-q|要大由，如果|p-q|小，則(p-q)2/4也??；因此(p+q)2/4稍大于n,即(p+q)/2稍大于n1/2。那么①順序檢查大于n1/2的每一整數(shù)x，直到找到一個(gè)x使得x2-n是某一整數(shù)（記為y）的平方。②由x2-n=y2，得n=(x+y)(x-y)，可得n的分解.例如若n=79523，則n1/2

>281，則2822-79523=1，因此p=282+1=283，q=282-1=281RSA算法的安全性403）p-1和q-1都應(yīng)有大素因子設(shè)攻擊者截獲密文c，可如下進(jìn)行重復(fù)加密：

RSA算法的安全性41若，即，則有，即，所以在重復(fù)加密的倒數(shù)第2步就可以恢復(fù)出明文m.這種攻擊法只有在t較小時(shí)才是可行的，為抵抗這種攻擊，應(yīng)保證使t很大.所以為使t大，p-1和q-1都應(yīng)有大的素因子，且Φ((p-1)*(q-1))有大的素因子RSA算法的安全性RSA算法的安全性4）RSA的選擇密文攻擊一般攻擊者是將希望解密的信息C作一下偽裝reC，讓擁有私鑰的實(shí)體解密（簽名）。然后，經(jīng)過(guò)解密計(jì)算就可得到它所想要的信息。

(reC)d=red*Cdmodn=r*Mmodn，所以M=(reC)d*r-1這個(gè)固有的問(wèn)題來(lái)自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無(wú)法解決這一問(wèn)題，只有采用好的公鑰協(xié)議，保證工作過(guò)程中實(shí)體不對(duì)其他實(shí)體任意產(chǎn)生的信息解密。RSA算法的安全性5）RSA的公共模數(shù)攻擊若系統(tǒng)中用戶(hù)共有一個(gè)模數(shù)n，而擁有不同的e和d。若存在同一信息（設(shè)為P）分別用不同的公鑰（e1和e2）加密，C1=Pe1modn；C2=pe2modn設(shè)密碼分析者截獲n、e1、e2、C1和C2，若恰好e1和e2互質(zhì)，則他可以得到P。RSA算法的安全性證明：因?yàn)閑1和e2互質(zhì)，故用Euclidean算法能找到r和s，滿(mǎn)足：r*e1+s*e2=1則(C1)r*(C2)s=(Pe1)r*(pe2)smodn=Pr*e1+s*e2modn=Pmodn不要共享模數(shù)n其它共模攻擊方法：在共模假設(shè)下，一對(duì)e和d將有利于攻擊者分解模數(shù)；或者計(jì)算出其它成對(duì)的e’和d’，而無(wú)需分解模數(shù)。45RSA算法的安全性RSA存在很多種攻擊，并不是因?yàn)樗惴ū旧泶嬖谌毕荩怯捎趨?shù)選擇不當(dāng)造成的，為保證算法足夠安全，參數(shù)須滿(mǎn)足下面幾個(gè)基本要求：需要選擇足夠大的素?cái)?shù)p,q,|p-q|較大，且(p-1)和(q-1)沒(méi)有小的素因子.通常選擇小的加密指數(shù)e,且與?(N)

互素，

e對(duì)所有用戶(hù)可以是相同的，最初建議使用e=3，現(xiàn)在3太小，常使用e=216-1=65535.解密指數(shù)比較大素?cái)?shù)的產(chǎn)生在非對(duì)稱(chēng)密碼體制中，無(wú)論是基于大數(shù)分解難題，還是離散對(duì)數(shù)難題，都要用到大素?cái)?shù)。因而，尋找大素?cái)?shù)一直是密碼學(xué)家十分關(guān)注的。對(duì)于一個(gè)大整數(shù)是不是素?cái)?shù)，數(shù)學(xué)家們已經(jīng)做了很多探索，也提出了一些有效地算法，人們常采用的是Miller-Rabin算法，該算法常用來(lái)判斷一個(gè)大整數(shù)是否素?cái)?shù)的算法。如果該算法判定一個(gè)數(shù)是合數(shù)，這個(gè)數(shù)肯定是合數(shù)。Miller-Rabin算法是一個(gè)概率算法。也就是說(shuō)，該算法判定一個(gè)大整數(shù)是素?cái)?shù)，該整數(shù)不是素?cái)?shù)的概率很小。Miller-Rabin概率檢測(cè)算法Miller-Rabin概率檢測(cè)算法的理論基礎(chǔ)是費(fèi)爾馬定理，即設(shè)n是正奇整數(shù)，如果n是素?cái)?shù)，由費(fèi)爾馬定理，對(duì)于任意整數(shù)b(1<b<n-1),有bn-1≡1modn.如果n是素?cái)?shù)，該等式一定成立；如果n不是素?cái)?shù)，該等式一般不成立。如果n不是素?cái)?shù)而又使得該等式成立，稱(chēng)n為對(duì)于基b的擬素?cái)?shù)。擬素?cái)?shù)就表示不是素?cái)?shù)是合數(shù)。整數(shù)63是合數(shù)，當(dāng)b=8時(shí)，該等式成立，稱(chēng)整數(shù)63是對(duì)于基b=8的擬素?cái)?shù)由此可知，如果對(duì)整數(shù)b(1<b<n-1),(n,b)=1,使得bn-1≡1modn不成立，則n是一個(gè)合數(shù)。Miller-Rabin概率檢測(cè)算法由上面的討論可知，判斷一個(gè)正奇整數(shù)是不是合數(shù)，可以通過(guò)嘗試找整數(shù)b(1<b<n-1),(n,b)=1,使得bn-1≡1modn成立與否。如果不成立，則n是一個(gè)合數(shù)，如果成立，則n可能是素?cái)?shù)，可以通過(guò)再找別的整數(shù)b(1<b<n-1)進(jìn)行嘗試。Miller-Rabin概率檢測(cè)算法正是如此Miller-Rabin概率檢測(cè)算法的實(shí)現(xiàn)思路計(jì)算n-1=2st，則有：故若bn-1≡1(modn)，則下面等式至少有一個(gè)成立。，Miller-Rabin概率檢測(cè)算法可如下描述Miller-Rabin(n)//把n-1寫(xiě)成n-1=2st,其中t是一個(gè)奇數(shù),選取隨機(jī)整數(shù)a,使得1<a<n-1b≡at(modn)ifb≡1(modn)thenreturn(“n通過(guò)測(cè)試，n可能是素?cái)?shù)”),結(jié)束fori=0tos-1{ifb≡-1(modn)thenreturn(“n通過(guò)測(cè)試，n可能是素?cái)?shù)”),結(jié)束

elseb≡b2(modn)}return(“n是合數(shù)”)Miller-Rabin概率檢測(cè)算法舉例Miller-Rabin概率檢測(cè)算法舉例例5-3：取n=29，29-1=22*7,即s=2,t=7設(shè)a=3,b=37(mod29)≡12,i=0,b2=144(mod29)≡-1輸出：n是素?cái)?shù)設(shè)a=4,b=47(mod29)≡28,i=0,b=28(mod29)≡-1輸出：n是素?cái)?shù)此例為判定合數(shù)為素?cái)?shù)的例子以n=25,a=7為例。取n=25，25-1=23*3,即s=3,t=3由算法，b=73≡18mod25i=0,b2=182≡-1(mod25),輸出：n是素?cái)?shù)實(shí)際上，25是合數(shù)。這時(shí)可以通過(guò)另選擇一個(gè)a(1<a<n-1),(n,a)=1,如a=2，再次運(yùn)行算法。由算法，b=23≡8mod25i=0,b2=82=64≡14(mod25)i=1,b2=142=196≡21(mod25)i=2,b2=212=441≡16(mod25)循環(huán)完畢，輸出：n是合數(shù)由此判斷n肯定是個(gè)合數(shù)。（2）大素?cái)?shù)個(gè)數(shù)的估計(jì)通過(guò)一個(gè)簡(jiǎn)單的例子，可以明白大素?cái)?shù)的個(gè)數(shù)是十分龐大的資源，不用擔(dān)心會(huì)被用完。例5-8：小于10100

的素?cái)?shù)個(gè)數(shù)x大概為多少？由素?cái)?shù)個(gè)數(shù)定理，x=10100/ln10100因

ln10100<log210100=100*log210<100*4=400

故x=10100/ln10100>10100/400可以看到，這是非?？捎^的數(shù)量。事實(shí)上，素?cái)?shù)的分布是數(shù)字越大越稀，所以沒(méi)有上面估計(jì)的這么樂(lè)觀，但也沒(méi)有必要杞人憂(yōu)天到去擔(dān)心是不是會(huì)用完的這種狀況。非對(duì)稱(chēng)密碼體制的分類(lèi)主要分成如下幾類(lèi)：（1）基于大數(shù)分解難題的，包括RSA密碼體制，Rabin密碼等。（2）基于離散對(duì)數(shù)難題的，如ElGamal密碼，有限域上的離散對(duì)數(shù)問(wèn)題的難度和大整數(shù)因子分解問(wèn)題的難度相當(dāng)。（3）基于橢圓曲線(xiàn)離散對(duì)數(shù)的密碼體制。嚴(yán)格說(shuō)來(lái)，它可以歸與基于離散對(duì)數(shù)難題的密碼體制中。另外，頗受關(guān)注的還有NTRU作業(yè)（測(cè)試）(1)在RSA算法密鑰產(chǎn)生過(guò)程中，設(shè)p=19，q=11，取公鑰的參數(shù)e＝7，則求RSA的公鑰和私鑰？若明文m=19，求密文？

(2)若已知RSA中公鑰參數(shù)e=5，模數(shù)n=194477，能否破解出私鑰參數(shù)d的值？（寫(xiě)出破解過(guò)程）

(3)假設(shè)攻擊者已知用戶(hù)A的公鑰（7,119），用戶(hù)B的公鑰（5,119)，然后用戶(hù)A和用戶(hù)B對(duì)同一信息P進(jìn)行加密，得到密文分別為C1=9，C2=32，求解出明文P？（采用共模攻擊方法）習(xí)題講解(1)n=p*q=209，φ(n)=（p-1)(q-1)=18*10=180e*d≡1（mod180），即7*d≡1（mod180）180=25*7+57=1*5+25=2*2+11=5-2*2=5-2*(7-5)=3*5-2*7=(180-25*7)*3-2*7=180*3-77*7,兩邊同時(shí)模180，可得1≡-77*7（mod180);私鑰d參數(shù)d=180-77=103RSA私鑰為(103,209),公鑰為（7,209）（2）m=19則密文c≡197(mod209)c≡(192)3*19(mod209)≡(152)3*19(mod209)≡57習(xí)題講解(2)若已知RSA中公鑰參數(shù)e=5，模數(shù)n=194477，能否破解出私鑰參數(shù)d的值？（寫(xiě)出破解過(guò)程）

解：猜測(cè)p和q相差不大，則模數(shù)n>4402

，則需要尋找一個(gè)x>440，滿(mǎn)足x2-n=y2，則從x=441開(kāi)始嘗試4412-194477=4=22，因此（x-2)(x+2)=194477(441-2)(441+2)=194477，因此p=439，q=443φ(n)=（p-1)(q-1)=438*442=1935965*d≡1（mod193595）193596=38719*5+11=193596-5*38719私鑰d=-38719≡193595-38719（mod193595）d=154877習(xí)題講解(3)假設(shè)攻擊者已知用戶(hù)A的公鑰（7,119），用戶(hù)B的公鑰（5,119)，然后用戶(hù)A和用戶(hù)B對(duì)同一信息P進(jìn)行加密，得到密文分別為C1=9，C2=32，求解出明文P？（采用共模攻擊方法）解：r*e1+s*e2=1，即：r*7+s*5=15*s≡1（mod7）7=5+25=2*2+11=5-2*（7-5）=3*5-2*7，因此r=-2，s=3P=(C1)r*(C2)s=(9)-2*(32)3mod119=(9-1)2*(32)3mod119(9-1)mod119,求逆元119=13*9+29=4*2+11=9-4*2=9-4*(119-13*9)=-4*119+53*9(9-1)mod119=53,因此P=(53)2*(32)3mod119=72*43mod119=2，明文是是119補(bǔ)充內(nèi)容RSA算法數(shù)學(xué)基礎(chǔ)RSA算法的實(shí)現(xiàn):快速模冪運(yùn)算（FastExponentiation）擴(kuò)展歐幾里得算法（ExtendedEuler’sAlgorithm）模求逆（Modularinverses）費(fèi)馬定理(Fermat’sLittleTheorem)中國(guó)剩余定理CRT(ChineseRemainderTheorem)素?cái)?shù)檢測(cè)算法RSA算法的實(shí)現(xiàn)在RSA算法的實(shí)現(xiàn)過(guò)程中，參考已知文獻(xiàn)，需要考慮以下的問(wèn)題：①如何判定一個(gè)大的整數(shù)是不是素?cái)?shù)困難嗎？②指定長(zhǎng)度的素?cái)?shù)個(gè)數(shù)是有限的，當(dāng)有很多人使用RSA算法時(shí)會(huì)不會(huì)發(fā)生兩個(gè)人用同一個(gè)素?cái)?shù)的情況？③從RSA算法可以看到，算法中的主要運(yùn)算都集中在指數(shù)運(yùn)算以及模運(yùn)算上。如何有效提高這兩種運(yùn)算，可以加快算法的加解密速度。另外，具體實(shí)現(xiàn)RSA算法時(shí)，還要參考RSA的加密標(biāo)準(zhǔn)(PKCS#1,IEEEP1363)，可以提高算法加密的安全性。大整數(shù)是否素?cái)?shù)的判定定理5-2：小于n的素?cái)?shù)的總數(shù)近似為n/(lnn)，這個(gè)結(jié)論稱(chēng)為素?cái)?shù)個(gè)數(shù)定理。（1）大整數(shù)是否素?cái)?shù)的判定，產(chǎn)生素?cái)?shù)困難嗎？大整數(shù)是否素?cái)?shù)的判定可以參考5.1.5節(jié)。由素?cái)?shù)個(gè)數(shù)定理，如果在1~N之間任取一個(gè)數(shù)，其為素?cái)?shù)的概率為1/lnN，如果取N＝2512，約為10160,則1/lnN約為1/355，如果再去掉2、3、5、7等的倍數(shù)，嘗試的次數(shù)就不會(huì)很多了。63RSA算法RSA的快速實(shí)現(xiàn)加密很快，指數(shù)小；解密比較慢，指數(shù)較大.利用中國(guó)剩余定理CRT，加快計(jì)算速度.CRT對(duì)RSA解密算法生成兩個(gè)解密方程（利用M=CdmodR）即:M1=Mmodp=(Cmodp)dmod(p-1)modp

M2=Mmodq=(Cmodq)dmod(q-1)modq解方程組M=M1modp;M=M2modq.利用CRT,具有唯一解：M=[((M2+q-M1)umodq]p+M1.其中p.umodq=1.中國(guó)剩余定理中國(guó)剩余定理mod3:Nmod3=1中國(guó)剩余定理mod5:Nmod5=2中國(guó)剩余定理mod7:Nmod7=2中國(guó)剩余定理Na(mod3)N

b(mod5)N

c(mod7)N如何求解？中國(guó)剩余定理設(shè)m1,m2,…,mn是兩兩互素的正整數(shù)，令m=m1m2…mn=miMi,MiMi’≡1modmi,i∈[1,n]，則方程組：的解為：x≡M1M1’b1+M2M2’b2+…+MnMn’bn(modm)注意，

m=m1m2…mn=miMi，故Mi=m/mi。m1,m2,…,mn是兩兩互素的正整數(shù)，故（Mi,mi）=1,通過(guò)MiMi’≡1modmi計(jì)算的逆元一定存在。韓信點(diǎn)兵有兵若干，若列成5行縱隊(duì)，則末行1人，若列成6行縱隊(duì)，則末行5人，若列成7行縱隊(duì)，則末行4人，若列成11行縱隊(duì)，則末行10人，求兵數(shù)？解：由題意得x≡1(mod5)，x≡5(mod6)，x≡4(mod7)，x≡10(mod11)。令m1＝5，m2＝6，m3＝7，m4＝11，b1＝1，b2＝5，b3＝4，b4＝10。則m＝2310，M1＝462，M2＝385，M3＝330，M4＝210。利用輾轉(zhuǎn)相除法得M1’＝－2，M2’＝1，M3’＝1，M4’＝1。x≡1·(－2)·462＋5·1·385＋4·1·330＋10·1·210≡4421≡2111(mod2310)練習(xí)題x1(mod3)x

2(mod5)x

2(mod7)x如何求解？平方剩余設(shè)m為大于1的正整數(shù)，(a,m)=1,如果方程x2≡a(modm)有解，則稱(chēng)a為modm的平方剩余，也稱(chēng)二次剩余；若方程無(wú)解，則稱(chēng)a為modm的平方非剩余。以m=11為例。12≡1，22≡4，32≡9，42≡5，52≡3，62≡3，72≡5，82≡9，92≡4，102≡1mod11由定義5-1知，1，3，4，5，9為mod11的平方剩余，故2，6，7，8，10為mod11的平方非剩余。也就是說(shuō)，我們找不到一個(gè)整數(shù)，使得它的平方在mod11后，其余數(shù)是2，6，7，8，10這5個(gè)整數(shù)中的一個(gè)。勒讓得符號(hào)設(shè)p為奇素?cái)?shù)，a為整數(shù)，定義勒讓得(Legendre)符號(hào)為：

通過(guò)計(jì)算勒讓得符號(hào)，容易判斷二次方程x2≡a(modp)(p是奇素?cái)?shù))有沒(méi)有解。因此5不是模23的平方剩余離散對(duì)數(shù)設(shè)p為奇素?cái)?shù)，對(duì)于整數(shù)g,1<g<p,使得g?≡1(modp)成立的最小正整數(shù)如果是p-1,則g就是模p的原根。離散對(duì)數(shù)問(wèn)題已知g是模p的原根，對(duì)于集合G={gk,k=0,1,2,…p-1}，給定的x,x為整數(shù)，計(jì)算y≡gxmodp是容易的，但對(duì)于給定的y∈G,x可以表示為x≡loggymodp，當(dāng)p是一個(gè)大素?cái)?shù)的時(shí)候，要計(jì)算x是困難的。求解x≡loggymodp的問(wèn)題，稱(chēng)為離散對(duì)數(shù)問(wèn)題。76Diffie-Hellmankeydistributionscheme的變形能夠用于安全交換密鑰Publishedin1985byElGamal:T.ElGamal,"APublicKeyCryptosystemandaSignatureSchemeBasedonDiscreteLogarithms",IEEETrans.InformationTheory,volIT-31(4),pp469-472,July1985.

安全性基于有限域上的離散對(duì)數(shù)問(wèn)題的困難性.缺點(diǎn)：增加了傳送信息長(zhǎng)度（2倍）ElGamal算法771)密鑰產(chǎn)生過(guò)程：

首先選擇一素?cái)?shù)p,生成元g和小于p的隨機(jī)數(shù)x，計(jì)算y≡gxmodp，以(y,g,p)作為公開(kāi)密鑰，x作為秘密密鑰.2)加密過(guò)程：設(shè)欲加密明文消息為M.

隨機(jī)選一與p-1互素的整數(shù)k，0<=k<=p-1；計(jì)算密文對(duì):C={C1,C2},發(fā)送給接收者.C1≡gkmodp,C2≡ykMmodp.ElGamal算法78

3)

解密過(guò)程:

計(jì)算明文:因?yàn)?ElGamal算法k需要永久保密，且不能重復(fù)使用.為什么？791)密鑰生成.

選擇公開(kāi)參數(shù)：p=97

及本原根

a=5

；

Bob選擇秘密鑰xB=58，計(jì)算并發(fā)布公鑰yB=558=44mod97.

2)Alice要加密M=3

給Bob.

首先得到Bob的公開(kāi)密鑰yB=44，選擇隨機(jī)k=36

計(jì)算:

K=4436=75mod97.計(jì)算密文對(duì):C1=536=50mod97

；

C2=75.3mod97=31mod97.發(fā)送{50,31}

給Bob.3)Bob解密消息.恢復(fù)消息密鑰K=5058=75mod97.Bob計(jì)算K-1=22mod97.Bob恢復(fù)明文M=31*22=3mod97.ElGamal算法ElGamal算法有限域上離散對(duì)數(shù)問(wèn)題已知（Zp，+，*）是一個(gè)有限域，g為Zp*的生成元，y∈Zp，求x使得y=gxmodp如果求離散對(duì)數(shù)問(wèn)題是容易的，則獲得公鑰攻擊者能夠解出x，則算法完全破譯.RSA與ElGamal比較RSAElGamal加密一次模冪運(yùn)算兩次模冪+一次模乘解密一次模冪運(yùn)算一次模冪運(yùn)算密文密文不擴(kuò)張密文擴(kuò)張確定算法不確定算法安全RSA問(wèn)題離散對(duì)數(shù)問(wèn)題RSA與EIGamal算法比較512位768位1024位加密0.03秒0.05秒0.08秒解密0.16秒0.48秒0.93秒簽名0.16秒0.52秒0.97秒驗(yàn)證0.02秒0.07秒0.08秒512位768位1024位加密0.33秒0.80秒1.09秒解密0.24秒0.58秒0.77秒簽名0.25秒0.47秒0.63秒驗(yàn)證1.37秒5.12秒9.30秒具有8位公開(kāi)密鑰RSA對(duì)于不同長(zhǎng)度模數(shù)的加解密速度（SPARCII上）具有160位指數(shù)的EIGamal對(duì)于不同長(zhǎng)度模數(shù)的加解密速度（SPARCII上）

當(dāng)前的技術(shù)進(jìn)展使分解算法和計(jì)算能力在不斷提高，計(jì)算所需的硬件費(fèi)用在不斷下降。

RSA-129：110位十進(jìn)制數(shù)字早已能分解。Rivest等最初懸賞$100的RSA-129，已由包括五大洲43個(gè)國(guó)家600多人參加，用1600臺(tái)機(jī)子同時(shí)產(chǎn)生820條指令數(shù)據(jù)，通過(guò)Internet網(wǎng)，耗時(shí)8個(gè)月，于1994年4月2日利用二次篩法分解出為64位和65位的兩個(gè)因子，原來(lái)估計(jì)要用4億億年。所給密文的譯文為“這些魔文是容易受驚的魚(yú)鷹”。這是有史以來(lái)最大規(guī)模的數(shù)學(xué)運(yùn)算。

RSA-130于1996年4月10日利用數(shù)域篩法分解出來(lái)。

RSA-140于1999年2月分解出來(lái)。

RSA-155(512bit)于1999年8月分解出來(lái)大數(shù)分解進(jìn)程

目前RSA的攻擊現(xiàn)狀是有關(guān)RSA-155分解，其具體情況是1999年8月22日，來(lái)自六個(gè)不同國(guó)家的科學(xué)家們?cè)贑WI（CWI是在荷蘭的一個(gè)數(shù)學(xué)和計(jì)算機(jī)科學(xué)的國(guó)家研究學(xué)會(huì)）的HermanteRiele的帶領(lǐng)下，在對(duì)RSA-155的攻擊中，利用數(shù)域篩法（NFS）成功的分解出了512-bitRSA模的素因子。要分解RSA-155所需的CPU時(shí)間大約為8400MIPS年（MIPS-年指以每秒執(zhí)行1000000條指令的計(jì)算機(jī)運(yùn)行一年），這大約為分解RSA-140所需時(shí)間的4倍。分解RSA-155總共用了7個(gè)月的時(shí)間。密碼分析者估計(jì)在3年內(nèi)分解RSA-155所用到的算法和計(jì)算技術(shù)至少在科技界將會(huì)得到普及，因此RSA-155將不再安全。并且人們預(yù)計(jì)，在十年內(nèi)RSA-232也將被攻破。大數(shù)分解進(jìn)程2005年，作為公共研究一部分的有663bit長(zhǎng)的RSA-200已經(jīng)被一種一般用途的方法所分解。

采用廣義數(shù)域篩分解不同長(zhǎng)度RSA公鑰模所需的計(jì)算機(jī)資源

密鑰長(zhǎng)(bit)所需的MIPS-年*

116(Blacknet密鑰)4001295,00051230,000768200,000,0001024300,000,000,0002048300,000,000,000,000,000,000*MIPS-年指以每秒執(zhí)行1,000,000條指令的計(jì)算機(jī)運(yùn)行一年

橢圓曲線(xiàn)密碼體制概述為保證RSA算法的安全性，它的密鑰長(zhǎng)度需一再增大，使得它的運(yùn)算負(fù)擔(dān)越來(lái)越大。相比之下，橢圓曲線(xiàn)密碼體制ECC（ellipticcurvecryptography）可用短得多的密鑰獲得同樣的安全性，因此具有廣泛的應(yīng)用前景。ECC已被IEEE公鑰密碼標(biāo)準(zhǔn)P1363采用橢圓曲線(xiàn)舉例一般來(lái)講，橢圓曲線(xiàn)的曲線(xiàn)方程是以下形式的三次方程：

y2+axy+by=x3+cx2+dx+e(4.1)其中a，b，c，d，e是滿(mǎn)足某些簡(jiǎn)單條件的實(shí)數(shù)。定義中包括一個(gè)稱(chēng)為無(wú)窮點(diǎn)的元素，記為O。加法運(yùn)算橢圓曲線(xiàn)上的加法運(yùn)算定義如下：如果其上的3個(gè)點(diǎn)位于同一直線(xiàn)上，那么它們的和為O。進(jìn)一步可如下定義橢圓曲線(xiàn)上的加法律（加法法則）：①O為加法單位元，即對(duì)橢圓曲線(xiàn)上任一點(diǎn)P，有P+O=P。②設(shè)P1=(x,y)是橢圓曲線(xiàn)上的一點(diǎn)（如圖4.4，見(jiàn)書(shū)），它的加法逆元定義為P2=-P1=(x,-y)。這是因?yàn)镻1、P2的連線(xiàn)延長(zhǎng)到無(wú)窮遠(yuǎn)時(shí)，得到橢圓曲線(xiàn)上的另一點(diǎn)O，即橢圓曲線(xiàn)上的3點(diǎn)P1、P2，O共線(xiàn)，所以P1+P2+O=O，P1+P2=O，即P2=-P1。由O+O=O，還可得O=-O加法運(yùn)算③設(shè)Q和R是橢圓曲線(xiàn)上x(chóng)坐標(biāo)不同的兩點(diǎn)，Q+R的定義如下：畫(huà)一條通過(guò)Q、R的直線(xiàn)與橢圓曲線(xiàn)交于P1（這一交點(diǎn)是惟一的，除非所做的直線(xiàn)是Q點(diǎn)或R點(diǎn)的切線(xiàn)，此時(shí)分別取P1=Q和P1=R）。由Q+R+P1=O得Q+R=-P1。④點(diǎn)Q的倍數(shù)定義如下：在Q點(diǎn)做橢圓曲線(xiàn)的一條切線(xiàn)，設(shè)切線(xiàn)與橢圓曲線(xiàn)交于點(diǎn)S，定義2Q=Q+Q=-S。類(lèi)似地可定義3Q=Q+Q+Q+，…，等。密碼學(xué)中用的橢圓曲線(xiàn)最為常用的橢圓曲線(xiàn)是由方程y2≡x3+ax+b(modp)(a,b∈GF(p),4a3+27b2(modp)≠0) (4.2)定義的曲線(xiàn)。例p=23，a=b=1，4a3+27b2(mod23)≡8≠0，方程為y2≡x3+x+1，其圖形是連續(xù)曲線(xiàn)，由圖4.4(b)所示。設(shè)Ep(a,b)表示方程(4.2)所定義的橢圓曲線(xiàn)上的點(diǎn)集{(x,y)|0≤x<p,0≤y<p，且x,y均為整數(shù)}并上無(wú)窮遠(yuǎn)點(diǎn)O。橢圓曲線(xiàn)上點(diǎn)的產(chǎn)生一般來(lái)說(shuō)，Ep(a,b)由以下方式產(chǎn)生：①對(duì)每一x(0≤x<p且x為整數(shù)），計(jì)算x3+ax+b(modp)。

②決定①中求得的值在模p下是否有平方根，如果沒(méi)有，則曲線(xiàn)上沒(méi)有與這一x相對(duì)應(yīng)的點(diǎn)；如果有，則求出兩個(gè)平方根（y=0時(shí)只有一個(gè)平方根）。加法定義Ep(a,b)上的加法定義如下：設(shè)P，Q∈Ep(a,b)，則①P+O=P。②如果P=(x,y)，那么(x,y)+(x,-y)=O，即(x,-y)是P的加法逆元，表示為-P。由Ep(a,b)的產(chǎn)生方式知，-P也是Ep(a,b)中的點(diǎn)，如上例，P=(13,7)∈E23(1,1)，-P=(13,-7)，而-7mod23≡16，所以-P=(13,16)，也在E23(1,1)中。加法定義③設(shè)P=(x1,y1)，Q=(x2,y2)，P≠-Q，則P+Q=(x3,y3)由以下規(guī)則確定：

x3≡λ2-x1-x2(modp) y3≡λ(x1-x3)-y1(modp)其中加法舉例－不同點(diǎn)相加以E23(1,1)為例，設(shè)P=(3,10)，Q=(9,7)，計(jì)算P+Q加法舉例－同點(diǎn)相加求2P，P=(3,10)

在橢圓曲線(xiàn)上實(shí)現(xiàn)Diffie-Hellman的體制。假定橢圓曲線(xiàn)E定義在Zq域上。設(shè)P∈E，要求由P產(chǎn)生的群的元素足夠多。A和B分別選a和b予以保密，但將aP,bP∈E公開(kāi)。A、B間通信用的密鑰為abP，這是第三者無(wú)法得知的。

橢圓曲線(xiàn)上實(shí)現(xiàn)DH體制DH體制第1步，選取橢圓曲線(xiàn)，其上面的點(diǎn)構(gòu)成的Abel群Ep(a,b)第2步，取Ep(a,b)的一個(gè)生成元G(x1,y1)，要求G的階是一個(gè)非常大的素?cái)?shù)，G的階是滿(mǎn)足nG=O的最小正整數(shù)n。Ep(a,b)和G作為公開(kāi)參數(shù)。兩用戶(hù)A和B之間的密鑰交換如下進(jìn)行：①A選一小于n的整數(shù)nA，作為秘密鑰，并由PA=nAG產(chǎn)生Ep(a,b)上的一點(diǎn)作為公開(kāi)鑰。②B類(lèi)似地選取自己的秘密鑰nB和公開(kāi)鑰PB。③A、B分別由K=nAPB和K=nBPA產(chǎn)生出雙方共享的秘密鑰。這是因?yàn)镵=nAPB=nA(nBG)=nB(nAG)=nBPA。攻擊者若想獲取K，則必須由PA和G求出nA，或由PB和G求出nB，即需要求橢圓曲線(xiàn)上的離散對(duì)數(shù)，因此是不可行的。DH體制例p=211，Ep(0,-4)，即橢圓曲線(xiàn)為y2≡x3-4，G=(2,2)是E211(0,-4)的階為241的一個(gè)生成元，即241G=O。A的秘密鑰取為nA=121，公開(kāi)鑰為PA=121(2,2)=(115,48)。B的秘密鑰取為nB=203，公開(kāi)鑰為PB=203(2,2)=(130,203)。由此得到的共享密鑰為121(130,203)=203(115,48)=(161,169)，即共享密鑰是一對(duì)數(shù)。DH體制舉例離散對(duì)數(shù)問(wèn)題（DLP）：給定一個(gè)素?cái)?shù)p，Zp*的一個(gè)生成元g及一個(gè)元素b∈Zp*，尋找整數(shù)x，使得gx≡bmodp。另一個(gè)取法：給定一個(gè)素?cái)?shù)p，g是Zp*的一個(gè)q階元素，b∈Zp*，尋找整數(shù)x，使得gx≡bmodp。例：如果p=41，6是模11的一個(gè)生成元，若取g=6，它的階為40。如果p=41，6是模11的一個(gè)生成元，64mod41=25，若取g=25，它的階為10。離散對(duì)數(shù)問(wèn)題ElGamal公鑰密碼：（1）密鑰產(chǎn)生過(guò)程。A選擇一個(gè)素?cái)?shù)p以及整數(shù)模p的乘法群Zp*的一個(gè)生成元g。選取一個(gè)隨機(jī)整數(shù)r(1≤r≤p-2)，計(jì)算β=grmodp。以(p,g,β)作為公鑰，r作為私鑰。（2）加密過(guò)程。設(shè)B欲向A發(fā)送的明文消息為m。B獲取公鑰(p,g,β)，將消息m表示成{0,1,…,p-1}范圍內(nèi)的整數(shù)。選取隨機(jī)整數(shù)k(1≤k≤p-2)，計(jì)算c1=gkmodp和c2=m(β)kmodp，得密文為c=(c1,c2)；B發(fā)送(c1,c2)給A.（3）解密過(guò)程。A計(jì)算c1-rc2modp恢復(fù)出m

（因?yàn)?c1-r)c2≡g-rkmgrk≡mmodp）。ElGamal公鑰密碼用戶(hù)A選取p=41，因6是模11的一個(gè)生成元，取g=6，又取私鑰r=4，計(jì)算β=grmodp=25。公布(p,g,β)=（41