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

2、hy）（1976年以前）vBC 487 : 置換密碼Transposition Cipher, “Scytale”vBC 300 : 隱匿術(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”擴散密碼學的歷史現(xiàn)代密碼學（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的標準算法）加密( Encryption) 算法： 密碼員對明文進行加密時所采用的一組規(guī)則。接收者(Receiver)：傳送消息的預定對象。解密 ( Decryption) 算法：接收者對密文進行解密時所采用的一組規(guī)則。密鑰(Key)：控制加密和解密算法操作的數(shù)據(jù)處理，分別稱作加密密鑰和解密密鑰。截收者(Eavesdropper)：在信息傳輸和處理系統(tǒng)中的非受權者，通過搭線竊聽、電磁竊聽、聲音竊聽等來竊取機密信息。密碼分析(Cryptanalysis)：截收者試圖通過分析從

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

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

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

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

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

10、，即基于大整數(shù)分解困難問題的密碼體制與基于離散對數(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 attackA

11、BK = 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*,PatarinvL

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

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

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

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

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

17、1階循環(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為離散對數(shù)問題。最快求解法運算次數(shù)漸近值為 p=512時， 。 )ln(lnln)1 (1exp()(ppoOpL（77256.102)(pL3 公鑰加密體制公鑰加密體制: RSA 密碼體制 1978年，MIT三位年青數(shù)學家R.L.Rivest，A.Shamir和L.Adleman 發(fā)現(xiàn)了一種用數(shù)論構造雙鑰的方法，稱作MIT體制體制，后來被廣泛稱之為RSA體

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

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

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

21、S-年年* 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條指令的計算機運行一年 當前的技術進展使分解算法和計算能力在不斷提高，計算所需的硬件費用在不斷下降。 RSA-129： 110位十進制數(shù)字早已能分解。Rivest等最初懸賞$100的RSA-129，已由包括五大洲43個國家600多人參加，用1600臺機子同時產(chǎn)生820條指令數(shù)據(jù)，通過Internet網(wǎng)，耗時8個月，

22、于1994年4月2日利用二次篩法分解出為64位和65位的兩個因子，原來估計要用4億億年。所給密文的譯文為“這些魔文是容易受驚的魚鷹”。這是有史以來最大規(guī)模的數(shù)學運算。 RSA-130于1996年4月10日利用數(shù)域篩法分解出來。 RSA-140于1999年2月分解出來。 RSA-155(512bit)于1999年8月分解出來 目前RSA的攻擊現(xiàn)狀是有關RSA-155分解分解，其具體情況是1999年8月22日，來自六個不同國家的科學家們在CWI（CWI是在荷蘭的一個數(shù)學和計算機科學的國家研究學會）的Herman te Riele的帶領下，在對RSA-155的攻擊中，利用數(shù)域篩法（NFS）成功的分解

23、出了512-bit RSA模的素因子。要分解RSA-155所需的CPU時間大約為8400MIPS年（MIPS-年指以每秒執(zhí)行1000000條指令的計算機運行一年），這大約為分解RSA-140所需時間的4倍。分解RSA-155總共用了7個月的時間。 密碼分析者估計在3年內(nèi)分解RSA-155所用到的算法和計算技術至少在科技界將會得到普及，因此RSA-155將不再安全。并且人們預計，在十年內(nèi)RSA-232也將被攻破。 （2）其它途徑：）其它途徑：從n若能求出(n)，則可求得p1, p2，因為n(n)1=p1p2(p11)(p21)1=p1p2 而 ，已證明，求(n)等價于分解n的困難。 從n求d亦等

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

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

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

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

28、99. /dabo/abstracts/RSAattack-survey.html3. RSA的參數(shù)選擇。的參數(shù)選擇。 (1) n 的選擇的選擇：n=p1p2，p1與p2必須為強素數(shù)強素數(shù)。 p1與p2之差要大。 p11與 p21的最大公因子要小。 p1與p2 要足夠大，以使 n 分解在計算上不可行。 (2) e 的選?。旱倪x?。?(e, (n)=1的條件易于滿足，因為兩個隨機數(shù)為互素的概率約為3/5。e小時，加密速度快，Knuth和Shamir曾建議采用e=3。但e太小存在一些問題。若e小，x小，y=xe mod n，當xen，則未取模，由y

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

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

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

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

33、密碼領域中得以發(fā)揮重要作用。v由于ECC具有的特性，利用ECC不但可以實現(xiàn)高度安全性，且在同等安全強度下，可以用較小的開銷(所需的計算量、存儲量、帶寬、軟件和硬件實現(xiàn)的規(guī)模等)和時延(加密和簽字速度高)實現(xiàn)較高的安全性。v ECC已經(jīng)成為公鑰密碼的主流,成為設計大多數(shù)計算能力和集成電路空間受限(如Smart卡)、帶寬受限又要求高速實現(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 satisfying

34、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 intersec

35、ted 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=0)Elli

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

37、A,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 spade &am

38、p; 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 timeSupersingular

39、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 choose cur

40、ve 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(Compl

41、ex 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 ElGama

42、l 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 http:/en

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

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

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