李赫男

摘 要 文章對圓錐曲線密碼體制的安全性進(jìn)行分析與總結(jié)，分別給出大整數(shù)分解，圓錐曲線上的離線對數(shù)上安全性問題的淺析。而結(jié)合兩個困難問題的密碼體制也越來越成為當(dāng)今圓錐密碼體制的主要方向。

關(guān)鍵詞 圓錐曲線密碼體制；離散對數(shù)；大數(shù)分解；剩余類環(huán)

中圖分類號：TN918 文獻(xiàn)標(biāo)識碼：A 文章編號：1671-7597（2014）13-0156-01

20世紀(jì)90年代，對基于有限域Fp上的圓錐曲線Cp（a，b）及其在大整數(shù)分解和密碼算法中應(yīng)用的研究，引起人們很大的興趣。近年來，圓錐曲線上的數(shù)字簽名方案的研究有進(jìn)一步發(fā)展。而在圓錐曲線密碼體制安全性上的分析目前還沒有較系統(tǒng)的論述，本文重點(diǎn)分析總結(jié)了了倆類圓錐曲線上的安全性分析。

1 圓錐曲線上大整數(shù)分解困難安全性淺析

基于環(huán)Zn上圓錐曲線的RSA類型的密碼方案的安全基礎(chǔ)主要基于此類困難性問題。對環(huán)Zn上圓錐曲線上此類困難問題的安全性，做以下總結(jié)。

1）環(huán)Zn上圓錐曲線的參數(shù)n的選取方法為n=pq，其中p，q選取為兩個適當(dāng)大的素?cái)?shù)，這保證了n的規(guī)模較大以使對其進(jìn)行因式分解是個困難問題，同時滿足p+1=2r，q+1=2s，并且r，s也為素?cái)?shù)，滿足這樣條件p，q是一種強(qiáng)素?cái)?shù)，這保證了n的分解非常困難。這樣，Zn上圓錐曲線的RSA型加密算法的安全性就建立在大數(shù)分解的困難性。顯然，從公鑰：n，a，b和e，很難得到私鑰d，p，q和Nn。

2）可以抵抗小公鑰指數(shù)攻擊[1]。為了加快加密速率，通常RSA方案中使用小公鑰，不過一般的RSA方案使用小公鑰會使系統(tǒng)變的不安全。攻擊方法有很多，如廣播攻擊，相關(guān)信息攻擊，短填充攻擊等。

對于圓錐曲線上構(gòu)建的RSA方案，取公鑰為3作為例字，則其密文為：P（c）=3P（m），具體計(jì)算出c=m（m2+3a）（3m2+a）-1（mod n）

上面的式子可以化成模n的三次多項(xiàng)式求根，針對這個問題的求解目前都需要分解n，所以在抵抗小公鑰指數(shù)方面，圓錐曲線上的RSA方案有足夠的安全性。

3）針對圓錐曲線上的RSA方案小解密指數(shù)d的攻擊，孫琦等[2][3]人已證明其能抵抗Wiener的攻擊，以及Boneh，Durfee等攻擊。隨后，劉鐸等[4]人提出一種連分?jǐn)?shù)攻擊可以在私鑰過小的情況下，得到私鑰d，并進(jìn)而分解n。該攻擊的私鑰時生效。因此圓錐曲線上的RSA方案私鑰過小的情況下仍然是不安全的。不過，由于在圓錐曲線上的RSA方案對于選取小公鑰有足夠安全，而在選取e為小常數(shù)的時候，由ed=1（mod Nn） 可知d將會很大，因此系統(tǒng)可以在保證安全的同時也很好提高了效率。

2 圓錐曲線離散對數(shù)困難的安全性淺析

1）2000年，戴宗鐸，裴定一，楊君輝等提出了一種在有限域上的廣義圓錐曲線R（a，b），定義了其上的加法，并證明R（a，b）是一個加群以及至少能在擴(kuò)域上構(gòu)造與圓錐曲線群同構(gòu)的普通乘法群。由于有限域上操作數(shù)的長度比有限域上操作數(shù)的長度多了一倍所以其上的離散對數(shù)的困難性比有限域上離散對數(shù)的困難性的安全性是更加困難的。

2）圓錐曲線參數(shù)的選取也影響圓錐曲線的安全性[5]。

由于參數(shù)a參與了加法運(yùn)算，所以其值選取影響圓錐曲線的安全性。

①有限域上的圓錐曲線。

a.在有限域上Fp的圓錐曲線如果a為p的二次剩余，在已知其平方剩余的情況下，可以通過一些數(shù)學(xué)變換構(gòu)造從有限域Fp上的圓錐曲線構(gòu)成的點(diǎn)群到有限域Fp上的普通乘法群的映射，使基于圓錐曲線上的離散對數(shù)安全性降低到普通有限域乘法群上的離散對數(shù)安全性。特別的當(dāng)a為p的二重根時，可以映射到有限域上的普通加法群上，這使圓錐曲線上的離散對數(shù)安全性降低到有限域加法群上的離散對數(shù)安全性，如此便毫無安全性可言，因此此種參數(shù)選取是不可取的。

b.當(dāng)a不是p的二次剩余，若要構(gòu)造相應(yīng)的映射，必需通過擴(kuò)域在規(guī)模至少為有限域Fp2的域上才有可能實(shí)現(xiàn)。而由于有限域Fp2上操作數(shù)的長度比有限域Fp上操作數(shù)的長度多了一倍，此時即使能夠構(gòu)成的相應(yīng)的映射也并未降低原有的圓錐曲線上離散對數(shù)的安全性。

②Zn上的圓錐曲線。

對于剩余類環(huán)上的圓錐曲線，在不知道n的因數(shù)分解的情況下，對于求解二次剩余或平方根的問題都是沒有多項(xiàng)式時間解法的問題，即難解問題。這樣想要構(gòu)造相應(yīng)的映射是困難的，因此參數(shù)a的選取對安全性影響不大。但是為了避免潛在的安全漏洞，仍然取a不是n的二次剩余為宜。具體可取（a/p）=-1，（a/q）=1或（a/p）=1，（a/q）=-1，或（a/p）=-1，（a/q）=-1。同時為了使曲線中的運(yùn)算落在C1，第三種參數(shù)選取為最佳選擇。

3 總結(jié)

通過上述分析，在兩類困難問題的安全性，各有利弊，如果能夠同時結(jié)合兩類困難問題，則將是一種更優(yōu)的選擇。而在Zn的圓錐曲線上可以很方便的構(gòu)建RSA類型的大整數(shù)分解困難問題的密碼，同時還可以結(jié)合其上的離散對數(shù)困難問題，從而構(gòu)建基于雙困難問題的密碼方案，方案只有在兩個困難問題被破解時才能被攻破，這可以有效的提高密碼方案的安全性。因此這也將是圓錐曲線密碼體制今后主流研究方向。

參考文獻(xiàn)

[1]曹珍富.RSA與改進(jìn)的RSA的圓錐曲線模擬[J].黑龍江大學(xué)學(xué)報(bào)，自然科學(xué)版，1999（4）：15-18.

[2]王標(biāo)，朱文余，孫琦.基于剩余類環(huán)Zn上圓錐曲線的公鑰密碼體制[J].四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2005（5）：112-117.

[3]周興旺，曹煒.關(guān)于RSA型公鑰密碼體制與抗小解密指數(shù)攻擊的注記[J].四川大學(xué)學(xué)報(bào)（自然科學(xué)版），2008（4）：

233-235.

[4]劉鐸，戴一奇.對環(huán)Z/nZ上圓錐曲線RSA型公鑰密碼體系的小私鑰d攻擊[J].四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2008（3）：86-89.

[5]徐旭東，靳巖巖，趙磊.圓錐曲線公鑰密碼算法的參數(shù)選擇[J].計(jì)算機(jī)工程，2007（8）：158-159.endprint