第4章-公鑰密碼算法課件

1、1公鑰密碼體制概述 1976年Diffie和Hellman的“New directions in cryptography”導(dǎo)致了密碼學(xué)上的一場(chǎng)革命，開(kāi)創(chuàng)了公鑰密碼學(xué)的新紀(jì)元。他們首次證明了在發(fā)送端和接收端無(wú)密鑰傳輸?shù)谋Ｃ芡ㄐ攀强赡艿摹?1977年Rivest，Shamir和Adleman提出了RSA公鑰密碼算法。 90年代逐步出現(xiàn)橢圓曲線密碼等其他公鑰算法。n公鑰公鑰密碼體制，又稱(chēng)為雙鑰雙鑰或非對(duì)稱(chēng)非對(duì)稱(chēng)密碼體制 密碼系統(tǒng)有兩個(gè)密鑰，即加密密鑰和解密密鑰不同，從一個(gè)難于推出另一個(gè)。這兩個(gè)密鑰一個(gè)是公開(kāi)的，一個(gè)是秘密的，分別稱(chēng)為公開(kāi)密鑰和私有密鑰，公開(kāi)密鑰是對(duì)外公開(kāi)的，即所有的人都可知，私有密

2、鑰是只有特定的用戶方能擁有。2公鑰密碼體制概述 公鑰密碼體制與私鑰密碼體制的最大不同點(diǎn)就是：加密密鑰和解密密鑰不同，從一個(gè)難于推出另一個(gè)。在公鑰密碼體制中，將這兩個(gè)不同的密鑰區(qū)分為公開(kāi)密鑰PK(Public Key)和私有密鑰SK(Secrete Key）。 六個(gè)組成部分：明文、密文；公鑰、私鑰；加密算法、解密算法3公鑰密碼體制模型A加密B解密A加密B解密明文明文明文密文密文加密模型加密模型認(rèn)證模型認(rèn)證模型B的公鑰B的私鑰A的私鑰A的公鑰明文4公鑰密碼體制的特點(diǎn) 加密和解密能力分開(kāi)。 可以實(shí)現(xiàn)多個(gè)用戶加密的消息只能由一個(gè)用戶解讀（用于公共網(wǎng)絡(luò)中實(shí)現(xiàn)保密通信）。 可實(shí)現(xiàn)只能由一個(gè)用戶加密消息而使

3、多個(gè)用戶可以解讀（可用于認(rèn)證系統(tǒng)中對(duì)消息進(jìn)行數(shù)字簽字）。 無(wú)需事先分配密鑰。 重要特點(diǎn)僅根據(jù)密碼算法和加密密鑰來(lái)確定解密密鑰在計(jì)算上不可行。 有些算法如RSA還具有：兩個(gè)密鑰中的任何一個(gè)都可用來(lái)加密，另一個(gè)用來(lái)解密。 優(yōu)點(diǎn)：能很好解決私鑰加密中由于密鑰數(shù)量過(guò)多導(dǎo)致的管理難和費(fèi)用高等問(wèn)題，也不用擔(dān)心傳輸中的私鑰泄漏，保密性能優(yōu)于私鑰加密。 缺點(diǎn)：加密算法復(fù)雜，加密速度難以達(dá)到理想狀態(tài)。5公鑰密碼體制依賴(lài)的基礎(chǔ) 傳統(tǒng)的對(duì)稱(chēng)密碼體制依賴(lài)的基礎(chǔ)是替代和置換兩種轉(zhuǎn)換思想。與對(duì)稱(chēng)密碼體制不同的是，公鑰密碼體制依賴(lài)的基礎(chǔ)是數(shù)學(xué)上的某類(lèi)問(wèn)題的求解困難。 經(jīng)典的公鑰密碼算法RSA、橢圓曲線密碼算法ECC等都是依

4、賴(lài)某類(lèi)數(shù)學(xué)問(wèn)題的，它們共同的特點(diǎn)是基于某個(gè)單向陷門(mén)函數(shù)。單向陷門(mén)函數(shù) y=fk(x) 是指同時(shí)滿足下列條件的一類(lèi)可逆函數(shù)：6公鑰密碼體制依賴(lài)的基礎(chǔ) 函數(shù)是一一映射關(guān)系，也就是說(shuō)，對(duì)于每個(gè)函數(shù)值y，只有唯一的一個(gè)原象x與之對(duì)應(yīng)； 給定x與關(guān)鍵參數(shù)k,函數(shù)y=fk(x)很容易計(jì)算； 給定y，存在某個(gè)關(guān)鍵參數(shù)k，在未知k時(shí)，由y計(jì)算出x非常困難，即在未知k的條件下，逆函數(shù)x=f-1k(y)的計(jì)算相當(dāng)復(fù)雜，實(shí)際上是不可行的；在已知k時(shí)，對(duì)給定的任何y，則逆函數(shù)x=f-1k(y)很容易計(jì)算； 給定y和參數(shù)k，無(wú)法從函數(shù)y=fk(x)推導(dǎo)出影響其逆函數(shù)f-1的關(guān)鍵參數(shù)k。 設(shè)計(jì)任何一種公鑰密碼方案，所要做

5、的工作就是尋找這樣的單向陷門(mén)函數(shù)，其中陷門(mén)信息就是私鑰，也就是上面所列舉的關(guān)鍵參數(shù)k。7公鑰密碼系統(tǒng)的特征 根據(jù)密碼系統(tǒng)的組成以及公鑰密碼體制自身的特點(diǎn)，一個(gè)公鑰密碼系統(tǒng)可以表示為：加密算法E、解密算法D、公鑰/私鑰(PK/SK)對(duì)、明文M、密文C六個(gè)元素，且各元素必須要滿足以下條件：8公鑰密碼系統(tǒng)的特征 密鑰。要滿足兩點(diǎn)要求：公鑰/私鑰(PK/SK)對(duì)容易產(chǎn)生，且私鑰除了生成密鑰的用戶自己知道之外，其他任何人都不可知；已知公鑰PK，無(wú)法計(jì)算出私鑰SK，即公鑰密碼系統(tǒng)所要滿足的基本條件之一是從公開(kāi)密鑰無(wú)法通過(guò)計(jì)算得到私有密鑰。9公鑰密碼系統(tǒng)的特征 加密算法E。要滿足兩點(diǎn)要求：已知公鑰PK，對(duì)任

6、何明文M，由E計(jì)算出密文C非常容易，即C = EPK(M) 易計(jì)算，或者已知私鑰SK，對(duì)任何信息M，由E計(jì)算數(shù)字簽名也非常容易，即 C = ESK(M) 易計(jì)算。 解密算法D。要滿足兩點(diǎn)要求：已知私鑰SK，對(duì)任何密文C，由D容易計(jì)算出明文M，或者已知公鑰PK，對(duì)任何用SK所做的數(shù)字簽名C，容易通過(guò)D計(jì)算，得到簽名前的信息；但是已知公鑰PK、密文C，以及解密算法D，無(wú)法由三者推導(dǎo)出明文M或者私鑰SK。即由公鑰、密文和解密算法 ，推導(dǎo)明文和解密密鑰都是計(jì)算不可行的。 一個(gè)設(shè)計(jì)良好的密碼系統(tǒng)，加密算法E和解密算法D應(yīng)該都是公開(kāi)的，該原則同樣適用于公鑰密碼系統(tǒng)，公鑰密碼系統(tǒng)中唯一需要保密的就是私鑰SK

7、。10公鑰密碼體制加解密過(guò)程 假設(shè)網(wǎng)絡(luò)上的兩個(gè)用戶Alice和Bob需要進(jìn)行秘密通信，為了防止攻擊者Eve竊聽(tīng)信息，Alice和Bob選擇使用公鑰密碼體制加密傳輸?shù)男畔?。Alice是信息的發(fā)送方；Bob是信息的接收方。11公鑰密碼體制加解密過(guò)程 Alice與Bob產(chǎn)生公鑰/私鑰對(duì)：PKA/SKA，PKB/SKB。 Alice與Bob通過(guò)某種機(jī)制公布各自的公鑰PKA與PKB，例如將公鑰放到一個(gè)公共的服務(wù)器，供其他用戶查詢(xún)。 Alice通過(guò)查詢(xún)公共服務(wù)器獲得Bob的公鑰PKB。如果Alice欲給Bob發(fā)送報(bào)文M，他就用Bob的公鑰PKB加密報(bào)文。已知待加密的明文M以及Bob的公鑰PKB，Alice

8、很容易通過(guò)加密算法E計(jì)算出密文，即 C = EPKB(M)。 （4）接收方Bob收到Alice發(fā)送的信息之后，使用自己的私鑰SKB解密報(bào)文。已知密文C和私鑰SKB，Bob很容易通過(guò)解密算法計(jì)算出明文M，即 M=DSKB(C)。 假設(shè)攻擊者Eve竊聽(tīng)到Alice發(fā)送的報(bào)文，雖然Eve可查詢(xún)獲得Bob的公鑰PKB，但從PKB確定Bob的私鑰SKB 在計(jì)算上是不可行的，因此Eve無(wú)法獲知Bob的私鑰 SKB ；僅知道公開(kāi)密鑰和密文，無(wú)法計(jì)算出明文M。因此攻擊者Eve無(wú)法得到Alice發(fā)給Bob的密碼信息。12公鑰密碼體制 公鑰密碼技術(shù)的主要價(jià)值是解決下列問(wèn)題： 1）密鑰分發(fā)； 2）大范圍應(yīng)用中，數(shù)據(jù)

9、的保密性和完整性； 3）實(shí)體鑒別； 4）不可抵賴(lài)性； 公鑰密碼體制的應(yīng)用可分為3類(lèi)： a）加密/解密：發(fā)送方用接收方的公鑰對(duì)消息加密。 b）數(shù)字簽名：發(fā)送方用其私鑰對(duì)消息簽名。簽名可以對(duì)整條消息加密或?qū)ο⒌囊粋€(gè)小的數(shù)據(jù)塊加密來(lái)產(chǎn)生，其中該小的數(shù)據(jù)塊是整條消息的函數(shù)。 c）密鑰交換：通信雙方交換會(huì)話密鑰。有幾種不同的方法可用于密鑰交換，這些方法都使用了通信一方或雙方的私鑰。13公鑰密碼體制 有些算法可用于上述三種應(yīng)用，而其他一些算法則只適用其中一種或兩種應(yīng)用。算法加密/解密 數(shù)字簽名 密鑰交換RSA是是是橢圓曲線密碼是是是Diffie-Hellman否否是DSS否是否14公鑰密碼體制 自197

10、6年提出公鑰密碼系統(tǒng)以來(lái)，密碼專(zhuān)家們已設(shè)計(jì)出多種公鑰密碼算法，這些算法的共同點(diǎn)都是基于某類(lèi)數(shù)學(xué)難題，通過(guò)找到該類(lèi)問(wèn)題的某個(gè)單向陷門(mén)函數(shù)實(shí)現(xiàn)對(duì)數(shù)據(jù)的加密和解密。 依據(jù)所依賴(lài)的數(shù)學(xué)難題類(lèi)別劃分，主要有以下3類(lèi)系統(tǒng)：基于大整數(shù)因子分解問(wèn)題的公鑰系統(tǒng)，典型代表是RSA算法；基于有限域橢圓曲線離散對(duì)數(shù)問(wèn)題的公鑰系統(tǒng)，典型代表是ECC算法；基于有限域離散對(duì)數(shù)問(wèn)題的公鑰系統(tǒng)，典型算法是DSA。15若干較有影響的公鑰加密算法 RSA算法：基于大整數(shù)素因子分解問(wèn)題，目前認(rèn)為是安全的。 Merkle-Hellman背包體制：基于子集和問(wèn)題，已證明不安全。 McEliece體制：基于余代數(shù)編碼中的線性解碼問(wèn)題，目前

11、認(rèn)為是安全的。 ElGamal體制：基于有限域上的離散對(duì)數(shù)問(wèn)題，目前認(rèn)為有一定安全性。 Chor-Rivest背包體制：基于子集和問(wèn)題，目前認(rèn)為是安全的。 橢圓曲線密碼：基于橢圓曲線上的離散對(duì)數(shù)問(wèn)題，是對(duì)ElGamal體制的改進(jìn)，目前認(rèn)為是安全的。 有限自動(dòng)機(jī)密碼：基于有限自動(dòng)機(jī)的求逆問(wèn)題，目前認(rèn)為有一定安全性。16RSA算法1976年Deffie和Hellman提出公鑰密碼系統(tǒng)思想之后，1977年麻省理工學(xué)院的Ron Rivest、Adi Shamir和Len Adleman三位學(xué)者研制了RSA(Rivest-Shamir-Adleman)公鑰密碼方案，該方案于1978年首次發(fā)表，從那以后至

12、今，RSA算法是被使用最多的公鑰密碼方案。17RSA算法依賴(lài)的數(shù)學(xué)問(wèn)題 RSA算法基于“大整數(shù)質(zhì)因子分解”非常困難這一數(shù)學(xué)難題，這里大整數(shù)通常有幾百位長(zhǎng)。RSA算法依賴(lài)以下幾個(gè)數(shù)論定理： 模運(yùn)算的性質(zhì)：正整數(shù)n是素?cái)?shù)，集合Zn = 0，1，2.，(n-1) 表示小于n的所有非負(fù)整數(shù)集合，則對(duì)于集合Zn 中的每一個(gè)非零整數(shù)wZn，均存在一個(gè)z，滿足公式 w z = 1 mod n，我們稱(chēng)z是w的乘法逆元，且n是它們的模。18RSA算法依賴(lài)的數(shù)學(xué)問(wèn)題 費(fèi)馬定理：如果p是素?cái)?shù)，a是不能被p整除的正整數(shù)，則： ap-1 1 mod p 例如：P=7， a=2，則27-1 =26 = 64，64 mod

13、 7 = 119RSA算法依賴(lài)的數(shù)學(xué)問(wèn)題 歐拉函數(shù)：正整數(shù)n的歐拉函數(shù)是指小于n且與n互素的正整數(shù)個(gè)數(shù)，通常記為(n)。 對(duì)于任一素?cái)?shù)p，顯然有：(p) p 1， 例如：設(shè)p=3，小于3且與3互素的正整數(shù)為1，2，因此(3) = 2；類(lèi)似地，當(dāng)p=7時(shí)，小于7且與7互素的正整數(shù)為1，2，3，4，5，6，因此(7) = 6。 假定有兩個(gè)不同的素?cái)?shù)p和q，n是p與q之積，即 n = p q，則有如下公式關(guān)系：(n)=(pq)= (p)(q)=(p-1)(q-1) 例如：取n=21，(21) = (3) (7) = (3-1) (7-1) = 2 6 = 12，其中這12個(gè)整數(shù)是1，2，4，5，8，

14、10，11，13，16，17，19，20 。20RSA算法依賴(lài)的數(shù)學(xué)問(wèn)題 歐拉定理： 任何兩個(gè)互素的整數(shù)a和n，有如下關(guān)系： a(n) 1 mod n 例如：a = 3；n=8；由(3)歐拉函數(shù)的定義，(8) = 4；則a(n) = 34 = 81 =108 +1 1 mod 8 1 mod n21RSA算法依賴(lài)的數(shù)學(xué)問(wèn)題 （）歐幾里德(Euclid)算法：該算法主要的思想是：用一個(gè)簡(jiǎn)單的方法確定兩個(gè)正整數(shù)的最大公因子，并且如果這兩個(gè)整數(shù)互素，通過(guò)擴(kuò)展該算法能確定它們各自的乘法逆元。 22歐幾里德(Euclid)算法設(shè)，求和的最大公因子（，）以及（，）中的與。 令r0=a, r1=n，利用輾轉(zhuǎn)

15、相除法可得： r0 = r1q1 + r2, 0 r2 r1 r1 = r2q2 + r3, 0 r3 r2 rm-2 = rm-1qm-1 + rm, 0 rm rm-1 rm-1 = rmqm + rm+1, rm+1 = 0 (a,n) = (r0, r1) = (r1, r2) = = (rm-1, rm) = (rm, 0) = rm. 由上述關(guān)系式可以得到（，）中的與23歐幾里德(Euclid)算法24歐幾里德(Euclid)算法25歐幾里德(Euclid)算法26歐幾里德(Euclid)算法27RSA算法密鑰產(chǎn)生過(guò)程 隨機(jī)選擇兩個(gè)秘密的大素?cái)?shù) p與q，且p q = n。 為了增強(qiáng)

16、算法的安全性，避免攻擊者通過(guò)數(shù)學(xué)攻擊的方法找到n的歐拉函數(shù)(n)，從而攻破RSA密碼方案，RSA算法的設(shè)計(jì)者建議：1. p與q長(zhǎng)度應(yīng)該只差幾個(gè)數(shù)字，這樣對(duì)于1024位的密鑰來(lái)說(shuō)，p與q都應(yīng)該約位于區(qū)間1075 ,10100內(nèi)；2. p-1 與 q-1 都應(yīng)有一個(gè)大的素因子；3. gcd（p-1，q-1）應(yīng)該較小。另外，已經(jīng)證明，若 en 且 d160 時(shí)受到青睞。47Zp上的橢圓曲線 不是所有的橢圓曲線都適合加密。 y2 = x3 + ax + b是一類(lèi)可以用來(lái)加密的橢圓曲線，也是最簡(jiǎn)單的一類(lèi)。把 y2 = x3 + ax + b 這條曲線定義在Zp上，x，y和系數(shù)都屬于Zp 。這里p為大于3

17、的素?cái)?shù)，a，b Zp，4a3 + 27b2 0 mod p。 記Zp上滿足該方程的整數(shù)對(duì)（x，y）和無(wú)窮遠(yuǎn)點(diǎn)O組成的集合為Ep（a，b）。則基于該集合可定義一個(gè)有限阿貝爾群（ 4a3 + 27b2 0 mod p 等價(jià)于x3 + ax + b 無(wú)重復(fù)因子）。 Zp上的橢圓曲線就是由集合Ep（a，b）中的點(diǎn)組成。48Zp上的橢圓曲線49Zp上的橢圓曲線運(yùn)算 Ep（a，b）上的加法運(yùn)算與定義在實(shí)數(shù)域上的橢圓曲線中描述的代數(shù)方法是一致的。對(duì)任何點(diǎn)P，Q Ep（a，b）： P+O=P 若P=（xP，yP），則 P+（ xP，-yP）= O。點(diǎn)（ xP，-yP）是P的負(fù)元，記為-P。 例如，對(duì) E23（

18、1，1）上的點(diǎn)P=（13，7），有-P=（13，-7），而-7 mod 23=16.因此，-P=（13，16），該點(diǎn)也在E23（1，1）上。50Zp上的橢圓曲線運(yùn)算 若P=（xP，yP）和 Q=（xQ，yQ），且P-Q，則R=P+Q=（xR，yR）由下列規(guī)則確定： xR= （2 - xP xQ）mod p yR = （xP xR） - yP）mod p，其中 乘法定義為重復(fù)相加。如4P=P+P+P+P。 為確定各種橢圓曲線密碼的安全性，需要知道定義在橢圓曲線上的有限阿貝爾群中點(diǎn)的個(gè)數(shù)。在有限群Ep（a，b）中，點(diǎn)的個(gè)數(shù)N的范圍是：P+1-2pN P+1+2p 所以Ep（a，b）上點(diǎn)的個(gè)數(shù)約等于

19、Zp中元素的個(gè)數(shù)，即p個(gè)元素。QPpyaxQPpxxyyPPPQPQ，若，若mod)23(mod)(251有限域F2m上的橢圓曲線F2m上的橢圓曲線與Zp上的三次方程不同，可表示成 y2 + xy = x3 + ax2 + b這里a，b（0） F2m，或曲線方程 y2 + cy = x3 + ax + b這里a，b，c（0） F2m上述曲線上的所有有理點(diǎn)（x，y都在F2m上）和無(wú)窮遠(yuǎn)點(diǎn)組成的集合記為E F2m （a，b），有限域F2m上的橢圓曲線就是由該集合中的點(diǎn)組成。52有限域F2m上的橢圓曲線運(yùn)算 對(duì)任何P E F2m （a，b），P+O=P。 若 P=（xP，yP），則P+ （xP， x

20、P +yP）=O。點(diǎn)（xP， xP +yP）是P的負(fù)元，記為-P。 1）方程為）方程為 y y2 2 + xy = x+ xy = x3 3 + ax+ ax2 2 + b + b 時(shí)時(shí)， 若P=（xP，yP）和 Q=（xQ，yQ）都屬于F2m ，且P-Q， PQ，則R=P+Q=（xR，yR）由下列規(guī)則確定： xR= 2 + + a + xP + xQ yR = （xP + xR） + xR + yP其中， =（ yQ + yP）/（ xQ + xP） 若 P=（xP，yP），則R=2P= （xR，yR）由下列規(guī)則確定： xR= 2 + + a yR = （+1）xR + xP2 其中， =

21、xP + yP / xP53有限域F2m上的橢圓曲線運(yùn)算 2）方程為）方程為 y y2 2 + cy = x+ cy = x3 3 + ax + b+ ax + b 時(shí) 對(duì)任何P=（xP，yP）和 Q=（xQ，yQ）都屬于F2m ， 其中 ，否則，若)(,ORRPQPQ,yxcxyxxQPQPcaxQPxxxxyyxPQPQPQPR，若，若222QPcyxxcaxQPcyxxxxyyyPRPPPRPQPQPR，若，若)()(254橢圓曲線密碼橢圓曲線密碼ECCECC算法依賴(lài)的數(shù)學(xué)問(wèn)題算法依賴(lài)的數(shù)學(xué)問(wèn)題 橢圓曲線離散對(duì)數(shù)問(wèn)題給定橢圓曲線E及該橢圓曲線上的一點(diǎn)P，kP 表示k個(gè)P相加，k為某整數(shù)，

22、如果橢圓曲線上存在一點(diǎn)Q，能夠滿足方程 Q = kP，那么橢圓曲線離散對(duì)數(shù)問(wèn)題就是給定點(diǎn)P和點(diǎn)Q，求解k的問(wèn)題，在數(shù)學(xué)上該問(wèn)題是同時(shí)涉及整數(shù)因式分解和離散對(duì)數(shù)的難題。ECC算法就是基于“橢圓曲線離散對(duì)數(shù)問(wèn)題”難以求解而設(shè)計(jì)的，給定P和k容易通過(guò)方程Q = kP計(jì)算Q；但是反過(guò)來(lái)，給定Q和P，求k在計(jì)算上是不可行的，因此我們可以設(shè)定k為私鑰。55ECC算法密鑰的選擇 基于橢圓曲線密碼體制的ECC算法在加解密之前，首先要給出橢圓曲線域的一些參數(shù)，如基點(diǎn)P，階n ，以確定具體的橢圓曲線。 ECC算法密鑰的產(chǎn)生是都是建立在某個(gè)有限域的橢圓曲線上，設(shè)給定一個(gè)具有q個(gè)元素有限域的橢圓曲線E，E 的基點(diǎn)是P

23、，P的階為n。 下面介紹一種利用橢圓曲線實(shí)現(xiàn)加解密的方法，這種方法很簡(jiǎn)單。 密鑰的選擇： （1） 密鑰的產(chǎn)生者在區(qū)間2，n-1隨機(jī)選取某整數(shù)k； （2） 計(jì)算Q = kP。 則Q就是公鑰，私鑰是k。 56一種ECC算法加解密過(guò)程 假設(shè)網(wǎng)絡(luò)上的用戶Alice和Bob要進(jìn)行保密通信，它們選擇ECC算法加密通信的報(bào)文。Alice與Bob知道同一條橢圓曲線E，并已分別產(chǎn)生公鑰/私鑰對(duì)QA/kA，QB/kB，Alice欲發(fā)送明文m送給Bob，并且已獲知Bob的公鑰QB。Alice加密過(guò)程如下：（1）首先要將明文m編碼成橢圓曲線上的點(diǎn)Pm，Pm為(Xm，Ym)；（2） Alice隨機(jī)選擇整數(shù)k2,n-1；

24、（3）計(jì)算 kP = R1 (X1，Y1)，kQB = R2 (X2，Y2）；如果X2 =0；則返回到（2）； (4) 則密文C由 R1，Pm + R2 組成； 57一種ECC算法的加解密過(guò)程 Bob收到密文C后，解密過(guò)程如下：（1）計(jì)算 kBR1 = kBkP = kkBP = kQB（2）Bob利用密文C的第二點(diǎn)的值R2 + Pm 減去由（1）計(jì)算得到的結(jié)果kQB，即 Pm + R2 kQB = Pm + kQB kQB = Pm；（3）Bob得到橢圓曲線上點(diǎn)Pm ，然后按照某種解碼方法從點(diǎn)Pm獲取明文m。舉例：取 p=751，Ep(-1,188),即其橢圓曲線方程為y2 = x3 -x

25、+ 188，基點(diǎn)為（0，376）。假設(shè)A要將編碼為橢圓曲線上點(diǎn) Pm（562，201）的消息發(fā)給B，且A挑選的隨機(jī)數(shù)為k=386，B的公鑰為（201，5），那么有386（0，376）=（676，558）和（562，201）+386（201，5）=（385，328）。于是A發(fā)送的密文是（676，558），（385，328）。58Menezes-Vanstone 橢圓曲線密碼體制 Menezes-Vanstone 橢圓曲線密碼體制是ElGamal密碼體制在橢圓曲線上的模擬，它是由A J Menezes與S A Vanstone 在1993年12月提出的。 ElGamal 公鑰密碼體制是1985年7

26、月由Taher ElGamal 發(fā)明的，它是建立在解有限乘法群上的離散對(duì)數(shù)問(wèn)題的困難性基礎(chǔ)之上的一種公鑰密碼體制。該密碼體制至今仍被認(rèn)為是一個(gè)安全性能較好的公鑰密碼體制，目前它被廣泛用于許多密碼協(xié)議中。59ElGamal 加密算法 ElGamal 算法既可用于加密，也可用于簽名。加密算法描述如下： （1）公開(kāi)參數(shù)：首先選取大素?cái)?shù)p，并取是乘法群 Zp*=1，p-1的一個(gè)生成元。 （2）密鑰生成：再隨機(jī)選取整數(shù)d：0dp-1，并計(jì)算=d mod p。這里p與是公開(kāi)參數(shù)，是公開(kāi)的加密密鑰（公鑰），d是保密的解密密鑰（私鑰）。 （3）加密運(yùn)算：對(duì)明文m Zp*，隨機(jī)選取整數(shù)k：0k3是一個(gè)素?cái)?shù)，E是

27、有限域Zp上的由方程y2 = x3 + ax + b 表示的橢圓曲線，E（Zp）是相應(yīng)的阿貝爾群。G是該群中具有較大素?cái)?shù)階n的一個(gè)點(diǎn)。 （2）密鑰生成：隨機(jī)選取整數(shù)d：2dn-1，計(jì)算P=dG。d是保密的密鑰，P是公開(kāi)鑰。 （3）加密運(yùn)算：對(duì)任意明文m=（m1，m2） Zp* Zp*，隨機(jī)選取一個(gè)秘密整數(shù)k：1kn-1,使得（x，y）=kP，滿足x與y均為非零元素。并計(jì)算 C0=kG，c1= m1 x mod p，c2= m2 y mod p， 明文m=（ m1，m2）經(jīng)加密后的密文為（C0，c1，c2）。密文空間為E（Zp） Zp* Zp* 。 （4）解密運(yùn)算：對(duì)任意密文c=（C0，c1，c

28、2），計(jì)算標(biāo)量乘 dC0 =（x，y），計(jì)算 m1 = c1 x-1 mod p，m2 = c2 y-1 mod p，即得c解密后的明文為（m1，m2）。63ECC 算法的安全性分析ECC算法的安全性依賴(lài)于橢圓曲線離散對(duì)數(shù)問(wèn)題計(jì)算的困難性，如果離散對(duì)數(shù)問(wèn)題容易計(jì)算，從用戶的公鑰能夠推導(dǎo)出私鑰，那么整個(gè)密碼體制就會(huì)坍塌。除此之外，橢圓曲線E的選擇也非常重要。為防止窮搜索攻擊，有限域的階應(yīng)是一個(gè)較大的素?cái)?shù)冪。解有限群離散對(duì)數(shù)問(wèn)題的通用方法均可用來(lái)解橢圓曲線上阿貝爾群上的離散對(duì)數(shù)問(wèn)題。但是關(guān)于解有限域乘法群上的指數(shù)演算法則對(duì)橢圓曲線離散對(duì)數(shù)問(wèn)題(ECDLP)不適用，即目前還沒(méi)有找到對(duì)ECDLP適用的

29、類(lèi)似算法。已知的對(duì)ECDLP最好的算法是（并行）Pollard-算法。解 ECDLP 比解有限域上的離散對(duì)數(shù)問(wèn)題 FFDLP 要困難得多，因而橢圓曲線密碼體制比同等規(guī)模的Zp*上的 ElGamal 公鑰密碼體制安全性要強(qiáng)很多。64ECC算法的優(yōu)點(diǎn)橢圓曲線加密算法ECC與其他公鑰算法（如RSA）相比有很多優(yōu)點(diǎn)： a)安全性能更高： 加密算法的安全性能一般通過(guò)該算法的抗攻擊強(qiáng)度來(lái)反映。ECC和其他幾種公鑰系統(tǒng)相比，其抗攻擊性具有絕對(duì)的優(yōu)勢(shì)。橢圓曲線的離散對(duì)數(shù)（ECDLP）計(jì)算困難性在計(jì)算復(fù)雜度上目前是完全指數(shù)級(jí)，而RSA是亞指數(shù)級(jí)的。這體現(xiàn)ECC比RSA的每bit安全性能更高。 b)計(jì)算量小和處理

30、速度快： 在一定的相同的計(jì)算資源條件下，在私鑰 的處理速度上（解密和簽名），ECC遠(yuǎn)比RSA、DSA 快得多。ECC總的速度比RSA、DSA要快得多。 同時(shí)ECC系統(tǒng)的密鑰生成速度比RSA快百倍以上。 因此在相同條件下，ECC則有更高的加密性能。65ECC算法的優(yōu)點(diǎn) c)存儲(chǔ)空間占用?。?ECC的密鑰尺寸和系統(tǒng)參數(shù)與RSA、DSA相比要小得多。160位ECC與1024位RSA、DSA具有相同的安全強(qiáng)度，210位ECC則與2048位RSA、DSA具有相同的安全強(qiáng)度。意味著它所占的存貯空間要小得多。這對(duì)于加密算法在資源受限環(huán)境上（如智能卡等）的應(yīng)用具有特別重要的意義。 d)帶寬要求低： 當(dāng)對(duì)長(zhǎng)消息

31、進(jìn)行加解密時(shí)， 三類(lèi)密碼系統(tǒng)有相同的帶寬要求，但應(yīng)用于短消息時(shí)ECC帶寬要求卻低得多。而公鑰密碼系統(tǒng)多用于短消息，例如用于數(shù)字簽名和用于對(duì)對(duì)稱(chēng)系統(tǒng)的會(huì)話密鑰傳遞。帶寬要求低使ECC在無(wú)線網(wǎng)絡(luò)領(lǐng)域具有廣泛的應(yīng)用前景。 6667ECC 算法的缺點(diǎn) 公開(kāi)密鑰加密系統(tǒng)是基于尖端的數(shù)學(xué)難題，計(jì)算非常復(fù)雜，實(shí)現(xiàn)難度大； 安全性高，但實(shí)現(xiàn)速度卻遠(yuǎn)趕不上對(duì)稱(chēng)密鑰加密系統(tǒng)。 隨著計(jì)算能力的提高，從安全性角度考慮，對(duì)密鑰長(zhǎng)度的要求越來(lái)越高。相對(duì)于其他公鑰密碼算法，ECC逐漸體現(xiàn)出其優(yōu)越性。但是自從使用公鑰密碼體制以來(lái)，實(shí)際應(yīng)用中，RSA算法因?yàn)樵砗?jiǎn)單被廣泛使用，ECC算法在實(shí)際應(yīng)用中相對(duì)比較少。但是隨著時(shí)間的推

32、移，ECC算法理論不斷完善，相信它逐漸會(huì)被應(yīng)用到實(shí)際系統(tǒng)中。68ECC算法應(yīng)用與現(xiàn)狀算法在標(biāo)準(zhǔn)化中應(yīng)用 國(guó)內(nèi)外軟硬件中應(yīng)用69ECC算法在標(biāo)準(zhǔn)化中應(yīng)用 ECC的特點(diǎn)使它在某些領(lǐng)域（如手機(jī)、智能卡）的應(yīng)用將取代RSA，并成為通用的公鑰加密算法。 許多國(guó)際標(biāo)準(zhǔn)化組織（政府、工業(yè)界、金融界、商業(yè)界等）已將各種橢圓曲線密碼體制作為其標(biāo)準(zhǔn)化文件向全球頒布。 ECC標(biāo)準(zhǔn)大體可以分為兩種形式： 一類(lèi)是技術(shù)標(biāo)準(zhǔn)，即描述以技術(shù)支撐為主的ECC體制，主要有 IEEEP1363、ANSIX9.62、ANSIX9.63、SEC1、SEC2、FIP1862、ISO/IEC148883。規(guī)范了ECC的各種參數(shù)的選擇，并給

33、出了各級(jí)安全強(qiáng)度下的一組 ECC參數(shù)。 另一類(lèi)是應(yīng)用標(biāo)準(zhǔn)，即在具體的應(yīng)用環(huán)境中建議使用 ECC技術(shù)，主要有ISO/IEC 15946、IETFPKIX、IETFTLS、WAPWTLS 等。70ECC在軟硬件中應(yīng)用 在標(biāo)準(zhǔn)化的同時(shí)，一些基于標(biāo)準(zhǔn)（或草案）的各種橢圓曲線加密、簽名、密鑰交換的軟、硬件也相繼問(wèn)世。 美國(guó)RSA數(shù)據(jù)安全公司在1997年公布了包含ECC的密碼引擎工具包BSAFE4.0。 以加拿大Certicom為首的安全公司和工業(yè)界聯(lián)合也研制、生產(chǎn)了以橢圓曲線密碼算法為核心的密碼產(chǎn)品，還提出了各種安全條件下對(duì)橢圓曲線離散對(duì)數(shù)攻擊的懸賞挑戰(zhàn)。 德國(guó)、日本、法國(guó)、美國(guó)、加拿大等國(guó)的很多密碼學(xué)研究小組及一些公司實(shí)現(xiàn)了橢圓曲線密碼體制。 我國(guó)也有一些密碼學(xué)者做了這方面的工作。許多標(biāo)準(zhǔn)化組織已經(jīng)或正在制定關(guān)于橢圓曲線的標(biāo)準(zhǔn)，同時(shí)也有許多的廠商已