姓名：朱睿琦

學(xué)號(hào)：15180288015

參考：http://www.xzbu.com/8/view-6540335.htm

? ? ? ? ? ?http://www.doc88.com/p-982460038116.html

? ? ? ? ? ?http://www.cnblogs.com/7hat/p/3407897.html

【嵌牛導(dǎo)讀】：RSA算法是迄今在網(wǎng)絡(luò)安全領(lǐng)域應(yīng)用最為廣泛的非對(duì)稱密碼算法，其安全性是基于大整數(shù)的因數(shù)分解難問題的，算法的攻破一般被認(rèn)為等同于大數(shù)分解。另一方面，對(duì)RSA算法的攻擊可針對(duì)設(shè)計(jì)與應(yīng)用該算法的系統(tǒng)的某些缺陷。本文研究了對(duì)RSA算法的攻擊的主要方法，并對(duì)攻擊防御提出了建議。

【嵌牛鼻子】：網(wǎng)絡(luò)安全，RSA算法，算法攻擊

【嵌牛提問】：RSA算法的加密原理是什么？為什么在現(xiàn)階段RSA算法被認(rèn)為是安全的？

【嵌牛正文】：

1>RSA算法基本原理：

1.1公鑰與私鑰的生成：

(1)隨機(jī)挑選兩個(gè)大質(zhì)數(shù) p 和 q，構(gòu)造N = p*q；

(2)計(jì)算歐拉函數(shù)φ(N) = (p-1) * (q-1)；

(3)隨機(jī)挑選e，使得gcd(e,φ(N)) = 1，即 e 與φ(N) 互素；

(4)計(jì)算d，使得 e*d ≡ 1 (modφ(N))，即d 是e 的乘法逆元。

此時(shí)，公鑰為（e, N），私鑰為（d, N），公鑰公開，私鑰自己保管。

1.2加密信息：

(1)待加密信息（明文）為 M，M < N；（因?yàn)橐瞿＿\(yùn)算，若M大于N，則后面的運(yùn)算不會(huì)成立，因此當(dāng)信息比N要大時(shí)，應(yīng)該分塊加密）

(2)密文C = Memod N

(3)解密Cdmod N = (Me)dmod N = Md*emod N ；

要理解為什么能解密？要用到歐拉定理（其實(shí)是費(fèi)馬小定理的推廣）aφ(n)≡ 1 (mod n)，再推廣：aφ(n)*k≡ 1 (mod n)，得：aφ(n)*k+1≡ a (mod n)

注意到?e*d ≡ 1 mod?φ(N)，即：e*d = 1 + k*φ(N)。

因此，Md*emod N =?M1 + k*φ(N)mod N = M

簡(jiǎn)單來說，別人用我的公鑰加密信息發(fā)給我，然后我用私鑰解密。

1.3數(shù)字簽名：

(1)密文C = Mdmod N

(2)解密M = Cemod N =?(Md)emod N = Md*emod N ?= M ；（原理同上）

簡(jiǎn)單來說，我用自己的密鑰加密簽名，別人用我的公鑰解密可以看到這是我的簽名。注意，這個(gè)不具有隱私性，即任何人都可以解密此簽名。

算法的安全性：基于大整數(shù)N難以分解出p和q，構(gòu)造φ(N)；或由N直接構(gòu)造φ(N)同樣難。

2>RSA算法的攻擊方法:

RSA 算法的安全性依賴于大整數(shù)分解的困難性。 最直接的攻擊方法是分解 n 得到 p,q，進(jìn)而基于 e 計(jì)算 d，隨著計(jì)算機(jī)運(yùn)算能力的不斷提高，通過二次篩法已能分解 180 多位的十進(jìn)制素?cái)?shù)，增加 p,q 的長度已成為許多安全應(yīng)用系統(tǒng)的加密要求。 另一方面，利用系統(tǒng)設(shè)計(jì)和實(shí)現(xiàn)的缺陷， 人們也提出了一些基于非因子分解方式破解 RSA 算法的方案。 目前，對(duì) RSA 算法的攻擊主要有以下幾種：

2.1 對(duì)模數(shù) n 的因子分解

分解模數(shù) n 是最直接的攻擊方法，也是最困難的方法。 攻擊者可以獲得公鑰 e 和模數(shù) n；如果 n=pq 被成功分解，則攻擊者可以計(jì)算出φ(n)=(p-1)(q-1)，進(jìn)而從 ed≡1modφ(n)解得私鑰 d。

2.2 對(duì) RSA 的公共模數(shù)攻擊

若一個(gè)多用戶系統(tǒng)中只采用一個(gè)模數(shù) n，不同的用戶擁有不同的e 和 d，系統(tǒng)將是危險(xiǎn)的。 在此系統(tǒng)中，若有同一消息用不同的公鑰加密，這些公鑰共模且互質(zhì)，那該信息無需私鑰就可解密。 舉例來說，設(shè)P 為信息明文，兩個(gè)加密公鑰為 e1和 e2，公共模數(shù)是 n，有：C1=Pe1modn 和 C2=Pe2modn。如果攻擊者獲得 n、e1、e2、C1和 C2，就能得到 P。 因?yàn)?e1和 e2互質(zhì)，故用歐幾里德(Euclid)算法能找到 r 和 s，滿足：r*e1+s*e2=1，設(shè) r 為負(fù)數(shù)，則(C1-1)-r*C2s=(Pe1modn)r*(Pe2modn)s=(Pr*e1+s*e2)modn=Pmodn，如果 P

2.3 對(duì) RSA 的小指數(shù)攻擊

如果 RSA 系統(tǒng)的公鑰 e 選取較小的值， 可以使加密和驗(yàn)證簽名的速度有所提高。 但如果 e 取得太小，就容易受到小指數(shù)攻擊。 例如，有同一系統(tǒng)的三個(gè)用戶，分別使用不同的模數(shù) n1，n2，n3，但都選取 e=3；另有一用戶欲將同一明文消息 P 發(fā)送給以上三人，使用各人的公鑰加密得：C1=P3(modn1)，C2=P3(modn2)和 C3=P3(modn3)一般地，n1，n2，n3互素（否則，會(huì)比較容易求出公因子，降低安全性），根據(jù)中國剩余定理，可由 C1，C2，C3計(jì)算：C=P3(modn1n2n3)如果 P

2.4 對(duì) RSA 的選擇密文攻擊

選擇密文攻擊指的是攻擊者能選擇不同的密文，并擁有對(duì)應(yīng)的明文，由此推出想要的信息。一般攻擊者會(huì)偽裝若干信息，讓擁有私鑰的用戶簽名，由此獲得有用的明文-密文對(duì)，然后推算想要的信息。

例 1 攻擊者想要偽造用戶 u 對(duì)消息 x 的簽名。 他可以先計(jì)算 x1,x2，使得 x≡(x1x2)(modn)，并騙取 u 對(duì) x1和 x2的簽名 s1=x1d(modn)和 s2=x2d(modn)， 則對(duì) x 的簽名可計(jì)算如：s=xd(modn)=(((x1x2)(modn))d)(modn)=((x1dmodn)(x2dmodn))modn=(s1s2)(modn)。

例 2 攻擊者獲得了用戶 u 使用公鑰 e 加密的密文 y=xe(modn)，想要得到 x。 他可以先計(jì)算 y′=re(modn)（r 是小于 n 的隨機(jī)數(shù)），y″=(yy′)(modn)，然后騙取 u 對(duì) y″的簽名 s=y″d(modn)。 則通過計(jì)算(r-1s)(modn)可以恢復(fù)出 x，這是因?yàn)椋?r-1s)(modn)=((y′dmodn)-1y″d)(modn)=(y′-dy″d)(modn)=(y′-dydy′d)(modn)=yd(modn)=x。

3對(duì)RSA算法的攻擊的防御建議對(duì)于以上幾種攻擊，防御方案各不相同。攻擊 1 源于 RSA 算法的數(shù)學(xué)安全基礎(chǔ)， 增加初始化參數(shù)長度是有效的提高安全度的方法。而攻擊 2 和攻擊 3 源于應(yīng)用 RSA 算法的系統(tǒng)的設(shè)計(jì)缺陷， 改進(jìn)方法為：1）在多用戶系統(tǒng)中必須采用多個(gè)模數(shù)；2）避免為了圖求方便而使用取值太小的公鑰 e。

攻擊 4 最為復(fù)雜，從算法上無法解決這一問題，主要對(duì)應(yīng)策略有兩條：1）私鑰持有者不對(duì)不信任的信息簽名；2）簽名信息時(shí)，先使用Hash 函數(shù)生成的摘要，再對(duì)摘要簽名，避免直接對(duì)信息的簽名。

以上防御方案并不能解決所有的 RSA 安全問題， 我們建議利用RSA 算法的系統(tǒng)仔細(xì)審核安全需求 ，投入使用先進(jìn)行測(cè)試 ，并對(duì)系統(tǒng)安全做一個(gè)全面的審核。 必須對(duì)各種安全策略及程序進(jìn)行合理優(yōu)化，才能盡可能地降低風(fēng)險(xiǎn)，RSA 算法才能發(fā)揮最大的效用。