第8章公鑰密碼體制和RSA算法8.1公鑰密碼體制8.2RSA數(shù)學(xué)基礎(chǔ)8.3RSA算法8.4RSA安全

8.1公鑰密碼體制

8.1.1簡(jiǎn)介在對(duì)稱密碼體制中,收發(fā)雙方需要事先共享一個(gè)用于加密和解密的密鑰,加密和解密用的也是同一個(gè)密鑰。公鑰密碼體制則使用兩個(gè)密鑰,因此也稱為非對(duì)稱密碼體制。這兩個(gè)密鑰當(dāng)中,一個(gè)是公開(kāi)的稱為公鑰(PublicKey),另一個(gè)是只有用戶自己知道的稱為私鑰(PrivateKey)。公鑰和私鑰都可以用于加密和解密,一個(gè)密鑰加密可以用另一個(gè)密鑰解密。

公鑰密碼體制的模型如圖8.1所示,由六個(gè)部分組成,分別是明文、加密算法、公鑰、私鑰、密文、解密算法。8.1公鑰密碼體制。圖8.1公鑰密碼體制模型

公鑰密碼體制的主要應(yīng)用分以下三類:

(1)加密/解密,發(fā)送方用接收方的公鑰對(duì)信息加密。

(2)數(shù)字簽名,發(fā)送方用自身的私鑰對(duì)消息“簽名”。

(3)密鑰交換,通信雙方通過(guò)交換一些信息計(jì)算出共同的密鑰或者利用公鑰加密共享密鑰實(shí)現(xiàn)密鑰交換和分發(fā)。

8.1.2理論基礎(chǔ)

根據(jù)8.1.1對(duì)公鑰密碼體制的介紹,可以總結(jié)以下對(duì)公鑰密碼的要求:

·收發(fā)雙方產(chǎn)生一對(duì)密鑰在計(jì)算上是容易的。

·已知公鑰和明文消息

M,發(fā)送方

A

產(chǎn)生相應(yīng)的密文在計(jì)算上是容易的,即

·接收方

B使用私鑰對(duì)接收的密文解密以恢復(fù)明文在計(jì)算上是容易的,即

·已知公鑰

KPUB,攻擊者要確定私鑰

KPRI

在計(jì)算上是不可行的。

·已知公鑰

KPUB

和密文C,攻擊者要恢復(fù)明文

M

在計(jì)算上是不可行的。

·對(duì)于部分公鑰密碼應(yīng)用,還應(yīng)滿足加密和解密函數(shù)的順序可以交換,即

事實(shí)上,要滿足

上

述

條

件

即

是

要

找

到

一

個(gè)

單

向

陷

門

函

數(shù)(One-wayTrapdoorFunc-tion)。公鑰密碼的理論基礎(chǔ)是單向陷門函數(shù)。給定任意兩個(gè)集合X

和Y,對(duì)每一個(gè)x

屬于

X,每一個(gè)y

屬于Y。單向陷門函數(shù)滿足下列性質(zhì):

(1)若k

和x已知,求y=fk(x)容易計(jì)算;

(2)若k

和y

已知,求x=fk-1(y)容易計(jì)算;

(3)若y已知但k

未知,則求x=fk-1(y)是不可行的。k

就相當(dāng)于我們的解密密鑰,這個(gè)秘密信息稱為陷門。陷門使得單向函數(shù)只能夠在特定的情況下逆轉(zhuǎn)。

以上計(jì)算中容易是指一個(gè)問(wèn)題可以在輸入長(zhǎng)度的多項(xiàng)式時(shí)間內(nèi)得到解決,若輸入長(zhǎng)度為n

位,則計(jì)算的時(shí)間復(fù)雜度為n

a(一個(gè)多項(xiàng)式表達(dá)式),a

為常數(shù)。

計(jì)算上不可行是指解決一個(gè)問(wèn)題所需時(shí)間比輸入規(guī)模的多項(xiàng)式增長(zhǎng)更快,若輸入長(zhǎng)度是n

位,則計(jì)算時(shí)間復(fù)雜度是2n

。

理論上不能證明單向函數(shù)一定存在,但實(shí)際上只要函數(shù)的單向性足夠在工程中應(yīng)用就行。目前最重要的未被破解的單向陷門函數(shù)有大數(shù)分解問(wèn)題和離散對(duì)數(shù)問(wèn)題。

(1)大數(shù)分解問(wèn)題:大素?cái)?shù)的乘積容易計(jì)算(p×q→n),而大合數(shù)的因子分解卻很難(n→p×q)。

(2)有限域上的離散對(duì)數(shù)問(wèn)題:有限域上大素?cái)?shù)的冪乘容易計(jì)算(ab

→c),而對(duì)數(shù)計(jì)算困難(logac→b)。

例如,假定n

為兩個(gè)大素?cái)?shù)p

和q的乘積,b

為一個(gè)正整數(shù),那么定義以下函數(shù)f:Zn→Zn

被認(rèn)定是單向的。

如果gcd(b,?(n))=1,那么事實(shí)上f

就是RSA加密函數(shù)。

單向和陷門單向函數(shù)的概念是公鑰密碼學(xué)的核心,可以說(shuō),公鑰密碼體制的設(shè)計(jì)就是陷門單向函數(shù)的設(shè)計(jì)。

8.2RSA數(shù)學(xué)基礎(chǔ)

8.2.1模運(yùn)算模運(yùn)算的含義就是計(jì)算余數(shù),其在數(shù)論和密碼學(xué)中有著廣泛的應(yīng)用。對(duì)某個(gè)模數(shù)(Modulus)計(jì)算其余數(shù)稱之為模算術(shù)(ModularArithmetic)。模算術(shù)使得整數(shù)達(dá)到特定值時(shí)會(huì)“折返”回來(lái),確保其計(jì)算結(jié)果在某個(gè)范圍之內(nèi),這個(gè)特定值就是模數(shù)。

典型的模運(yùn)算就是時(shí)鐘算術(shù)。時(shí)鐘表盤都是模數(shù)等于12的模算術(shù),其中包含12個(gè)值,對(duì)模數(shù)12的計(jì)算結(jié)果(余數(shù))為0,1,2,…,11。如圖8.2所示,時(shí)針剛開(kāi)始位于0點(diǎn),過(guò)了9個(gè)小時(shí)以后到達(dá)(0+9)mod12=9點(diǎn)的位置,再過(guò)4個(gè)小時(shí)到達(dá)(9+4)mod12點(diǎn)的位置。

圖8.2時(shí)鐘算術(shù)(模12)

【例8-1】

選取a=7∈Z,b=30∈Z,n=23∈N+,因?yàn)?/p>

amodn=bmodn=7,所以a與b

模n同余,表示為a≡bmodn。

根據(jù)同余定義和模運(yùn)算法則,有以下關(guān)系式成立:

設(shè)n,t∈N+,a≡bmodn,c≡bmodn,k∈Z。

·(a+c)≡(b+d)modn,特別地有a+k≡b+k(modn);

·ac≡bd

modn,特別地有ak≡bk

modn,以及at

≡btmodn;

·若m

為非零整數(shù),則a≡bmodn?am≡bmmod

mn;

·若m|n(即m

整除n),則a≡bmodn。特別地,若l∈N+,

a≡b(modnl),則有a≡bmodn;

·若ak≡bkmodn,則其中(k,n)表示k

與n

的最大公約數(shù)。特別地,若(k,n)=1,則a≡bmod

n;·若m∈N+,?1≤i≤m,ni∈N+,則有

其中,[n1,n2,…,nm]表示n1,n2,…,nm

的最小公倍數(shù)。

【例8-3】a∈{1,2,3,4,5,6},依次計(jì)算a

取1、2、3、4、5、6時(shí)模7的逆。

解:當(dāng)a=1時(shí),顯然,1×1≡1×1≡1mod7,所以1-1=1(mod7);

當(dāng)a=2時(shí),依次代入1、2、3、4…到方程2x≡1mod7,發(fā)現(xiàn)代入4時(shí)滿足方程

2×4≡4×2≡1(mod7)

所以

2-1=4(mod7)

同理,可以找到模7意義下a

對(duì)應(yīng)的逆元,如表8.1所示。

8.2.2歐幾里得算法

歐幾里得算法又稱輾轉(zhuǎn)相除法,用于快速計(jì)算出兩個(gè)整數(shù)a、b

的最大公約數(shù),表示為gcd(a,b)。當(dāng)gcd(a,b)=1時(shí),則稱a

與b

互素(或稱互質(zhì))。

歐幾里得算法的基本思想如下,假設(shè)a>b,則可以設(shè)a=qb+r,其中a、b、q、r

都是整數(shù),且r<b,則gcd(a,b)=gcd(b,r),即gcd(a,b)=gcd(b,a%b)。

8.2.3擴(kuò)展歐幾里得算法

擴(kuò)展歐幾里得算法是指對(duì)于不完全為0的非負(fù)整數(shù)a、b,必然存在整數(shù)對(duì)x、y,使得gcd(a,b)=ax+by,其中g(shù)cd(a,b)是a、b的最大公約數(shù)。擴(kuò)展歐幾里得算法可以計(jì)算出x

和y

的值。對(duì)于gcd(a,n)=ax+ny,如果gcd(a,n)=1,則可以得到同余方程ax≡1modn,且方程只有唯一解,計(jì)算出的x

為a

模n的逆元。

8.2.4素

數(shù)

設(shè)p

為大于1的正整數(shù),如果p

除1和它本身外沒(méi)有其他正因數(shù),則稱p

為素?cái)?shù)(或質(zhì)數(shù)),否則稱為合數(shù)。公約數(shù)只有1的兩個(gè)數(shù),稱互素?cái)?shù)(也稱互質(zhì)數(shù))。

素?cái)?shù)相關(guān)性質(zhì)有:

·任何大于1的自然數(shù),要么本身是素?cái)?shù),要么可以分解為幾個(gè)素?cái)?shù)之積,且這種分解是唯一的。

·若p

為素?cái)?shù),a

是小于p

的正整數(shù),則ap-1modp=1。

·若p

為素?cái)?shù),n∈Z,則

·若p為素?cái)?shù),a,b∈Z,p|ab,則p|a

或p|b。

·任意兩個(gè)素?cái)?shù)一定構(gòu)成互素?cái)?shù)。

·較大數(shù)是素?cái)?shù)的兩個(gè)數(shù)一定是互素?cái)?shù)。

·如果一個(gè)素?cái)?shù)不能整除另一個(gè)合數(shù),那么這兩個(gè)數(shù)為互素?cái)?shù)。

·相鄰的兩個(gè)自然數(shù)或相鄰的兩個(gè)奇數(shù)都是互素?cái)?shù)。

【例8-6】

判斷101和301是否為素?cái)?shù)?

解:因?yàn)槌?和101本身再也找不到101的其他正因數(shù),所以101是素?cái)?shù);除了1和301本身,301還能找到因數(shù)7和43,所以301不是素?cái)?shù),而是合數(shù)。

2)基于費(fèi)馬小定理的費(fèi)爾馬素性檢測(cè)算法

費(fèi)爾馬素性檢測(cè)算法指對(duì)于奇整數(shù)n,若任取一個(gè)整數(shù)2≤a≤n-2,gcd(a,n)=1,使得an-1mod

n=1,則n至少有一半的概率為素?cái)?shù)。

由于卡邁克爾(Carmichael)數(shù)的存在,費(fèi)爾馬素性檢測(cè)算法可能會(huì)失效?？ㄟ~克爾數(shù)定義如下:對(duì)于合數(shù)n,如果對(duì)于所有與n

互質(zhì)的正整數(shù)b,都有同余式bn-1≡1modn

成立,則稱合數(shù)n

為卡邁克爾數(shù)。所以,卡邁克爾數(shù)是滿足費(fèi)馬小定理的強(qiáng)偽素?cái)?shù),可以使用后續(xù)的米勒

拉賓算法檢測(cè)。

【例8-8】

判別整數(shù)n=277可能為素?cái)?shù),并指出其可能性的概率。

解:取安全參數(shù)k=4。

3)基于強(qiáng)偽素?cái)?shù)的米勒-拉賓(Miller-Rabin)算法

米勒-拉賓算法是經(jīng)典的大數(shù)素性測(cè)試算法,能夠有效驗(yàn)證強(qiáng)偽素?cái)?shù),算法的實(shí)現(xiàn)基于素?cái)?shù)的兩個(gè)性質(zhì)。

性質(zhì)1:如果p是素?cái)?shù),a

是小于p的正整數(shù),則a2mod

p=1當(dāng)且僅當(dāng)amod

p=1或者a

modp=-1modp=p-1。一

方

面

由

模

運(yùn)

算

法

則:(amodp)(a

modp)=a2

modp,因此,如果a

modp=±1,則有a2

modp=1;反過(guò)來(lái),如果a2

modp=1,則有a

modp=±1。

性質(zhì)2:設(shè)p

是大于2的素?cái)?shù),則該素?cái)?shù)可以表示為p-1=2

kq,其中整數(shù)k>0,q為奇數(shù)。設(shè)a

是整數(shù)且1<a<p-1,則下面兩個(gè)條件之一成立。

(1)aq

模p

和1同余,即aq≡1modp。

(2)在整數(shù)aq,a2q,…,a2(k-1)q

里存在一個(gè)數(shù),該數(shù)和-1模p時(shí)同余,即存在一個(gè)j(1≤j≤k)滿足a2(j-1)q

modp=-1mod

p=p-1,或a2(j-1)q≡-1mod

p。

基于上述性質(zhì),有以下的米勒-拉賓素?cái)?shù)檢測(cè)算法(奇整數(shù)n≥3):

·找出滿足等式n-1=2kq

的整數(shù)k、q,其中k>0,q

是奇數(shù)。

·隨機(jī)選取整數(shù)a,其中1<a<n-1。

·判斷aqmodn

的值。若aqmodn=1,則n

可能是素?cái)?shù)。

·繼續(xù)判斷a2jqmodn

的值,其中j是按序取值從0到s的整數(shù)(其中s≤k,一般取6)。若存在a2jqmodn=n-1,則n

可能是素?cái)?shù);否則,n

是合數(shù)。

2.素?cái)?shù)生成

要得到一個(gè)素?cái)?shù),最通用的方法就是隨機(jī)生成一個(gè)整數(shù)作為候選素?cái)?shù),然后對(duì)其進(jìn)行素性檢測(cè),檢測(cè)通過(guò)就可以得到想要的素?cái)?shù)。素?cái)?shù)生成過(guò)程如圖8.3所示。圖8.3素?cái)?shù)生成過(guò)程

8.2.5歐拉函數(shù)和歐拉定理

對(duì)于給定正整數(shù)n,小于n且與n互素的正整數(shù)的個(gè)數(shù)稱為n例如,對(duì)于?(15),可以先列出小于15且與15互素的正整數(shù)如下:

1,2,4,7,8,11,13,14

由上可知共有8個(gè)數(shù)與15互素,因此?(15)=8

【例8-10】

計(jì)算200的歐拉函數(shù)。

解:對(duì)200進(jìn)行標(biāo)準(zhǔn)素因數(shù)分解為200=23×52,根據(jù)歐拉函數(shù)計(jì)算公式

基于上述歐拉函數(shù)的定義,對(duì)應(yīng)的歐拉定理如下:

若整數(shù)a和n

互素,則滿足

費(fèi)馬小定理的定義如下:

若p

是素?cái)?shù),a

是正整數(shù)且不能被p

整除,則

另外,費(fèi)馬小定理可以在a

與p

互素的前提下快速計(jì)算出屬于剩余類環(huán){1,2,…,p-1}中的a

模p的逆元,即

【例8-12】

計(jì)算2100除以13的余數(shù)。

解:

8.2.6中國(guó)剩余定理

中國(guó)剩余定理適用于求解某類特定同余方程組。設(shè)正整數(shù)m1,m2,…,mk

兩兩互素(即當(dāng)i≠j時(shí),gcd(mi,mj)=1),那么對(duì)于任意k個(gè)整數(shù)a1,a2,…,ak,考慮如下同余方程組:

在模下必有解,且解的個(gè)數(shù)為1。事實(shí)上,該解是:

其中Mi-1

是滿足MiMi-1≡1modmi的一個(gè)整數(shù)。

中國(guó)剩余定理的求解公式可以按以下方式來(lái)理解。對(duì)于第一項(xiàng)

M1M1-1a1,對(duì)

m1

取模后為a1,而對(duì)其他的mi

取模應(yīng)當(dāng)為0,因此,把a(bǔ)1和

M1=m2×m3×…×mk

相乘,同時(shí)為了消除上述

M1

的影響,又乘上了

M1

-1。

【例8-13】

求解同余方程59x≡27mod91。

解:因?yàn)?1=7×13,所以該同余方程等價(jià)于下面的同余方程組

對(duì)于上述方程組,由于7、13互素,直接運(yùn)用中國(guó)剩余定理來(lái)求解,此時(shí)有:

從而,由中國(guó)剩余定理得方程組的解為

8.3RSA算

法

8.3.1密鑰生成

RSA公鑰加密算法有兩個(gè)密鑰,分別是公鑰和私鑰,其產(chǎn)生分為以下步驟。

(1)隨機(jī)選擇兩個(gè)不同的大素?cái)?shù)

p

和q,計(jì)算模數(shù)n=p×q;

(2)根據(jù)歐拉函數(shù),計(jì)算?(n)=?(p)·?(q)=(p-1)×(q-1);

(3)選擇一個(gè)小于?(n)的指數(shù)e,使e和?(n)互素,并計(jì)算e關(guān)于?(n)的逆元d:

ed≡1

mod?(n)

(4)(n,e)是公鑰,(n,d)是私鑰。

完整的公鑰、私鑰生成過(guò)程如圖8.4所示。圖8.4RSA密鑰生成過(guò)程

【例8-14】RSA密鑰產(chǎn)生舉例

(1)選取素?cái)?shù)p=53和q=37(實(shí)際應(yīng)用中,這兩個(gè)素?cái)?shù)越大就越難破解),計(jì)算模數(shù)n=pq=1961。

(2)根據(jù)歐拉函數(shù),計(jì)算?(n)=(p-1)(q-1)=1872。

(3)選取1<e=61<?(n),因?yàn)間cd(e,?(n))=1,故e滿足要求。計(jì)算e模?(n)的逆元d,得到d=1381。

(4)所以公鑰是(1961,61),私鑰是(1961,1381)。

另外,可以導(dǎo)入rsa庫(kù),調(diào)用rsa.newkeys(nbits)函數(shù)直接生成RSA公鑰和私鑰,示例代碼如下:

8.3.2消息加解密

RSA對(duì)消息進(jìn)行加密之前,需要將消息以一個(gè)雙方約定好的格式轉(zhuǎn)化為一個(gè)小于模數(shù)n,且與n

互質(zhì)的整數(shù)明文

m。如果消息太長(zhǎng),可以將消息分為幾塊,對(duì)每一塊分別進(jìn)行加密。

利用公鑰(n,e)對(duì)明文m

進(jìn)行加密:

利用私鑰(n,d)對(duì)密文c進(jìn)行解密:

圖8.5給出了模數(shù)n=3127,公鑰加密指數(shù)e=3、解密指數(shù)d=2011、消息m=89(大寫字母“Y”)時(shí)的加密解密過(guò)程。圖8.5RSA加解密

8.3.3正確性證明

證明

RSA加解密的正確性,即證明:

已知ed≡1

mod?(n),那么ed=k?(n)+1(其中k

為整數(shù)),也就是證明

在此分兩種情況證明:

第一種情況,gcd(m,n)=1,那么根據(jù)歐拉定理可得

因此原式成立。

第二種情況,gcd(m,n)≠1,那么m

必然是p

或者q的倍數(shù),并且

m小于n。假設(shè)

那么x必然小于q,又由于q是素?cái)?shù),根據(jù)歐拉定理可得

8.3.4參數(shù)之間的安全關(guān)系

由上述對(duì)RSA加解密算法的介紹,可以知道RSA相關(guān)參數(shù)有p、q、n、?(n)、e、d、m、c。這些參數(shù)同RSA的安全息息相關(guān),下面從以下四個(gè)方面探討參數(shù)之間的約束關(guān)系以及對(duì)RSA算法安全性的影響。

1.已知n

和?(n)的情況下,n

是否能容易被因子分解

根據(jù)密鑰產(chǎn)生過(guò)程可知,n=p×q,?(n)=(p-1)(q-1)=n-p-q+1,結(jié)合這兩個(gè)等式很容易解出p和q,就能對(duì)n

進(jìn)行因子分解。

2)模平方根方法

3.已知n

和d,能否得到e

根據(jù)ed≡1

mod?(n)公式,要計(jì)算出e,需要先知道?(n),要知道?(n),需要知道p和q

的值,而n=p×q,所以只有n

可以進(jìn)行因素分解的情況下才能得到?(n)的值。

4.已知d

和?(n),能否得到e

根據(jù)ed≡

mod?(n)公式知道,e和d

對(duì)模?(n)互逆,所以對(duì)d

進(jìn)行模?(n)的逆運(yùn)算就可得到e。

8.4RSA安

全

RSA的安全性依賴于整數(shù)的分解難題。一般認(rèn)為只要模數(shù)n

的長(zhǎng)度達(dá)到一定要求并且參數(shù)p、q

和e選取恰當(dāng)?shù)脑?RSA密碼算法還是相當(dāng)安全的。但是,在某些情況下,如參數(shù)選取不當(dāng)或者泄露某些重要信息時(shí),就可能突破RSA密碼獲取密鑰或者明文信息。

8.4.1模數(shù)分解攻擊

既然RSA密碼的安全性是基于模數(shù)n=pq

難以分解,那么自然而然的如果能找到計(jì)算上可行的分解方法將有助于破解RSA密碼。本節(jié)討論某些特定情形下的模數(shù)n

分解問(wèn)題,例如模數(shù)n有小的素因子、兩個(gè)因子相差不大、模數(shù)n長(zhǎng)度不夠、兩組模數(shù)n1

和n2有公因子等。常見(jiàn)的模數(shù)分解攻擊算法如圖8.6所示。

圖8.6模數(shù)分解算法

2.Pollard＇s

p

-1方法

Pollard＇s

p-1方法由Pollard于1974年提出,適用于模數(shù)n存在一個(gè)素因子較小的情況。其基本思想主要有以下兩點(diǎn):

(1)找到一個(gè)數(shù)與模數(shù)n

有公因子。

分解模數(shù)n就是找到一個(gè)因子,如果能找到另一個(gè)數(shù)x和模數(shù)n

有公因子,就可以借助最大公約數(shù)gcd(x,n)快速找到模數(shù)n

的一個(gè)因子。數(shù)x

的查找可以通過(guò)費(fèi)馬小定理

ap-1mod

p=1來(lái)實(shí)現(xiàn)。設(shè)素?cái)?shù)p|n,那么任取一整數(shù)2≤a≤n-2,則有p|(ap-1-1),因此,p

既是n

的因子,也是ap-1-1的因子,計(jì)算gcd(ap-1-1,n)就能找到模數(shù)n

的一個(gè)素因子。

(2)p

未知情況下構(gòu)造出該數(shù)。

假設(shè)p-1的因子都很小,都不大于最大素因子

B,我們稱這個(gè)整數(shù)為

B

光滑數(shù)(B－Smooth)。例如12=2×2×3,因此12是

B-Smooth的數(shù)。

3.Pollard＇s

ρ

方法

除了試除法挨個(gè)比較的策略之外,還有一種尋找某個(gè)數(shù)是否滿足要求的策略就是隨機(jī)選取。如果運(yùn)氣好可以在O(1)的時(shí)間復(fù)雜度下得到答案,但是對(duì)于大模數(shù)n,猜測(cè)成功的概率非常小,因此需要對(duì)隨機(jī)猜測(cè)進(jìn)行優(yōu)化。

由生日悖論知道,在一年有

N

天的情況下,當(dāng)房間中有

N

個(gè)人時(shí),至少有兩個(gè)人的生日相同的概率約為50%。因此不斷在[1,N-1]范圍內(nèi)生成隨機(jī)數(shù),就有很大概率在這些整數(shù)中找到兩個(gè)是模p

同余的數(shù),即xj≡ximod

p。此時(shí)通過(guò)計(jì)算gcd(xj-xi,n)就能得到模數(shù)n的一個(gè)素因子。

由于偽隨機(jī)數(shù)序列xi中的每個(gè)數(shù)都是由前一個(gè)數(shù)決定的,而生成的數(shù)又是有限的,因此遲早會(huì)進(jìn)入循環(huán)。生成的序列常常形成如圖8.7所示的ρ形,這也是這個(gè)算法名字rho(ρ)的由來(lái),圖中給出了x0=0、c=24、n=9400時(shí)的偽隨機(jī)序列。

Pollard＇sρ算法取初始值相同的xi和xj

以不同的速度增長(zhǎng)(即xi調(diào)用函數(shù)一次時(shí),xj

調(diào)用兩次函數(shù)),根據(jù)Floyd判環(huán)算法(也稱為龜兔賽跑算法),xi

和xj

最終會(huì)在環(huán)上相遇,此時(shí)如果還沒(méi)有找到答案,則重新設(shè)置初始值繼續(xù)上述過(guò)程。

圖8.7Pollard

sρ算法生成的偽隨機(jī)序列(c=24、n=9400)

5.Dixon隨機(jī)平方算法

Dixon算法試圖找到x

和y,以滿足x?±ymodn,若滿足x2≡y2modn,則有下式成立:

但是x-y

和x+y

又都不能被n整除,那就是說(shuō),x+y或x-y

必定包含模數(shù)n的因子。

【例8-15】

分解模數(shù)n=84923。

解:令B=7,那么因子基FB={2,3,5,7}。

記T={Q(x1),Q(x2),Q(x3),…,Q(xj)},則T

集合中所有的光滑數(shù)Q(xi)的乘積滿足:

這時(shí),同余符號(hào)右邊已經(jīng)符合平方數(shù)形式,左邊由于

Q(xi)是光滑的,只要選擇適合的Q(xi)相乘,確保乘積結(jié)果的所有因子的冪是偶數(shù)次即可。

【例8-16】

二次篩法分解n=15347。

解:

最終T6

中出現(xiàn)的值等于1所對(duì)應(yīng)的

Q(xi)就是能夠被因子基完全分解的B光滑數(shù),其詳細(xì)信息如表8.2所示。

通過(guò)上表,不難看出Q(3)直接滿足指數(shù)矩陣為全零的條件。由二次函數(shù)有

即1262≡232mod15347

最后計(jì)算gcd(126+23,15347)=149和

gcd(126-23,15347)=103得到n

的兩個(gè)素因子149和103。

但大多數(shù)情況下,Q(xi)不會(huì)直接滿足Q(x),而是需要多個(gè)Q(xi)的組合才能構(gòu)造出Q(x)。此時(shí)可以通過(guò)求解由指數(shù)矩陣構(gòu)成的線性方程來(lái)得到Q(x)的組成。

8.4.2加解密指數(shù)攻擊

本節(jié)討論RSA算法中同加解密指數(shù)(e和d)有關(guān)的安全問(wèn)題,其中Rabin解密攻擊、低加密指數(shù)攻擊、低加密指數(shù)廣播攻擊以及低解密指數(shù)攻擊是針對(duì)加解密指數(shù)或解密指數(shù)較小情況的攻擊方式,共模攻擊是針對(duì)加密指數(shù)與模數(shù)的關(guān)聯(lián)性來(lái)解密的攻擊,e與?(n)不互素攻擊則是針對(duì)加密指數(shù)與?(n)關(guān)聯(lián)性來(lái)解密的攻擊。

1.Rabin解密攻擊

Rabin加密是RSA算法中加密指數(shù)e=2的一個(gè)特例,因此是一種基于模平方和模平方根的非對(duì)稱加密算法,其加解密過(guò)程如下。

上述方程與RSA類似,但并不是單射,Rabin密碼的1個(gè)密文能解出4個(gè)明文。上述方程可以借助歐拉準(zhǔn)則來(lái)判定c是否為模p

或者模q

的二次剩余,如果加密正確的話,c確實(shí)應(yīng)該是一個(gè)模p

或者模q

的二次剩余,但是這對(duì)于解密并沒(méi)有實(shí)質(zhì)幫助,詳細(xì)的明文計(jì)算過(guò)程如下。

(1)已知模數(shù)n

以及p、q;

(2)計(jì)算

mp和mq:

2.低加密指數(shù)攻擊

如果加密指數(shù)e很小(一般為3)且明文

me

不大,則根據(jù)加密公式變形得到的公式me=kn+c(k

為非負(fù)整數(shù))通過(guò)密文的三次方根或暴力破解k可得到明文。

根據(jù)加密公式c≡memod

n,可知低加密指數(shù)攻擊分如下兩種情況。

3.低加密指數(shù)廣播攻擊

如果有同一個(gè)明文m

在不同模數(shù)n和相同加密指數(shù)e條件下進(jìn)行加密,那么就可以利用中國(guó)剩余定理計(jì)算出m3,再開(kāi)三次方根得到明文。不妨設(shè)加密指數(shù)e=3,低加密指數(shù)廣播攻擊過(guò)程如下。

(1)相同明文在不同模數(shù)下的加密公式如下:

(2)根據(jù)中國(guó)剩余定理計(jì)算出m3(modn1n2n3)的值。由于

m3<n1n2n3,可以直接由m3開(kāi)立方根得到明文m。詳細(xì)推導(dǎo)和示意圖可以參考8.4.5小節(jié)的Hastad廣播攻擊。

4.低解密指數(shù)攻擊

【例8-17】

找出3.245的連分?jǐn)?shù)。

解:連分?jǐn)?shù)計(jì)算過(guò)程如表8.3所示。

由表可知,3.245的連分?jǐn)?shù)是{3,4,12,4},可表示為

其漸進(jìn)分?jǐn)?shù)依次為3、13/4、159/49、649/200。

5.共模攻擊

當(dāng)多個(gè)用戶使用相同模數(shù)n

但加密指數(shù)e不同的公鑰加密同一明文消息時(shí),可考慮使用共模攻擊解密密文。只要找出一對(duì)互素的加密指數(shù),就可以推導(dǎo)出明文

m。共模攻擊過(guò)程如下

設(shè)兩個(gè)用戶的加密指數(shù)分別為e1

和e2,且兩者互素。加密公式分別為

當(dāng)攻擊者截獲

c1和

c2

后,就可以恢復(fù)出明文。攻擊者用擴(kuò)展歐幾里得算法計(jì)算出re1+se2=1mod

n

的兩個(gè)整數(shù)r

和s,由此可得

就可以得到明文m≡cr1cs2mod

n。

6.e與?(n)不互素攻擊

e與?(n)不互素的情況下,往往需要根據(jù)已知條件找出e

與?(n)的最大公約數(shù)b,然后判斷b

的大小。若公約數(shù)b

較小,則可嘗試求b

次方根解出明文m;若公約數(shù)b

較大,則通過(guò)中國(guó)剩余定理構(gòu)造新的RSA密鑰求解。

(5)根據(jù)步驟(2),由兩組數(shù)據(jù)可得到bd1

和bd2的值,代入式(8.6)可得到同余式如下:

(6)由式(8.7)、式(8.8)得:

8.4.3dp、dq泄露攻擊

除了模數(shù)n=p×q、加解密指數(shù)e、d

和歐拉函數(shù)?(n)等參數(shù)以外,RSA公鑰密碼有時(shí)為了提高加解密速度還會(huì)提供參數(shù)dp

和dq。dp

和dq參數(shù)的定義為

但事實(shí)上參數(shù)dp

和dq

中的部分或全部一旦泄露,就有可能破壞RSA公鑰密碼安全。

1.dp&dq

泄露攻擊

在dp&dq

都泄露的情況下,可推導(dǎo)出明文

m的計(jì)算公式并代入?yún)?shù)得到明文m。dp&dq

泄露攻擊過(guò)程如下。

1)計(jì)算m1

和m2

將式(8.11)、式(8.12)變形為

根據(jù)解密公式m≡cdmodpq,得到

2.dp

泄露攻擊

在僅dp

泄露的情況下,可以通過(guò)暴力破解找到參數(shù)x

的值,然后計(jì)算出模數(shù)n

的素因子p,最終得到明文,推導(dǎo)過(guò)程如下。

1)確定參數(shù)x

的范圍已知公式:

已知公式:

兩邊同乘加密指數(shù)e得到:

等式變形得:

2)確定x

和p

的值

通過(guò)遍歷范圍(0,e),若存在x

滿足以下兩式,再將x

代入式(8.31)就可以計(jì)算出p,后續(xù)就是常規(guī)的RSA解密。

8.4.4選擇明密文攻擊

1.選擇明文攻擊

攻擊者可以訪問(wèn)加密盒子提供的加密服務(wù),攻擊者給加密盒子輸入(可選)任意明文,加密盒子對(duì)其進(jìn)行加密并返回給攻擊者相應(yīng)的密文。

例如,攻擊者可以訪問(wèn)加密Oracle,但是加密所用的公鑰n

和e未知。

1)通過(guò)加密Oracle獲取n

攻擊者發(fā)送明文消息2、4、8給加密Oracle讓其加密,由此可以得到密文:

那么就有以下等式成立:

所以有關(guān)系式:

攻擊者接下來(lái)只要計(jì)算kn

和tn的最大公約數(shù),就可以大概率恢復(fù)n。攻擊者還可以構(gòu)造更多的明文消息和對(duì)應(yīng)密文對(duì),從而更加確定性地恢復(fù)n。

2.選擇密文攻擊

攻擊者已知公鑰(n,e),并可選擇一些密文然后發(fā)送給解密Oracle得到相應(yīng)的明文。

假設(shè)攻擊者有密文c=memodn

并且可以發(fā)送任意的密文給解密Oracle得到對(duì)應(yīng)的明文。攻擊者可以按照以下步驟計(jì)算出明文m:

(1)攻擊者選擇任意的x∈Zn*,即x

與n

互素;

(2)攻擊者計(jì)算y=c×xemodn;

(3)攻擊者把上述密文y

發(fā)送給解密Oracle,得到y(tǒng)

對(duì)應(yīng)的解密結(jié)果z=yd

;

(4)解密結(jié)果z=yd=(c×xe)d=cdx=medx=mxmodn,由于x

與n

互素,因此攻擊者很容易求得相應(yīng)的逆元,進(jìn)而可以得到m。

3.RSA奇偶校驗(yàn)盒子攻擊

在此RSA奇偶校驗(yàn)(ParityOracle)對(duì)攻擊者提供的密文進(jìn)行解密,返回(泄露)明文的最低位信息,因此RSAParityOracle攻擊又稱為RSALeast-Significant-BitOracle攻擊。

假設(shè)攻擊者可以訪問(wèn)一個(gè)解密Oracle,它會(huì)對(duì)攻擊者輸入的密文解密得到明文,并且會(huì)檢查解密的明文的奇偶性,并根據(jù)奇偶性返回相應(yīng)的值,比如返回1表示奇數(shù),返回0表示偶數(shù)。

針對(duì)上述場(chǎng)景,攻擊者在已知密文的情況下,只需要log2n次就可以知道該密文對(duì)應(yīng)的明文。

由加密公式知:

第一次向服務(wù)器發(fā)送構(gòu)造的密文c×2e:

第一次服務(wù)器會(huì)計(jì)算并返回解密后2m(modn)的值所對(duì)應(yīng)的奇偶性。顯然,2m

是偶數(shù),它的冪次也是偶數(shù);而n

是奇數(shù),因?yàn)樗怯蓛蓚€(gè)大素?cái)?shù)相乘得到的,所以2m(modn)的奇偶性有兩種情況,可以是奇數(shù)或者是偶數(shù)。

圖8.9二分法逐步限定明文范圍

4.RSA字節(jié)/比特盒子攻擊

RSAByte/BitsOracle攻擊顧名思義就是服務(wù)端返回明文的一個(gè)字節(jié)(Byte)或者多個(gè)比特(Bits)的攻擊,因此也可以看作是RSAParityOracle攻擊的擴(kuò)展。

RSAByte/BitsOracle攻擊當(dāng)中,服務(wù)端的解密Oracle對(duì)給定的密文進(jìn)行解密,并且會(huì)返回給攻擊者明文的最后一個(gè)字節(jié)b(8個(gè)比特)。因此這種攻擊可以更快地恢復(fù)明文消息,通常只需要log256n次就可以知道密文對(duì)應(yīng)的明文消息。

在確定了k值的范圍以后,其具體取值可以根據(jù)服務(wù)器返回的一個(gè)字節(jié)b

來(lái)推導(dǎo)。我們知道256m-kn

的最后一個(gè)字節(jié)b

其實(shí)就相當(dāng)于(256m-kn)%256≡-kn%256=b。而模數(shù)n

是已知的,因此可以根據(jù)服務(wù)器返回的一個(gè)字節(jié)b算出k

的值,或者就是提前計(jì)算好對(duì)應(yīng)關(guān)系,然后查表即可,如表8.4所示。

5.RSA奇偶校驗(yàn)變種攻擊

如果服務(wù)端的加密或者解密Oracle參數(shù)每隔一定時(shí)間有變化,那么攻擊者再采用前面的二分法進(jìn)行破解就不適用了。在此考慮實(shí)時(shí)逐位恢復(fù)。

對(duì)于k比特明文m

可以表示為

那么ai

可以理解為明文m對(duì)應(yīng)二進(jìn)制從低位向高位數(shù)第i+1位的值。

首先,明文的最低位a0是通過(guò)給服務(wù)器發(fā)送初始密文c,服務(wù)器就會(huì)返回對(duì)應(yīng)明文m(modn)的奇偶性,因此就能判斷出明文的第1位比特a0

的值。

8.4.5格與Coppersmith相關(guān)攻擊

1995年Coppersmith提出利用格(Lattices)和格約減技術(shù)(LatticeReductionTech_x0002_niques)來(lái)攻擊RSA密碼。幾年后Howgrave-Graham簡(jiǎn)化了Coppersmith算法使得其更易于實(shí)際攻擊。Coppersmith提出的建設(shè)性構(gòu)造理論對(duì)于某些條件不是太苛刻的情況下,例如已知部分明文消息、小私鑰指數(shù)等,有著很高的攻擊效率。

1.格基礎(chǔ)

在量子計(jì)算機(jī)誕生之后,現(xiàn)有的RSA、橢圓曲線等公鑰密碼體制的安全性受到極大挑戰(zhàn),其基于的數(shù)學(xué)難題(大整數(shù)分解、橢圓曲線離散對(duì)數(shù))可以被量子計(jì)算機(jī)上運(yùn)行的Shor算法破解。目前基于格理論的密碼體制是抗量子算法攻擊最熱門的研究方向。因此除了RSA攻擊應(yīng)用之外,格本身在隱私保護(hù)、聯(lián)邦學(xué)習(xí)、安全多方計(jì)算、差分隱私和同態(tài)加密等都有廣泛應(yīng)用,足見(jiàn)格密碼的重要性。

格與向量空間V(VectorSpace)類似,是n

維向量的集合,其加法和數(shù)乘運(yùn)算滿足封閉性。設(shè)有向量v1,v2,…,vn∈V,將v1,v2,…,vn

的線性組合構(gòu)成的集合{a1v1+a2v2+…+anvn:ai∈R}稱為{v1,v2,…,vn}所張成的空間。若v1,v2,…,vn

線性無(wú)關(guān),則稱其為向量空間V

的基。

平面可看作由向量(0,1)和(1,0)構(gòu)成的二維向量空間,二維向量空間如圖8.10所示。

圖8.10二維向量空間

格L

指的是向量v1,v2,…,vn

的線性組合構(gòu)成的向量集合,重點(diǎn)是系數(shù)ai

都是整數(shù),即

從格的定義可以看出,其與向量空間的定義非常相似,只不過(guò)將線性組合的系數(shù)限定為整數(shù),因而導(dǎo)致格在幾何上是由一些離散呈周期性結(jié)構(gòu)的點(diǎn)構(gòu)成的。格中每個(gè)點(diǎn)都被一個(gè)球體包圍,且此球體內(nèi)部?jī)H包含格中唯一一個(gè)點(diǎn),如圖8.11所示。

圖8.11二維格

任意一組可以生成格的線性無(wú)關(guān)的向量都稱為格的基,格的基中的向量個(gè)數(shù)稱為格的維度。任意兩組這樣的向量中,向量的個(gè)數(shù)相同。

格的基不是唯一的,圖8.12分別給出了兩組基[(1,0)T、(0,1)T]和[(1,1)T、(2,1)T]生成的包含所有整數(shù)的格Z2,其中所有二維向量的坐標(biāo)都是整數(shù)。圖8.12格Z

1)范數(shù)與正交基

如果將向量v,w∈V?Rm

表示成坐標(biāo)形式v=(x1,x2,…,xm)、w=(y1,y2,…,ym),則點(diǎn)乘運(yùn)算表示為v·w=x1y1+x2y2+…+xmym

。

向量v的長(zhǎng)度或歐氏范數(shù)為

若向量空間V

的一組基v1,v2,…,vn

滿足vi·vj=0,i≠j,則稱v1,v2,…,vn

是正交基。此外若‖vi‖=1,i=1,2,…,n,則稱v1,v2,…,vn

為標(biāo)準(zhǔn)正交基。

【例8-18】

v1=(1,1),v2=(2,0),請(qǐng)分別計(jì)算v1·v2、v1+v2、v1-v2、2v1、v1

的歐氏范數(shù)以及v1

的單位向量。

圖8.13施密特正交化算法

圖8.14計(jì)算v2*、v3*示意圖

【例8-19】

設(shè)v1=(0,0,2)、v2=(4,3,1)、v3=(2,1,-2)是R3

的基,用施密特正交化方法求R3

的一組正交基。

3)格基相互轉(zhuǎn)換

格L

的任意兩個(gè)基可以通過(guò)左邊乘上一個(gè)特定的矩陣來(lái)相互轉(zhuǎn)化,矩陣的元素全是整數(shù),并且它的行列式為±1。

【例8-20】

一個(gè)三維格L?R3,由以下三個(gè)向量構(gòu)成:

即v1、v2、v3

為格L

的一個(gè)基,將這三個(gè)向量作為行向量來(lái)構(gòu)造矩陣:

通過(guò)以下表達(dá)式來(lái)構(gòu)造三個(gè)新的向量:

這等價(jià)于在矩陣A

的左邊乘上一個(gè)矩陣:

可以得知w1、w2、w3即為如下矩陣的三個(gè)行向量:

因?yàn)榫仃嘦

的行列式值為1,所以矩陣B

中所求出的三個(gè)向量w1、w2、w3

也是格L

的一個(gè)基。

矩陣U的逆矩陣U-1為

由U-1B=A

可知,vj

可用wj

的線性組合來(lái)表示:

4)基礎(chǔ)區(qū)域

設(shè)L

是一個(gè)維度為n

的格,且v1,v2,…,vn

是L

的基,對(duì)應(yīng)于這組基的基礎(chǔ)區(qū)域是如下向量的集合:

圖8.15中深色平行四邊形構(gòu)成的區(qū)域即為格Z2

的一組基(1,1)T

和(2,1)T構(gòu)成的基礎(chǔ)區(qū)域。平移這個(gè)基礎(chǔ)區(qū)域,可以得到整個(gè)格,即把基礎(chǔ)區(qū)域置于每個(gè)格點(diǎn)上能覆蓋整個(gè)格平面。

圖8.15格Z2

的基礎(chǔ)區(qū)域

5)格L

的行列式

設(shè)L

是一個(gè)維度為n

的格,Ｆ是L

的一個(gè)基礎(chǔ)區(qū)域,的n

維體積稱為L(zhǎng)的行列式,記為detL。

將基向量v1,v2,…,vn

想象成固定長(zhǎng)度的向量,它們組成平行多面體的各個(gè)邊,那么在向量長(zhǎng)度都不變的情況下,當(dāng)基向量?jī)蓛烧粫r(shí),的體積才能取到最大值。例如在所有平行四邊形中,矩形的面積最大。因此可得到如下不等式。

Hadamard不等式:設(shè)L

是一個(gè)格,對(duì)于它的任意一個(gè)基向量v1,v2,…,vn

和基礎(chǔ)區(qū)域Ｆ,有

基向量v1,v2,…,vn

越接近于垂直,不等式就越接近于等式。

【例8-21】

格L

的一組基構(gòu)成的矩陣如下:

格中所有向量可表示成(1001a,2008b)(a、b∈Z)的形式,很明顯,最短非零向量為(1001,0)或(-1001,0)。例子當(dāng)中可以很容易找到最短非零向量是因?yàn)檫@組格基是正交的。若給出的格基不是正交的,找到最短非零向量就是一個(gè)計(jì)算難題。因此格中向量的施密特正交化處理對(duì)于尋找格中最短非零向量難題至關(guān)重要。

2.LLL格基約減算法

給定格的一組基,使用LLL算法對(duì)它進(jìn)行約減,約減的主要目的是將這組任意給定的基轉(zhuǎn)化為一組正交性較好的優(yōu)質(zhì)基,并使得這個(gè)優(yōu)質(zhì)基中的各個(gè)向量盡量短。

LLL算法與Gram-Schmidt正交化過(guò)程密切相關(guān),為得到一組改進(jìn)的基,首先需要根據(jù)施密特正交算法構(gòu)造一組正交基。假設(shè)B={v1,v2,…,vn}是格L

的一組基,開(kāi)始時(shí)令

向量集合B*=v1*,v2*,…,vn*

是一組正交基,其與B={v1,v2,…,vn}張成的向量空間相同,且這兩組基具有相同的行列式,但B*

不一定是格L

的一組基,因?yàn)槭┟芴卣换^(guò)程中得到的ui,j

可能不是整數(shù),涉及利用非整數(shù)系數(shù)進(jìn)行的線性組合,但格要求系數(shù)必須為整數(shù)。因此LLL約減算法放寬了嚴(yán)格正交的條件,得到格的近似正交的基。LLL算法示意圖如圖8.16所示。

圖8.16LLL格基約減

LLL算法得到的約減基{v1,v2,…,vn}滿足以下兩個(gè)條件。

圖8.17LLL算法步驟

【例8-22】

二維格L

的一組基由下面矩陣B

給出,請(qǐng)使用LLL算法對(duì)其進(jìn)行約減。

【例8-24】f(x)=x3+10x2+5000x-222mod10001,求解該模方程的小根x0。

已知

N=10001,d=3,根據(jù)上述過(guò)程可得,當(dāng)

x0≤X≈2.07時(shí),可

以

利

用Coppersmith方法求解f(x)≡0modN

的小根。為簡(jiǎn)化計(jì)算,假設(shè)

X=10。

構(gòu)造多項(xiàng)式gi(x)=Nxi,0≤i<3,使用gi(xX)和f(xX)的系數(shù)構(gòu)造格基矩陣B。

【例8-25】

根據(jù)例8-24中的f(x)構(gòu)造x

移位多項(xiàng)式h1(x)=xf(x),h2(x)=x2f(x),向該例題中的格基矩陣中添加由h1(xX)、h2(xX)構(gòu)造的行向量,得到新的格基矩陣如下:

Coppersmith定理:設(shè)N

為一正整數(shù),其分解未知,f(x)=x

d+ad-1xd-1+…+a1x+a0是一個(gè)次數(shù)為d

的單變?cè)滓欢囗?xiàng)式,

則可以在多項(xiàng)式時(shí)間內(nèi)找到滿足以下方程的所有整數(shù)小根x0。

總體來(lái)說(shuō),求解x0

的過(guò)程可用圖8.18表示。

圖8.18Coppersmith方法計(jì)算過(guò)程

【例8-26】

設(shè)模方程f(x)=((2+x)3-6)mod21,利用Coppersmith算法求f(x)=0mod21的根。

根據(jù)Coppersmith方法原理和題目可得到如下參數(shù)信息:

根據(jù)fi(xX)構(gòu)造的格基矩陣的維度w=dm=9。

使用LLL算法對(duì)格B

進(jìn)行格基約減,得到BLLL:

4.模板消息攻擊

模板消息(StereotypedMessages)指每次發(fā)送的消息主體結(jié)構(gòu)相同,只有部分特定位置的內(nèi)容不同。例如消息:“thepasswordofthenextperiodoftimeis:XXX”,每次發(fā)送只改

變“XXX”的內(nèi)容。這樣的消息在日常生活中很常見(jiàn),例如,平時(shí)收到的短信驗(yàn)證碼,除了驗(yàn)證碼外,其他部分的內(nèi)容都是一樣的;銀行賬戶金額變動(dòng)通知,只更改賬號(hào)、時(shí)間、金額等幾個(gè)關(guān)鍵信息。

使用RSA加密如上所述的模板消息是很不安全的。Coppersmith提出了模板消息攻擊方法,當(dāng)消息的變化部分和RSA的加密指數(shù)足夠小時(shí),攻擊者可以在多項(xiàng)式時(shí)間內(nèi)破解該RSA密碼。攻擊者在已知這種固定的消息格式以及消息中固定的部分內(nèi)容后,可以抽象出一個(gè)模方程,并使用Coppersmith方法構(gòu)建一個(gè)合適的格,然后利用LLL算法得到該格中較短的約減基,進(jìn)而求解該模方程的一個(gè)小根,從中解密感興趣的信息。

【例8-27】Alice經(jīng)常發(fā)送模板消息:

“YourPINcodeisXXXX”,每條消息只改變“XXXX”對(duì)應(yīng)的內(nèi)容,然后使用RSA加密上述消息。已知某次發(fā)送的密文c和公鑰(e,N),請(qǐng)恢復(fù)明文m。

運(yùn)行結(jié)果如下:

5.Hastad廣播攻擊

Hastad廣播攻擊是指將一條重要消息m

發(fā)送給k

個(gè)用戶,每次加密使用的公鑰指數(shù)e都相同,且k≥e,模數(shù)

N

不同但互素。該攻擊示意圖如圖8.19所示。

圖8.19Hastad廣播攻擊

這種加密方式非常不安全,攻擊者截獲密文后,可以通過(guò)中國(guó)剩余定理反推出明文。根據(jù)攻擊場(chǎng)景有:

由中國(guó)剩余定理:

【例8-28】Alice欲將一重要消息m

發(fā)送給

A、B和C三個(gè)人,使用RSA加密,公鑰分別為(3,NA)、(3,NB

)和(3,NC

),已知模數(shù)

NA

、NB

、NC

以及相應(yīng)的密文c1、c2、c3,計(jì)算消息明文m。

6.線性填充Hastad廣播攻擊

Hastad廣播攻擊表明用低加密指數(shù)加密相同的信息,發(fā)送給多個(gè)用戶的方法是極不安全的。為抵御這種攻擊,有方法在RSA加密之前,先用時(shí)間t對(duì)明文進(jìn)行變換,變換后的明文m'=2|t|m+t,然后對(duì)m'進(jìn)行加密。但事實(shí)證明這種線性填充方法也不安全。

問(wèn)題可以轉(zhuǎn)化為給定k

個(gè)同余方程ci≡(aim+bi)e(modNi),i=1,2,…k,k>e,其中ai、bi

均已知,如何推斷出m?

Hastad針對(duì)這種線性填充提出了一種更強(qiáng)的攻擊方法,若攻擊者了解發(fā)送方使用的線性變換方法,即已知ai

和bi

后,可利用中國(guó)剩余定理將多個(gè)模方程經(jīng)過(guò)線性組合構(gòu)造出一個(gè)新的模方程,而這一新的模方程可用Coppersmith算法求出所有小根。

7.FranklinReiter消息相關(guān)攻擊

Franklin和Reiter提出了一種針對(duì)相關(guān)消息的攻擊。相關(guān)信息是指第i+1次