尹緒昆,黃世中

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

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

尹緒昆,黃世中

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

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

RSA;中國剩余定理;Montgomery;進(jìn)位保留加法器;超前進(jìn)位加法器

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

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

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

1 Montgomery模乘法算法

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

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

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

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

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

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

基于2為基的Montgomery模乘算法

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

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

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

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

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

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

3 超前進(jìn)位加法器CLA

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

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

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

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

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

圖2 16位超前進(jìn)位加法器原理圖

4 中國剩余定理

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

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

4.1 RSA加密算法的過程是

1.取兩個(gè)素?cái)?shù)p和q(保密);

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

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

4.計(jì)算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來實(shí)現(xiàn),都可以明顯提高算法芯片的運(yù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-),男,河北武安人,助理工程師,主要從事計(jì)算機(jī)技術(shù)應(yīng)用與開發(fā).