RSA算法的定時(shí)攻擊及其防范措施

計(jì)國民

（滁州職業(yè)技術(shù)學(xué)院，安徽 滁州 239000）

一、引言

RSA算法是以其發(fā)明人MIT的Ronald.L.Rivest，A－di.Shamir和Leonard.M.Adleman三人名字的首字母來命名的，是公鑰密碼體制中使用最廣泛的一種安全密碼體制算法。其安全性是基于整數(shù)的因子分解困難性的。RSA算法的私鑰(d,n)，公鑰(e,n)，要求滿足條件ed=1mod φ(n)，其中n為兩個(gè)大素?cái)?shù)p和q的積，即n=p*q。

假設(shè)明文和密文分組分別用M、C來表示，RSA算法加密和解密過程為：

（1）加密：C=Memod n

（2）解密：M=Cdmod n

RSA算法的數(shù)字簽名過程：

（1）簽名過程：計(jì)算消息M的散列值H(M)，用簽名者的私鑰(d,n)計(jì)算簽名s=(H(M))dmodn，發(fā)送消息和簽名(M,s)。

（2）驗(yàn)證過程：利用簽名者的公鑰(e,n)計(jì)算

h=semod n,利用M計(jì)算其散列值H(M)，比較h=H(M),如果成立，表示簽名有效。否則，該簽名無效。

二、基本思想

根據(jù)RSA算法的描述，在對(duì)消息進(jìn)行處理時(shí)，都要用到冪運(yùn)算，即F=abmod n，這就給定時(shí)攻擊留下了一個(gè)機(jī)會(huì)。所謂的定時(shí)攻擊是由密碼分析家P.C.Kocher于1996年提出，該攻擊與常規(guī)攻擊方式完全不同，其僅僅使用密文進(jìn)行攻擊，所以通常被安全專家稱之為“有創(chuàng)意的攻擊”。定時(shí)攻擊的基本思想為：要計(jì)算F=abmod n,其中b用二進(jìn)制表示為b=(bk…b1bo)2，即為k比特長(zhǎng)度。那么程序可以用如下偽代碼實(shí)現(xiàn)（其中m為臨時(shí)變量）：

從上面的算法可以看出，如果指數(shù)的當(dāng)前比特為1時(shí)（即b1=1），就要運(yùn)算額外的模運(yùn)算(d×a)mod n，這必將花費(fèi)一定的計(jì)算時(shí)間，從而導(dǎo)致運(yùn)算速度減慢。對(duì)于一些a和d來說，該模運(yùn)算是相當(dāng)?shù)穆粽吆苋菀拙湍苷莆者@些值。由此，攻擊者可以通過觀察系統(tǒng)處理上述函數(shù)所花費(fèi)的時(shí)間來判斷，當(dāng)很慢時(shí)指數(shù)比特很可能就是1，否則就是0，利用此原理就可以得到整個(gè)指數(shù)。也就是說可以得出其私鑰和相應(yīng)的公鑰，從而會(huì)導(dǎo)致該算法的不安全。

三、防范措施

要克服RSA算法中的定時(shí)攻擊，可以采取以下三種方法：

（一）對(duì)密文進(jìn)行盲化處理

所謂的盲化處理，就是為了避免逐位運(yùn)算，在其取冪運(yùn)算之前，先產(chǎn)生一個(gè)隨機(jī)數(shù) t，要求0＜t≤(n-1)，然后對(duì)密文進(jìn)行盲化， 分別計(jì)算C＇=c(te)mod n，M＇=(C＇)dmod n，M=(M＇t-1)mod n。 這樣，就可以防止攻擊者了解計(jì)算機(jī)中所處理的數(shù)據(jù)，從而防止了定時(shí)攻擊的逐位分析。

（二）隨機(jī)延長(zhǎng)冪運(yùn)算時(shí)間

由于定時(shí)攻擊主要是根據(jù)逐位運(yùn)算時(shí)間的長(zhǎng)短來得到該位的值是0還是1，因此，在取冪運(yùn)算時(shí)可以增加一個(gè)隨機(jī)延時(shí)來調(diào)整其運(yùn)算時(shí)間，從而迷惑攻擊者判斷真正的運(yùn)算時(shí)間。

（三）固定取冪運(yùn)算時(shí)間

除了隨機(jī)延長(zhǎng)冪運(yùn)算時(shí)間外，也可以采用固定冪運(yùn)算時(shí)間，也就是說保證所有取冪運(yùn)算操作在返回結(jié)果之前都花費(fèi)同樣多的時(shí)間，這樣攻擊者就無法得到哪一位運(yùn)算時(shí)間需要的時(shí)間是長(zhǎng)還是短，從而無法判斷是0還是1。

四、建議

RSA算法的安全性不僅是要對(duì)其安全攻擊進(jìn)行防范，而且還要對(duì)各種不安全的因素進(jìn)行防范，這些因素包括以下幾個(gè)方面：

（一）參數(shù)的選擇要合理

RSA算法中所涉及到的主要參數(shù)包括 p、q、e和d四個(gè)。對(duì)于p和q來說，要求為強(qiáng)素?cái)?shù)并且足夠大，p與q之間的差值要大，(p-1)與(q-1)的最大公因子要小。參數(shù)e的值不可太小，選擇的e在mod φ(n)中的階數(shù)i要求達(dá)到(p-1)(q-1)/2，即滿足 ei=1 mod φ(n)。 選擇參數(shù)d時(shí)，應(yīng)使d>n1/4。

（二）在RSA數(shù)字簽名算法中，要使用散列函數(shù)

在RSA數(shù)字簽名中，使用散列函數(shù)可以使數(shù)據(jù)的完整性得到保護(hù)，在對(duì)簽名進(jìn)行驗(yàn)證時(shí)，其驗(yàn)證h=H(M)，如果消息M在傳輸過程中被篡改或發(fā)生其他變化，其散列值H(M)也會(huì)發(fā)生變化。如果不使用散列函數(shù)，那么在簽名驗(yàn)證時(shí)，僅驗(yàn)證h=M，其完整性無法得到保證。

（三）明文的熵要盡可能的大

明文的熵越大，就會(huì)使得在已知密文的情況下，要猜測(cè)明文就越接近于完全隨機(jī)等概情況。如果明文的熵值比較低，可以在明文分組中加入一個(gè)隨機(jī)數(shù)t來處理。

（四）不要使用公共模

使用公共?？梢允沟妹荑€管理簡(jiǎn)單，其存儲(chǔ)空間相應(yīng)減小，重新分配密鑰問題也變得比較簡(jiǎn)單，但其安全性也相應(yīng)地變得脆弱，建議不要使用公共模。

[1]賴溪松，韓亮，張真誠．計(jì)算機(jī)密碼學(xué)及其應(yīng)用[M]．北京：國防工業(yè)出版社，2001：84-105.

[2]呂述望，范修斌，張如文．密碼學(xué)函數(shù)迭代原理信息論分析[J]．電子學(xué)報(bào)，2002，(2)：1511-1513.