1、1公鑰密碼（二）現(xiàn)代密碼學(xué)第七章上節(jié)內(nèi)容回顧公鑰密碼體制的提出及分類公鑰密碼體制的基本概念單向陷門函數(shù)的概念設(shè)計公鑰加密算法-背包密碼體制3本節(jié)主要內(nèi)容RSA算法及其分析ElGmal算法橢圓曲線密碼體制其它公鑰密碼算法4 RSA算法是1978年由R.Rivest, A.Shamir和L.Adleman提出的一種用數(shù)論構(gòu)造的、也是迄今為止理論上最為成熟完善的公鑰密碼體制，該體制已得到廣泛的應(yīng)用。 它既可用于加密、又可用于數(shù)字簽字。 RSA算法的安全性基于數(shù)論中大整數(shù)分解的困難性。 R L Rivest, A Shamir, L Adleman, On Digital Signatures and

2、 Public Key Cryptosystems, Communications of the ACM, vol 21 no 2, pp120-126, Feb 1978RSA算法51. 密鑰的產(chǎn)生 選兩個安全的大素數(shù)p和q。 計算n=pq，(n)=(p-1)(q-1),其中(n)是n的歐拉函數(shù)值。 選一整數(shù)e，滿足1e(n)，且gcd(n),e)=1。 計算d，滿足de1 mod (n),即d是e在模(n)下的乘法逆元，因e與(n)互素，由模運算可知，它的乘法逆元一定存在。 以e,n為公開鑰,d,n為秘密鑰。RSA算法1 選取大素數(shù)的方法：隨機產(chǎn)生一個大整數(shù)，利用素性檢測算法判定該整數(shù)是否

3、為素數(shù)2 以往素檢測的算法都是概率性的，即存在一定的錯誤概率；3 2003年，印度人發(fā)表文章“Primes is in P”，證明了素判定問題是一個多項式時間問題。1）輾轉(zhuǎn)相除法2）利用歐拉定理求e( (n)-1思考：分析兩種計算方法的效率62. 加密加密時首先將明文比特串分組，使得每個分組對應(yīng)的十進制數(shù)小于n，即分組長度小于log2n。然后對每個明文分組m，作加密運算： cme mod nRSA算法73. 解密對密文分組的解密運算為：mcd mod n證明RSA算法中解密過程的正確性.證明： 由加密過程知cme mod n，所以cd mod nmed mod nm1 mod (n) mod

4、n mk(n)+1 mod nRSA算法8下面分兩種情況： m與n互素，則由Euler定理得m(n)1 mod n,mk(n)1 mod n,mk(n)+1m mod n即cd mod nm。 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ù)，與mn=pq矛盾RSA算法9 由gcd(m,q)=1及Euler定理得m(q)1 mod q，所以mk(q)1 mod q,m

5、k(q)(p)1 mod q, mk(n)1 mod q 因此存在一整數(shù)r，使得mk(n)=1+rq，兩邊同乘以m=tp得mk(n)+1=m+rtpq=m+rtn即mk(n)+1m mod n，所以cd mod nm.RSA算法10例： 選p=7，q=17. 求得n=pq=119，(n)=(p-1)(q-1)=96.取e=5，滿足1e(n)，且gcd(n),e)=1，計算滿足de=1 mod 96且小于96的d.因為775=385=496+1，所以d為77，因此公開鑰為5，119，秘密鑰為77，119.設(shè)明文m=19，則由加密過程得密文為c195 mod 1192476099 mod 1196

6、6;解密過程為 m 6677mod 11919.RSA算法11RSA中的計算問題1. RSA的加密與解密過程 RSA的加密、解密過程都為求一個整數(shù)的整數(shù)次冪，再取模。如果按其含義直接計算，則中間結(jié)果非常大，有可能超出計算機所允許的整數(shù)取值范圍。如上例中解密運算6677 mod 119，先求6677再取模，則中間結(jié)果就已遠遠超出了計算機允許的整數(shù)取值范圍。而用模運算的性質(zhì)：(ab) mod n=(a mod n)(b mod n) mod n就可減小中間結(jié)果。RSA算法12 2. 模指數(shù)運算的快速算法 例如求x16，直接計算的話需做15次乘法。然而如果重復(fù)對每個部分結(jié)果做平方運算即求x，x2，x

7、4，x8，x16則只需4次乘法。 求am可如下進行，其中a，m是正整數(shù)： 將m表示為二進制形式bk bk-1b0，即m=bk2k+bk-12k-1+b12+b0因此RSA算法13例：求a1919=124+023+022+121+120所以 a19=(a1)2a0)2a0)2a1)2a1練習：求a7和a8，并統(tǒng)計快速運算法的運算次數(shù). RSA算法14RSA算法RSA的快速實現(xiàn)加密很快，指數(shù)?。唤饷鼙容^慢，指數(shù)較大. 利用中國剩余定理CRT，加快計算速度.CRT 對RSA解密算法生成兩個解密方程（利用M=Cd mod R） 即: M1 = M mod p = (C mod p )d mod (p-

8、1) mod p M2 = M mod q = (C mod q )d mod (q-1) mod q 解方程組 M = M1 mod p ; M = M2 mod q .利用CRT, 具有唯一解：M = (M2 +q - M1)u mod q p + M1.其中 p.u mod q = 1 .15 整數(shù)分解問題：已知n是兩個大素數(shù)的乘積，求n的素分解RSA的安全性 是基于分解大整數(shù)困難的假定 如果RSA的模數(shù)n被成功地分解為pq，則獲得(n)=(p-1)(q-1)，從而攻擊者能夠從公鑰e解出d，即de-1 mod (n)，攻擊成功. RSA算法的安全性16 至今還未能證明分解大整數(shù)就是NPC

9、問題，也許有尚未發(fā)現(xiàn)的多項式時間分解算法. 隨著人類計算能力的不斷提高，原來被認為是不可能分解的大數(shù)已被成功分解.例如RSA-129（即n為129位十進制數(shù)，大約428個比特）已在網(wǎng)絡(luò)上通過分布式計算歷時8個月于1994年4月被成功分解，RSA-130 已于1996年4月被成功分解.RSA算法的安全性17 分解算法的進一步改進.過去分解算法都采用二次篩法, 如對RSA-129的分解. 而對RSA-130的分解則采用了一個新算法，稱為推廣的數(shù)域篩法，該算法在分解RSA-130時所做的計算僅比分解RSA-129多10%. 1）在使用RSA算法時對其密鑰的選取要特別注意其大小。估計在未來一段比較長的

10、時期，密鑰長度介于1024比特至2048比特之間的RSA是安全的.RSA算法的安全性18 2） |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的分解 .RSA算法的安全性19 3） p-1和q-1都應(yīng)有大素因子設(shè)攻擊者截獲密文c，可如下進行重復(fù)加密：RSA算法的安全性20若 ，即 ，則有 ，即 ，所以在重復(fù)加密的倒數(shù)第2步就可以恢復(fù)出明文m.這種攻擊法只有在t較小

11、時才是可行的，為抵抗這種攻擊，應(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 * Cd mod n = r * M mod n ，所以 M= ( reC ) d * r-1這個固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征-每個人都能使用公鑰。但從算法上無法解決這一問題，只有采用好的公鑰協(xié)議，保證工作過程中實體不對其他實體任意產(chǎn)生的信息解密。R

12、SA算法的安全性5）RSA的公共模數(shù)攻擊若系統(tǒng)中用戶共有一個模數(shù)n ，而擁有不同的e和d。若存在同一信息（設(shè)為P）分別用不同的公鑰（e1和e2）加密，C1 = Pe1 mod n ；C2 = pe2 mod n 設(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) s mod n = P r * e1 + s * e2 mod n =P mod n不要共享模數(shù)n

13、其它共模攻擊方法：在共模假設(shè)下，一對e和d將有利于攻擊者分解模數(shù)；或者計算出其它成對的e和d，而無需分解模數(shù)。24RSA算法的安全性RSA存在很多種攻擊，并不是因為算法本身存在缺陷，而是由于參數(shù)選擇不當造成的，為保證算法足夠安全，參數(shù)須滿足下面幾個基本要求：需要選擇足夠大的素數(shù) p, q, |p-q|較大，且(p-1)和(q-1)沒有小的素因子.通常選擇小的加密指數(shù)e, 且與(N) 互素， e對所有用戶可以是相同的，最初建議使用e=3，現(xiàn)在3太小，常使用 e=216-1 = 65535.解密指數(shù)比較大25Diffie-Hellman key distribution scheme 的變形 能夠

14、用于安全交換密鑰Published in 1985 by ElGamal: T. ElGamal, A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, IEEE Trans. Information Theory, vol IT-31(4), pp469-472, July 1985. 安全性基于有限域上的離散對數(shù)問題的困難性. 缺點：增加了傳送信息長度（2倍） ElGamal算法261) 密鑰產(chǎn)生過程： 首先選擇一素數(shù)p,生成元g和小于p的隨機數(shù)x，計算ygx mod p，以(y, g,

15、 p)作為公開密鑰，x作為秘密密鑰.2)加密過程：設(shè)欲加密明文消息為M. 隨機選一與p-1互素的整數(shù)k，0=k=p-1； 計算密文對: C = C1,C2, 發(fā)送給接收者. C1gk mod p, C2ykM mod p. ElGamal算法27 3) 解密過程: 計算明文: 因為 .ElGamal算法k 需要永久保密，且不能重復(fù)使用.為什么？281) 密鑰生成. 選擇公開參數(shù)：p=97 及本原根 a=5 ； Bob 選擇 秘密鑰xB=58，計算并發(fā)布公鑰yB=558=44 mod 97. 2) Alice 要加密 M=3 給 Bob. 首先得到 Bob的公開密鑰 yB=44，選擇隨機 k=3

16、6 計算:K=4436=75 mod 97.計算密文對: C1 = 536 = 50 mod 97 ； C2 = 75.3 mod 97 = 31 mod 97.發(fā)送 50,31 給Bob .3) Bob 解密消息.恢復(fù)消息密鑰 K=5058=75 mod 97.Bob 計算 K-1 = 22 mod 97.Bob 恢復(fù)明文 M = 31*22 = 3 mod 97.ElGamal算法ElGamal算法有限域上離散對數(shù)問題 已知（Zp，+，*）是一個有限域，g為Zp*的生成元，y Zp ，求x使得y=gx mod p如果求離散對數(shù)問題是容易的，則獲得公鑰攻擊者能夠解出x，則算法完全破譯.ElG

17、amal算法為什么離散對數(shù)問題難解？RSA與ElGamal比較RSAElGamal加密一次模冪運算兩次模冪+一次模乘解密一次模冪運算一次模冪運算密文密文不擴張密文擴張確定算法不確定算法安全RSA問題離散對數(shù)問題32橢圓曲線密碼體制ECC（elliptic curve cryptography）被IEEE公鑰密碼標準P1363采用.橢圓曲線并非橢圓，一般來講，橢圓曲線的曲線方程是以下形式的三次方程： y2+axy+by=x3+cx2+dx+e 其中a，b，c，d，e是滿足某些簡單條件的實數(shù). 定義中包括一個稱為無窮點的元素，記為O.橢圓曲線密碼體制33橢圓曲線的兩個例子橢圓曲線密碼體制34橢圓曲

18、線關(guān)于x軸對稱, 定義橢圓曲線上的加法律（加法法則）如下： O為加法單位元，即對橢圓曲線上任一點P，有P+O=P. 設(shè)Q和R是橢圓曲線上x坐標不同的兩點，Q+R的定義如下： 畫一條通過Q、R的直線與橢圓曲線交于P1（這一交點是唯一的，除非所做的直線是Q點或R點的切線，由Q+R+P1=O得Q+R=-P1.橢圓曲線密碼體制35 點Q的倍數(shù)定義如下： 在Q點做橢圓曲線的一條切線，設(shè)切線與橢圓曲線交于點S，定義2Q=Q+Q=-S。類似地可定義3Q=Q+Q+Q+，等.設(shè)P1=(x,y)是橢圓曲線上的一點（如圖所示），它的加法逆元定義為P2=-P1=(x, -y).以上定義的加法具有一般數(shù)域加法運算的一般

19、性質(zhì)，如交換律、結(jié)合律等. 橢圓曲線密碼體制這是因為P1、P2的連線延長到無窮遠時，得到橢圓曲線上的另一點O，即橢圓曲線上的3點P1、P2，O共線，P1+P2+O=O，P1+P2=O，所以P2=-P1. 由O+O=O，還可得O=-O.36密碼學(xué)中通常采用有限域上的橢圓曲線，它指曲線方程定義式中，所有系數(shù)都是某一有限域GF(p)中的元素（其中p為一大素數(shù)）.其中最為常用的是y2x3+ax+b(mod p)(a,bGF(p), 4a3+27b2(mod p)0)定義的曲線.橢圓曲線密碼體制37例： p=23，a=b=1，4a3+27b2(mod 23)80 方程為y2x3+x+1.橢圓曲線密碼體制

20、其圖形是連續(xù)曲線, 我們只考慮曲線在第一象限中的整數(shù)點橢圓曲線密碼體制設(shè)Ep(a,b)表示上面方程所定義的橢圓曲線上的點集(x,y)|0 xp,0yp，且x,y均為整數(shù)并上無窮遠點O.Ep(a,b)由以下方式計算： 對每一x(0 xp且x為整數(shù)），計算x3+ax+b(mod p). 決定中求得的值在模p下是否有平方根，如果沒有，則曲線上沒有與這一x相對應(yīng)的點；如果有，則求出兩個平方根（y=0 時只有一個平方根）.39本例中E23(1,1)由下表給出（表中不包含O）.橢圓曲線密碼體制40Ep(a,b)上的加法定義 設(shè)P，QEp(a,b)，則 P+O=P. 如果P=(x,y)，那么(x, y)+(

21、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)，而-7 mod 2316，所以-P=(13, 16)，也在E23(1,1)中.橢圓曲線密碼體制思考：根據(jù)曲線和兩點確定的直線推導(dǎo)P+Q和2P的求解公式41 設(shè)P=(x1,y1)，Q=(x2,y2)，P-Q，則P+Q=(x3,y3)由以下規(guī)則確定：x32-x1-x2(mod p)y3(x1-x3)-y1(mod p)其中橢圓曲線密碼體制42 例： 以E23(1,1)為例，設(shè)P=(3,10)，Q=(9,7)，

22、則 所以P+Q=（17,20），仍為E23(1,1)中的點.橢圓曲線密碼體制43 若求2P則 所以2P=(7,12) ，仍為E23(1,1)中的點.橢圓曲線密碼體制44 從上例看出，加法運算在E23(1,1)中是封閉的，且能驗證還滿足交換律. 對一般的Ep(a,b)，可證其上的加法運算是封閉的、滿足交換律，同樣還能證明其上的加法逆元運算也是封閉的，所以Ep(a,b)是一個Abel群.橢圓曲線密碼體制45 在橢圓曲線構(gòu)成的Abel群Ep(a,b)上考慮方程Q=kP，其中P，QEp(a,b)，kp，則由k和P易求Q，但由P、Q求k則是困難的，這就是橢圓曲線上的離散對數(shù)問題，可應(yīng)用于公鑰密碼體制.倍

23、點運算仍定義為重復(fù)加法，如4P=P+P+P+P橢圓曲線密碼體制為使用橢圓曲線構(gòu)造密碼體制，需要找出橢圓曲線上的數(shù)學(xué)困難問題.46利用橢圓曲線實現(xiàn)ElGamal密碼體制 1 密鑰生成 選取一條橢圓曲線，并得Ep(a,b)，取Ep(a,b)的一個生成元G，Ep(a,b)和G作為公開參數(shù). 用戶A選nA作為秘密鑰，并以PA=nAG作為公開鑰. 橢圓曲線密碼體制472 加解密運算任一用戶B若想向A發(fā)送消息Pm，可選取一隨機正整數(shù)k，產(chǎn)生以下點對作為密文：Cm=kG, Pm+kPA A解密時，以密文點對中的第二個點減去用自己的秘密鑰與第一個點的倍乘，即 Pm+kPA-nAkG=Pm+k(nAG)-nAk

24、G=Pm橢圓曲線密碼體制將明文消息m通過編碼嵌入到曲線上的點Pm，再對點Pm做加密變換.這里不對具體的編碼方法做進一步介紹，讀者可參考有關(guān)文獻.攻擊者若想由Cm得到Pm，就必須知道k。而要得到k，只有通過橢圓曲線上的兩個已知點G和kG，這意味著必須求橢圓曲線上的離散對數(shù)，因此不可行.48例：取p=751，Ep(-1,188)，即橢圓曲線為y2x3-x+188, Ep(-1,188)的一個生成元是G=(0,376)，設(shè)A的公開鑰為PA=(201,5).假定B已將欲發(fā)往A的消息嵌入到橢圓曲線上的點Pm=(562,201)，B選取隨機數(shù)k=386，由kG=386(0,376)=(676,558)，P

25、m+kPA=(562，201)+386(201,5)=(385,328)，得密文為(676,558),(385,328).橢圓曲線密碼體制49與基于有限域上離散對數(shù)問題的公鑰體制相比，橢圓曲線密碼體制有如下優(yōu)點: 1） 安全性高攻擊有限域上的離散對數(shù)問題可以用指數(shù)積分法，其運算復(fù)雜度為 ，其中p是模數(shù)（為素數(shù)）, 而這種方法對橢圓曲線上的離散對數(shù)問題并不有效.橢圓曲線密碼體制50目前攻擊橢圓曲線上的離散對數(shù)問題的方法只有適合攻擊任何循環(huán)群上離散對數(shù)問題的大步小步法，其運算復(fù)雜度為 ，其中pmax是橢圓曲線所形成的Abel群的階的最大素因子. 因此，橢圓曲線密碼體制比基于有限域上的離散對數(shù)問題的公鑰體制更安全.橢圓曲線密碼體制51 2) 密鑰量小 由攻擊兩者的算法復(fù)雜度可知，在實現(xiàn)相同的安全性能條件下，橢圓曲線密碼體制所需的密鑰量遠比基于有限域上的離散