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

非對稱密碼體制

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

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

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

公鑰密碼體制的原理8公鑰加密體制的原理郵箱的例子任何人可以向郵箱投舉報信用戶(審計人員)才能打開郵箱，讀信的內(nèi)容9公鑰加密體制的原理公鑰密鑰對參數(shù)生成需滿足的要求：公開密鑰(public-key),可以被任何人知道,用于加密或驗證簽名；私鑰(private-key),只能被消息的接收者或簽名者知道,用于解密或簽名；由私鑰及公開參數(shù)容易計算出公開密鑰；由公鑰及公開參數(shù)推導(dǎo)私鑰是困難的；10定義單向函數(shù)是兩個集合X、Y之間的一個映射，使得Y中每一元素y都有惟一的一個原像x∈X，且由x易于計算它的像y，由y計算它的原像x是不可行的.一個函數(shù)是單向陷門函數(shù)，是指該函數(shù)是易于計算的，但求它的逆是不可行的，除非再已知某些附加信息。當(dāng)附加信息給定后，求逆可在多項式時間完成.單向陷門函數(shù)11單向陷門函數(shù)是一族可逆函數(shù)fk，滿足①Y=fk1(X)易于計算（當(dāng)k1和X已知時）.②X=f-1k2(Y)易于計算（當(dāng)k2和Y已知時）.③X=f-1k2(Y)計算上是不可行的（當(dāng)Y已知，但k2未知時）已知K1，計算出K2是不可行的（當(dāng)K1已知，但k2未知時）研究公鑰密碼算法就是要找出合適的陷門單向函數(shù)單向陷門函數(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)生①選兩個安全的大素數(shù)p和q。②計算n=p×q，φ(n)=(p-1)(q-1),其中φ(n)是n的歐拉函數(shù)值。③選一整數(shù)e，滿足1<e<φ(n)，且gcd(φ(n),e)=1。④計算d，滿足d·e≡1modφ(n),即d是e在模φ(n)下的乘法逆元，因e與φ(n)互素，由模運算可知，它的乘法逆元一定存在。(一般公鑰取值為65537（216+1））⑤以{e,n}為公開鑰（PK）,{d,n}為秘密鑰（SK）。RSA算法1選取大素數(shù)的方法：隨機(jī)產(chǎn)生一個大整數(shù)，利用素性檢測算法判定該整數(shù)是否為素數(shù)2以往素檢測的算法都是概率性的，即存在一定的錯誤概率；32003年，印度人發(fā)表文章“PrimesisinP”，證明了素判定問題是一個多項式時間問題。1）輾轉(zhuǎn)相除法2）利用歐拉定理求e^{φ(

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

c≡memodnRSA算法173.解密對密文分組的解密運算為：m≡cdmodn證明RSA算法中解密過程的正確性.證明：由加密過程知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ù)。此時必有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ù)個數(shù)，稱

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

(3)＝2，

(5)＝4，

(8)＝4。顯然，當(dāng)p為素數(shù)時，

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

(m1m2)＝

(m1)

(m2),尤其是當(dāng)m1，m2都為素數(shù)時，

(m1m2)＝

(m1)

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

(15)=

(3)×

(5)=2×4=8.實際上，這些數(shù)是1，2，4，7，8，11，13，14，共8個?？梢杂玫炔顢?shù)列的方式證明當(dāng)m1，m2都為素數(shù)時的情形歐拉定理

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

(n)

1(modn)例如，求132001mod17。因為(13，17)＝1，所以13

(17)

1(mod17)，因為

(17)＝16，即1316≡1(mod17)。而2001＝125×16＋1，132001＝（1316）125·13≡13(mod17)，即被17除得的余數(shù)為13。當(dāng)n為素數(shù)p時，就是費爾馬定理。費爾馬定理若p是素數(shù)，(a，p)＝1，則ap-1≡1(modp).RSA算法舉例在RSA算法密鑰產(chǎn)生過程中，設(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，因為8×7≡1(mod11)當(dāng)a和m互素的情況下，即（a,m）=1,則a的模m的逆元總是存在的，且可以用上面的輾轉(zhuǎn)相除法求得。求逆元舉例例如，我們知道89是素數(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求逆元舉例等式兩端同時mod89得：60×(-43)≡1mod89故60模89的逆元為-43，為方便記為最小非負(fù)數(shù)，因為-43≡46mod89，故一般說60模89的逆元為46.如何用程序?qū)崿F(xiàn)求逆元？實際上，這里的逆元通常稱為乘法逆元。從后面的學(xué)習(xí)可以看到，定義不同的運算和單位元，就可能有不同情況下的逆元。RSA算法舉例（1）加密過程：設(shè)RSA算法的參數(shù)選擇如上所述，當(dāng)消息m=9所對應(yīng)的密文的計算過程為：929mod299＝211（2）解密過程：211173mod299≡929例：選p=7，q=17.取e=5，設(shè)明文m=19，求密文c求得n=p×q=119，φ(n)=(p-1)(q-1)=96.取e=5，滿足1<e<φ(n)，且gcd(φ(n),e)=1，計算滿足d·e=1mod96且小于96的d.因為77×5=385=4×96+1，所以d為77，因此公開鑰為{5，119}，秘密鑰為{77，119}.設(shè)明文m=19，則由加密過程得密文為c≡195mod119≡2476099mod119≡66;解密過程為m≡6677mod119≡19.RSA算法30RSA中的計算問題1.RSA的加密與解密過程

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

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

例如求x16，直接計算的話需做15次乘法。然而如果重復(fù)對每個部分結(jié)果做平方運算即求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算法模冪運算32例：求a1919=1×24+0×23+0×22+1×21+1×20所以

a19=((((a1)2a0)2a0)2a1)2a1練習(xí)：求a7和a8，并統(tǒng)計快速運算法的運算次數(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中，運算的形式一般是memodn,則在程序或算法中，所有的乘法或乘方運算之后都有一個模運算。練習(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ù)分解問題：已知n是兩個大素數(shù)的乘積，求n的素分解RSA的安全性是基于分解大整數(shù)困難的假定

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

RSA算法的安全性37

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

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

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

如對RSA-129的分解.而對RSA-130的分解則采用了一個新算法，稱為推廣的數(shù)域篩法，該算法在分解RSA-130時所做的計算僅比分解RSA-129多10%.1）在使用RSA算法時對其密鑰的選取要特別注意其大小。估計在未來一段比較長的時期，密鑰長度介于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，直到找到一個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較小時才是可行的，為抵抗這種攻擊，應(yīng)保證使t很大.所以為使t大，p-1和q-1都應(yīng)有大的素因子，且Φ((p-1)*(q-1))有大的素因子RSA算法的安全性RSA算法的安全性4）RSA的選擇密文攻擊一般攻擊者是將希望解密的信息C作一下偽裝reC，讓擁有私鑰的實體解密（簽名）。然后，經(jīng)過解密計算就可得到它所想要的信息。

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

互素，

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

elseb≡b2(modn)}return(“n是合數(shù)”)Miller-Rabin概率檢測算法舉例Miller-Rabin概率檢測算法舉例例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是素數(shù)設(shè)a=4,b=47(mod29)≡28,i=0,b=28(mod29)≡-1輸出：n是素數(shù)此例為判定合數(shù)為素數(shù)的例子以n=25,a=7為例。取n=25，25-1=23*3,即s=3,t=3由算法，b=73≡18mod25i=0,b2=182≡-1(mod25),輸出：n是素數(shù)實際上，25是合數(shù)。這時可以通過另選擇一個a(1<a<n-1),(n,a)=1,如a=2，再次運行算法。由算法，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肯定是個合數(shù)。（2）大素數(shù)個數(shù)的估計通過一個簡單的例子，可以明白大素數(shù)的個數(shù)是十分龐大的資源，不用擔(dān)心會被用完。例5-8：小于10100

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

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

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

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

(3)假設(shè)攻擊者已知用戶A的公鑰（7,119），用戶B的公鑰（5,119)，然后用戶A和用戶B對同一信息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,兩邊同時模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的值？（寫出破解過程）

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

，則需要尋找一個x>440，滿足x2-n=y2，則從x=441開始嘗試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è)攻擊者已知用戶A的公鑰（7,119），用戶B的公鑰（5,119)，然后用戶A和用戶B對同一信息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算法的實現(xiàn):快速模冪運算（FastExponentiation）擴(kuò)展歐幾里得算法（ExtendedEuler’sAlgorithm）模求逆（Modularinverses）費馬定理(Fermat’sLittleTheorem)中國剩余定理CRT(ChineseRemainderTheorem)素數(shù)檢測算法RSA算法的實現(xiàn)在RSA算法的實現(xiàn)過程中，參考已知文獻(xiàn)，需要考慮以下的問題：①如何判定一個大的整數(shù)是不是素數(shù)困難嗎？②指定長度的素數(shù)個數(shù)是有限的，當(dāng)有很多人使用RSA算法時會不會發(fā)生兩個人用同一個素數(shù)的情況？③從RSA算法可以看到，算法中的主要運算都集中在指數(shù)運算以及模運算上。如何有效提高這兩種運算，可以加快算法的加解密速度。另外，具體實現(xiàn)RSA算法時，還要參考RSA的加密標(biāo)準(zhǔn)(PKCS#1,IEEEP1363)，可以提高算法加密的安全性。大整數(shù)是否素數(shù)的判定定理5-2：小于n的素數(shù)的總數(shù)近似為n/(lnn)，這個結(jié)論稱為素數(shù)個數(shù)定理。（1）大整數(shù)是否素數(shù)的判定，產(chǎn)生素數(shù)困難嗎？大整數(shù)是否素數(shù)的判定可以參考5.1.5節(jié)。由素數(shù)個數(shù)定理，如果在1~N之間任取一個數(shù)，其為素數(shù)的概率為1/lnN，如果取N＝2512，約為10160,則1/lnN約為1/355，如果再去掉2、3、5、7等的倍數(shù)，嘗試的次數(shù)就不會很多了。63RSA算法RSA的快速實現(xiàn)加密很快，指數(shù)??；解密比較慢，指數(shù)較大.利用中國剩余定理CRT，加快計算速度.CRT對RSA解密算法生成兩個解密方程（利用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.中國剩余定理中國剩余定理mod3:Nmod3=1中國剩余定理mod5:Nmod5=2中國剩余定理mod7:Nmod7=2中國剩余定理Na(mod3)N

b(mod5)N

c(mod7)N如何求解？中國剩余定理設(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,通過MiMi’≡1modmi計算的逆元一定存在。韓信點兵有兵若干，若列成5行縱隊，則末行1人，若列成6行縱隊，則末行5人，若列成7行縱隊，則末行4人，若列成11行縱隊，則末行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)有解，則稱a為modm的平方剩余，也稱二次剩余；若方程無解，則稱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的平方非剩余。也就是說，我們找不到一個整數(shù)，使得它的平方在mod11后，其余數(shù)是2，6，7，8，10這5個整數(shù)中的一個。勒讓得符號設(shè)p為奇素數(shù)，a為整數(shù)，定義勒讓得(Legendre)符號為：

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

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

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

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

3)

解密過程:

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

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

及本原根

a=5

；

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

2)Alice要加密M=3

給Bob.

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

計算:

K=4436=75mod97.計算密文對:C1=536=50mod97

；

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

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

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

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

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

RSA-140于1999年2月分解出來。

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

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

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

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

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

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

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

②決定①中求得的值在模p下是否有平方根，如果沒有，則曲線上沒有與這一x相對應(yīng)的點；如果有，則求出兩個平方根（y=0時只有一個平方根）。加法定義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)中的點，如上例，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)其中加法舉例－不同點相加以E23(1,1)為例，設(shè)P=(3,10)，Q=(9,7)，計算P+Q加法舉例－同點相加求2P，P=(3,10)

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

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

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