圓錐曲線上的密碼體制安全性淺析

李赫男

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

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

中圖分類號：TN918 文獻標識碼：A 文章編號：1671-7597（2014）13-0156-01

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

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

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

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

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

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

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

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

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

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

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

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

①有限域上的圓錐曲線。

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

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

②Zn上的圓錐曲線。

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

3 總結

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

參考文獻

[1]曹珍富.RSA與改進的RSA的圓錐曲線模擬[J].黑龍江大學學報，自然科學版，1999（4）：15-18.

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

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

233-235.

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

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