椭圆曲线密码系统软体实现技术之探讨new

《椭圆曲线密码系统软体实现技术之探讨new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、文章分類由編輯部依內容編訂CommunicationsoftheCCISAVol.11No.1January2005橢圓曲線密碼系統軟體實現技術之探討楊中皇國立高雄師範大學資訊教育研究所chyang@computer.org摘要橢圓曲線密碼系統(ECC)近年來已被廣泛地制訂於國際標準。在相同的安全強度下，ECC的密碼學參數可遠較諸如RSA的其他公開金鑰密碼系統為小，這使得ECC非常適合在例如智慧卡或行動裝置的有限資源環境下使用。但是ECC的實現較目前國內常用的RSA或Diffie-Hellman密碼系

2、統複雜。本文以橢圓曲線數位簽章演算法ECDSA為例，探討如何以Mathematica工具及C語言快速開發與測試橢圓曲線密碼系統相關軟體。關鍵詞：密碼學，橢圓曲線，數位簽章。壹、前言密碼學技術是目前所知唯一能有效地在不安全的網路上安全傳遞訊息的工具，而橢圓曲線密碼系統（ellipticcurvecryptosystem，ECC）[8][12]則是在西元1985年由Koblitz與Miler各別提出的一種新的密碼學技術，且ECC近年來已被廣泛地制訂於國際標準如ISO11770-3、ANSIX9.62、IE

3、EEP1363、FIPS186-2等。橢圓曲線的技術不只可用在加解密、數位簽章、金鑰交換等，也可用於大數分解(factorization)與質數判斷(primalitytesting)，如圖一。在相同的安全強度下，ECC的密碼學金鑰長度可遠較諸如RSA的其他密碼系統為小且速度較快，這使得ECC非常適合在例如智慧卡或無線行動裝置的有限資源環境下使用。圖一：橢圓曲線於密碼學的應用1文章分類由編輯部依內容編訂CommunicationsoftheCCISAVol.11No.1January2005ECC在具

4、體實現方面有許多瓶頸，遠較目前國內常用的RSA或Diffie-Hellman複雜。但是也由於ECC與傳統的公開金鑰密碼系統(RSA或Diffie-Hellman等)比較時具有執行效率上的優勢，所以目前ECC已廣被採納，甚至美國國防部的可當成智慧卡或PKI/KMI符記(token)[5]也採納ECC。在相同的安全強度下，ECC的金鑰長度與RSA的金鑰長度比較[10]，如下表所示。從表一中可見ECC的金鑰長度或數位簽章的長度遠比RSA小。隨著加解密演算法由128DES/Triple-DES改進為AES，且

5、128位元金鑰到256位元金鑰AES的安全性為2至2562，相同安全性的RSA金鑰長度需3072位元到15360位元，但ECC僅需256位元到512位元。若RSA或ECC是用做金鑰交換來保護256位元金鑰的AES時，RSA應該用15360位元的公開金鑰，而對應的ECC僅需使用512位元金鑰。所以無論從增快執行速度或節省空間的角度，我們可見ECC是優於RSA。表一：相同安全性時RSA與ECC金鑰長度比較[10]安全性8011212819225622222演算法RSA長度(位元)1024204830727

6、68015360ECC長度(位元)161224256384512金鑰長度比6:19:112:120:130:1232橢圓曲線的通用格式為y+a1xy+a3y=x+a2x+a4x+a6。用於密碼學技術的橢圓曲線是由滿足上述方程式的所有點(x,y)及一個無限遠點(pointatinfinity)O所形成的集合，其中座標x與y屬於某個有限體(finitefield)。目前軟硬體具體實現的橢圓曲線n有限體為質數體(primefield，GF(p))、二元體(binaryfield，GF(2))、最佳擴展體n(

7、optimalextensionfield，GF(p))[2]等三種。橢圓曲線上的點可進行兩點間之加法[8][12]。幾何上，如果要計算相異兩點P與Q的和，則我們先找出通過這兩點的直線，然後找出這條直線與橢圓曲線相交的第三點，再將此點對x軸做鏡射得到和。如果橢圓曲線上的某三點共線的話，三點相加之和就是O。若P=(x1,y1)與Q=(x2,y2)為橢圓曲線上的任意兩點，但P∫O∫Q，且選取質數體23(此時橢圓曲線方程式為y=x+ax+b)，則我們有下列兩點加法的運算規則：1.P+O=O+P=P2.(x1

8、,y1)+(x1,-y1)=P+(-P)=O3.P+Q=R=(x3,y3),2文章分類由編輯部依內容編訂CommunicationsoftheCCISAVol.11No.1January2005y2-y1ifP¹Q2x-x(1)x3=l-x1-x2,y3=l(x1-x3)-y1,l=2123x+a1ifP=Q2y1232如果我們選擇二元體，那麼橢圓曲線方程式為y+xy=x+ax+b，上述的加法規則3須改為P+Q=R=(x3,y3),2l+