曾健林，黃 凱，馬 德，馮 炯，葛海通，嚴(yán)曉浪

（1．浙江大學(xué)超大規(guī)模集成電路研究所，浙江杭州 310027;2．杭州市中天微系統(tǒng)有限公司，浙江 杭州 310012）

0 引言

隨著現(xiàn)代通信和計(jì)算機(jī)網(wǎng)絡(luò)的快速發(fā)展，公鑰基礎(chǔ)設(shè)施（public key infrastructure，PKI）成為信息安全領(lǐng)域不可或缺的一部分。作為PKI重要一部分，RSA［1］算法得到了廣泛的關(guān)注。RSA算法是在1978年由Rivest R，Shamirh A和Adleman L提出的一種非對(duì)稱加解密算法。RSA的安全級(jí)別與密鑰長(zhǎng)度呈正比，而運(yùn)算復(fù)雜度也相應(yīng)加大。當(dāng)前不同的應(yīng)用迫切需要根據(jù)安全和成本需求來采用不同長(zhǎng)度的密鑰，并具備高速的加解密性能。然而，傳統(tǒng)的純軟件實(shí)現(xiàn)方法雖具備高度的靈活可配型，但遠(yuǎn)遠(yuǎn)不能滿足高速RSA加解密應(yīng)用需求。因此，設(shè)計(jì)密鑰長(zhǎng)度可配置的高性能RSA硬件加速器已逐漸成為一個(gè)重要的研究方向。

RSA算法的實(shí)質(zhì)是大數(shù)的模冪運(yùn)算，可以通過多次模乘循環(huán)實(shí)現(xiàn)。雖然RSA加密算法具有很高的安全性，但由于模乘運(yùn)算的復(fù)雜性，RSA的運(yùn)算速度始終成為制約RSA廣泛應(yīng)用的瓶頸。RSA硬件加速器可以顯著提高RSA的運(yùn)算速度，但模乘運(yùn)算中包含著多次加法、減法和除法迭代運(yùn)算，VLSI實(shí)現(xiàn)具有很高的代價(jià)。當(dāng)前，RSA硬件設(shè)計(jì)的相關(guān)研究主要集中在模乘算法的改進(jìn)和高效的VLSI實(shí)現(xiàn)2個(gè)方面。蒙哥馬利模乘［2］（Montgomery modular multiplication，MMM）算法被認(rèn)為是最高效的模乘算法，利用MMM算法，RSA可以通過簡(jiǎn)單的移位和加法實(shí)現(xiàn)，這使得VLSI實(shí)現(xiàn)變得可行。文獻(xiàn)［3，4］提出了基于MMM算法的RSA協(xié)處理器，但運(yùn)算并行度不高，導(dǎo)致數(shù)據(jù)吞吐率較低。

本文采用基—64MMM模乘算法來實(shí)現(xiàn)RSA加解密運(yùn)算加速器，通過五級(jí)流水線架構(gòu)的模乘器和高度并行可配架構(gòu)的存儲(chǔ)器，可支持不同長(zhǎng)度的密鑰，并顯著地提升了運(yùn)算效率，取得了較好的性能和硬件資源消耗比。

1 算法描述

1．1 Montgomery算法的描述

MMM算法由Montgomery P L在1985年提出，提供了一種快速計(jì)算A×B×R－1mod N的方法，通過一定的預(yù)運(yùn)算和后運(yùn)算得到真正形如S=A×B mod N模乘運(yùn)算結(jié)果。它采用模加和右移的方法，避免了通常求模算法中費(fèi)時(shí)的除法操作。

算法1為原始的MMM算法，其中A，B為任意2個(gè)整數(shù)，N為模數(shù)且N＞1，R為滿式（1）的一個(gè)基（通常取R為2n，n為輸入大數(shù)的位數(shù)）

R－1和N'為滿足式（2）和式（3）的正整數(shù)

算法 1:function MMM（A，B，N）{

算法1中每次模乘運(yùn)算總有A×B和M×N兩次大數(shù)運(yùn)算，對(duì)于2048位 RSA，A，B和M可能是2048位的大整數(shù)，大數(shù)乘法的硬件實(shí)現(xiàn)仍然具有很大的代價(jià)，因此，Montgomery提出了改進(jìn)的算法，取r=2w稱為基，w為字長(zhǎng)，大整數(shù)A，B，N表示如下

此時(shí)式（3）相應(yīng)的為

改進(jìn)的MMM算法通過循環(huán)的辦法，分多次來完成大數(shù)的運(yùn)算，比算法1更利于硬件的實(shí)現(xiàn)。

1．2 MMM—64 算法

目前，大多數(shù)模乘運(yùn)算的硬件結(jié)構(gòu)都基于改進(jìn)的MMM算法。文獻(xiàn)［5］在改進(jìn)的MMM算法基礎(chǔ)上取基r為2得到基2—MMM算法，然后采用脈動(dòng)陣列實(shí)現(xiàn)模乘運(yùn)算。但基—2的MMM算法運(yùn)算并行度不高，會(huì)導(dǎo)致整體的運(yùn)算效率較低。為了提高運(yùn)算并行度，需要采用高基的MMM算法。

現(xiàn)提出一種適合硬件實(shí)現(xiàn)的基—64MMM算法。算法描述如下

算法 2:function MMM_64（A，B，N）{

可以看出:上述基—64MMM采用64位的乘法運(yùn)算和加法運(yùn)算，極大地提高了運(yùn)算并行度，可以充分利用硬件的運(yùn)算能力，提高效率。同時(shí)，該算法對(duì)可支持的運(yùn)算長(zhǎng)度沒有限制，通過控制循環(huán)次數(shù)k實(shí)現(xiàn)了運(yùn)算長(zhǎng)度的可配。

1．3 基于MMM的RSA算法

MMM算法實(shí)現(xiàn)的只是A×B×R－1mod N，可提供了解決模乘甚至是模冪運(yùn)算的新的方法。經(jīng)過適當(dāng)?shù)念A(yù)處理，循環(huán)運(yùn)算以及反處理，可以得到形如AEmod N的結(jié)果。算法如下:

將冪數(shù)E展開成二進(jìn)制形式，形如E=（ew，ew－1…ei…e1，e0）2，通過從左到右遍歷E的每一位，來實(shí)現(xiàn)模冪運(yùn)算。

算法 3:function RSA（A，E，N）{

其中，P=R2mod N只需運(yùn)算一次，且僅與R和N有關(guān)，故可由軟件來完成。從上述算法可知，模冪運(yùn)算可由多次MMM算法來完成。對(duì)于N位的RSA運(yùn)算，在最差情況下，E的每一個(gè)二進(jìn)制位都為1，需要（2N+2）次MMM運(yùn)算;在平均情況下，E的二進(jìn)制表示中“1”的期望值為N/2，需要（1．5N+2）次MMM運(yùn)算。

2 RSA硬件架構(gòu)設(shè)計(jì)

2．1 整體架構(gòu)

RSA加速器整體架構(gòu)如圖1所示，主要由AHB接口、寄存器組、存儲(chǔ)區(qū)、控制器和模乘器5個(gè)部分組成。

AHB接口模塊是加速器總線交互的接口，處理器運(yùn)行完預(yù)處理的軟件操作后，可以通過AHB接口配置或讀取加速器的內(nèi)部寄存器組和存儲(chǔ)器。

寄存器組是用來存放一些控制信息和狀態(tài)信息，如支持不同長(zhǎng)度密鑰模式的配置等。存儲(chǔ)區(qū)是用來存放RSA運(yùn)算所需的密鑰和運(yùn)算數(shù)據(jù)等信息。

控制器通過狀態(tài)轉(zhuǎn)換控制模乘器的運(yùn)算。由算法3可知，RSA運(yùn)算可由多次模乘迭代運(yùn)算完成。需要注意的是，每一次模乘運(yùn)算輸入與輸出不盡相同，數(shù)據(jù)將在模乘器和存儲(chǔ)區(qū)之間頻繁的流通?？刂破鲗⑼瓿刹煌琈MM運(yùn)算的調(diào)度，保證存儲(chǔ)區(qū)提供正確的數(shù)據(jù)給模乘器，同時(shí)保證模乘器的輸出存放到正確的存儲(chǔ)區(qū)。

模乘器是運(yùn)算的主體，承擔(dān)基—64MMM算法。

圖1 加速器架構(gòu)Fig 1 Architecture of accelerator

2．2 模乘器流水線架構(gòu)

基—64MMM算法中，涉及2個(gè)64位的乘法運(yùn)算，為了使系統(tǒng)能夠運(yùn)行在較高的頻率，提高系統(tǒng)吞吐率，采用帶流水級(jí)的乘法器來實(shí)現(xiàn)。同時(shí)，由于2個(gè)乘法運(yùn)算沒有數(shù)據(jù)依賴性，可以并行的運(yùn)算，進(jìn)一步提高性能。模乘器流設(shè)計(jì)如圖2所示。

圖2 模乘器結(jié)構(gòu)Fig 2 Architecture of modular multiplier

在乘法器的選擇上，需要綜合考慮流水級(jí)深度和硬件資源，前者直接關(guān)系到運(yùn)算性能，后者則關(guān)系到實(shí)現(xiàn)代價(jià)。MUL2為一個(gè)兩級(jí)流水的乘法器。這個(gè)乘法器將承擔(dān)T［i］的計(jì)算。算法2可知，這一過程需要2個(gè)乘法運(yùn)算，并且這2個(gè)乘法運(yùn)算具有數(shù)據(jù)依賴性，只能依次完成。因此，乘法器每增加一級(jí)流水，就相當(dāng)于需要額外增加2個(gè)周期的等待時(shí)間。故犧牲一部分面積，采用一個(gè)兩級(jí)流水的乘法器，以提高性能。得到的T［i］將存儲(chǔ)在寄存器T中。同時(shí)這個(gè)乘法器還將承擔(dān)流水級(jí)中ai×bj的運(yùn)算。這個(gè)乘法器為流水線的前兩級(jí)。第三級(jí)流水為加法級(jí)，完成cj的累加。MUL3為一個(gè)三級(jí)流水的乘法器，將承擔(dān)T［i］×bj的運(yùn)算，既匹配了流水線，實(shí)現(xiàn)了并行運(yùn)算，又節(jié)省了一部分面積。第四級(jí)也為加法級(jí)，將MUL3的結(jié)果與前三級(jí)的結(jié)果相加。第五級(jí)為進(jìn)位和寫回級(jí)，運(yùn)算結(jié)果將直接寫回存儲(chǔ)區(qū)，同時(shí)產(chǎn)生進(jìn)位給下一次運(yùn)算。所用的加法器同時(shí)將承擔(dān)C-N的運(yùn)算。

模乘器的設(shè)計(jì)，綜合考慮了高的性能和低的硬件資源消耗。合適的流水深度保證了高的數(shù)據(jù)吞吐率。完成N位的模乘運(yùn)算僅需M=N/64×（N/64+5+4）個(gè)時(shí)鐘。

2．3 存儲(chǔ)結(jié)構(gòu)

在運(yùn)算過程中，模乘器需要同時(shí)讀入3個(gè)64位的數(shù)據(jù)（cj，bj，nj），寫出一個(gè) 64 位的數(shù)據(jù)（cj－1），對(duì)數(shù)據(jù)帶寬要求很高。同時(shí)，從RSA運(yùn)算的整體來看，這些數(shù)據(jù)需要頻繁的讀取和寫入，因此，這里考慮在加速器內(nèi)加入存儲(chǔ)區(qū)域，以方便數(shù)據(jù)的并行訪問。存儲(chǔ)結(jié)構(gòu)如圖3所示。

圖3 存儲(chǔ)結(jié)構(gòu)Fig 3 Architecture of memory

這個(gè)存儲(chǔ)器由5塊單端口SRAM組成，每一塊的數(shù)據(jù)寬度為64位，可實(shí)現(xiàn)并行訪問。其中，第一塊存儲(chǔ)模數(shù)N;第二塊分成3個(gè)區(qū)間，分別存儲(chǔ)密鑰E，預(yù)處理輔助參數(shù)P和待加密數(shù)A;第三，四和五塊用來存儲(chǔ)運(yùn)算中間值和運(yùn)算結(jié)果。如圖4所示，存儲(chǔ)器的大小由密鑰的長(zhǎng)度需求來決定。在低端應(yīng)用中，可以通過將存儲(chǔ)器配小，節(jié)省硬件資源。在高端應(yīng)用中，可以通過增加存儲(chǔ)器來支持長(zhǎng)達(dá)2048 bit位的RSA運(yùn)算。同時(shí)，大配置的存儲(chǔ)器能夠兼容低端的應(yīng)用，可以通過配置寄存器組中相關(guān)的寄存器來完成不同長(zhǎng)度的RSA運(yùn)算。這樣就從硬件和軟件2個(gè)方面實(shí)現(xiàn)了加速器的可配性?？膳浯鎯?chǔ)器大小如表1。

在運(yùn)算過程中，N，E，P的值是保持不變的，MMM（A，P，N）運(yùn)算后，A會(huì)更新為A'。在 MMM（B，B，N）運(yùn)算中，M0，M1，M2將分別提供cj，bj讀取以及cj－1寫入，保證了模乘器的數(shù)據(jù)供給和寫出，流水線可以不阻塞的工作。

表1 可配存儲(chǔ)器的大小Tab 1 Size of configurable memory

3 實(shí)現(xiàn)與比較

本文采用Verilog HDL語(yǔ)言實(shí)現(xiàn)了采用基—64MMM算法五級(jí)流水模乘器的RSA硬件加速器RTL代碼。對(duì)于N位的RSA運(yùn)算，完成一次模乘所需時(shí)鐘數(shù)為M=N/32×（N/64+5+4）;最差情況下，完成一次模冪運(yùn)算所需時(shí)鐘數(shù)為（2N+2）M，而在平均情況下，完成一次RSA運(yùn)算所需時(shí)鐘數(shù)為（1．5N+2）M。在存儲(chǔ)結(jié)構(gòu)最大支持2048位RSA運(yùn)算情況下，采用SMIC0．18 μm工藝庫(kù)綜合后，在最差條件下，加速器可以運(yùn)行高達(dá)200 MHz，所需硬件資源為73 k門和1792 byte SRAM，各模塊所需資源如表2所示。

表2 各模塊硬件資源Tab 2 Hardware resource of each module

表3是本文所實(shí)現(xiàn)的模乘器與其他文獻(xiàn)的性能對(duì)比?？梢钥闯?本文實(shí)現(xiàn)的模乘器所需時(shí)鐘數(shù)節(jié)省了約50%。

表3 模乘器性能對(duì)比Tab 3 Performance comparison of modular multiplier

表4是RSA硬件加速器的性能對(duì)比。本文所設(shè)計(jì)的RSA硬件加速器，在硬件資源消耗差別不大的情況下，實(shí)現(xiàn)了2～3倍的數(shù)據(jù)吞吐率，達(dá)到了較好的性能資源消耗比。

表4 RSA硬件加速器性能對(duì)比Tab 4 Performance comparison of RSA hardware accelerator

4 結(jié)束語(yǔ)

本文采用一種利于硬件實(shí)現(xiàn)的基—64MMM算法，實(shí)現(xiàn)了高速可配的RSA硬件加速器。該加速器通過五級(jí)流水線模乘器及對(duì)應(yīng)的并行存儲(chǔ)結(jié)構(gòu)，顯著提高了RSA運(yùn)算性能，并支持不同密鑰長(zhǎng)度的高度可配性。與相關(guān)工作比較，具有較好的性能資源消耗比。

［1］ Rivest R L，Shamir A，Adleman L．Method for obtaining digital signatures and public key cryptosystems［J］．Communications of the ACM ，1978 ，21（2）:120 －126．

［2］ Montgomery P L．Modular multiplication without trial division［J］．Mathematics of Computation，1985，170（44）:519 －521．

［3］ Zheng Xinjian，Liu Zexiang ，Peng Bo．Design and implementation of an ultra low power RSA coprocessor［C］∥The 4th International Conference on Wireless Communications，Networking and Mobile Computing，WiCOM 2008，2008:1 －5．

［4］ Liu Jizhong，Dong Jinming．Design and implementation of an efficient RSA crypto-processor［C］∥2010 IEEE International Conference on Progress in Informatics and Computing（PIC），2010:368 －372．

［5］ 蔣曉娜，段成華．改進(jìn)的蒙哥馬利算法及其模乘器實(shí)現(xiàn)［J］．計(jì)算機(jī)工程，2008，34（12）:209 －211．

［6］ Huang Miaoqing，Gaj K，Kwon S，et al．An optimized hardware architecture for the Montgomery multiplication algorithm ［J］．Public Key Cryptography（PKC），LNCS，2008，4939:214 －228．

［7］ 王締酈，白國(guó)強(qiáng)，陳弘毅．一種 Montgomery模乘算法硬件結(jié)構(gòu)［J］．微電子學(xué)與計(jì)算機(jī)．2010，27（5）:1 －4

［8］ Chen Yunlu，Tseng Chihyeh，Chang Hsiechia C．Design and implementation of reconfigurable RSA cryptosystem［C］∥International Symposium on VLSI Design，Automation and Test，2007:1 －4．