有限域切比雪夫多項式算法性能測試與分析

劉亮

(中央電視臺新聞制作部，北京100859)

在L.Kocarev和Z.Tasev首次利用切比雪夫多項式的混沌特性構(gòu)造了一種公鑰加密算法［1］后，很快 Pina Bergamo 等就對其進(jìn)行了破解［2］。文獻(xiàn)［3］通過將切比雪夫多項式擴(kuò)展到有限域上，使得文獻(xiàn)［2］的攻擊方式對其無效，并進(jìn)一步提出了具體的公鑰算法。文獻(xiàn)［4］通過理論證明和實驗分析，解決了文獻(xiàn)［3］中忽略的切比雪夫多項式在有限域上仍然可能存在破解方法［5-6］，指出有限域切比雪夫多項式作為公鑰加密體系的基礎(chǔ)是可行的。

本文對文獻(xiàn)［3］所提出的密鑰協(xié)商、公鑰加密和數(shù)字簽名算法做了具體的編程實現(xiàn)，并對其計算性能進(jìn)行了精確的測量。然后，結(jié)合有限域切比雪夫多項式的性質(zhì)對實驗數(shù)據(jù)進(jìn)行分析，并選擇一定的比較策略和相應(yīng)的安全參數(shù)，將之與公鑰體系中常用的RSA、ELGAMAL和ECC算法性能進(jìn)行比較。發(fā)現(xiàn)有限域切比雪夫多項式算法具有加密簡單，計算量小，處理速度快，存儲空間占用小和所需帶寬小的優(yōu)勢，更加適合于帶寬有限的無線公鑰加密系統(tǒng)。

1 有限域切比雪夫多項式的矩陣迭代算法及其計算量

有限域切比雪夫多項式算法的迭代形式如下:

其中 n∈Z，變量 x∈ZP，多項式 Tn(x):ZP→ZP。

在編程實驗中，采用矩陣迭代方法，利用系數(shù)矩陣的累乘簡化了代數(shù)多項式的迭代計算的復(fù)雜性，關(guān)系式如下:

其中，k是n轉(zhuǎn)換成二進(jìn)制表示時的總位數(shù);h是n轉(zhuǎn)換成二進(jìn)制表示時1的總個數(shù)，即漢明距。又因為0＜h＜k，所以有如下計算量關(guān)系:

其中，式(3)是在已知比特位數(shù)n和漢明距h的情況下的精確的次數(shù)，而式(6)是在只知道比特位數(shù)n而不知道漢明距h的情況下的估算次數(shù)。

2 測試參數(shù)的選擇

2.1 安全參數(shù)的選擇

現(xiàn)有公鑰體系中常用的非對稱加密算法主要分為三類:

1)大整數(shù)分解難題(integer factorization problem，IFP):如 RSA;

2)離散對數(shù)難題(discrete logarithm problem，DLP):如 ElGamal，DSA;

3)橢圓曲線離散對數(shù)難題(elliptic curve discrete logarithm problem，ECDLP):如 EC ElGamal，ECDSA。

而一個系統(tǒng)的安全性主要取決于它自身算法的幾個安全參數(shù)，比如:RSA的安全參數(shù)是它的模N。DLP的安全參數(shù)有兩個，一個是它的群生成元p，一個是它的子群生成元q，它們都是素數(shù);ECDLP的安全參數(shù)是它的橢圓曲線點所組成的加法群的生成元n。這些安全參數(shù)是相應(yīng)算法的安全保障，同時它也是破解的主要對象。安全度相同時，三者的安全參數(shù)滿足關(guān)系如下:

其中，|n|表示其中參數(shù)的比特長度，k是對稱加密算法的密鑰長度。表1給出了相同安全度下，這三種加密算法安全參數(shù)的比特長度。

表1 安全參數(shù)的比特長度

有限域切比雪夫多項式的安全度是由生成域Zp決定的。因此，素數(shù)P就是有限域切比雪夫多項式加密系統(tǒng)的安全參數(shù)，對應(yīng)著RSA的N和Elgamal的p。又由于目前只有窮舉搜索可以有效地破解基于有限域切比雪夫多項式的加密體系，因此，它的安全度可以類比于對稱密鑰加密算法。于是，對應(yīng)表1中安全參數(shù)的比特位數(shù)，選擇一系列測試域(P)進(jìn)行實驗，如表2所示。

表2 測試域P的選取

續(xù)表

2.2 公鑰x和私鑰n的選擇

由于性能測試主要針對有限域切比雪夫多項式常規(guī)算法的密鑰生成時間、加/解密時間、簽名和驗證簽名時間以及密鑰協(xié)商時間，因此，可以不考慮有限域切比雪夫多項式中易破解的特殊點［4］，而在域內(nèi)隨機(jī)選擇x和n。

另外，由于x的值對計算時間影響很小，可以忽略不計，而n的取值卻對計算時間有較大影響。因此，在具體測試中，將根據(jù)實驗不同的側(cè)重點對n做一定的設(shè)置或限制。

3 測試方案及測試結(jié)果

3.1 單次矩陣乘法時間

實驗中，將不同域下一次系數(shù)矩陣乘法的時間作為標(biāo)準(zhǔn)單位，以獲得較精確的算法性能。具體測試時，首先選擇一個域(即P)，接著隨機(jī)生成一個x，然后選取一個n值。采用式(3)計算乘法次數(shù)。同時，設(shè)ni=1(i=0…k)，即n轉(zhuǎn)換為二進(jìn)制后的各位全為1。這樣，乘法次數(shù)就達(dá)到最大，為2(k+1)，測試精度也就達(dá)到最高。需要注意的是，對不同的域，要選取不同的n，使得n較接近P，以達(dá)到較好的效果。

由于在具體的實驗中采用的是一般的PC機(jī)(奔騰 4代 CPU，主頻 2.5GHz，256M 內(nèi)存)，WIN2000 SERVER的操作系統(tǒng)和VC6的編譯環(huán)境結(jié)合GNU大數(shù)運算庫，因此整個實驗環(huán)境的精度就不太高。所以，在每個域，對同一個n值測量10次，每次隨機(jī)生成x，以獲得現(xiàn)有條件基礎(chǔ)上較理想的測試結(jié)果。同時還對每一次乘法反復(fù)測量1000次，以減小系統(tǒng)時間的分辨率低，而每次計算的時間短對測試結(jié)果精度的影響。由此，便形成了兩個循環(huán)嵌套，將兩個循環(huán)的時間累加，然后在循環(huán)外做一次除法，便得到較高精度的某一域中一次矩陣乘法所用的時間。再對不同的域重復(fù)上述算法，得到不同域的單次矩陣乘法所用的時間。如表3所示，其中，P的取值同表2對應(yīng)。

表3 不同域下單次矩陣乘法時間

3.2 密鑰生成和加、解密時間

這里，不需要準(zhǔn)確的知道n轉(zhuǎn)換成二進(jìn)制表示后的漢明距，而只需要知道n的位數(shù)，然后利用式(6)估算出平均矩陣乘法次數(shù)，再用測量到的時間除以平均矩陣乘法次數(shù)得到的時間與表3中不同域下單次矩陣乘法時間進(jìn)行比較，便可以知道兩者是否在方法誤差范圍的許可內(nèi)一致。從而進(jìn)一步推出不同域下密鑰生成和加、解密的最大時間(n等于P-2)和最小時間(n等于1)，得知其計算時間的范圍和平均計算時間。

為了比較不同域下密鑰生成和加、解密的時間，我們把切比雪夫多項式計算中的n都設(shè)定為40位的隨機(jī)數(shù)，P和x的選取同3.1。仍舊采用3.1中的雙重循環(huán)嵌套的方法，進(jìn)行多次測量再取平均值以獲得最佳測試結(jié)果。測試中，采用文獻(xiàn)［3］中的加、解密方案，設(shè)密鑰生成過程中的SK為40位，加密過程中的R也為40位，得到測試結(jié)果如表4所示。

3.3 簽名、驗證簽名及密鑰協(xié)商時間

由于數(shù)字簽名、驗證簽名以及密鑰協(xié)商也都是基于有限域切比雪夫多項式構(gòu)造，因此測試方法同3.2中密鑰生成和加解密時間。

表4 不同域下密鑰生成和加、解密時間

測試簽名和驗證簽名時間時，采用文獻(xiàn)［3］中的簽名和驗證簽名的方案。P的取值同表3，簽名過程中簽名的私鑰SK為40位，簽名的消息M也為40位，得到測試結(jié)果如表5所示。

表5 不同域下簽名和驗證簽名時間

測試密鑰協(xié)商時，采用文獻(xiàn)［3］中的密鑰協(xié)商算法。P的取值同表3，Alice和Bob的協(xié)商密鑰KA和KB都為40位，得到測試結(jié)果如表6所示。

表6 密鑰協(xié)商時間

4 實驗數(shù)據(jù)分析

從表3-6可以看出，隨著P位數(shù)的增加，域越來越大，單次矩陣乘法時間、密鑰生成和加解密時間、簽名和驗證簽名時間以及密鑰協(xié)商時間都隨之增加。這是符合密碼學(xué)特性的，因為P是基于有限域切比雪夫多項式的公鑰體系的安全參數(shù)，而安全參數(shù)越大則計算量越大，計算時間越長［7］。此外，模運算更加復(fù)雜導(dǎo)致的計算量增大也是計算時間增加的原因。

還可以看到，隨著P位數(shù)的不斷增加，盡管計算時間變長，但是計算時間的增加幅度比P位數(shù)的增加幅度要小很多。這就使得在設(shè)計基于有限域切比雪夫多項式的公鑰體系時，可以通過不斷增大P的位數(shù)來獲得更高的安全性，而由于計算時間增加并不顯著，因此，整個公鑰體系的性能仍能保持較高，從而保證一定的效率。

由表4-6看到密鑰協(xié)商的時間同加密和簽名的時間大致相同，而約是密鑰生成、驗證簽名和解密時間的兩倍。這是因為，前者都進(jìn)行兩次有限域切比雪夫多項式計算，而后者都只進(jìn)行了一次有限域切比雪夫多項式計算，又由于它們在計算時選擇的n都是40位，所以得出的數(shù)據(jù)有以上規(guī)律。這說明，測得實驗數(shù)據(jù)同理論分析是相符的。

另外，可以利用表4-6中的測試數(shù)據(jù)估算出不同算法得單次矩陣乘法時間。結(jié)果，在相同域中，它們與表3中精確測量出來的單次的矩陣乘法時間極為接近。這就更加肯定了算法的正確性，為算法性能的評測提供依據(jù)。

5 有限域切比雪夫多項式算法在WPKI中的優(yōu)勢

由上述測試數(shù)據(jù)可以看出有限域切比雪夫多項式作為公鑰算法相對于RSA和Elgamal算法具備如下優(yōu)勢。

(1)安全性更高。由于它本身數(shù)學(xué)難題的復(fù)雜度高于RSA和Elgamal所基于的數(shù)學(xué)難題，因此，其抗攻擊性具有絕對的優(yōu)勢。又由于目前針對它并沒有有效的破解方法，所以，它的安全性近似對稱密鑰加密系統(tǒng)。

(2)計算量小，處理速度快，存儲空間小，帶寬要求低。由于有限域切比雪夫多項式所需的安全參數(shù)位數(shù)低，密鑰尺寸小，因此它整個系統(tǒng)的計算速度就快，效率高，而所需的存儲空間相對就小，對帶寬要求也低。這對無線終端來說是非常重要的。

(3)密鑰的生成和選取更加靈活方便。RSA和Elgamal算法本身對密鑰的選擇就有很高要求，而有限域切比雪夫多項式算法對密鑰的選擇可以十分隨意［4］，因此，整個公鑰系統(tǒng)開銷也可以大大降低。

同ECC相比，有限域切比雪夫多項式算法優(yōu)勢如下:

(1)數(shù)學(xué)原理通俗簡單，便于采用。ECC算法建立的數(shù)學(xué)模型相對來說比較復(fù)雜晦澀，給算法的具體實現(xiàn)和推廣帶來不少麻煩。而有限域切比雪夫多項式算法卻是在原來切比雪夫多項式算法基礎(chǔ)上的改進(jìn)，原理淺顯易懂，計算較前者也更加簡單，效率更高。

(2)加密簡單。ECC在利用公鑰進(jìn)行加密時需要計算點(x1，y1)=kP(k個P相⊕)，同時要防止點(x2，y2)=kQ 中的 x2=0，否則，就要重新選取［7］。而有限域切比雪夫多項式算法實現(xiàn)的條件寬松得多［4］。

由此可以看出，有限域切比雪夫多項式算法具備了RSA、Elgamal和ECC的優(yōu)點，而鄙棄了它們的缺點。因此，可以將其很好的應(yīng)用于WPKI體系的數(shù)字證書中。

6 結(jié)論

本文對采用有限域切比雪夫多項式的密鑰協(xié)商、公鑰加密和數(shù)字簽名算法做了具體的編程實現(xiàn)，并選擇一定的比較策略和相應(yīng)的安全參數(shù)，對其計算性能進(jìn)行了精確的測量。然后，結(jié)合有限域切比雪夫多項式的性質(zhì)對實驗數(shù)據(jù)進(jìn)行分析，并將之與公鑰體系中常用的RSA、Elgamal和ECC算法性能和應(yīng)用進(jìn)行比較。得知有限域切比雪夫多項式算法具有安全性高，加密簡單，計算量小，處理速度快，存儲空間占用小和所需帶寬小的優(yōu)勢，更加適合于帶寬有限，計算能力受限的無線公鑰加密系統(tǒng)。

［1］Kocarev L，Tasev Z.Public-key encryption based on Chebyshev maps［J］.The 2003 IEEE International Symposium on Circuits and Systems Proceedings，2003，28-31.

［2］P Bergamo，P D Arco，A D Santis.Security of public key cryptosystems based on Chebyshev polynomials［OL］.http://citebase.eprints.org，2004.

［3］寧紅宙，劉云，何德全.基于有限域上 Chebyshev多項式的新公鑰加密系統(tǒng)［J］.

［4］劉亮，劉云，寧紅宙.公鑰體系中切比雪夫多項式的改進(jìn)與特性研究［J］.北京交通大學(xué)學(xué)報，2005.

［5］G Maze.Algebraic Methods for Constructing oneway Trapdoor Functions［D］.Notre Dame:University of Notre Dame，2003

［6］Yoshimura T，Kohda T.Resonance properties of Chebyshev chaotic sequences［J］.Proceedings of the 2004 International Symposium on Circuits and Systems Volume 4 New York:IEEE，2004，23-26.

［7］L Fibìkov，J Vyskoc.Practical cryptography-the key size problem:PGP after year［J］.2001，11.