[發(fā)明專利]運(yùn)算電路和運(yùn)算方法

有效

• 申請?zhí)枺?/td>: 01143738.3
• 申請日: 2001-12-19
• 公開（公告）號: CN1366234A
• 公開（公告）日: 2002-08-28
• 發(fā)明（設(shè)計）人: 高野光司;佐藤證
• 申請（專利權(quán)）人: 國際商業(yè)機(jī)器公司
• 主分類號: G06F9/30
• 分類號: G06F9/30
• 代理公司: 北京市柳沈律師事務(wù)所
• 代理人: 黃小臨,王志森

?????????????????????????技術(shù)領(lǐng)域

本發(fā)明涉及一種運(yùn)算(arithmetic)電路和運(yùn)算方法，具體地說，涉及一種用于公開密鑰密碼系統(tǒng)的優(yōu)選的模乘法速度提高。

?????????????????????????背景技術(shù)

對于信息傳送，為保持信息的機(jī)密性并且為了數(shù)字認(rèn)證目的，采用公開密鑰密碼術(shù)(非對稱密碼術(shù))。公開密鑰密碼術(shù)是一種用于信息傳送的密碼系統(tǒng)，一種用于使用由公開密鑰和保密密鑰組成的一對密鑰傳送信息的密碼術(shù)方法。發(fā)送者使用接收者的公開密鑰加密明文，并且當(dāng)解碼密文時，使用只有接收者知道的保密密鑰。按照公開密鑰密碼術(shù)，由于與共用密鑰密碼術(shù)(對稱密碼術(shù))不同，不需要通信者共享和采用單一的共用密鑰，并且由于公開密鑰的廣泛公開不牽涉明顯的風(fēng)險，與不限數(shù)量的人通信時保持秘密是可能的。此外，當(dāng)公開密鑰密碼術(shù)采用來進(jìn)行數(shù)字認(rèn)證或準(zhǔn)備數(shù)字簽名時，可以建立不熟悉的人的可信度和可靠度。因此，可以迅速地斷定，對于通過諸如因特網(wǎng)這樣的通信系統(tǒng)支持的網(wǎng)絡(luò)社會，以及對于進(jìn)入了這樣的網(wǎng)絡(luò)社會的商業(yè)交易來說，公開密鑰密碼術(shù)是必不可少的技術(shù)。

RSA(Rivest-Shamir-Asleman?algorithm，里韋斯特-沙米爾-阿德萊曼算法)是最流行的公開密鑰密碼術(shù)。由RSA提供的安全是基于對于一個很大的整數(shù)的離散對數(shù)問題的，或者基于在素數(shù)分解中遇到的困難。例如，通過使用公開密鑰(e，n)按照關(guān)系式C＝M^e(mod?n)(M由小于整數(shù)n的塊形成)，將明文M加密成密文C。為了解碼密文C，必須執(zhí)行離散對數(shù)問題(使用a、y和p，獲得滿足y＝a^x(mod?p)的x)，并且必須求解由O(2^SQRT(log?n))所代表的量(SQRT是用于提供平方根的函數(shù))。當(dāng)整數(shù)n是一個具有至少等于或者大于512位，最好是等于或者大于1024位長度的值時，在實用時間內(nèi)破譯密碼是困難的。

可是，當(dāng)使用與公開密鑰(e，n)具有下面關(guān)系的保密密鑰(d，n)時，

ed(mod?lcm(p-1，q-1))＝1，n＝pq(其中p和q是足夠大的素數(shù))，

通過使用關(guān)系式M＝C^d(mod?n)(其中l(wèi)cm(a，b)提供a和b的最小公倍數(shù))，可以容易地獲得明文M。

通過使用指數(shù)的二進(jìn)制表示，重復(fù)模平方運(yùn)算和模乘法運(yùn)算，使得對于模乘法運(yùn)算要求指數(shù)是最多兩倍位長度。

可是，上述模乘法運(yùn)算甚至要求比對稱密碼術(shù)比如DES(Data?EncryptionStandard，數(shù)據(jù)加密標(biāo)準(zhǔn))所要求的還要多的計算量。因此，需要準(zhǔn)備和使用一種盡可能有效率的算法。

蒙特高瑪俐(Montgomery)乘法方法是一種用于增加上面模冪運(yùn)算中模平方運(yùn)算和模乘法運(yùn)算的速度的方法。正如皮特·L·蒙特高瑪俐(Peter?L.Montgomery)在“計算數(shù)學(xué)”，1985年4月44卷第170號，第519-522頁的“無試除的模乘法”(Mathematics?of?computations，Vol.44，No.170?April?1985，pp.519-522“Modular?Multiplication?Without?Trial?Division”)中所描述那樣，蒙特高瑪俐乘法方法是在要求的計算比為其反復(fù)執(zhí)行減法的除法所要求的少的同時，通過重復(fù)加法、乘法和移位運(yùn)算來執(zhí)行模乘法運(yùn)算的一種方法。蒙特高瑪俐乘法的基本計算部分P≡XYR^-1(mod?n)使用偽碼1.x被表示在下面。應(yīng)注意，在P≡XYR^-1(mod?n)中R＝(2^r)^m和N≡-n^-1(mod?2^r)。此外，應(yīng)注意，在偽碼中行號被加到每行的左面(下文中使用這個原則)。

(1.1)?????????????p＝0；

(1.2)?????????????for(i＝0；i＜m；i++){

(1.3)????????????????t＝(p₀+x_iy₀)N(mod?2^r)；

(1.4)????????????????P＝(P+x_iY+t·n)/2^r；

(1.5)?????????????}

(1.6)??????????if(P≥n)??P＝P-n；