融入中國剩余定理及Montgomery算法的快速RSA算法研究

于麗麗，王麗君

(遼寧科技大學 軟件學院，遼寧 鞍山114051)

RSA算法是一種公開密鑰算法，其加密密鑰和算法本身都可以公開，解密密鑰則歸用戶私人擁有。從誕生那天起，RSA就因為安全強度高、使用方便等卓越性能而受到關注，并得到廣泛應用。但是，近年來由于分解大整數的能力日益增強，為保證RSA密碼體制的安全性總是要增加模長，使加密、解密操作需要計算的位數達十進制百位以上的模冪乘函數，使運行時間很長，這一直是制約其應用的瓶頸問題，因此本文在速度方面對RSA算法做了相關改進。

本文主要針對RSA公鑰密碼體制中中國剩余定理的使用以及大整數模指數算法進行了深入的研究。經證明，在RSA算法中使用中國剩余定理可以提高其加密的速度達到之前的4倍。模指數運算是大部分密碼算法實現中最耗時的運算步驟，因此模指數運算正是這些密碼體制實現的關鍵，而大整數模運算又是其核心運算。本文將對密碼學中的大整數模運算進行研究。

1 利用中國剩余定理提高RSA算法效率

中國剩余定理(CRT)又稱為孫子定理，是數論中最有用的定理之一，并在我國科學技術史上對數學的發(fā)展作出了重要貢獻。

中國剩余定理可有幾種不同的表示形式，這里給出其中最有用的一種表示形式，即：

其中 mi是兩兩互素的， 即對 1≤i，j≤k，i≠j有 gcd(mi，mj)=1。可將ZM中的任一整數對應一個k元組，該k元組的元素均在Zmi中，這種對應關系可表示為：

其中 A∈ZM，對 1≤i≤k，ai∈Zmi，且 ai=Amodmi。中國剩余定理的用途之一是給出了一種方法，使非常大的數對M的模運算轉化到更小的數上運算，當M為150位或150位以上時，這種方法非常有效。

1.1 加速算法

在 RSA加密算法中，n=pq(p，q為大素數），因此，在試圖計算c≡md(modn)前，可以先計算：

而這兩步運算，又因為模數的變小，可以簡化為：

然后，根據中國剩余定理，計算出c為：

在這個算法中，假設 n的二進制長度為 k，那么 p，q的 長 度 約 為 k/2。 假 設 d1，d2，p-1(modq)，q-1(modp)都 已知，則整個計算過程約需要3k3/8次位運算。而不用中國剩余定理，則約需要3k3/2次位運算。其中的假設條件，由于RSA系統(tǒng)一經建立，所涉及參數就相對穩(wěn)定，因而是可以實現的。所以新算法可以切實地將RSA系統(tǒng)的運算速度提高約4倍。加之計算cp、cq的過程相對獨立，滿足并行計算的條件，因此基于中國剩余定理的改進算法在速度上有著明顯的優(yōu)勢。

1.2 出錯攻擊

用中國剩余定理加速計算RSA體制時，如果由于某些意外滿足以下3個條件：

(1)簽名(加密)信息己知；

(2)在簽名(加密)時出現了一個錯誤；

(3)錯誤的簽名(密文)被輸出。

那么，這個錯誤就可能導致參數n被分解。

假設，設備在計算 cp時發(fā)生了錯誤，即獲得了 cp′，cp′≠cp，而 cp計算正確。 則通過 cp′和 cp，可以計算出一個錯誤的c′。由此可以得到：

證明：

根據中國剩余定理有

等式成立。

從應用角度來看，出錯攻擊是一個非常強大的攻擊方法。它提醒在設計系統(tǒng)的過程中，必須小心謹慎。因為，只要發(fā)生了一個錯誤，那么整個系統(tǒng)將會面臨崩潰的危險。而事實上硬件電子設備出錯是時常出現的，所以這種威脅極其現實和緊迫。

對于簽名或者認證服務商，還存在一種被稱為“否定服務”的攻擊。一個攻擊者只需要匿名的聲稱，就能獲得服務商的一個錯誤簽名，進而將迫使服務商放棄目前的密鑰對。

而對于真正的攻擊者，有許多已知的方法可以幫助攻擊者實現誘導系統(tǒng)出錯，包括重寫ROM、修改EEPROM、破壞邏輯門電路等。

1.3 改進方法

幾種比較實用的，對抗出錯攻擊的方法有：

(1)冗余計算 cp，cq的值。對 cp，cq的值各做 2次計算，如果2次結果不同，則廢止此次運算；如果結果相同，則計算c值并輸出。

(2)增加對c的驗證環(huán)節(jié)。在計算獲得密文(簽名)c之后，驗證m=ce(modn)是否成立。若不成立，則廢止；若成立，則輸出結果c。

(3)Shamir在1997年提出了一種驗證模冪運算的方法[1]。具體到這個問題中，需要隨機選取r，并計算：

如果 cpr≡cqr(modr)，則認為計算過程正確，進而計算：

否則，廢止此次運算。

事實上，目前己經有很多將此加速算法應用到密碼產品中的想法，參考文獻[2]就是一個例子。只是它使用了混合半徑轉換，進一步降低了運算強度，即將

替換為

這是因為：

但是，混合半徑r的使用，本身并不能回避出錯攻擊。當cp被錯誤地計算成cp′時，依舊無法進行有效的驗證與更正。因此，這一計算同樣會受到出錯攻擊，需要對其步驟加以調整，增加輸出前的驗證。由于是硬件實現的問題，因此更適合采用方法(3)。方法(1)意味著運算量加倍，而方法(2)則會需要全程儲存被加密信息，方法(3)隨機參數的獲得可以增加運算過程的隨機性，同時驗證步驟只是簡單的位比對，更加適合硬件實現。

2 Montgomery模乘算法

在沒有出現Montgomery模約減算法之前，研究人員用除法求余數的方法進行模約減、模乘等算法，即經典的模約減算法。Montgomery模約減無需使用經典模約減算法而能有效地實現模乘法的技術。

設m是正整數，R和 T是整數，滿足 R＞m，gcd(m，R)=1，0≤T≤mR。Montgomery[3]于 1985年提出一種可以不使用經典乘法計算TR-1modm的方法。TR-1modm稱為T模m關于R的Montgomery約減。選擇適當的R，Montgomery約減可以有效地計算。

如果將m表示成n位的b進制數，那么R的典型選擇是 bn。條件 R＞m顯然滿足，但條件 gcd(b，m)=1當且僅當gcd(b，m)=1時才能滿足。因此這種R的選擇并非對所有的模數都是可行的。對于RSA算法來說，m是奇數，因此 b可以取 2的冪，且 R=bn。

引理 1 m和 R是整數，滿足 gcd(m，R)=1。 令 m′=-m-1modR，T是滿足 0≤T≤mR的正整數。若 U=Tm′modR，則(T+Um)/R 是整數，且(T+Um)/R≡TR-1(modm)。

證明：T+Um=T(modm)，因此(T+Um)/R-1≡TR-1(modm)。為了說明(T+Um)R-1是整數，觀察到對于某些整數k和1，有 U=Tm′+kR 和 mm′=-1+lR，于是(T+Um)/R=(T+(Tm′+kR)m)/R=(T+T(-1+lR)+kRm)/R=lT+km。 證畢。

(T+Um)R是對TR-1modm的估計。因為T＜mR且U＜R，所以(T+Um)/R＜(mR+mR)/R=2m。因此有(T+Um)/R=TR-1modm或(T+Um)/R=(TR-1modm)+m。即TR-1modm或者等于(T+Um)/R，或者等于(T+Um)/R-m。

如果所有的整數都表示成b進制，并且R=bn，那么TR-1modm可以采用算法1，用兩個多精度乘法(U=Tm′和Um)、一次多精度加法(T+Um)和一次右移(即除以 R)計算出來。

算法1 Montgomery模約減算法

輸入：整數 m=(mn-1…m1m0)b，gcd(m，b)=1，R=bn，m′=-m-1modR，T=(t2n-1…t1t0)b＜mR；

輸出：TR-1modm。

算法步驟為：

(1)A←T；

(2)U←Tm′modR；

(3)A←T+Um；

(4)A←A/bn；

(5)如果 A≥m，則 A←A-m；

(6)返回(A)。

顯然，在兩次多精度乘法中，算法1需要進行2n2次單精度乘法。1990年，Dusse等人[4]改進了算法 1，他們將步驟(2)和(3)巧妙地融合到一起，新的算法只需要n(n+1)即 n2+n次乘法，見算法 2。

算法2 改進的Montgomery模約減算法

輸入：整數 m=(mn-1…m1m0)b，gcd(m，b)=1，R=bn，m′=-m-1modb，T=(t2n-1…t1t0)b＜mR；

輸出：TR-1modm。

算法步驟為：

(1)A←T；

(2)對于 i從 0到 n-1，執(zhí)行：

①ui←aim′modb；

②A←A+uimbi。

(3)A←A/bn；

(4)如果 A≥m，則 A←A-m；

(5)返回(A)。

算法2沒有像算法1那樣要求m′=-m-1modR，而是要求 m′=-m-1modb。步驟(1)中，當 i=l時，A具有性質 aj=0，0≤j≤l-1。步驟(2)并沒有修改這些0的值，但是將 al替換成了0。于是在步驟(3)中，A能被bn整除。

算法2的步驟(1)和(2)總共需要 n+1次單精度乘法，由于步驟(2)需要執(zhí)行n次，因此單精度乘法的總數是 n(n+1)。此外，還需要少量可以忽略不計的加法和移位等運算，而不需要任何單精度除法。

2.1 SOS模乘法算法

Separated Operand Scanning算法簡稱SOS算法，是模乘法運算中最基本的方法。即先用傳統(tǒng)多精度乘法或其他方法進行多精度乘法運算，然后用算法2進行模約減運算。算法3給出了SOS算法的描述。

算法3SOS模乘算法

輸入：整數 m=(mn-1…m1m0)b，x=(xn-1…x1x0)b，y=(yn-1…y1y0)b，gcd(m，b)=1，R=bn，m′=-m-1modb；

輸出：xyR-1modm。

算法步驟為：

(1)A←xy；

(2)對于 i從 0到 n-1，執(zhí)行：

①ui←aim′modb；

②A←A+uimbi。

(3)A←A/bn；

(4)如果 A≥m，則 A←A-m；

(5)返 回(A)。

通過算法3可以看出，SOS算法僅僅是將乘法和模約減算法前后羅列，組合到一起，并沒有做實質性改進。該算法效率相對不高，其單精度乘法的次數為2n2+n。但是，由于步驟(1)相對于其他步驟是獨立的，因此，在某些特定的環(huán)境下，可以采用Karatsuba算法、Comba算法等快速乘法來提高算法3的效率。

2.2 CIOS模乘法算法

Coarsely Integrated Operand Scanning算法簡稱CIOS算法，是SOS算法的一個改進。Koc等人給出了CIOS的算法描述，并認為CIOS算法是最理想的模乘法算法。該方法將乘法和模約減算法完美地融合為一體，在讀寫內存等方面節(jié)省了許多的資源。算法4給出了CIOS算法的描述。

算法4 CIOS模乘法算法

輸 入 ： 整 數 m=(mn-1…m1m0)b，x=(xn-1…x1x0)b，y=(yn-1…y1y0)b，gcd(m，b)=1，R=bn，m′=-m-1modb；

輸出：xyR-1modm。

算法步驟為：

(1)A←0；

(2)對于 i從 0到 n-1，執(zhí)行：

①A←A+xiy；

②ui←a0m′modb；

③A←(A+uim)b。

(3)如果 A≥m，則 A←A-m；

(4)返回(A)。

算法 4實質是將 x×y和U×m兩個多精度乘法按照傳統(tǒng)乘法的方法結合到了一起。在步驟(2)開始的時候，U是未知的，需要在進行每個 ui×m之前用 xi×y0的值計算出 ui。最終，步驟(2)交替完成了將所有的 xi×y 和 ui×m累加到A的過程。

CIOS模乘法中，單精度乘法的次數和SOS算法一樣，也是2n2+n。但是與SOS算法相比，它將兩個乘法結合到了一起，減少了一次循環(huán)。步驟(3)在實現的時候，可以不進行除以b的移位運算，而是將結果直接保存到A的高一位中。CIOS詳細的效率分析，將在下一節(jié)中與FIPS方法一起給出。

2.3 FIPS模乘法算法

Finely Integrated Operand Scanning算法簡稱FIPS算法，在1993年由Kaliski提出，該方法設計思想來源于Comba算法，它采用類似Comba算法的從右向左的按列累加的方法設計而成，將乘法和模約減算法完美地融合為一體。Koc[5]認為FIPS算法的“乘積累加”結構非常適用于數字信號處理器(DSP)等微處理器，是RSA硬件實現中常用的算法，在某些特定的硬件設備上具有很高的執(zhí)行效率。算法5給出了FIPS算法的描述。

算法5 FIPS模乘法算法

輸 入 ： 整 數 m=(mn-1…m1m0)b，x=(xn-1…x1x0)b，y=(yn-1…y1y0)b，gcd(m，b)=1，R=bn，m′=-m-1modb；

輸出：U=xyR-1modm。

算法步驟為：

(1)(v2v1v0)b=0；

(2)對于 i從 0到 n-1，執(zhí)行：

(3)對于 i從 0到 n-1，執(zhí)行：

(4)un←v0；

(5)如果 U≥m，則 U←U-m；

(6)返回(U)。

算法 5實質上是將 x×y和 U×m這兩個多精度乘法按照Comba算法的方法結合到了一起。在步驟(2)中，分別計算了右邊n列的乘積之和，并求出所有的ui。步驟(3)計算出左邊的n-2列的乘積之和，同時得到了A=xyR-1modm的值。由于每得到一個ai時，相應的ui值不會被再用到，因此可以直接用 ui來保存ai的值，在編程序時可節(jié)省一個長為n的數組。

FIPS模乘法中，單精度乘法的次數和CIOS算法一樣，也是2n2+n。但在具體實現時的效率卻大大不同。可以根據算法，從理論上統(tǒng)計這兩種算法在乘法、加法、讀內存、寫內存方面的差異。通過表1可以看出，FIPS算法的讀內存、寫內存次數都遠遠高于CIOS算法。這是因為由于寄存器個數有限，在計算機程序中，FIPS算法中的三元組(v2v1v0)需要用內存變量來存儲，使訪問內存所消耗的時間大大增加。但是如果在數字信號處理器(DSP)等微處理器上實現，將會使這些訪問內存所消耗的時間忽略不計。因此，在這類硬件上實現FIPS算法，效率將大大提高。如果不考慮三元組(v2v1v0)訪問內存的次數，表1將修改為表2。表2中給出的數據可以明顯看出，在DSP等硬件上實現模乘法時，FIPS算法僅僅在加法次數上略多于CIOS算法，而讀寫內存的次數都大大減少，有著很大的優(yōu)勢，非常適合于RSA算法的硬件實現。

表1 CIOS算法與FIPS算法運算次數統(tǒng)計表

表2 特定硬件上CIOS算法與FIPS算法運算次數統(tǒng)計表

算法速度測試：

測試平臺環(huán)境為CPU：Genuine Intel(R)CPU 2140@1.60 GHz 1.60 GHz；內存：1 G；操作系統(tǒng)：Windows XP。

綜合運用以上3個加速方案，對于一次模冪運算Memodn所消耗的時間 (取50次的平均值)，對比結果如表3所示。

對于RSA密碼體制來說，安全性固然是其特征之一，但是加解密的速度卻是衡量其算法好壞的首要標準。經過以上分析表明，中國剩余定理可以使非常大的數對M的模運算轉化到更小的數上來運算，并且新算法可以切實地將RSA系統(tǒng)的運算速度提高了約4倍。Montgomery模乘算法不僅能夠簡化RSA算法中的模乘步驟，而且能夠有效地節(jié)省算法復雜度。

[1]SHAMIR A.How to check modular exponentiation[C].The rump session of EUROCRYPT，1977.

[2]涂航，劉玉珍，張煥國，等.智能卡操作系統(tǒng)中RSA算法的實現與應用[C].第六屆中國密碼學學術會議論文集，2000：239-243.

[3]MONTGOMERY P.Modular multiplication without trial division.Mathematics of Computation，1985，(44)：519-521.

[4]DUSSE B，KALISHI J.A cryptographic library for the Motorola DSP56000[C].Advances in Cryptology-EUROCRYPT90，1990.

[5]KOC C K.High-speed RSA implementation[C].RSA Labs Technical Report TR-201，1994.