基于Koblitz橢圓曲線的公鑰密碼體制實現(xiàn)技術(shù)研究.pdf

1、隨著計算機技術(shù)、網(wǎng)絡(luò)技術(shù)，特別是Intemet技術(shù)的飛速發(fā)展和廣泛普及，人類社會正處于由工業(yè)經(jīng)濟向信息經(jīng)濟的深刻變革之中，信息化已經(jīng)成為當(dāng)今世界經(jīng)濟和社會發(fā)展的倍增器，成為了衡量綜合國力的重要標(biāo)志。目前，各種基于網(wǎng)絡(luò)的應(yīng)用系統(tǒng)層出不窮，如電子政務(wù)和電子商務(wù)等，但由此也帶來了信息安全問題?，F(xiàn)代密碼技術(shù)作為解決信息安全問題的主要手段，其重要性得到了普遍認(rèn)同，對它的理論研究和應(yīng)用研究已成為計算機領(lǐng)域重要的研究方向。 自1949年Sha

2、nnon發(fā)表《保密通信的信息理論》將密碼學(xué)研究納入科學(xué)軌道以來，現(xiàn)代密碼學(xué)基本可分為以DES為代表的對稱密碼學(xué)和以RSA為代表的公鑰密碼學(xué)。由于公鑰密碼體制的非對稱結(jié)構(gòu)，使得它不僅可應(yīng)用于數(shù)據(jù)加密，還可被廣泛地應(yīng)用于身份識別、數(shù)字簽名、密鑰協(xié)商和電子支付等諸多領(lǐng)域，所以自1976年Diffie和Hellman提出公鑰密碼思想以來，就引起了人們的廣泛重視。 目前大多數(shù)被普遍認(rèn)可的公鑰密碼體制的安全性均基于某個數(shù)學(xué)困難問題。根據(jù)所依

3、據(jù)的數(shù)學(xué)難題這些體制主要有三類：基于大整數(shù)分解問題的RSA型公鑰密碼、基于有限域上離散對數(shù)問題的E1Gamal型公鑰密碼和基于橢圓曲線離散對數(shù)問題(ECDLP：Elliptic Curve Discrete Logarithms Problem)的橢圓曲線公鑰密碼(ECC：Elliptic Curve Cryptography)。與其他公鑰密碼體制相比，ECC突出的優(yōu)勢在于：對于其所基于的數(shù)學(xué)難題并不存在亞指數(shù)時間算法，從而能夠以更小的

4、密鑰尺寸滿足相同的安全性要求。通常認(rèn)為，為得到合理的安全性，RSA應(yīng)當(dāng)使用1024比特的模長，而對于ECC來說，只需使用160比特的模長。正是由于ECC密鑰短的特點而受到國際上的廣泛關(guān)注，已經(jīng)對RSA、E1Gamal等公鑰密碼體制形成強勁的挑戰(zhàn)。同時國際上對有關(guān)ECC的標(biāo)準(zhǔn)化也已完成，如美國國家標(biāo)準(zhǔn)與技術(shù)研究所(ANSI)公布的ANSI X9.62和ANSIX9.63、IEEE-P1363制定的公鑰密碼標(biāo)準(zhǔn)?？梢哉f在未來的若干年內(nèi)，EC

5、C將日漸成熟，應(yīng)用領(lǐng)域?qū)⒅鸩缴钊氲叫畔踩母鱾€方面。 快速實現(xiàn)問題是目前ECC研究中的一個重要問題。ECC的實現(xiàn)可分為三個層次來討論：第一層次為數(shù)乘運算，討論如何將數(shù)乘轉(zhuǎn)化為次數(shù)盡可能少的點加和倍點運算；第二層次為群運算，討論如何將點加和倍點在一定的坐標(biāo)系下轉(zhuǎn)化為域運算；第三層次為域運算，主要包括域元素加法、乘法、平方和求逆，因求逆運算可轉(zhuǎn)化為乘法和平方，因而主要的域運算是乘法和平方。綜上所述，實現(xiàn)ECC的核心環(huán)節(jié)是數(shù)乘和域元

6、素乘法與平方運算，因此，提高這三種運算的速度是提高ECC效率的關(guān)鍵。適用于建立ECC的有限域有三類：素域、基域和擴域，目前最常用的有限域是基域，因此對基域域運算進行深入研究具有較高的實用價值?；蛟爻朔ㄓ袃深悓崿F(xiàn)方法，一為多項式基域元素乘法，二為正規(guī)基特別是優(yōu)化正規(guī)基域元素乘法。大量研究表明，多項式基域元素乘法較適合于軟件實現(xiàn)，而因正規(guī)基表示域元素時平方運算僅需一次循環(huán)移位即可完成，但此時乘法運算較為復(fù)雜，因此，努力提高正規(guī)基域元素乘

7、法速度對于實現(xiàn)ECC具有較高的理論和實踐價值。 近年來，國內(nèi)外的密碼學(xué)研究者對基域上實現(xiàn)ECC進行了廣泛研究。這些研究結(jié)果表明，基域上的所有橢圓曲線均可同構(gòu)于y2+xy=x3+a2x2+a6和y2+y=x3+a4x+a6.兩式，后者為超奇異橢圓曲線，不適合密碼學(xué)，只有前式表示的曲線適合于構(gòu)建安全的密碼算法；前式中，當(dāng)a2取0或1及a6取1時所得曲線稱為Koblitz曲線。利用正規(guī)基實現(xiàn)基于Koblitz曲線的數(shù)乘運算時，可首先利

8、用Frobenius映射將整數(shù)k轉(zhuǎn)換成TNAF表示式，然后利用該表示式計算數(shù)乘，由此帶來的好處是無需倍點運算。因此，如何進一步減少整數(shù)k的TNAF表示式長度是提高數(shù)乘運算的關(guān)鍵。 本文對橢圓曲線公鑰密碼體制的實現(xiàn)問題進行了較為深入的研究，重點考察了正規(guī)基表示時的Lambda矩陣快速生成、基域元素乘法算法和基于Koblitz曲線的數(shù)乘算法。 首先，對橢圓曲線公鑰密碼體制的理論基礎(chǔ)做了較為深入的討論，對正規(guī)基域元素乘法中La

9、mbda矩陣生成算法進行了深入剖析，給出了Type I型和Type II型Lambda矩陣的生成算法，并通過詳細(xì)分析Type II型Lambda矩陣的生成過程，提出了一種快速生成算法，該算法將Lambda矩陣的生成速度提高約50％。 其次，深入研究了正規(guī)基域元素乘法運算，給出了優(yōu)化正規(guī)基域元素乘法的一般計算公式，同時通過仔細(xì)分析Rosing算法和Ning-Yin算法，提出了一種優(yōu)化正規(guī)基域元素乘法的改進算法和三種預(yù)計算方法，實驗

10、結(jié)果表明，該改進算法與Ning-Yin算法相比能提高約20％。 再次，深入研究了Koblitz橢圓曲線的性質(zhì)，討論了優(yōu)化正規(guī)基表示域元素對數(shù)乘算法的影響，并討論了數(shù)乘算法的NAF算法和TNAF算法，實現(xiàn)了一種TNAF改進算法，將數(shù)乘運算速度提高了約50％，從而從數(shù)乘層面進一步提高了ECC的實現(xiàn)速度。 最后，將這些算法應(yīng)用于實現(xiàn)ECDSA數(shù)字簽名體制，從實踐角度證明了這些改進算法和實現(xiàn)的可行性，從而從整體上將數(shù)乘的計算速度