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

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

2、間,Atikin 和Elkies 對其作出重大的改進,后來在Couvergnes 、Morain 、Lercier 等人的完善下,到1995年人們已能很容易地計算出滿足密碼要求的任意橢圓曲線有理點的個數(shù)了。到今天,橢圓曲線密碼技術已是密碼學領域中應用相當廣泛的加密技術,其應用已擴散到銀行結算、電子商務、通訊領域等。2.橢圓曲線算法介紹2.1橢圓曲線離散對數(shù)問題理論橢圓曲線命名的原因是因為它是由三次方程描述的(虧格為1的特殊超橢圓曲線,它的計算類似于計算一個橢圓周長的方程。橢圓曲線是指光滑的Weierstrass 方程所確定的平面曲線。設方程為:方程中的參數(shù)取自域F 上。F 可以使有理數(shù)域、實數(shù)

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

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

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

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