劉亮

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

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

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

1 有限域切比雪夫多項(xiàng)式的矩陣迭代算法及其計(jì)算量

有限域切比雪夫多項(xiàng)式算法的迭代形式如下:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表2 測(cè)試域P的選取

續(xù)表

2.2 公鑰x和私鑰n的選擇

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

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

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

3.1 單次矩陣乘法時(shí)間

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

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

表3 不同域下單次矩陣乘法時(shí)間

3.2 密鑰生成和加、解密時(shí)間

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

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

3.3 簽名、驗(yàn)證簽名及密鑰協(xié)商時(shí)間

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

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

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

表5 不同域下簽名和驗(yàn)證簽名時(shí)間

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

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

4 實(shí)驗(yàn)數(shù)據(jù)分析

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

［4］劉亮，劉云，寧紅宙.公鑰體系中切比雪夫多項(xiàng)式的改進(jìn)與特性研究［J］.北京交通大學(xué)學(xué)報(bào)，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.