[發(fā)明專利]用于RSA算法的素?cái)?shù)生成的保護(hù)

有效

• 申請(qǐng)?zhí)枺?/td>: 201010188562.5
• 申請(qǐng)日: 2010-05-28
• 公開(kāi)（公告）號(hào): CN101902331A
• 公開(kāi)（公告）日: 2010-12-01
• 發(fā)明（設(shè)計(jì)）人: 瓊·德門(mén);弗蘭克·庫(kù)佩斯;吉勒斯·范艾思;皮埃爾-伊萬(wàn)·利阿德特
• 申請(qǐng)（專利權(quán)）人: 質(zhì)子世界國(guó)際公司;意法半導(dǎo)體(胡希)公司
• 主分類號(hào): H04L9/32
• 分類號(hào): H04L9/32;H04L9/30
• 代理公司: 北京安信方達(dá)知識(shí)產(chǎn)權(quán)代理有限公司 11262
• 代理人: 張春媛;閻娬斌

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

本發(fā)明一般涉及電子電路，尤其涉及一種執(zhí)行RSA類型非對(duì)稱加密算法的電路。本發(fā)明尤其涉及電子電路中素?cái)?shù)生成期間的保護(hù)，以防御旁路攻擊，例如，通過(guò)對(duì)電路功耗進(jìn)行統(tǒng)計(jì)分析(SPA-簡(jiǎn)單功耗分析)，或?qū)﹄娐返碾姶藕炚逻M(jìn)行統(tǒng)計(jì)分析，或防御故障植入攻擊。

本發(fā)明應(yīng)用于采用了使用素?cái)?shù)因子分解的算法的任何電子電路，尤其是芯片卡。

背景技術(shù)

RSA算法是最常用的非對(duì)稱加密算法(具有公鑰)中的一種。該算法用于加密/解密數(shù)據(jù)或?qū)?shù)據(jù)簽名以使它們能被認(rèn)證。它基于一對(duì)密鑰的使用，其中包括公鑰和私鑰。在加密/解密模式中，公鑰由發(fā)送器使用以加密將被秘密發(fā)送到接收器的數(shù)據(jù)，后者使用它的私鑰(或密鑰)解密所述數(shù)據(jù)。為進(jìn)行認(rèn)證，所述私鑰被所述發(fā)送器使用以簽名所述數(shù)據(jù)，而所述公鑰被所述接收器使用以認(rèn)證所述簽名。

所述公鑰相對(duì)廣泛的可被訪問(wèn)以使得所述加密數(shù)據(jù)的發(fā)送器或所述簽名數(shù)據(jù)的接收器能使用這些數(shù)據(jù)。然而，所述私鑰被保留在已經(jīng)生成所述一對(duì)密鑰的電路。所述一對(duì)密鑰的持有者可能直接將所述公鑰發(fā)送到對(duì)方以使得它能夠處理所述數(shù)據(jù)。

所述一對(duì)公鑰和私鑰的生成需要兩個(gè)相對(duì)不同的素?cái)?shù)“p”和“q”，具有相對(duì)大的大小(一般地，1,024或2,048比特)。這些素?cái)?shù)的乘積表示加密模數(shù)“n”。數(shù)字p和q被選擇，所以數(shù)字p-1和q-1關(guān)于數(shù)字“e”互質(zhì)，被稱為公共指數(shù)，后者與乘積的歐拉指示器(n)互質(zhì)。結(jié)果，存在一整數(shù)“d”滿足乘積e*d與1相對(duì)于模(n)來(lái)說(shuō)是同余的。對(duì)n和e表示公鑰，而對(duì)n和d表示私鑰。私秘指數(shù)d表示指數(shù)e的逆以(p-1)(q-1)為模。素?cái)?shù)p和q僅僅存在于包含所述私鑰的電路中。

RSA算法的魯棒性依賴于素?cái)?shù)p和q。為“破壞”基于公鑰的RSA算法，必須能夠?qū)?shù)字n進(jìn)行分解，從而獲得素?cái)?shù)p和q。一旦這個(gè)分解被獲知，私秘指數(shù)d能夠被從公共指數(shù)e中計(jì)算出來(lái)(d是根據(jù)計(jì)算e的逆以(p-1)(q-1)為模而得到)。顯然可以想到，通過(guò)使用足夠大小的模數(shù)n(尤其是1500比特)，在合理的時(shí)間內(nèi)，當(dāng)前算法不能分解數(shù)字n。

然而，將數(shù)字p和q引進(jìn)到電子電路或由該電路進(jìn)行它們的生成對(duì)于安全性是至關(guān)重要的，因?yàn)楹诳驮谠撾娐返幕顒?dòng)時(shí)刻發(fā)現(xiàn)這些數(shù)則使得他能夠分解數(shù)字n。

用于生成RSA密鑰的第一種技術(shù)包括在所述電子電路的外部生成這些密鑰。數(shù)字p和q被在用戶化階段被引進(jìn)到電子電路中。這種技術(shù)不能響應(yīng)于故障引入攻擊，因?yàn)槠渌雒荑€不是由真正的電子電路生成。

第二種已知技術(shù)包括使所述真正電子電路在安全環(huán)境(實(shí)際是在受保護(hù)的安裝中，具有預(yù)定的訪問(wèn))中生成所述素?cái)?shù)。根據(jù)這種技術(shù)，在所述素?cái)?shù)生成期間，攻擊也不成為問(wèn)題。

然而，更通常的情況是，電子電路被希望能夠在這樣的安全環(huán)境之外生成它們的RSA密鑰。例如，在一先前密鑰已經(jīng)被拋棄(密鑰可能被竊取)的情況下，這能夠重新生成新的密鑰。這種生成例如能被執(zhí)行在處于非安全環(huán)境中的電子電路的用戶化期間，或在第一次使用期間(例如，針對(duì)被用于簽名計(jì)算或電子標(biāo)識(shí)的電路)。根據(jù)電子證書(shū)的一個(gè)應(yīng)用實(shí)例，一旦它在它的持有者手中時(shí)，密鑰被希望能由所述證書(shū)中包含的電子芯片生成。因此，這個(gè)密鑰不能在證書(shū)認(rèn)證過(guò)程中已先被使用。

公共指數(shù)e可能是公鑰基礎(chǔ)結(jié)構(gòu)(PKI)的參數(shù)，并且對(duì)于所有的密鑰都是相同的。例如，在(ROM中的)電子電路的制造期間或是在(EEPROM中的)用戶化階段期間可以被引入進(jìn)所述電子電路中。

公共指數(shù)e可能還被由電子電路生成，例如通過(guò)選擇隨機(jī)數(shù)，并且可能被發(fā)送到它必須與之進(jìn)行通信的元件那里。

公鑰(公共指數(shù)和加密模數(shù))因而被所述接收器(簽名)獲知，或被所述發(fā)送器(加密)獲知，或被持有所述私鑰的電子電路另外發(fā)送(對(duì)于每個(gè)事務(wù)一次全部完成)。所述公鑰必須進(jìn)一步被驗(yàn)證。

大素?cái)?shù)的生成在時(shí)間和計(jì)算方面消耗很大。特別的，所謂的素性測(cè)試，能夠證實(shí)數(shù)字的素?cái)?shù)的特征有效或無(wú)效，其一般執(zhí)行需要大量計(jì)算的模冪運(yùn)算(例如，所說(shuō)的Miller-Rabin素性測(cè)試)。這就是為什么它被希望僅僅為已經(jīng)成功通過(guò)關(guān)于相對(duì)較小的素?cái)?shù)的測(cè)試的候選數(shù)字進(jìn)行這樣的測(cè)試的原因。這樣的測(cè)試相應(yīng)于由相對(duì)較小的素?cái)?shù)進(jìn)行除法，或與素?cái)?shù)表進(jìn)行對(duì)比。例如，米勒-拉賓(Miller-Rabin)測(cè)試可能被通過(guò)一小基數(shù)執(zhí)行(例如2)，或一最大公約數(shù)計(jì)算可能被執(zhí)行(例如，增加字節(jié)模數(shù)255以獲得比255小的結(jié)果，然后用255計(jì)算該結(jié)果的最大公約數(shù)-如果不是1，一單獨(dú)的測(cè)試能告知所述數(shù)字對(duì)于255的3個(gè)因子是不可除的，即3。5和17)。