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

于麗麗，王麗君

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

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

本文主要針對(duì)RSA公鑰密碼體制中中國(guó)剩余定理的使用以及大整數(shù)模指數(shù)算法進(jìn)行了深入的研究。經(jīng)證明，在RSA算法中使用中國(guó)剩余定理可以提高其加密的速度達(dá)到之前的4倍。模指數(shù)運(yùn)算是大部分密碼算法實(shí)現(xiàn)中最耗時(shí)的運(yùn)算步驟，因此模指數(shù)運(yùn)算正是這些密碼體制實(shí)現(xiàn)的關(guān)鍵，而大整數(shù)模運(yùn)算又是其核心運(yùn)算。本文將對(duì)密碼學(xué)中的大整數(shù)模運(yùn)算進(jìn)行研究。

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

中國(guó)剩余定理(CRT)又稱(chēng)為孫子定理，是數(shù)論中最有用的定理之一，并在我國(guó)科學(xué)技術(shù)史上對(duì)數(shù)學(xué)的發(fā)展作出了重要貢獻(xiàn)。

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

其中 mi是兩兩互素的， 即對(duì) 1≤i，j≤k，i≠j有 gcd(mi，mj)=1?？蓪M中的任一整數(shù)對(duì)應(yīng)一個(gè)k元組，該k元組的元素均在Zmi中，這種對(duì)應(yīng)關(guān)系可表示為：

其中 A∈ZM，對(duì) 1≤i≤k，ai∈Zmi，且 ai=Amodmi。中國(guó)剩余定理的用途之一是給出了一種方法，使非常大的數(shù)對(duì)M的模運(yùn)算轉(zhuǎn)化到更小的數(shù)上運(yùn)算，當(dāng)M為150位或150位以上時(shí)，這種方法非常有效。

1.1 加速算法

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

而這兩步運(yùn)算，又因?yàn)槟?shù)的變小，可以簡(jiǎn)化為：

然后，根據(jù)中國(guó)剩余定理，計(jì)算出c為：

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

1.2 出錯(cuò)攻擊

用中國(guó)剩余定理加速計(jì)算RSA體制時(shí)，如果由于某些意外滿(mǎn)足以下3個(gè)條件：

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

(2)在簽名(加密)時(shí)出現(xiàn)了一個(gè)錯(cuò)誤；

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

那么，這個(gè)錯(cuò)誤就可能導(dǎo)致參數(shù)n被分解。

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

證明：

根據(jù)中國(guó)剩余定理有

等式成立。

從應(yīng)用角度來(lái)看，出錯(cuò)攻擊是一個(gè)非常強(qiáng)大的攻擊方法。它提醒在設(shè)計(jì)系統(tǒng)的過(guò)程中，必須小心謹(jǐn)慎。因?yàn)?，只要發(fā)生了一個(gè)錯(cuò)誤，那么整個(gè)系統(tǒng)將會(huì)面臨崩潰的危險(xiǎn)。而事實(shí)上硬件電子設(shè)備出錯(cuò)是時(shí)常出現(xiàn)的，所以這種威脅極其現(xiàn)實(shí)和緊迫。

對(duì)于簽名或者認(rèn)證服務(wù)商，還存在一種被稱(chēng)為“否定服務(wù)”的攻擊。一個(gè)攻擊者只需要匿名的聲稱(chēng)，就能獲得服務(wù)商的一個(gè)錯(cuò)誤簽名，進(jìn)而將迫使服務(wù)商放棄目前的密鑰對(duì)。

而對(duì)于真正的攻擊者，有許多已知的方法可以幫助攻擊者實(shí)現(xiàn)誘導(dǎo)系統(tǒng)出錯(cuò)，包括重寫(xiě)ROM、修改EEPROM、破壞邏輯門(mén)電路等。

1.3 改進(jìn)方法

幾種比較實(shí)用的，對(duì)抗出錯(cuò)攻擊的方法有：

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

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

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

如果 cpr≡cqr(modr)，則認(rèn)為計(jì)算過(guò)程正確，進(jìn)而計(jì)算：

否則，廢止此次運(yùn)算。

事實(shí)上，目前己經(jīng)有很多將此加速算法應(yīng)用到密碼產(chǎn)品中的想法，參考文獻(xiàn)[2]就是一個(gè)例子。只是它使用了混合半徑轉(zhuǎn)換，進(jìn)一步降低了運(yùn)算強(qiáng)度，即將

替換為

這是因?yàn)椋?/p>

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

2 Montgomery模乘算法

在沒(méi)有出現(xiàn)Montgomery模約減算法之前，研究人員用除法求余數(shù)的方法進(jìn)行模約減、模乘等算法，即經(jīng)典的模約減算法。Montgomery模約減無(wú)需使用經(jīng)典模約減算法而能有效地實(shí)現(xiàn)模乘法的技術(shù)。

設(shè)m是正整數(shù)，R和 T是整數(shù)，滿(mǎn)足 R＞m，gcd(m，R)=1，0≤T≤mR。Montgomery[3]于 1985年提出一種可以不使用經(jīng)典乘法計(jì)算TR-1modm的方法。TR-1modm稱(chēng)為T(mén)模m關(guān)于R的Montgomery約減。選擇適當(dāng)?shù)腞，Montgomery約減可以有效地計(jì)算。

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

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

證明：T+Um=T(modm)，因此(T+Um)/R-1≡TR-1(modm)。為了說(shuō)明(T+Um)R-1是整數(shù)，觀察到對(duì)于某些整數(shù)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是對(duì)TR-1modm的估計(jì)。因?yàn)門(mén)＜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。

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

算法1 Montgomery模約減算法

輸入：整數(shù) 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需要進(jìn)行2n2次單精度乘法。1990年，Dusse等人[4]改進(jìn)了算法 1，他們將步驟(2)和(3)巧妙地融合到一起，新的算法只需要n(n+1)即 n2+n次乘法，見(jiàn)算法 2。

算法2 改進(jìn)的Montgomery模約減算法

輸入：整數(shù) 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)對(duì)于 i從 0到 n-1，執(zhí)行：

①u(mài)i←aim′modb；

②A←A+uimbi。

(3)A←A/bn；

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

(5)返回(A)。

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

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

2.1 SOS模乘法算法

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

算法3SOS模乘算法

輸入：整數(shù) 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)對(duì)于 i從 0到 n-1，執(zhí)行：

①u(mài)i←aim′modb；

②A←A+uimbi。

(3)A←A/bn；

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

(5)返 回(A)。

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

2.2 CIOS模乘法算法

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

算法4 CIOS模乘法算法

輸 入 ： 整 數(shù) 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)對(duì)于 i從 0到 n-1，執(zhí)行：

①A←A+xiy；

②ui←a0m′modb；

③A←(A+uim)b。

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

(4)返回(A)。

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

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

2.3 FIPS模乘法算法

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

算法5 FIPS模乘法算法

輸 入 ： 整 數(shù) 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)對(duì)于 i從 0到 n-1，執(zhí)行：

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

(4)un←v0；

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

(6)返回(U)。

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

FIPS模乘法中，單精度乘法的次數(shù)和CIOS算法一樣，也是2n2+n。但在具體實(shí)現(xiàn)時(shí)的效率卻大大不同。可以根據(jù)算法，從理論上統(tǒng)計(jì)這兩種算法在乘法、加法、讀內(nèi)存、寫(xiě)內(nèi)存方面的差異。通過(guò)表1可以看出，F(xiàn)IPS算法的讀內(nèi)存、寫(xiě)內(nèi)存次數(shù)都遠(yuǎn)遠(yuǎn)高于CIOS算法。這是因?yàn)橛捎诩拇嫫鱾€(gè)數(shù)有限，在計(jì)算機(jī)程序中，F(xiàn)IPS算法中的三元組(v2v1v0)需要用內(nèi)存變量來(lái)存儲(chǔ)，使訪問(wèn)內(nèi)存所消耗的時(shí)間大大增加。但是如果在數(shù)字信號(hào)處理器(DSP)等微處理器上實(shí)現(xiàn)，將會(huì)使這些訪問(wèn)內(nèi)存所消耗的時(shí)間忽略不計(jì)。因此，在這類(lèi)硬件上實(shí)現(xiàn)FIPS算法，效率將大大提高。如果不考慮三元組(v2v1v0)訪問(wèn)內(nèi)存的次數(shù)，表1將修改為表2。表2中給出的數(shù)據(jù)可以明顯看出，在DSP等硬件上實(shí)現(xiàn)模乘法時(shí)，F(xiàn)IPS算法僅僅在加法次數(shù)上略多于CIOS算法，而讀寫(xiě)內(nèi)存的次數(shù)都大大減少，有著很大的優(yōu)勢(shì)，非常適合于RSA算法的硬件實(shí)現(xiàn)。

表1 CIOS算法與FIPS算法運(yùn)算次數(shù)統(tǒng)計(jì)表

表2 特定硬件上CIOS算法與FIPS算法運(yùn)算次數(shù)統(tǒng)計(jì)表

算法速度測(cè)試：

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

綜合運(yùn)用以上3個(gè)加速方案，對(duì)于一次模冪運(yùn)算Memodn所消耗的時(shí)間 (取50次的平均值)，對(duì)比結(jié)果如表3所示。

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

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

[2]涂航，劉玉珍，張煥國(guó)，等.智能卡操作系統(tǒng)中RSA算法的實(shí)現(xiàn)與應(yīng)用[C].第六屆中國(guó)密碼學(xué)學(xué)術(shù)會(huì)議論文集，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.