??? 摘? 要： 提出了一種基于嵌入式系統(tǒng)的高速、可配置RSA密碼協(xié)處理器的ASIC設(shè)計方案，可實現(xiàn)256 bit到2 048 bit的RSA加密運算,。為了提高運算速度,，采用改進的高基模乘算法和流水線結(jié)構(gòu)；為了消除協(xié)處理器與內(nèi)存之間的通信速度瓶頸,，使用DMA直接訪問方式,；同時，數(shù)據(jù)輸入輸出都使用雙口存儲體,，形成加解密數(shù)據(jù)流,，本文將該加解密協(xié)處理器簡稱為SPU（Streaming Processing Unit）。?

??? 關(guān)鍵詞： RSA,；模乘算法,；蒙哥馬利乘法；專用集成電路,；加解密協(xié)處理器

?

??? 公鑰密碼系統(tǒng),，也稱為非對稱密碼系統(tǒng)，是密碼學(xué)的一種形式,。它有一對密鑰：公鑰和私鑰,。它們在數(shù)學(xué)上有一定的關(guān)系，但是很難從公鑰得到私鑰,。公鑰密碼學(xué)的兩個主要分支：?

??? 公鑰加密：任何人都可以將消息（明文）加密成密文,，但只有接收者才能生成有意義的密文。這樣確保了數(shù)據(jù)的安全性,，用于可靠性方面,。?

??? 數(shù)字簽名：發(fā)送者通過私鑰加密的消息(明文)，可以被任何人通過公鑰解密,。因此證明了這條消息是發(fā)送者簽名并且沒被人修改過,。這種方法用于數(shù)字簽名與認(rèn)證方面。?

??? 公鑰制密碼學(xué)中,，目前應(yīng)用最為廣泛的是RSA公鑰制密碼算法^[1],。RSA算法通過模冪運算實現(xiàn)，模冪運算是整個RSA算法的核心,。在操作數(shù)較小的情況下,，模冪運算比較簡單，可以直接計算。但是為了保證必要的安全等級,，一般采用512 bit或1 024 bit的密鑰長度,，在銀行等需要更高安全等級的系統(tǒng)中，會采用更長位寬的密鑰,，模冪的難度隨之成指數(shù)級增長,。RSA算法安全性的保證和需要就像一把雙刃劍，在給攻擊者帶來計算難度的同時也提高了運算的復(fù)雜度,。?

??? 本文提出一種基于ASIC設(shè)計的高速,、可配置的RSA密碼協(xié)處理器體系結(jié)構(gòu)，可實現(xiàn)256 bit到2 048 bit的RSA加密運算,。該方案綜合考慮RSA模冪和模乘算法的特點和瓶頸,，采用改進的高基模乘算法和流水線結(jié)構(gòu)，提高運算速度,；采用DMA直接訪問方式,，消除協(xié)處理器與內(nèi)存之間的通信速度瓶頸；數(shù)據(jù)輸入輸出都使用雙口存儲體,，形成加解密數(shù)據(jù)流,。?

1 公鑰密碼算法RSA?

1.1 RSA算法?

??? RSA加密算法是目前在理論和實際應(yīng)用中較為成功的公鑰密碼體制，它的安全性是基于數(shù)論中大整數(shù)分解為素數(shù)因子的困難性,，這一困難在目前仍是一個NP問題,。要建立一個RSA密碼系統(tǒng)，首先任選兩個大素數(shù)p,、q,，使：?

??? N=p×q?

??? 并得到Euler函數(shù):?

??? Ψ(n)=(p-1)×(q-1)?

??? 然后任選一個與Ψ(n)互素的整數(shù)e作為密鑰,，再根據(jù)e求出解密密鑰d,，d滿足：?

??? d×e=1modΨ(n)?

??? 事實上，加密密鑰e和解密密鑰d是完全可互換的,，因此在求e或d時,，不論先假設(shè)哪一個，再由它去求另一個都是一樣的,。對某個明文分組M和密文分組C,，加密和解密的過程如下：?

??? 加密過程：?

??? C=M^emodN?

??? 而解密過程是：?

??? M=C^dmodN?

??? RSA加解密就是做模冪運算的過程，而模冪運算是通過一系列的模乘運算得到的,。模冪算法根據(jù)冪指數(shù)掃描順序不同可以分為兩種：從左往右的L-R算法和從右往左的R-L算法,。?

??? 算法一：R-L模冪算法?

??? 式中n為指數(shù)e的位數(shù)，P為中間變量?

??? 輸入：M,，e,，N；?

??? 輸出：C=M^e modN；?

??? (1)P=M,；C=1,；?

??? (2)for i=0 to n-2；?

??? (3)if e[i]=1 then C=C×P mod N,；?

??? (4)P=P×P mod N,；?

??? (5)next i；?

??? (6)if e[n-1]=1 then C=C×P mod N,；?

??? (7)return C,；?

??? 算法二：L-R模冪算法?

??? 輸入：M，e,，N,；?

??? 輸出：C=M^e modN；?

??? (1)if e[n-1]=1 then C=M,，else C=1,；?

??? (2)for i=n-2 to 1；?

??? (3)C=C×C mod N,；?

??? (4)if e[i]=1 then C=C×M mod N,；?

??? (5)next i；?

??? (6)return C,；?

??? 從以上兩種算法可以看出,，一次模冪運算需要進行N次平方模運算和平均N/2次乘法模運算；但在從右往左的掃描中,，乘法和平方是相互獨立的,，可以并行。因此可以增加一個N位的乘法器,，一個做乘法,，一個做平方，這可以顯著提高一次模冪運算的速度,。本文面向高速應(yīng)用場合,，因此采用R-L模冪算法。?

??? 在RSA算法中,，不論是加密過程還是解密過程,，都有一個共同的模乘運算(ABmod N)，這個看似簡單的運算,，需要做一次乘法和一次除法,，最后取余數(shù)。但由于M,，e,，C,，d，N等參數(shù)的長度通常是1 024個二進制位或更高,，使得模冪運算量巨大,，很難在一般的協(xié)處理器上或處理器上運行，直到1985年由Montgomery提出了一種免除法的模乘算法^[2],，才使RSA算法在硬件和軟件中得以實現(xiàn),。?

1.2 Montgomery模乘算法?

??? Montgomery算法的基本思想是把一個大整數(shù)轉(zhuǎn)換為一個模R(R通常取2r)的余數(shù)表示形式，用轉(zhuǎn)換后的余數(shù)進行一系列模乘運算,，最后再轉(zhuǎn)換為正常的表達形式,。將計算A*B mod N時的mod N的除法運算轉(zhuǎn)化為簡單的移位運算，能夠有效地提高模乘運算的速度,。?

??? 算法三：Montgomery算法?

??? 設(shè)N為模數(shù),，R是2的整數(shù)冪，且R>N,，并令R^-1和N′滿足0-1-1-NN′=1成立,。?

??? 輸入：A,，B，R,，N,；?

??? 輸出：c=M(A，B)=A*B*R-1 modN?

??? (1)T=A*B,；?

??? (2)m=(Tmod R)*N′ mod R,；?

??? (3)c=(T+mN)/R；?

??? (4)if c>=N return c-N,；?

??? (5)else return m,；?

??? 該算法不能直接實現(xiàn)RSA算法，需要進行相應(yīng)的預(yù)處理才能消除R^-1帶來的影響（見算法五）,。該算法仍然包含大整數(shù)的乘法,，因此需要對其進行改進,，使用高基模乘算法（見算法四）,，細化為小整數(shù)的乘法，以便于硬件實現(xiàn),。另外,，該算法最后需要判斷m是否大于N，如果大于N,，必須再做減法,，這在硬件設(shè)計上會增加額外的芯片面積,。本文通過在模乘循環(huán)過程中增加一次循環(huán)，就可以免去最后的減法（見算法五）,。?

1.3 高基Montgomery算法?

??? 把n位大整數(shù)A,，B，N分別表示成s位r進制整數(shù),，即A=(a_s-1 a_s-2…a₀),，B=(b_s-1b_s-2…b₀)r，N=(n_s-1n_s-2…n₀)r,，且R=r^s,，s=n/r，則有N

??? 算法四：高基Montgomery算法?

??? Function M(A,，B)?

??? S：=0；m=0,；?

??? (1)計算中間結(jié)果m[i]：?

??? ?? for i=0 to s-1?

??????? {for j=0 to i?

??????? ?? {s：=s+a[j]*b[i-j]+m[j]*n[i-j],；}?

??? ?? m[i]：=s*n′[i] mod r；?

??? ?? s：=s+m[i]n[i]?

??? ?? s：=s/r,；}?

??? (2)計算最終結(jié)果并存于m[i]中：?

??? for i=s to 2s-1?

??? {for j=i-s+1 to s-1?

??? {s=s+a[j]b[I-j]+m[j]n[I-j]}?

??? m[i-s]：=s mod r?

??? s：=s/r}?

??? 算法五：從右往左掃描的免減高基模乘算法?

??? (1)預(yù)處理：?

??? R²=R*R mod N,；(事先計算出來，可消除R^-1帶來的影響)?

??? P=M（M,，R²）,；?

??? C=1；?

??? (2)中處理：?

??? for i=0 to n-2?

??? if e[i]=1 then C=M(C,，P),；?

??? P=M(P，P),；?

??? next i,；?

??? if e[n-1]=1 then C=M(C，P),；?

??? return C,；（計算C=M(Me))?

??? (3)后處理：?

??? C=M（C，1）,；（免去了montgomery算法每次的減法運算）,。?

2 協(xié)處理器體系結(jié)構(gòu)?

2.1 SPU整體結(jié)構(gòu)與模塊劃分?

??? SPU與CPU通過CROSSBAR^[3]交叉通信開關(guān)進行通信，而SPU與MEM之間則采取DMA方式直接通信,，這樣可以消除數(shù)據(jù)存取的速度瓶頸,。同時，當(dāng)SPU進行加解密工作時,，CPU可以并行執(zhí)行其他指令(只要不發(fā)生數(shù)據(jù)相關(guān)),。?

??? SPU劃分為控制模塊,，數(shù)據(jù)通道和存儲單元。其中控制單元主要用于密鑰移位控制,，控制密鑰的降冪,，并根據(jù)密鑰產(chǎn)生乘或平方控制信號。另外,，控制單元還包括一個狀態(tài)控制器,，用于對前處理、中處理和后處理各個運算環(huán)節(jié)的控制,。?

??? 數(shù)據(jù)通道部分則由Montgomery模乘單元和平方單元構(gòu)成,，兩個單元并行，根據(jù)控制單元產(chǎn)生的控制信號來進行相應(yīng)的操作,，產(chǎn)生部分積和中間結(jié)果,。?

??? 存儲單元大小為8 Kbit，分為兩部分,。一部分是4 KB的RAM,，用于加解密過程中暫存數(shù)據(jù)，以便形成流水線,；另一部分是4 KB的ROM,，用于存放公鑰和密鑰，掉電可以保存數(shù)據(jù),。?

??? 系統(tǒng)框圖如圖1所示,。?

?

?

2.2 流水線設(shè)計?

??? 為了實現(xiàn)高速、可配置的RSA密碼協(xié)處理器,，采用了按字讀入的高基模乘算法,，同時對模冪單元采用流水線結(jié)構(gòu)：這樣一方面可以增加數(shù)據(jù)吞吐率，加快數(shù)據(jù)運算速度,；另一方面可以通過增減流水線的級數(shù)來增強可配置性,。?

??? 從按字讀入的高基模乘算法（算法五）中可以看出，每次密鑰長度為N bit的RSA加解密過程是一次冪指數(shù)為N的模冪運算,，而一次這樣的模冪運算則是N次模乘運算,。因此通過設(shè)計模冪流水線結(jié)構(gòu)，可以大大增加RSA加解密的速度,。?

??? 流水線結(jié)構(gòu)的模冪運算如圖2所示,。明文M經(jīng)過T級流水線數(shù)據(jù)通路，最后輸出密文C,；對于一個N位的RSA加密系統(tǒng)來說,，如果采用T級流水線，則每一級流水線需要循環(huán)做N/T次MM運算,。RSA的運算速度取決于一級流水線的速度,。?

?

?

2.3 DMA通道的工作過程?

??? SPU向DMA控制器發(fā)出DMA請求，DMA控制器在接到SPU發(fā)出的DMA請求后,，向CPU發(fā)出總線請求,，請求CPU脫離對總線的控制，而由DMA控制器接管對系統(tǒng)總線的控制,；CPU在執(zhí)行完當(dāng)前指令的當(dāng)前總線周期后,，向DMA控制器發(fā)出總線響應(yīng)信號，CPU脫離對系統(tǒng)總線的控制,，處于等待狀態(tài)(但一直監(jiān)視DMAC),；DMA控制器接管對系統(tǒng)總線的控制；DMA控制器向SPU發(fā)出DMA應(yīng)答信號,，DMA控制器把存儲器與SPU之間進行數(shù)據(jù)傳送所需要的有關(guān)地址送到總線,，通過控制總線向存儲器和SPU發(fā)出讀或?qū)懶盘枺瑥亩瓿梢粋€字節(jié)的傳送,；當(dāng)設(shè)定的字節(jié)數(shù)據(jù)傳送完畢后(DMA控制器自動計數(shù)),，DMA控制器將總線請求信號變成無效，同時脫離對總線的控制,；CPU檢測到總線請求信號變成無效后(CPU一直監(jiān)視著),，也將總線響應(yīng)信號變成無效，CPU恢復(fù)對系統(tǒng)總線的控制,，繼續(xù)執(zhí)行被DMA控制器中斷的當(dāng)前指令的當(dāng)前總線周期,。?

2.4 存儲體結(jié)構(gòu)設(shè)計?

??? SPU內(nèi)部共設(shè)計兩部分RAM，都使用雙口存儲體,，主要用作數(shù)據(jù)輸入,、輸出緩存。雙口RAM分A和B兩部分,，每部分的深度32,，寬度64，即32×64的存儲空間,；一塊RAM可以存儲2 KB的數(shù)據(jù),，輸入輸出各需要一塊作為緩存，也就是說片內(nèi)共設(shè)計4 KB的RAM,。雙口RAM的兩部分是對稱的,，但是對每部分的讀寫都是獨立的，當(dāng)需要加密或解密時,，數(shù)據(jù)先輸入到A部分,，當(dāng)A部分輸入滿2 KB數(shù)據(jù)時，數(shù)據(jù)繼續(xù)輸入到B中,，此時運算模塊讀取A中的數(shù)據(jù)計算,，當(dāng)B部分?jǐn)?shù)據(jù)輸入滿時,，運算模塊已經(jīng)計算完A中的數(shù)據(jù)，然后讀取B中的數(shù)據(jù),，輸出則是相反的過程,，如此形成加解密數(shù)據(jù)流，運算流程如圖3所示,。?

?

?

??? 本文基于改進的按字輸入的從右往左掃描的高基Montgomery模乘算法,，提出了一種高速、可配置的RSA加解密協(xié)處理器的ASIC設(shè)計方案,。該方案很好地解決了模冪和模乘運算的瓶頸問題,，提高了算法并行性和運算效率?；谠摲桨缚梢苑奖愕卦O(shè)計出各種速度和密鑰長度的RSA密碼協(xié)處理器,，尤其對高速RSA市場具有很廣闊的應(yīng)用前景。?

參考文獻?

[1] RIVEST R L,，SHAMIR A,，ADELMAN L M.A method for?obtaining digital signatures and public key cryptosystems.?Communications of the ACM，1978,，21(2)：120-160.?

[2] MONTGOMERY P L.Modular multiplication without trial?division[J].Mathematics of Comptutation,，1985，44(170)：519-521.?

[3] OpenSPARC T1 Microarchitecture Specification.http：//www.sun.com/hwdocs/feedback.?

[4] Kong Fan Yu,，Yu Jia,，Li Da Xing.An improved fast montgomery multiplication algorithm.Computer Engineering，2005,，31(8)：1-4.?

[5] Fan Yi Bo,，Zeng Xiao Yang，Yu Yu.VLSI design of a?High-speed RSA Crypto-Coprocessor with reconfigurable?architecture.Journal of Computer Research and Development.2006,，43(6)：1076-1082.?

[6] Wang Long,，Zhao Hui，Bai Guo Qiang.A cost-efficient implementation of pubilc-key cryptography on embedded?systems.IEEE,，I-4244-1098-3/07,，2007：194-197.?

[7] BLUM T，PAAR C.Brief contributions：high-radix Montgomery modular exponentiation on reconfigurable hardware.IEEE Transactions on Computers,，2001,，50(7)：759-764.?

[8] PIEPRZYK J，HARDJONO T,SEBERRY J.Fundamentals of?computer security.Spring-Verlag,，2003.?

[9] 吳行軍,，白立晨，孫怡樂，等.一種適用于多種公鑰密碼算法的模運算處理器.微電子學(xué),，2005,，35(5)：549-552.?

[10] 朱海峰.RSA關(guān)鍵運算的分析優(yōu)化與硬件實現(xiàn)研究.南通大學(xué)學(xué)報，2006,，5(4)：97-100.