第三章公開密鑰體制

1、 公鑰密碼學(xué)研究與進(jìn)展公鑰密碼學(xué)研究與進(jìn)展主要內(nèi)容主要內(nèi)容v引論引論v基本概念基本概念v公鑰密碼學(xué)公鑰密碼學(xué): 基本原理基本原理v公鑰加密體制公鑰加密體制: RSA、ElGamal、ECCv數(shù)字簽名及其應(yīng)用數(shù)字簽名及其應(yīng)用v研究動(dòng)態(tài)與熱點(diǎn)研究動(dòng)態(tài)與熱點(diǎn)1 基本概念保密學(xué)保密學(xué)(Cryptology)：研究信息系統(tǒng)安全保密的科學(xué)。它包含兩個(gè)分支:密碼學(xué)密碼學(xué)(Cryptography)，對(duì)信息進(jìn)行編碼實(shí)現(xiàn)隱蔽信息的一門學(xué)科。密碼分析學(xué)密碼分析學(xué)(Cryptanalytics)，研究分析破譯密碼的學(xué)問。兩者相互對(duì)立，而又互相促進(jìn)地向前發(fā)展。密碼學(xué)的歷史古典密碼（Classic Cryptograp

2、hy）（1976年以前）vBC 487 : 置換密碼Transposition Cipher, “Scytale”vBC 300 : 隱匿術(shù)(Steganography)：希臘人用奴隸傳遞信息vBC 100BC 44 : 代換密碼Substitution Cipher, “Caesar Cipher”v1883 : Kerckhoffs AssumptionvWW II : Turing Machine for Cryptanalysis (Breaking the Enigma)v1949 : Perfect Secrecy (C.E.Shannon) “Confusion”混淆 and “

3、Diffusion”擴(kuò)散密碼學(xué)的歷史現(xiàn)代密碼學(xué)（Modern Cryptography） (1976年以后)v1976 : Public-Key Cryptography (Diffie, Hellman)v1977 : Data Encryption Standard, DES (NIST)v1978 : RSA (Rivest, Shamir, Adleman)v1982/85 : Goldwasser presented 2 paradigms for firm foundations of cryptography. “Indistinguishability” and “Simula

4、tability”v1998 : DES被破譯v2000: AES（ 2000年10月2日確定了以Rijdeal作為AES的標(biāo)準(zhǔn)算法）加密( Encryption) 算法： 密碼員對(duì)明文進(jìn)行加密時(shí)所采用的一組規(guī)則。接收者(Receiver)：傳送消息的預(yù)定對(duì)象。解密 ( Decryption) 算法：接收者對(duì)密文進(jìn)行解密時(shí)所采用的一組規(guī)則。密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密鑰和解密密鑰。截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非受權(quán)者，通過搭線竊聽、電磁竊聽、聲音竊聽等來(lái)竊取機(jī)密信息。密碼分析(Cryptanalysis)：截收者試圖通過分析從

5、截獲的密文推斷出原來(lái)的明文或密鑰。密碼分析員(Cryptanalyst)：從事密碼分析的人。被動(dòng)攻擊(Passive attack)：對(duì)一個(gè)保密系統(tǒng)采取截獲密文進(jìn)行分析的攻擊。主動(dòng)攻擊(Active attack)：非法入侵者(Tamper)、攻擊者(Attacker) 或黑客(Hacker) 主動(dòng)向系統(tǒng)竄擾，采用刪除、增添、重放、偽造等竄改手段向系統(tǒng)注入假消息，達(dá)到利已害人的目的?；靖拍罨靖拍畋Ｃ芟到y(tǒng)模型保密系統(tǒng)模型 保密系統(tǒng)模型保密系統(tǒng)模型 保密系統(tǒng)保密系統(tǒng)(Secrecy Sysetem)：(M, C, K1, K2, Ek1, Dk2 )：1.明文消息空間明文消息空間 M2.密文消

6、息空間密文消息空間 C3.密鑰空間密鑰空間K1和K2：在單鑰體制下K1=K2=K，此時(shí)密鑰 k K 需經(jīng)安全的密鑰信道由發(fā)方傳給收方。4.加密變換：加密變換： Ek1 E， mc=Ek1(m)，其中k1K1，mM, cC 由加密器完成。5.解密變換：解密變換：Dk2D，cm= Dk2(c)，其中k2K2，mM, cC, 由解密器實(shí)現(xiàn)。保密系統(tǒng)應(yīng)當(dāng)滿足下述要求保密系統(tǒng)應(yīng)當(dāng)滿足下述要求l系統(tǒng)即使達(dá)不到理論上是不可破的，即prm=m=0，也應(yīng)當(dāng)為實(shí)際上不可破的。就是說(shuō)，從截獲的密文或某些已知明文密文對(duì)，要決定密鑰或任意明文在計(jì)算上是不可行的。l系統(tǒng)的保密性不依賴于對(duì)加密體制或算法的保密，而依賴于密鑰

7、。這是著名的Kerckhoff原則。l加密和解密算法適用于所有密鑰空間中的元素。l系統(tǒng)便于實(shí)現(xiàn)和使用方便。密碼體制分類密碼體制分類密碼體制有密碼體制有2大類大類：v 單鑰體制單鑰體制(One-key system)：加密密鑰和解密密鑰相同。v 雙鑰體制雙鑰體制(Two-key system)：加密密鑰和解密密鑰不同。單鑰體制主要研究問題單鑰體制主要研究問題：v 密鑰產(chǎn)生(Key generation)v 密鑰管理(Key management)密碼體制分類密碼體制分類 單鑰體制單鑰體制密碼體制分類密碼體制分類 雙鑰體制雙鑰體制 密碼體制分類密碼體制分類 雙鑰認(rèn)證體制雙鑰認(rèn)證體制雙鑰認(rèn)證體制：雙

8、鑰認(rèn)證體制： 用戶A以自己的秘密鑰kA2對(duì)消息m進(jìn)行A的專用變換DkA2，A計(jì)算密文密文 c=DkA2(m)送給用戶B，B驗(yàn)證 m=EkA1（c）=EkA1(DkA2(m) 是否成立？安全性安全性：由于kA2是保密的，其他人都不可能偽造密文密文c，可用A的公開鑰解密時(shí)得到有意義的消息m。因此可以驗(yàn)證消息 m 來(lái)自A而不是其他人，而實(shí)現(xiàn)了對(duì)A所發(fā)消息的認(rèn)證。2 公鑰密碼學(xué) 1976年，Whitfield Diffie和 Martin Hellman 發(fā)表了的“New directions in cryptography”。這篇?jiǎng)潟r(shí)代的文章奠定了公鑰密碼系統(tǒng)的基礎(chǔ)。同時(shí)R. Merkle也獨(dú)立提出

9、了這一體制?？捎糜诒Ｃ芡ㄐ牛部捎糜跀?shù)字簽字。這一體制的出現(xiàn)在密碼學(xué)史上是劃時(shí)代的事件，它為解決計(jì)算機(jī)信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)。自從公鑰密碼的概念被提出以來(lái)，相繼提出了許多公鑰密碼方案，如RSA、背包體制、McEliece、ElGamal體制等。在不斷的研究和實(shí)踐中，有些方案被攻破了，有些方案不太實(shí)用。關(guān)于最初十年的公鑰密碼技術(shù)的研究和發(fā)展，可參見文獻(xiàn)W. Diffie. The first ten years of public-key cryptography. Proceeding of the IEEE, 76(5), 1988, 560-577.。目前只有兩種類型的公鑰

10、系統(tǒng)是安全實(shí)用的，即基于大整數(shù)分解困難問題的密碼體制與基于離散對(duì)數(shù)困難問題的密碼體制。還有一些新的密碼體制正在被研究，如基于辮群的密碼體制、NTRU、量子密碼體制等。 Diffie-Hellman密鑰交換vInput （p，g）， p is a prime， g is a generator of Fp*vOutput a shared element of Fp*.vAlice sends gx mod p to B.Bob sends y mod p to A. vThe shared key is ： Keyx y mod pvDisadvantage：Man in the middle

11、 attackABK = gXaXoOK = gXbXoPKC SchemesvRSA scheme (78) : R.L.Rivest, A.Shamir, L.AdlemanvMcEliecescheme (78)vRabin scheme (79)vKnapsack scheme (79): Merkle-Hellman, Chor-RivestvWilliams scheme (80)vElGamal scheme (85)vElliptic Curve based scheme(85): Koblitz, MillervHidden Field Equations(95): C*,P

12、atarinvLattice Cryptography(97): Ajtai (AD, DDH, NTRU)vNon abelian group Cryptography(2000): BraidvSubgroup Cryptography: GH (99)；LUC(94)；XTR(2000)公鑰密碼學(xué)原理1. 基本概念基本概念 在公鑰密碼系統(tǒng)中，首先要求加密函數(shù)具有單向性單向性，即求逆的困難性求逆的困難性。因此，設(shè)計(jì)雙鑰體制的關(guān)鍵是先要尋求一個(gè)合適的單向函數(shù)。 （1）單向函數(shù)）單向函數(shù) 定義：一個(gè)可逆函數(shù)定義：一個(gè)可逆函數(shù)f：AB，若它滿足：，若它滿足： 1o 對(duì)所有對(duì)所有x A，易于計(jì)算，

13、易于計(jì)算f(x)。 2o 對(duì)對(duì)“幾乎所有幾乎所有x A”由由f(x)求求x“極為困難極為困難”，以至于實(shí)際上不可能做到，以至于實(shí)際上不可能做到，則稱則稱f為一單向?yàn)橐粏蜗?One-way)函數(shù)。函數(shù)。 定義中的“極為困難”是對(duì)現(xiàn)有的計(jì)算資源和算法而言。Massey稱此為視視在困難性在困難性(apparent difficulty)，相應(yīng)函數(shù)稱之為視在單向函數(shù)視在單向函數(shù)。以此來(lái)和本本質(zhì)上質(zhì)上(Essentially)的困難性相區(qū)分 Massey 1985。（2）陷門單向函數(shù)）陷門單向函數(shù) 單向函數(shù)是求逆困難的函數(shù)，而單向陷門函數(shù) (Trapdoor one-way function)，是在不知

14、陷門信息陷門信息下求逆困難的函數(shù)，當(dāng)知道陷門信息后，求逆是易于實(shí)現(xiàn)的。這是Diffie和Hellmam1976引入的有用概念。 但如何給陷門單向函數(shù)下定義則很棘手，因?yàn)?(1) 陷門函數(shù)其實(shí)就不是單向函數(shù)，因?yàn)閱蜗蚝瘮?shù)是在任何條件下求逆 都是困難的； (2) 陷門可能不止一個(gè)，通過試驗(yàn),一個(gè)個(gè)陷門就可容易地找到逆。如果 陷門信息的保密性不強(qiáng)，求逆也就不難。 定義定義: 陷門單向函數(shù)是一類滿足下述條件的單向函數(shù)： fz：AzBz，zZ，Z是陷門信息集。 (1) 對(duì)所有zZ，在給定z下容易找到一對(duì)算法Ez和Dz使對(duì)所有xA，易于計(jì)算fz及其逆，即 fz(x)=Ez(x) ；Dz(fz(x)=x (

15、2) 對(duì)“幾乎”所有zZ，當(dāng)只給定Ez和fz時(shí)，對(duì)“幾乎所有”xAz，“很難”意即“實(shí)際上不可能”從y=fz(x)算出x。 (3) 對(duì)任一z，集Az必須是保密系統(tǒng)中明文集中的一個(gè)“方便”集，即便于實(shí)現(xiàn)明文到它的映射。 (Diffie和Hellman定義的陷門函數(shù)中，Az=A，對(duì)所有Z成立。而實(shí)際中的Az取決于Z)。（3） 用于構(gòu)造雙鑰密碼的陷門單向函數(shù)用于構(gòu)造雙鑰密碼的陷門單向函數(shù) 1976年Diffie和Hellman發(fā)表的文章中雖未給出陷門單向函數(shù)，但大大推動(dòng)了這方面的研究工作。雙鑰密碼體制的研究雙鑰密碼體制的研究在于給出這種函數(shù)的構(gòu)造方法以及它們的安全性在于給出這種函數(shù)的構(gòu)造方法以及它們

16、的安全性。 陷門單向函數(shù)的定義并沒有給出這類函數(shù)是否存在。但他們指出“一個(gè)單鑰密碼體制，如果能抗擊選擇明文攻擊，就可規(guī)定一個(gè)陷門單向函數(shù)”。以其密鑰作為陷門信息，則相應(yīng)的加密函數(shù)就是這類函數(shù)。這是構(gòu)造雙鑰體制的途徑。下面給出一些目前多數(shù)雙鑰體制所用的單向函數(shù)的例子。v大整數(shù)分解大整數(shù)分解。 判斷一個(gè)大奇數(shù)n是否為素?cái)?shù)的有效算法，大約需要的計(jì)算量是lb n4，當(dāng)n為256或512位的二元數(shù)時(shí)，用當(dāng)前計(jì)算機(jī)做可在10分鐘內(nèi)完成。若已知二大素?cái)?shù)p和q，求n=pq只需一次乘法，但若由n，求p和q，則是幾千年來(lái)數(shù)論專家的攻關(guān)對(duì)象。v離散對(duì)數(shù)離散對(duì)數(shù)。給定一大素?cái)?shù)p，p1含另一大素?cái)?shù)因子q?？蓸?gòu)造一乘群Z

17、p*，它是一個(gè)p1階循環(huán)群。其生成元為整數(shù)g，1gp1。已知x，求y=gx mod p容易，只需lb x1次乘法。如x=15=11112，g15=(1g)2g)2g)2g mod p，要用3416次乘法。若已知y, g, p，求x=logg y mod p為離散對(duì)數(shù)問題。最快求解法運(yùn)算次數(shù)漸近值為 p=512時(shí)， 。 )ln(lnln)1 (1exp()(ppoOpL（77256.102)(pL3 公鑰加密體制公鑰加密體制: RSA 密碼體制 1978年，MIT三位年青數(shù)學(xué)家R.L.Rivest，A.Shamir和L.Adleman 發(fā)現(xiàn)了一種用數(shù)論構(gòu)造雙鑰的方法，稱作MIT體制體制，后來(lái)被廣

18、泛稱之為RSA體制體制。它既可用于加密、又可用于數(shù)字簽字，易懂且易于實(shí)現(xiàn)，是目前仍然安全并且逐步被廣泛應(yīng)用的一種體制。國(guó)際上一些標(biāo)準(zhǔn)化組織ISO、ITU、及SWIFT等均已接受RSA體制作為標(biāo)準(zhǔn)。在Internet中所采用的PGP(Pretty Good Privacy)中也將RSA作為傳送會(huì)話密鑰和數(shù)字簽字的標(biāo)準(zhǔn)算法。 RSA密碼體制 1. 方案：獨(dú)立地選取兩大素?cái)?shù)p1和p2(各100200位十進(jìn)制數(shù)字)，計(jì)算 n=p1p2， 其歐拉函數(shù)值 (n)=(p11)(p21)。 隨機(jī)選一整數(shù)e， 1e(n)，(n), e)=1。因而在模(n)下，e有逆元 d=e -1 mod (n)， 取公鑰為n

19、，e。秘密鑰為d。 (p1, p2不再需要，可以銷毀。) 加密：加密：將明文分組，各組在mod n下可惟一地表示(以二元數(shù)字表示，選2的最大冪小于n)。各組長(zhǎng)達(dá)200位十進(jìn)數(shù)字?？捎妹魑募?Az=x：1xn, (x, n)=1 注意，(x, n)1是很危險(xiǎn)的，請(qǐng)思考。 xAz的概率：。11111) 1)(1()(21212121ppppppppnn 密文密文 y=xe mod n解密：解密： x=yd mod n證明：證明：yd=(xe)d=xde，因?yàn)閐e1 mod (n) 而有 de=q(n)1。由歐拉定理， (x, n)=1意味 x(n)1 mod n，故有yd=xde=xq(n)+1x

20、xq(n)=x1=x mod n陷門函數(shù)陷門函數(shù)：Z=(p1, p2, d) 2. RSA的安全性的安全性 （1）分解模數(shù)）分解模數(shù)n。在理論上，RSA的安全性取決于模n分解的困難性，但數(shù)學(xué)上至今還未證明分解模就是攻擊RSA的最佳方法，也未證明分解大整數(shù)就是NP問題，可能有尚未發(fā)現(xiàn)的多項(xiàng)式時(shí)間分解算法。人們完全可以設(shè)想有另外的途徑破譯RSA，如求解密指數(shù)d或找到(p11)(p21)等。但這些途徑都不比分解n來(lái)得容易。甚至Alexi等1988曾揭示，從RSA加密的密文恢復(fù)某些bit的困難性也和恢復(fù)整組明文一樣困難。采用廣義數(shù)域篩分解不同長(zhǎng)度RSA公鑰模所需的計(jì)算機(jī)資源 密鑰長(zhǎng)密鑰長(zhǎng)(bit) 所

21、需的所需的MIPS-年年* 116(Blacknet密鑰密鑰) 400 129 5,000 512 30,000 768 200,000,000 1024 300,000,000,000 2048 300,000,000,000,000,000,000 * MIPS-年指以每秒執(zhí)行1,000,000條指令的計(jì)算機(jī)運(yùn)行一年 當(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ù)，通過Internet

22、網(wǎng)，耗時(shí)8個(gè)月，于1994年4月2日利用二次篩法分解出為64位和65位的兩個(gè)因子，原來(lái)估計(jì)要用4億億年。所給密文的譯文為“這些魔文是容易受驚的魚鷹”。這是有史以來(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) 目前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ì)）的Herman te Riele的帶領(lǐng)下，在對(duì)RSA-155的攻擊中，利用數(shù)域篩法（N

23、FS）成功的分解出了512-bit RSA模的素因子。要分解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也將被攻破。 （2）其它途徑：其它途徑：從n若能求出(n)，則可求得p1, p2，因?yàn)閚(n)1=p1p2(p11)(p21)1=p1p2 而 ，已證明，求(n)等價(jià)于分解n的困難。

24、 從n求d亦等價(jià)于分解n。目前尚不知是否存在一種無(wú)需籍助于分解n攻擊法。也未能證明破譯RSA的任何方法都等價(jià)于大整數(shù)分解問題。 （3）迭代攻擊法：）迭代攻擊法： Simmons和Norris曾提出迭代或循環(huán)攻擊法。例如，給定一RSA的參數(shù)為(n, e, y)=(35, 17, 3)，可由y0=y=3計(jì)算y1=317=33 mod 35。再由y1計(jì)算y2=y117=3 mod 35，從而得到明文x=y1=33 mod 35。一般對(duì)明文x加密多次，直到再現(xiàn)x為止。Rivest證明，當(dāng)p11和p21中含有大素?cái)?shù)因子，且n足夠大時(shí)，這種攻擊法成功的概率趨于0。2124ppnn（4）選擇明文攻擊）選擇明

25、文攻擊 攻擊者收集用戶A以公鑰e加密的密文y=xe mod n，并想分析出消息x。 選隨機(jī)數(shù)rn，計(jì)算y1=re mod n，y2=y1y mod n。現(xiàn)在攻擊者請(qǐng)A對(duì)消息y2進(jìn)行解密得到s=y2d mod n。攻擊者計(jì)算 s/r mod n=x，得到了明文x。（5）公用模攻擊）公用模攻擊 若很多人共用同一模數(shù)n，各自選擇不同的e和d，這樣實(shí)現(xiàn)當(dāng)然簡(jiǎn)單，但是不安全。若消息以兩個(gè)不同的密鑰加密，在共用同一個(gè)模下，若兩個(gè)密鑰互素(一般如此)，則可用任一密鑰恢復(fù)明文。還有兩種攻擊共用模RSA的方法，用概率方法可分解n和用確定性算法可計(jì)算某一用戶密鑰而不需要分解n。 （6）低加密指數(shù)攻擊：低加密指數(shù)攻

26、擊：采用小的e可以加快加密和驗(yàn)證簽字的速度，且所需的存儲(chǔ)密鑰空間小，但若加密鑰e選擇得太小，則容易受到攻擊。令網(wǎng)中三用戶的加密鑰e均選3，而有不同的模n1, n2, n3，若有一用戶將消息x傳給三個(gè)用戶的密文分別為 y1=x3 mod n1 x n1y2=x3 mod n2 x n2y3=x3 mod n3 x n3 一般選n1, n2, n3互素(否則，可求出公因子，而降低安全性)，利用中國(guó)余定理，可從y1, y2, y3求出 y=x3 mod (n1 n2 n3)。 由xn1, xn2, xn3，可得x3 n1 n2, n3，故有 。xy 3 （7）定時(shí)攻擊法：）定時(shí)攻擊法：定時(shí)(Timi

27、ng)攻擊法由P. Kocher提出，利用測(cè)定RSA解密所進(jìn)行的模指數(shù)運(yùn)算的時(shí)間來(lái)估計(jì)解密指數(shù)d，而后再精確定出d 的取值。R. Rivest曾指出，這一攻擊法可以通過將解密運(yùn)算量與參數(shù)d無(wú)關(guān)挫敗。另外還可采用盲化技術(shù)，即先將數(shù)據(jù)進(jìn)行盲化，再進(jìn)行加密運(yùn)算，而后做去盲運(yùn)算。這樣做雖然不能使解密運(yùn)算時(shí)間保持不變，但計(jì)算時(shí)間被隨機(jī)化而難于推測(cè)解密所進(jìn)行的指數(shù)運(yùn)算的時(shí)間。 D. Boneh. Twenty Years of Attacks on the RSA Cryptosystem. Notices of the American Mathematical Society, 46(2):203-2

28、13, 1999. /dabo/abstracts/RSAattack-survey.html3. RSA的參數(shù)選擇。的參數(shù)選擇。 (1) n 的選擇的選擇：n=p1p2，p1與p2必須為強(qiáng)素?cái)?shù)強(qiáng)素?cái)?shù)。 p1與p2之差要大。 p11與 p21的最大公因子要小。 p1與p2 要足夠大，以使 n 分解在計(jì)算上不可行。 (2) e 的選取：的選?。?(e, (n)=1的條件易于滿足，因?yàn)閮蓚€(gè)隨機(jī)數(shù)為互素的概率約為3/5。e小時(shí)，加密速度快，Knuth和Shamir曾建議采用e=3。但e太小存在一些問題。若e小，x小，y=xe mod n，當(dāng)xen，則

29、未取模，由y直接開e次方可求x。易遭低指數(shù)攻擊。 (3) d 的選擇：的選擇： e選定后可用Euclidean算法在多項(xiàng)式時(shí)間內(nèi)求出d。d要大于n1/4。d小，簽字和解密運(yùn)算快，這在IC卡中尤為重要(復(fù)雜的加密和驗(yàn)證簽字可由主機(jī)來(lái)做)。類似于加密下的情況，d不能太小，否則由已知明文攻擊。Wiener給出對(duì)小d的系統(tǒng)攻擊法，證明了當(dāng)d長(zhǎng)度小于n的1/4時(shí)，由連分式算法，可在多項(xiàng)式時(shí)間內(nèi)求出d值。這是否可推廣至1/2還不知道。 4. RSA實(shí)現(xiàn)實(shí)現(xiàn) 由于RSA是簡(jiǎn)單且比較成熟的一種公鑰密碼體制，許多公司及研究團(tuán)體都對(duì)它進(jìn)行了實(shí)現(xiàn)。除RSA公司的產(chǎn)品RSAref以外，主要還有IBM的CCA、Cryp

30、tix、Cryptlib、Crypto+、Cryptolib、Python、SSLava、SSLeay及CRYPTOMAThIC的實(shí)現(xiàn)等。 硬件實(shí)現(xiàn)的速度最快也只為DES的1/1000，512 bit模下的VLSI硬件實(shí)現(xiàn)只達(dá)64 kb/s。計(jì)劃開發(fā)512 bit RSA，達(dá)1 Mb/s的芯片。1 024 bit RSA加密芯片也在開發(fā)中。人們?cè)谂SA體制用于靈巧卡技術(shù)中。 軟件實(shí)現(xiàn)的速度只為DES的軟件實(shí)現(xiàn)的1/100，512 bit RSA的軟件實(shí)現(xiàn)的速率可達(dá)11 kb/s。RSA多用于密鑰交換和認(rèn)證。 如果適當(dāng)選擇RSA的參數(shù)，可以大大加快速度。例如，選e為3、17或65 537(

31、216+1)的二進(jìn)制表示式中都只有兩個(gè)1，大大減少了運(yùn)算量。X. 509建議用65 5371989，PEM建議用3，而PKCS#1建議用65 537，當(dāng)消息后填充隨機(jī)數(shù)字時(shí)，不會(huì)有任何安全問題。 ElGamal 1984,1985 提出一種基于離散對(duì)數(shù)問題的雙鑰密碼體制，既可用于加密，又可用于簽字。本體制基于Zp中有限群上的離散對(duì)數(shù)的困難性。 （1） 方案：方案：令Zp 是一個(gè)有p個(gè)元素的有限域，p是一個(gè)素?cái)?shù)，令g是Zp(Zp中除去0元素)中的一個(gè)本原元或其生成元。明文集M為Zp，密文集C為 ZpZp。 公鑰公鑰：選定g(g p的生成元)，計(jì)算公鑰 g mod p 秘密鑰秘密鑰： p （2）

32、加密：加密：選擇隨機(jī)數(shù)kZp-1，且(k,p1)=1，計(jì)算：y1=g k mod p (隨機(jī)數(shù)k被加密) y2=Mk mod p(明文被隨機(jī)數(shù)k和公鑰加密) M是發(fā)送明文組。密文由y1、y2級(jí)連構(gòu)成，即密文C=y1|y2。 （3）解密）解密：收到密文組C后，計(jì)算 M=y2/y1=M k/gk=Mgk/gk mod pElGamal 加密體制加密體制橢圓曲線密碼體制vEliptic Curve Cryptography ，即ECC是1985年，華盛頓大學(xué)的Neal Koblitz和當(dāng)時(shí)在IBM工作的Victor Miller相互獨(dú)立地提出的，這使得被數(shù)學(xué)家在代數(shù)學(xué)和代數(shù)幾何學(xué)領(lǐng)域研究了150多年

33、的橢圓曲線在密碼領(lǐng)域中得以發(fā)揮重要作用。v由于ECC具有的特性，利用ECC不但可以實(shí)現(xiàn)高度安全性，且在同等安全強(qiáng)度下，可以用較小的開銷(所需的計(jì)算量、存儲(chǔ)量、帶寬、軟件和硬件實(shí)現(xiàn)的規(guī)模等)和時(shí)延(加密和簽字速度高)實(shí)現(xiàn)較高的安全性。v ECC已經(jīng)成為公鑰密碼的主流,成為設(shè)計(jì)大多數(shù)計(jì)算能力和集成電路空間受限(如Smart卡)、帶寬受限又要求高速實(shí)現(xiàn)的安全產(chǎn)品的首選。Elliptic curve group over real numbervy2 = x3 + ax + b, where x, y, a and b are real numbers. vAll (x,y) points satis

34、fying above equation along with infinite point O and addition operation, form a groupvSuppose P=(x,y) then define P=(x,-y)Addition operation: A Geometric ApproachvIf P and Q are distinct, and P -Q, define P+Q as follows:Draw a line through P and Q, then the line will intersect with the curve, the in

35、tersected point is denoted as R, and define P+Q=R.vDefine P + (-P) = OvIf P=(x,0), then P+P = O , (in fact, a vertical line)vOtherwise, draw a tangent line through p, the intersected point is defined as R, then P+P =2P =R.Definition of P+Q = RDefinition of P+P (where y!=0)Definition of P+P (where y=

36、0)Elliptic Curve Addition: An Algebraic ApproachElliptic Curve Groups over Zpy2 mod 23 = x3 + x mod 23橢圓曲線離散對(duì)數(shù)問題（ECDLP） v給定曲線E上階為n的點(diǎn)P，若Q是E上另一個(gè)點(diǎn)，找一個(gè)整數(shù)l, 0 l n 1，使得Q = l P（如果這樣的l 存在）。 vECC就是建立在求解相應(yīng)加法群中ECDLP困難基礎(chǔ)上的。vECDLP的攻擊類似于對(duì)有限域中乘法群的離散對(duì)數(shù)的攻擊,然而，ECDLP不存在亞指數(shù)時(shí)間算法攻擊-指數(shù)計(jì)算法（Index Calculus）。 Key LengthsSymme

37、tricRSA,DH/DSAECC,HashBreakable56512112Adequate801,024161StrongNear term1283,072256Long term25615,360512Don B. Johnson, “ECC, Future Resiliency and High Security Systems”ECC AttacksvPohlig-Hellman AttackvShanks Baby-step, Giant-stepvTame & Wild Kangaroos (Pollard)The tame kangaroo is given a spa

38、de & told to dig a hole every 10 jumpIf both kangaroo are jumping around a field, the wild will fall downvMOV Attack (Menezes, Okamoto, Vanstone)Discovered a reduction of the DLP in Fq to Fqk, for some small integers k, if qk = 1 (mod #E(Fq)the ECDLP can be solved in sub-exponential timeSupersin

39、gular curves(#E(Fq) = q+1-mchar(E) were susceptiblevAnomalous Curve AttacksAnomalous curve is introduced because it resists to MOV attack, Curves where #E(Fq) = qECDLP can be solved by p-adic numbersThey jump to random direction, but assumes the direction will depend on the current pointWhen we choo

40、se curve for ECC, we have to check these conditionsSelecting a CurvevRandon selection : max #E = smax vDraw E at random in Fq - coefficientsvCompute #E(Fq) SEA AlgorithmvCheck MOV & anomalous conditionsvAttempt to factor #E(Fq) in reasonable timevIf #E(Fq) = sr, ssmax, r is prime, then returnvCM

41、(Complex Multiplication) MethodCM : endomorphism : C/L C/L, (z) = czThere is Galois extension Kn = Q(i)(Cn) which is endomorphism by CMGiven n = #E(Fq), determine p and D, then calculate Kn by CMvCurves from Standard : proved, interoperableComputing order is the biggest issue in ECC !ECC Encryption

42、ElGamal Encryption for ECC version: vEncryption: Let (x,y=xP) is a secret/public key pair of the receiver. The sender randomly chooses a number t, the ciphertext for message m is(C1,C2)=(tP, m+t y)vDecryption: m= C2-x C1vDifficulties: 1、Message embedding algorithm; 2、CCA2 attack. vPlease refer to ht

43、tp://wiki/Integrated_Encryption_SchemeECC 標(biāo)準(zhǔn)化v國(guó)外已有用橢圓曲線進(jìn)行加解密的產(chǎn)品出現(xiàn)在市場(chǎng)上。美國(guó)NeXT Computer公司已開發(fā)出快速橢圓曲線加密(FEE)算法，其秘密鑰為容易記憶的字串。加拿大Certicom公司也開發(fā)出了可實(shí)用的橢圓曲線密碼體制的集成電路，可實(shí)現(xiàn)高效加密、數(shù)字簽字、認(rèn)證和密鑰管理等（http:/）。3COM/Palm Computing、Motorala、Verifone、AtallaLorp、terling Commerce、日本Mitsushita及NTT實(shí)驗(yàn)室、法國(guó)Thompson、德

44、國(guó)Siemens、加拿大Waterloo大學(xué)等也都實(shí)現(xiàn)這一體制。這些實(shí)現(xiàn)包括軟件和硬件。v目前，橢圓曲線密碼的標(biāo)準(zhǔn)化過程正在進(jìn)行中，雖然還沒有一種統(tǒng)一的標(biāo)準(zhǔn)方案，但已有一些較為成熟的標(biāo)準(zhǔn)出現(xiàn)。從事標(biāo)準(zhǔn)化的組織中較為突出的有：IEEE（P1363）、ANSI X9F1工作組（X9.42，X9.62和X9.63）、ISO/IEC等。v橢圓曲線密碼體制已被納入IEEE（電氣與電子工程師協(xié)會(huì)）公鑰密碼標(biāo)準(zhǔn)P1363中，包括加密、簽名、密鑰協(xié)議機(jī)制等。2000年2月P1363被批準(zhǔn)作為一個(gè)IEEE標(biāo)準(zhǔn)。公鑰加密方案的安全性v安全性定義：多項(xiàng)式時(shí)間/不可區(qū)分的加密。這個(gè)概念由Goldwasser 等人提出

45、，是指給定密文，攻擊這除了明文長(zhǎng)度的信息之外得不到任何關(guān)于明文的信息。與語(yǔ)義安全（Semantic security）在CPA下是等價(jià)概念。另一個(gè)概念是Non-malleable和IND在CCA2是等價(jià)的。v攻擊類型： 1.選擇明文攻擊（CPA） 2.選擇密文攻擊（CCA1） 3.自適應(yīng)選擇密文攻擊（CCA2）v安全模型：Random Oracle Model；Standard Model4 數(shù)字簽名及其應(yīng)用 公鑰密碼體制為解決計(jì)算機(jī)信息網(wǎng)中的安全提供了新的理論和技術(shù)基礎(chǔ)。公鑰密碼體制的最大特點(diǎn)是采用兩個(gè)密鑰將加密和解密能力分開，使得通信雙方無(wú)需事先交換密鑰就可進(jìn)行保密通信，從而大大減少了多實(shí)體通信網(wǎng)實(shí)體之間通信所需的密鑰量，便于密鑰管理。此外，公鑰體制的一個(gè)重要的特性是可用于實(shí)現(xiàn)數(shù)字簽字。數(shù)字簽名在信息安全，包括身份認(rèn)證、數(shù)據(jù)完整性、不可否認(rèn)性以及匿名性等方面有著重要的應(yīng)用，特別是在大型網(wǎng)絡(luò)安全通信中的密鑰分配、認(rèn)證以及電子商務(wù)系統(tǒng)安全性等方面具有非常重要的作用。 數(shù)字簽名應(yīng)滿足的要求數(shù)字簽名應(yīng)滿足的要求v收方能夠確認(rèn)或證實(shí)發(fā)方的簽名，但不能偽造，簡(jiǎn)記為R1-條件（條件（unforgeablity）。v發(fā)方發(fā)出簽名的消息給收方后，就不能再否認(rèn)他所簽發(fā)的消息，簡(jiǎn)記為S-條件條件(non-repudiation)。v收方對(duì)已收到的簽名消息不