尹緒昆,黃世中

(河北省科學(xué)院應(yīng)用數(shù)學(xué)研究所,河北石家莊 050081)

RSA算法硬件實現(xiàn)的幾個關(guān)鍵技術(shù)

尹緒昆,黃世中

(河北省科學(xué)院應(yīng)用數(shù)學(xué)研究所,河北石家莊 050081)

介紹了RSA算法硬件實現(xiàn)的關(guān)鍵技術(shù)的基本思想。通過這些技術(shù),可以極大增加算法的運行效率。

RSA;中國剩余定理;Montgomery;進位保留加法器;超前進位加法器

RSA算法是當(dāng)前世界首選的公鑰加密算法。目前在美國和歐洲的商務(wù)和政務(wù)一直使用。著名密碼學(xué)家Steve Burnett和Stephen Paine在《security official guide to cryp tography》指出:自1977年以來,盡管世界各國的研究人員發(fā)明了許多公鑰算法,但排在第一位的是仍然是RSA,其次是DH,然后是ECC。

大數(shù)模冪乘運算是很多公鑰密碼體制例如RSA的核心運算,它由一系列的模乘運算組成,大數(shù)的位數(shù)往往多達1024 bit或更多,運算量極大,是提高加解密運算速度的瓶頸。開發(fā)一種高速、實時并且安全的RSA密碼系統(tǒng),仍然是一個挑戰(zhàn)。采用超大規(guī)模集成電路來實現(xiàn)RSA算法的運算,這種實現(xiàn)方法比普通的PC機用軟件進行1024位數(shù)字簽名要快上百倍。

下面介紹一下RSA硬件實現(xiàn)的關(guān)鍵技術(shù)。

1 Montgomery模乘法算法

模乘冪運算是由一系列的模乘法運算完成。在實現(xiàn)大整數(shù)的模乘法運算的所有算法中,Montgomery模乘法算法不依賴于大整數(shù)的比較和除法,是一種便于硬件實現(xiàn)的算法。

1985年Montgomery提出了一種模乘的算法,其設(shè)計思想是借助一個新的特殊剩余系數(shù),將普通模乘轉(zhuǎn)化為易計算的模乘。Montgomery算法是基于以下結(jié)論:

假設(shè)2n-1≤N≤2n,R=2n且N與R互素,A,B

這樣算法中的整數(shù)模R約化和整數(shù)除以R運算只需要通過簡單的截取或移位就能實現(xiàn),從而避免了復(fù)雜耗時的除法運算。這就是Montgomery算法的根本精髓所在。

需要指出的是Montgomery模乘法算法對于單獨的一次模乘運算并無什么優(yōu)勢,因為它要經(jīng)歷對剩余系數(shù)的映射、具體Montgomery乘積計算和反映射三個階段。但對于模同一個數(shù)的連續(xù)的多個模乘運算,如模冪運算,具有很大的優(yōu)勢。

經(jīng)過S.E.Eldrifge和C.D.Walter改進以后的Montgomery算法可以按如下的方法來實現(xiàn):

基于2為基的Montgomery模乘算法

實際采用改進的基于2為基的Montgomery模乘法,即通過略微增加循環(huán)數(shù)量,減少中間步驟的復(fù)雜性(如可以去掉第7步的判斷),從而利用流水線技術(shù)來提高整個系統(tǒng)的工作主頻。

2 進位保留加法器結(jié)構(gòu)CSA

長的數(shù)據(jù)寬度,限制了許多原有的加法、乘法運算結(jié)構(gòu)的使用,因為他們需要很大的面積;同時其引起的長進位鏈?zhǔn)莻€難以解決的問題,因為其極大地影響了系統(tǒng)主頻的提高。因此可以采用進位保留加法器結(jié)構(gòu)(CSA)實現(xiàn),即輸入輸出采用普通表示,中間結(jié)果采用進位保留形式,最后采用一個32位的CLA(超前進位加法器)對乘法結(jié)果進行格式轉(zhuǎn)換。這一方法即充分利用的硬件的并行性,減少了由于長進位鏈產(chǎn)生的邏輯延遲,提高了工作主頻,也降低系統(tǒng)的面積。為了進一步利用CSA的并行性,還可以采用2個CSA的4:2結(jié)構(gòu)或3個CSA的5:3結(jié)構(gòu)。

進位保留加法器CSA結(jié)構(gòu)如圖1:

圖1 進位保留加法器結(jié)構(gòu)

CSA相當(dāng)于k個并行的全加器(FA),輸入3個k位整數(shù)A、B、C,產(chǎn)生2個整數(shù)C′和S,滿足C′+S =A+B+C。CSA不存在長進位鏈的問題,利于實現(xiàn)硬件的并行處理。

3 超前進位加法器CLA

超前進位加法器(CLA)克服了普通加法器不佳的時序特性,不單純將前一級產(chǎn)生的進位信號以串接的方式傳遞到當(dāng)前一級的全加器,而是利用了邏輯代入的方式來減少進位延遲時間。

可見,將迭代關(guān)系去掉,則各位彼此獨立,進位傳播不復(fù)存在。因此,總的延遲是兩級門的延遲。其高速也就自不待言。

但是當(dāng)加法器的位數(shù)增大時,如果仍采用上述的迭代公式,形成的電路將很不規(guī)則,并且需要長線驅(qū)動以及大驅(qū)動信號和大扇入門?？梢詫﹄娐愤M行改進,用兩個16位加法器來構(gòu)成32位的加法器。

設(shè)Ci為開始輸入的進位,對于16位CLA的超前進位鏈,考察第4、8、12、16位的進位,會得到:

于是對于16位加法器,按4位一組的形式對其分組,組內(nèi)實行超前進位,組間也實行超前進位。結(jié)構(gòu)如圖2所示。第一級中每個4位的CLA模塊分別計算各組內(nèi)的G,P和組間的PX,GX,第二級根據(jù)各組的PX,GX計算出組間的進位。

圖2 16位超前進位加法器原理圖

4 中國剩余定理

由于RSA加密運算的公鑰一般都取固定的小整數(shù)(如3或65537),而解密運算的私鑰往往高達1024bit甚至更多,因此解密(簽名)的速度明顯低于加密(驗證)的速度。為了進一步提高解密(簽名)的速度,在自己知道生成RSA密鑰的素數(shù)對的前提下,可采用中國剩余定理(CRT,Chinese Remainder Theorem)通過降低模乘冪運算的大整數(shù)的長度,達到提高運算速度的目的。

中國剩余定理(CRT)設(shè)m1,m2,…,mk是兩兩互素的正整數(shù),則同余方程

4.1 RSA加密算法的過程是

1.取兩個素數(shù)p和q(保密);

2.計算n=pq(公開),φ(n)=(p-1)(q-1)(保密);

3.隨機選取整數(shù)e滿足 (e,φ(n))=1(公開);

4.計算d,滿足de≡1 modφ(n)(保密)。

4.2 RSA密鑰結(jié)構(gòu)

4.3 RSA加密程序

4.4 RSA解密程序

4.5 RSA解密程序(帶CRT)(速度提高4倍)

5 結(jié)束語

綜上所述,采用上述的關(guān)鍵算法,不管是用FPGA,還是用ASIC來實現(xiàn),都可以明顯提高算法芯片的運算速度。

[1] M c Ivor C,M cLoone M,McCanny J,et al.Fast Montgomery Modular M ultiplication and RSA Cryptographic Processor A rchitectures[C].Proceedings of the 37th Asilomar Conference on Signals,Systems,and Computers.New York:IEEE Press,2003.

[2] Blum T,Paar C.Modular Exponentiation on Reconfigurable Hardware[C].Proceedingsof the 14th IEEE Symposium on Computer A rithmetic(ARITH-14).New York:IEEE Press,1999

Some key technologies of implementing RSA algorithm via hardware

YIN Xu-kun,HUANG Shi-zhong

(Institute of A pplied M athematics,Hebei Academ y of Sciences,Shijiazhuang Hebei,050081,China)

In this paper,the basic thoughts of imp lementing RSA algorithm via hardware are introduced.These methods can increase run efficiency of the user’s p roducts greatly.

RSA;Chinese Remainder Theorem;Montgomery;CSA;CLA

TP319

:A

1001-9383(2011)01-0010-05

2010-11-20

尹緒昆(1979-),男,河北武安人,助理工程師,主要從事計算機技術(shù)應(yīng)用與開發(fā).