一種高性能公鑰密碼計算構件的研究與應用

摘要：分析公鑰密碼算法的各種加速算法的基礎上，分別在Xilinx Virtex V600FG680-6 FPGA上用流水線和非流水線方式，以及TI公司的TMS320C5402和TMS320C6201系列高性能DSP上設計RSA密碼計算構件。并通過對四種方案特點的分析，比較了在校園卡應用領域中，不同設計方案適用的具體應用背景，得到了比較理想的結果。

關鍵詞：模冪運算；蒙哥馬利算法；FPGA；DSP

中圖分類號：TP393文獻標識碼：A文章編號：1009-3044(2008)33-1322-04

Research and Application of a Kind of High Performance Public Key Cryptography Computing Component

YANG Xuan1， HUANG Bin2

(1.International College， Central South University of Forestry and Technology; Changsha 410004，China;2.College of Information Engineering， Xiangtan University， Xiangtan 411105， China)

Abstract: On the basis of analysis on various accelerated algorithm of public key cryptography arithmetic， Cryptography component is designed in this paper by the way of pipeline and non-pipeline on Xilinx Virtex V600FG680-6 FPGA separately as well as on TI corporation’s high performance DSP of TMS320C5402 and TMS320C6201 series. Meanwhile， an analysis of specific application background of different projects in the application area of Campus Card through the comparison to those four projects was proposed in this paper. And a desired outcome is achieved.

Key words: modular exponentiation; montgomery arithmetic; FPGA; DSP

1 引言

PKI的是實現在現代電子政（商）務應用系統中對使用者的身份認證和信息的完整性、不可否認性認證的的關鍵技術，而公鑰密碼是PKI體系中公鑰加密和數字簽名最常采用的加密算法。以公鑰密碼公鑰算法[1]為基礎，來設計具有獨立功能的硬件芯片的公鑰密碼計算構件，以其高速的性能和硬件本身特有的安全優勢得到了廣泛的關注與巨大的投入，國內外對此都做了大量的研究[2-3] 。同時，國內外眾多學者對公鑰密碼及其相關算法的實現研究也取得了不錯的進展。

目前，僅具安全存儲功能的射頻IC卡在學校已經形成了龐大的用戶群體，為了實現校園卡與主機的互操作與數據加密、身份認證等安全計算的功能，可以在校園卡互操作性框架[4]的讀寫設備中配置公鑰密碼密碼計算構件。基于這種需求，針對不同的應用背景，我們設計了相應的公鑰密碼密碼計算構件實現方案。

2 公鑰加/解密算法介紹

由Rivest，Shamir和Adleman在1978年設計并公布的公鑰算法是最具有代表性的公開密鑰密碼體制，它是一個能同時用于加解密和數字簽名的算法。也是研究得最深入的公鑰算法。它從提出到現在的二十多年中，經歷了各種攻擊的考驗，逐漸被人們所接受，普遍認為是目前最優秀的公鑰方案之一。

公鑰密碼加/解密算法公式表述如下：

加密過程：c=md mod n

解密過程：m=ce mod n

其中，m是明文，d是加密密鑰（或公鑰），e是解密密鑰（或私鑰），n是模數，c是密文，mod是取模函數。

公鑰密碼算法主要難點在于大數的模冪乘運算效率較低。所以，提高大數模冪乘的效率一直都是提高公鑰密碼算法速度的一個非常重要的課題。

3 模冪加速算法的研究

3.1 長整數模冪乘運算

模冪乘運算me mod n不能先計算me然后再求模，這樣me的結果會占用巨大的存儲空間而無法實現必須對me的中間結果進行求模運算，使結果二進制位數始終保持在一定范圍內。計算me mod n最簡單的方法是重復進行c=c*m mod n模乘運算，直到求出me mod n為止，這種方法需要e-1次乘法運算。例如計算m15 mod n需要計算m→m2→m3→m4→…→m15，其需要14次乘法；而采用m→m2→m3→m6→m7→m14→m15 其需則僅需六次乘法運算。這種平方—乘冪方法也稱之為二進制法。在硬件實現上較為常用的方法是二進制位掃描法，分為從左到右和從右到左兩種。在從左向右掃描法中，主要是面積可以得到優化，而在從右向左掃描法中，主要是速度得到了優化。

在從左到右掃描法中，指數e的位被從最高有效位掃描到最低位，對于每一位要作一次平方求模，如果e的位值是1，還需要做一次模乘；從右到左掃描法則是最低有效位掃描到最高位，需要用中間變量保存中間值。

3.2 用Montgomery算法加速公鑰密碼算法

Montgomery算法是將部分積對任意的n取模轉化為對基數r取模，簡化了計算過程，提高了加解密的速度。這一有效的模約化方法是P. Montgomery1985年在文獻[5]中發表的，并在此后找到了廣泛的實際應用。

原始的Montgomery算法如下：

選擇與（模數）n互素的基數r，為計算方便，它通常是機器字長的整數的倍數；并且選擇r-1及n’，滿足0< 日r-1< n，0< n’< r，使得，r r-1- n n’=1。

Montgomery乘積的計算按以下算法產生。

在R(r，n)中Montgomery乘積mont(a，b)的計算

S1. 置t = a*b;

S2. 置m = t*n' mod r;

S3. 置u = (t+m*n)/r （商取整數）;

S4. 若u≥n，輸出u-n，否則輸出u.

3.3 用中國剩余定理（Chinese Remainder Theorem， CRT）加速公鑰密碼算法

根據公鑰密碼算法的性質，模數n可以分解為兩個大素數，這樣，我們可以用中國剩余定理來加速運算，模數n = p*q，p、q為大素數。

由于公鑰密碼中私鑰d遠遠大于公鑰e，所以算法的運行過程主要依賴于解密（簽名）過程。用CRT分解解密（簽名）過程：

M1 ＝ Cd mod p和M2 ＝ Cd mod q；

再根據Fermat定理，可得：

M1=Cdpmodp和M2=Cdqmodp，其中dp = d mod (p-1)，dq = d mod (q-1)；

最后根據CRT，計算M：

M = M2 + hq，其中qinv = q-1 mod p ， h = qinv(M1-M2) mod p。

由于p和q的長度為n的一半，所以冪運算的長度減少為原來的一半。如果采用這種方法來進行運算，在生成公私密鑰對時，公鑰的產生與前面相比無任何變化，但密鑰的計算就必須比原始的公鑰密碼計算更多參數，將p，q，dp，dq，qinv當作私鑰。這種方法雖然在生成密鑰時需要進行的運算更多，但在解密（簽名）運算時運算的位數比原來縮短了一半，所以速度會更快，與原始的直接對密鑰d執行模指數運算的做法快了近3倍。

4 公鑰密碼算法在FPGA上的優化實現

4.1 改進的Montgomery算法

在對Montgomery算法的基本形式進行分析時[6] ，可以看出它有以下幾個缺點：1) 所需存儲空間較大(2s+1個存儲單元)；2) 帶進位傳輸延遲，影響運算速度；3) 帶有除法運算，需要另外有專門的運算部件。

我們可以采用下面描述的改進的Montgomery算法[7]，把模乘轉化為加法和移位的反復迭代過程。

改進算法：MonPro (A，B，M)

MonPro (A，B，M)

{

S-1：=0;

A：=2×A;

for i=0 to n do

qi：=(Si-1) Mod 2; (Si-1的最低有效位（LSB）)

Si：=(Si-1+qiM+biA)/2;

end for

Return Sn;

}

上面MonPro函數通過下面的形式計算Montgomery乘積：

MonPro(A，B，M)=ABr-1 mod M

4.2 Montgomery改進算法的模乘器結構及優化

如果主要考慮速度的優化，根據改進的Montgomery算法，采用從右到左掃描法，直接可得到相應硬件結構，包含兩個加法器。但實際上，在一個給定乘法每次反復的執行中，第一級加法器只有4種可能的輸出。分別是：0，M，2A或M+2A，到底取何值由bi和qi由的決定。因此，2個加法器來執行太浪費了。可以改為，使用一個多路服用器來選擇4種加法器可能的輸入，如圖1所示。

4.3 MuxMult結構在FPGA的實現

在FPGA上，可以通過流水線和非流水線兩種方式來執行MuxMult結構。其運行結果如表1所示。

通過非流水線的實現，綜合考慮高速度和較低的面積要求，多路復用/加法體系結構（MuxMult）體系結構是一種比較適合用在公鑰密碼求冪運算中的硬件結構。

當乘法器的位長度超過FPGA的1column的時候，執行邏輯進位的優勢就失去了。可通過把計算劃分成j個p-bit的字，并且用流水線來操作，這樣時鐘速度得到了提高（在這里p是FPGA的1column的最大長度，而j=n/p）。

用流水線方式時，乘法器的輸入必須是分成p-bit長的字，并且加法的執行必須在下一級的加法器輸入之前延遲一個時鐘。然而，因為采用的是從右向掃描法，和的最低有效位（LSB）必須直接反饋到上一級加法器的最高有效位（MSB）。

5 公鑰密碼算法在DSP上的優化實現

在本節中，分析了適用于TI公司TMS320C54x和TMS320C62x DSP的優化算法。

5.1 公鑰密碼算法在TMS320C54x上的優化實現

5.1.1 選用TMS320C54x的考慮因素

TMS320c54x系列DSP有專用的硬件乘法/加法結構（MAC），數據指針在執行乘加運算后可自動增加，以及桶型移位器，適合于進行乘加等算數運算。特別是DSP特有的IEEE1149.1標準邊界掃描邏輯與片內掃描邏輯接口，該接口可在不占用用戶任何資源的情況下，通過主機查詢器件內部的狀態，極大方便了用戶調試。

5.1.2 算法的具體實現

首先，用從右到左掃描法把模冪運算轉化為反復的模乘運算。

然后，做模乘運算時，我們使用以下方法[8]：

模乘運算：（Interleaving Multiplication and Reduction Method）

Input:A，B，n，k(number of bits of A，B，n)

Output: P:=A*B(mod n)

P:=0

for i=0 to k-1

P:=2*P+A*Bk-1-I

P:=P mod n

return P

在以上方法中，需要計算2*P， A*Bk-1-I，P mod n。0<=P<=3n-3。因此計算P:=P mod n時最多需要做兩次減法就可以使0<=P

subtract at most two times

input:P(0<=p<=3n-3)

output P:=P mod n

Q:=P-n;if Q>=0 then P=Q

Q:=P-n;if Q>=0 then P=Q

Return P

基于上面主要算法，我們就可以利用TMC302C54x DSP 開發公鑰密碼算法了。

5.1.3 用剩余定理實現快速運算

公鑰密碼的簽名和解密操作M:=Cd(mod n)，都可以用剩余定理來加速。用剩余定理實現時，作為私鑰的不是解密指數d，而是5個數：p，q，d1=d mod (p-1)，d2=d mod (q-1)，u=q-1 mod p。算法如下：

input:p，q，d1，d2，u

output:m=md mod n

m1=cd1 mod p

m2=cd2 mod q

m=q*(u(m1-m2) mod p)+m2

end

5.2 公鑰密碼算法在TMS320C62x上的優化實現

5.2.1 選用TMS320C54x的考慮因素

TM302C62的CPU包含兩套8個基本功能單元，其中有兩個16×16bit的乘法器和6個ALU；8個功能單元能夠并行執行，在單個時鐘周期內能夠執行最多8條32比特指令；具有高速的處理能力，內部時鐘最高300MHz，指令執行速度最高可達2400MIPS(采用300MHz的時鐘)；具有豐富的寄存器資源，共有2×16個32位通用寄存器；靈活的尋址方式，能夠進行字節尋址，獲得8bit/16bit/32bit數據，充分利用存儲器資源；軟件流水，提高循環操作的效率。

5.2.2 算法的優化

通過中國剩余定理的運用，可使得指數及模數的長度減少為原來的一半。采用M-ary算法能減少預計算數來求乘方，模平方的次數是模乘運算的log2m倍，所以對模平方的優化顯得更加重要。對于TI公司的TMS320C6201 DSP開發平臺[9]，CPU運行時同時取8條指令組成一個指令包，為使運行時獲得更高的指令并行性以提高運算速度，必須對軟件流水線進行優化。在這里優化的關鍵在于通過對Montgomery平方約化算法的改進以適應DSP處理器的軟件流水。

在文獻[10]中對Montgomery平方約化的算法的設計，存在冗余的運算，且該算法的雙層循環結構使得軟件流水很難達到較高的效率。針對這些問題，可以考慮從兩個方面來對算法進行優化：首先，用一個單獨的循環來計算ai×ai；其次，乘法運算在TMS320C6201 DSP處理器上是一個多周期指令，在程序中會產生延遲間隙，為了將軟件流水的能量發揮到最高，則需要盡最大可能的填補延遲間隙。為此，通過對雙重循環進行改進減少了算法的冗余度，提高軟件流水的效率。

因此我們將ai×ai提到外層循環之外，改進的算法如下（其中sw代表字數，w代表每個字的bit數）：

for i = 0 to sw-1{(ti+i+1，ti+I) = ai×ai;}

for i = 0 to sw-1{

m = ti×n0’ mod 2w;

for j = 0 to i{

(C，ti+j) = ti+j + m×nj + C;

}

C1 = 0; C2 = 0;

for j=i+1 to sw-1{

Slong = 2×C1 + C + ti+j;

(C1，S) = ai×aj;

(C，ti+j) = Slong + 2×S;

(C2，ti+j) = m×nj + S + C2;

}

(pre，ti+sw) = C + 2×C1 + C2 + ti+sw + pre;

}

tsw+sw = tsw+sw + pre;

6 實驗結果及公鑰密碼密碼計算構件的應用

6.1 執行結果與公鑰密碼密碼計算構件設計方案比較

我們在Xilinx Virtex V600FG680-6 FPGA上分別用流水線和非流水線方式實現基于多路復用/加法結構的公鑰密碼算法，以及在TI公司TMS320C5402和TMS320C6201高性能DSP上基于1024位的公鑰密碼運算，其結果如表1所示：

6.2 以公鑰密碼密碼計算構件為基礎的應用系統

在校園內，基于校園卡互操作性框架，我們提出了如圖2所示的方法來使射頻卡（擴展的密碼設備）具有公鑰密碼密碼計算功能。

在讀寫器中加入公鑰密碼密碼計算構件。從而實現了即便使用射頻卡，學生也能夠進行報考、網上簽約等操作，而學校能在生成可信的學生信息（ASI）[11]時做簽名和認證等操作。

通過分析表1，基于圖2所示的應用需求，不同的情況下，可以采用不同的方案來設計公鑰密碼密碼計算構件：如果是學生作簽名，因為單個學生簽名對速度的要求不高，那么主要的考慮是降低成本，我們可以采用FPGA或TMS320C54x設計的公鑰密碼密碼計算構件。在這種情況下如果要考慮構件芯片化，則應采用FPGA；另外一種情況，如果是在校園卡認證中心[12]，當教育廳或省考試院等上級單位要調用ASI的時候，這時，校方就必須對ASI進行簽名，由于數據量很大，并且校方的校園卡認證中心只有一個，這時要考慮的主要因素是提高速度，所以可以采用TMS320C62x設計的公鑰密碼密碼計算構件。

7 結論

本文分析了公鑰密碼密碼計算構件在FPGA上用流水線和非流水線，以及TI公司的5000和6000系列高性能DSP設計方案。在對各種方案執行可信計算的速度和開銷，以及成本進行了綜合地比較的基礎上，分析了不同的方案的具體應用。

參考文獻：

[1] Rivest R L， Shamir A， Adleman L. A Method of obtaining Digital Signatures and Public Key Cryptosystems[J].Comm. Of ACM， 1978，21(2):120-126.

[2] 孫宏，楊義先.公鑰密碼算法在TMS320C62x中的高速實現[J].計算機工程與應用，2003(11):22.

[3] Krishnamurthy A，Tang Y，Xu C，et al.An Efficient Implementation of Multi-prime RSA on DSP Processor[J].ICASSP 2003.http://www.icme2003.com/Papers.2004

[4] 段斌，王鍵.密碼系統互操作性的泛化方法[R].第5次全國教育卡規范研討會論文，2004.

[5] Montgomery P L.Modular multiplication without trial division.Math.Computation，1985，44:519-521

[6] Kaya Koc C， Acar T， Kaliski B J. Analyzing and comparing Montgomery multiplication algorithms[J].IEEE Micro，1996，16(3) :26-33.

[7] Daly A， Marnane W. Efficient Architectures for implementing Montgomery Modular Multiplication and RSA Modular Exponentiation on Reconfigurable Logic[M].Copyright 2002 ACM，2002:24-26.

[8] 孔德琦，裴昌幸.基于TMS320C54x DSP的公鑰密碼加解密系統[J].電子科技，2002(1):12.

[9] TMS320C6000 CPU and Instruction Set Reference Guide[Z].Texas Instruments，1999.

[10] Itoh K， Takenaka M， Torii N， et al. Fast Implementation of Public-Key Cryptography on a DSP TMS320C6201[M].Proc. Of CHES 1999:61-71.

[11] 段斌.電子政務中的一個標準“零部件”：ASI及其語法、機制及安全評估[J].計算機工程與應用，2004(9):96-99.

[12] 段斌，王鍵.結合EMIF的校園卡互操作框架應用體系結構[R].第5次全國教育卡規范研討會論文，2004.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”