橢圓曲線加密算法理論研究

1、1412010年3月刊算法語(yǔ)言信息與電腦China Computer&Communication1.引言橢圓曲線(ECC 理論是代數(shù)幾何、數(shù)論等多個(gè)數(shù)學(xué)分支的一個(gè)交叉點(diǎn),一直被人們認(rèn)為是純理論學(xué)科。而橢圓曲線密碼體制,是基于橢圓曲線離散對(duì)數(shù)問(wèn)題的一種公鑰密碼體制,最早于1985年由Miller 和Koblitz 分別獨(dú)立提出,它是利用有限域上的橢圓曲線有限群代替基于離散對(duì)數(shù)問(wèn)題密碼體制中的有限循環(huán)群所得到的一類密碼體制。在該密碼體制提出的當(dāng)初,由于當(dāng)時(shí)對(duì)數(shù)論研究和運(yùn)算能力不足等原因,人們只是把它當(dāng)做一種理論上的選擇,與當(dāng)時(shí)已趨于成熟的RSA 算法相比,沒(méi)有任何優(yōu)勢(shì)可言。從1989年到1992年

2、間,Atikin 和Elkies 對(duì)其作出重大的改進(jìn),后來(lái)在Couvergnes 、Morain 、Lercier 等人的完善下,到1995年人們已能很容易地計(jì)算出滿足密碼要求的任意橢圓曲線有理點(diǎn)的個(gè)數(shù)了。到今天,橢圓曲線密碼技術(shù)已是密碼學(xué)領(lǐng)域中應(yīng)用相當(dāng)廣泛的加密技術(shù),其應(yīng)用已擴(kuò)散到銀行結(jié)算、電子商務(wù)、通訊領(lǐng)域等。2.橢圓曲線算法介紹2.1橢圓曲線離散對(duì)數(shù)問(wèn)題理論橢圓曲線命名的原因是因?yàn)樗怯扇畏匠堂枋龅?虧格為1的特殊超橢圓曲線,它的計(jì)算類似于計(jì)算一個(gè)橢圓周長(zhǎng)的方程。橢圓曲線是指光滑的Weierstrass 方程所確定的平面曲線。設(shè)方程為:方程中的參數(shù)取自域F 上。F 可以使有理數(shù)域、實(shí)數(shù)

3、域或有限域 。如果,則稱橢圓曲線E 定義在F 上。在這個(gè)點(diǎn)集上按如下規(guī)則定義一個(gè)代數(shù)運(yùn)算,稱為加法,記為“+”(注:這里的“+”代表了很多種運(yùn)算,不只是普通代數(shù)意義上的+,它的操作對(duì)象可能是字符串,乘法標(biāo)量也可能是整數(shù),分?jǐn)?shù),有理數(shù)。設(shè) 兩點(diǎn)為橢圓曲線上任意兩點(diǎn),(1O 是單位元, ;(注:O 可能就是空字符串(2若,則的定義(3若 ;(4 若表示經(jīng)過(guò)P 和Q 點(diǎn)的直線(時(shí)或經(jīng)過(guò)P 切線( 時(shí),則將與曲線交于第三點(diǎn)R ,定義加法規(guī)則滿足正常的加法性質(zhì),比如交換律和結(jié)合律。一個(gè)橢圓曲線上的一個(gè)點(diǎn)P 與一個(gè)正整數(shù)K 相乘的乘法被定義為K 個(gè)P 相加,因 而有 ,等等。通常主要有兩種形式的橢圓曲 線

4、: 域上橢圓曲線和 域(本文不做討論上曲線。上的橢圓曲 線是方程解的集合加上一個(gè)無(wú)窮遠(yuǎn)點(diǎn)O ,記為。其中 。一般研究較多的就是域上 橢圓曲線。設(shè) 是 上的任意兩點(diǎn),是MN 的連線。若M 、N 重合于一點(diǎn),退化為過(guò)M 的切線。設(shè)與曲線相較于另一點(diǎn)R ,它可以通過(guò)代數(shù)方法算出。2.2橢圓曲線離散對(duì)數(shù)問(wèn)題實(shí)例 現(xiàn)令 ,橢圓曲線 ,方程為,即a=b=1,所以根據(jù)條件,滿足一個(gè)摸23橢圓群的條件。 令,那 么(注 :可等價(jià)變換為 因此 。2.3橢圓曲線密碼體制橢圓曲線密碼體制是建立在求橢圓曲線離散對(duì)數(shù)(ECDLP 是困難問(wèn)題的基礎(chǔ)上。橢圓曲線上P 的階是指一個(gè)最小的正整數(shù)n, 滿足。橢圓曲線離散對(duì)數(shù)(E

5、CDLP 是指:給定曲線E 上階為n 的點(diǎn)P , 若是E 上的另一個(gè)點(diǎn),找到一個(gè)整數(shù) m, 使得(如果m 存在。定義 。在過(guò)去的10多年里,橢圓曲線離散對(duì)問(wèn)題受到了眾多數(shù)學(xué)家的極大關(guān)注,目前還沒(méi)有發(fā)現(xiàn)它有哪些明顯的缺點(diǎn)。3.ECC算法3.1橢圓曲線算法初始化選取基域 的橢圓曲線具體給定為確定的形式。在中選一個(gè)階數(shù)很大的點(diǎn) ,它的階數(shù)為一個(gè)大素?cái)?shù)n.用戶執(zhí)行如下計(jì)算生成密鑰:在區(qū)間1,n-1中隨機(jī)選取一個(gè)整數(shù)d. 計(jì)算點(diǎn)(d 個(gè)P 相加。 在橢圓曲線密碼系統(tǒng)中,公開(kāi)的信息是,橢圓曲線的參數(shù)為 ,n 。用戶的私鑰是整數(shù)d ,且是保密的。3.2ECC 加密 將明文分塊并數(shù)字化,每個(gè)數(shù)字化明文快的長(zhǎng)度

6、不大于,然后對(duì)每個(gè)明文快一次進(jìn)行下面的加密變換。 加密變換。選擇 ,計(jì)算點(diǎn) ,計(jì)算點(diǎn),如果 則重新選擇 。計(jì)算 。密文為。3.3ECC 解密解密變換。使用私鑰d 對(duì)密文 計(jì)算:點(diǎn),再計(jì)算 ,于是明文。4.結(jié)束語(yǔ)本文只對(duì)橢圓曲線作了初步的介紹。從當(dāng)前的總體形勢(shì)來(lái)說(shuō),橢圓曲線密碼還主要處于理論研究階段,還有大量的問(wèn)題未被解決,主要體現(xiàn)在 點(diǎn)的選取和大素?cái)?shù)n 的確定,這也是企業(yè)對(duì)橢圓曲線研究的主要方向。參考文獻(xiàn):1超橢圓曲線密碼體制的理論與實(shí)現(xiàn),肖如良 著,經(jīng)濟(jì)管理出版社,20062信息安全技術(shù)導(dǎo)論,陳克菲 黃征 編著,電子工業(yè)出版社,20073近世代數(shù),熊全淹 編著,武漢大學(xué)出版社,20074初等數(shù)論,閔嗣鶴 嚴(yán)士健 編著,高等教育出版社,20065應(yīng)用密碼學(xué),劉嘉勇 編著,清華大學(xué)出版社,2008橢圓曲線加密算法理論研究韓笑峰 哈爾濱學(xué)院 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,黑龍江 哈爾濱 150086摘要:隨著PKI 基礎(chǔ)設(shè)施和公鑰密碼的發(fā)展,基于它們的橢圓曲線加密算法已成為現(xiàn)代信息