密碼學(xué)可以認為是數(shù)學(xué)的一個分支，它是密碼編碼學(xué)和密碼分析學(xué)的總稱。通常主要用于保護通信雙方實施安全的信息傳遞，且不被非授權(quán)的第三方知道。密碼學(xué)的發(fā)展經(jīng)歷了三個階段：手工加密技術(shù)、經(jīng)典加密技術(shù)、現(xiàn)代計算機加密技術(shù)[1]。當(dāng)前的密碼技術(shù)和理論都是基于以算法復(fù)雜性理論為特征的現(xiàn)代密碼學(xué)。

　　摘要：現(xiàn)代密碼學(xué)協(xié)議的安全性多數(shù)是建立在數(shù)學(xué)難題基礎(chǔ)之上，比如：大整數(shù)因子分解、有限域上的離散對數(shù)問題。通常情況下，這些算法不存在多項式時間問題，但隨著攻擊算法地不斷改進，要求使用這些安全協(xié)議的算法密鑰不斷的加大，才得保證其使用的安全性。但密鑰的加大增加了算法的復(fù)雜性，因此，找到一種能抵抗各種常見攻算法，運算量小，速度快的離散對數(shù)密碼算法非常重要，橢圓曲線密碼算法正好滿足這種需要。論文回顧了常用公鑰密碼體制協(xié)議，相對于目前應(yīng)用的其它密碼體制，橢圓曲線密碼體制有很大的優(yōu)勢，最后，分析了橢圓曲線密碼體制在實際應(yīng)用中可能受到的各種攻擊算法。

　　關(guān)鍵詞：橢圓曲線密碼體制,對稱密碼體制,非對稱密碼體制

　　Shannon在1949年發(fā)表的“TheCommunicationTheoryofSecrecySystem”奠定了密碼學(xué)的理論基礎(chǔ)，并使之成為一門獨立的科學(xué)。1976年，Diffie&Hellman發(fā)表的“NewDirectionofTheCryptography”首次提出了公鑰密碼學(xué)的基本思想，開創(chuàng)了公鑰密碼學(xué)的新紀(jì)元[2]。

　　當(dāng)前通用的密碼體制一般基于以下三類數(shù)學(xué)難題：

　　1）基于大整數(shù)因子分解。1978年，麻省理工學(xué)院Rivest、Shamir、Adlman三位學(xué)者首次發(fā)表的RSA公鑰密碼體制就是基于此的一種公鑰密碼體系，簡稱RSA算法。

　　2）基于有限域上離散對數(shù)。最著名的有ElGamal、DSA數(shù)字簽名算法。

　　3）基于橢圓曲線離散對數(shù)�；�于橢圓曲線有限加法群上的橢圓曲線離散對數(shù)問題的求解困難性，同其他公鑰密碼體制相比較，在相同安全強度下，橢圓曲線密碼系統(tǒng)具有密鑰短、占用空間和帶寬小、處理速度快等優(yōu)勢�；�于橢圓曲線建立的密碼體制還有兩大優(yōu)點：一是可用于構(gòu)造有限點群的橢圓曲線數(shù)量多；二是計算橢圓曲線有限點群的離散對數(shù)亞指數(shù)算法不存在，解密算法難度很大，安全性高。

　　1公鑰密碼算法相關(guān)研究

　　由于對稱密碼算法在密鑰管理、分發(fā)和數(shù)字簽名方面的缺陷，1976年W.Diffie和M.Hellman提出了一種巧妙的密鑰交換協(xié)議，稱為Diffie-Hellman密鑰交換協(xié)議/算法[8]，比如Alice和Bob希望通過公共通信網(wǎng)協(xié)商一個會話密鑰，只需要以下操作過程：

　　這種算法是安全的，對于竊聽者Charlie，他只能得到gamodp或者gbmodp，如果他想構(gòu)造出gabmodp，這便屬于一個離散對數(shù)問題，我們知道目前這還是一個數(shù)學(xué)難題。

　　在公鑰密碼系統(tǒng)中，每位計算機網(wǎng)絡(luò)的通信者都應(yīng)該擁有兩個密鑰，其中一個是對外保密的“私鑰”，另一個是對網(wǎng)絡(luò)上所有人公開的“公鑰”。私鑰和公鑰都可以對信息加密，但私鑰加密的信息須用對應(yīng)的公鑰解開，公鑰加密則須用對應(yīng)的私鑰解開。使用公鑰密碼系統(tǒng)，網(wǎng)絡(luò)上的雙方無需事先傳遞密鑰就能進行保密通信[11]。

　　首個公鑰密碼系統(tǒng)由形Rivest、Shamir和Adleman在1978年提出來，簡稱為RSA公鑰密碼[9]，RSA的安全性是基于大整數(shù)因子分解難題。目前，國內(nèi)外大多數(shù)使用公鑰密碼進行加密、解密和數(shù)字簽名/驗證的產(chǎn)品都是基于RSA密碼體系。RSA密碼體系的安全性完全依賴于大整數(shù)因子分解問題，隨著解決因子分解方法的進步及完善、計算機運算速度的不斷提高和計算機網(wǎng)絡(luò)的發(fā)展，RSA密碼的安全性受到了前所未有的挑戰(zhàn)，人們必須選擇更大的整數(shù)，以增加破解的難度。目前，安全的RSA密碼需要的大整數(shù)都在1024位以上的二進制長度，造成了RSA密碼實現(xiàn)的代價變得越來越難以任受，導(dǎo)致了RSA應(yīng)用的效率越來越低，成為RSA應(yīng)用的主要瓶頸。

　　第二個著名的公鑰密碼是EGamal密碼[10]，它的安全性依賴于離散對數(shù)問題。假設(shè)G為一個有限乘法循環(huán)群，g為G的生成元，x為任意的整數(shù)，如果已知g及gx，如何求解x的問題在數(shù)學(xué)上稱為離散對數(shù)問題。在當(dāng)前環(huán)境下，當(dāng)群G選擇適當(dāng)，且整數(shù)x充分大時，求解是非常困難的，現(xiàn)己知最快的求解數(shù)域上離散對數(shù)的方法是亞指數(shù)級時間復(fù)雜度。

　　第三個著名的公鑰密碼是基于有限域上橢圓曲線加法群的離散對數(shù)問題，它是華盛頓大學(xué)的NealKoblitz[4]和在IBM工作的VictorMiller[5]各自獨立地提出來的，這使得研究了150多年的橢圓曲線在密碼領(lǐng)域中得以發(fā)揮重要作用。橢圓曲線密碼體制（EllipticCurvesCryptography，ECC）的數(shù)學(xué)基礎(chǔ)是橢圓曲線上的點構(gòu)成的Abel加法群中離散對數(shù)的計算困難性�？梢宰C明基于有限域上ECDLP的困難性要高于一般乘法群上的離散對數(shù)問題的困難性，而且橢圓曲線域的運算位數(shù)遠小于傳統(tǒng)離散對數(shù)，且很容易使用軟件或硬件在計算機上進行實現(xiàn)。同時，利用ECC實現(xiàn)速度非常快，在同等安全強度下，ECC所需的計算量、存儲量、帶寬、開銷都較小，且加密和簽名的速度高。因此，ECC特別適用于計算能力、帶寬和集成空間受限的地方，比如Smart卡。由于ECC具有其他公鑰密碼體制無法替代的優(yōu)點，ECC從提出就得了到廣泛關(guān)注，而且被認為是下一代最通用的公鑰密碼系統(tǒng)。

　　2橢圓曲線基本理論

　　2.1橢圓曲線定義

　　橢圓曲線是一門古老且內(nèi)容豐富的數(shù)學(xué)分支，1985年，VictorMiller和NealKoblitz各自獨立地提出橢圓曲線公鑰密碼學(xué)，它的基本思想仍然是基于有限域乘法群的公鑰密碼體制，用有限域上橢圓曲線構(gòu)成的群來類比有限域的乘法群，從而獲得類似的公鑰密碼體制。ECC的安全性是基于橢圓曲線離散對數(shù)問題的難解性，經(jīng)證明它目前還沒有亞指數(shù)攻擊方法，所以，ECC具有一些其它公鑰密碼體制無法比擬的優(yōu)點。橢圓曲線并非我們通常意義上的橢圓，這樣命名的原因是因為對橢圓曲線的研究來源于橢圓周長計算問題，以及所描述的橢圓積分等問題，這里[E（x）]是[x]的三次或四次多項式。

　　2.2橢圓曲線上點的加法規(guī)則

　　以上加法規(guī)則在復(fù)數(shù)、實數(shù)、有理數(shù)和有限域[GF（p）]上均有效。值得指出的是，對于有限域[GF（p）]的情形，上述加法規(guī)則得到的應(yīng)是[modp]的結(jié)果。對于有限域[GF（2m）]，由于所用橢圓曲線形式發(fā)生變化，因此上述加法規(guī)則應(yīng)做相應(yīng)修改，這方面可參考相關(guān)資料。

　　2.3橢圓曲線分類

　　3橢圓曲線在密碼學(xué)中的應(yīng)用

　　3.1橢圓曲線密碼體制的建立[7]

　　首先選取一個基域[Fq]，它可以是一個素域，也可以是一個特征為2的域[F2m]（[m]為素數(shù)）。其次在[Fq]上選取一條橢圓曲線[E]，并使其群階為一個大素數(shù)[N]，或者是一個大素數(shù)與一個小整數(shù)的乘積。然后選取[E]上的一個階為大素數(shù)的[n]的點[P]。有限域[Fq]、曲線[E]、點[P]和其階[N]均為公開的信息。

　　3.2橢圓曲線密鑰對的生成

　　每一個參與者需要完成下述過程：

　　3.3橢圓曲線加密方案

　　現(xiàn)在假設(shè)Alice要向Bob發(fā)送信息，則Alice加密過程如下：

　　3.4橢圓曲線簽名方案（ECDSA）

　　我們給出基于橢圓曲線的數(shù)字簽名方案，稱為ECDSA。

　　ECDSA簽名生成：設(shè)Alice要對信息M簽名后，傳送給Bob，則Alice要完成以下步驟：

　　3.5橢圓曲線密鑰生成協(xié)議（ECKEP）

　　這里給出一個基于橢圓曲線的密鑰協(xié)議：

　　由于ECC的安全性和優(yōu)勢非常明顯，再加上許多標(biāo)著名組織在橢圓曲線密碼算法標(biāo)準(zhǔn)化方面做了大量工作，在1998年ECC被確定為ISO/IEC數(shù)字簽名標(biāo)準(zhǔn)，1999年橢圓曲線數(shù)字簽名算法被ANSI確定為數(shù)字簽名標(biāo)準(zhǔn)。

　　3.6橢圓曲線密碼體制分析

　　同以往的公鑰密碼體制相比較，橢圓曲線密碼體制有以下三個方面的優(yōu)點[2]。

　　1）安全性高

　　目前，針對有限域上的離散對數(shù)問題攻擊的最快算法是指數(shù)積分法，其運算復(fù)雜度為：

　　而攻擊橢圓曲線上的離散對數(shù)問題的常用算法為大步小步算法，它的復(fù)雜度為：

　　2）密碼長度更小

　　對以上兩種攻擊密碼算法的復(fù)雜度進行比較，可知在同等安全性能下，橢圓曲線密碼體制算法需要的密鑰長度遠小于有限域上離散對數(shù)問題的公鑰密碼長度，因此，橢圓曲線密碼體制更適合于存儲空間有限、帶寬小、運算速度高的環(huán)境中。

　　3）算法靈活性更好

　　通常情況下，如果有限域[GF（p）]確定，那么其上的循環(huán)群也就確定了，但有限域上的橢圓曲線卻可以通過改變曲線參數(shù)而進行隨機變化，相應(yīng)地生成不同的循環(huán)群，從而導(dǎo)致橢圓曲線有著豐富的結(jié)構(gòu)和多種選擇，與RSA/DSA相比較，在安全性同等的條件下，橢圓曲線密鑰長度更小，靈活性也高。

　　4結(jié)論

　　自公鑰密碼體系被提出來，都是以某一含有“陷門”的數(shù)學(xué)難題作為其安全性基礎(chǔ)的，各種橢圓曲線公鑰密碼體系的安全性都與相應(yīng)的橢圓曲線離散對數(shù)問題的求解困難性等價。如果離散對數(shù)可以計算，那么從一個用戶的公鑰就可以推導(dǎo)出相應(yīng)的私鑰，這樣系統(tǒng)就不安全了。目前，有許多針對橢圓曲線離散對數(shù)的攻擊算法，主要有以下幾類：針對一般離散對數(shù)問題的攻擊算法，比如大步小步算法和Pollard-p算法；針對特殊橢圓曲線的攻擊算法，如針對超奇異型橢圓曲線的MOV類演化算法，還有針對畸異型橢圓曲線的SSAS多項式時間算法等。

　　從以上分析可知，只要選取的橢圓曲線能抵抗上述幾種常見的攻擊算法，即選取一條安全的橢圓曲線，那么橢圓曲線密碼的安全性是可以保證的，但如何才能選取一條安全的橢圓曲線，這是一個深刻的數(shù)學(xué)難題，有待于相關(guān)領(lǐng)域的深入研究�？傊�，我們在給橢圓曲線選擇參數(shù)時應(yīng)該謹(jǐn)慎，為避免安全隱患，所選擇的橢圓曲線上的離散對數(shù)問題必須能夠抵抗上述的所有攻擊。

　　參考文獻：

　　[1]郭海民，白永祥.數(shù)論在密碼學(xué)中的應(yīng)用[J].電腦知識與技術(shù)，2010（6）.

　　[2]WilliamStallings.CryptographyandNetworkSecurity–PrinciplesandPractice，F(xiàn)ifthEdition[M].PublishHouseofElectronicsIndustry，2011.

　　[3]胡向東，魏琴芳，等.應(yīng)用密碼學(xué)[M].2版.北京：電子工業(yè)出版社，2011.

---

轉(zhuǎn)載請注明來自：http://www.jinnzone.com/jisuanjiyingyonglw/28951.html