第一章信息安全概述-RSA算法存在的安全威脅計算機系統(tǒng)與網(wǎng)絡(luò)安全技術(shù)RSA的安全性是基于加密函數(shù)ek(x)=xe(modn)是一個單向函數(shù)，所以對攻擊的人來說求逆計算不可行。而Bob能解密的陷門是分解n=pq，知

(n)=(p-1)(q-1)，從而用歐幾里德算法解出解密私鑰d。RSA算法的安全性RSA算法存在的安全威脅信息安全概述

每個合數(shù)都可以唯一地分解出素數(shù)因子

6=2·3 999999=3·3·3·7·11·13·37 27641=131·121

從2開始試驗每一個小于等于√27641的素數(shù)。素數(shù)：只能被1和它本身整除的自然數(shù)；否則為合數(shù)。整數(shù)n的十進(jìn)制位數(shù)因子分解的運算次數(shù)所需計算時間（每微秒一次）

50 1.4x1010 3.9小時 75 9.0x1012 104天 100 2.3x1015 74年

200 1.2x1023 3.8x109年 300 1.5x1029 4.0x1015年

500 1.3x1039 4.2x1025年因子分解的難度和時間RSA算法存在的安全威脅信息安全概述對RSA的具體實現(xiàn)存在一些攻擊方法，但不是針對基本算法的，而是針對協(xié)議的。對RSA的選擇密文攻擊對RSA的公共模攻擊對RSA的小加密指數(shù)攻擊對RSA的小解密指數(shù)攻擊時間性攻擊：取決于解密算法的運算時間針對RSA的攻擊RSA算法存在的安全威脅信息安全概述例1：E監(jiān)聽A的通信，收集由A的公開密鑰加密的密文c，E想知道消息的明文m,使

m=cdmodn他首先選擇隨機數(shù)r,使r<n.然后用A的公開密鑰e計算：

x=remodny=xcmodnt=r-1modn如果x=remodn，則

r=xdmodn現(xiàn)在E讓A對y簽名，即解密y,A向E發(fā)送u=ydmodn而E計算

tumodn=r-1yd

modn=r-1xdcdmodn=cdmodn=m針對RSA的選擇密文攻擊RSA算法存在的安全威脅信息安全概述例2：E讓A對m3簽名。他產(chǎn)生兩個消息m1和m2，滿足

m3=m1m2(modn)如果E能讓A分別對m1和m2簽名，則可以計算m3：

m3d=(m1dmodn)(m2dmodn)啟示：不要用RSA對陌生人的隨機文件簽名，簽名前先使用一個散列函數(shù)針對RSA的選擇密文攻擊RSA算法存在的安全威脅信息安全概述一種可能的RSA實現(xiàn)方法是給每個人相同的n,但指數(shù)d和e不同。問題：如果相同的消息曾用兩個不同的指數(shù)加密，而這兩個指數(shù)是互素的，則明文可以不需要任何解密密鑰來恢復(fù)。令m為明文消息，兩個加密密鑰為e1，e2,兩個密文消息為c1,c2c1=me1modnc2=me2modn由于e1和e2互素，所以可以用擴展的Euclid算法找到r,s使re1+se2=1,同樣，可以用擴展的Euclid算法計算c1-1,而(c1-1)-r*c2s=mmodn啟示：不要讓一群用戶共享一個模n針對RSA的公共模攻擊RSA算法存在的安全威脅信息安全概述

對RSA的小加密指數(shù)攻擊如果使用一個較小的e值，則進(jìn)行RSA簽名和加密會很快，但也不安全。如果用相同e值的不同公鑰，可以得到e(e+1)/2個線性相關(guān)的消息，則系統(tǒng)是可破的；如果有少于這些的消息或消息不相關(guān)，則無問題。比如：消息為mj,使用同樣的指數(shù)e,模數(shù)分別為q1,q2,…qs（兩兩互素）,則密文為mjemodq1，mjemodq2，…mjemodqs，根據(jù)中國剩余定理，m'=mjemodq1q2…qs.可以計算出來，對于較小的e，可以解出mj。解決辦法：加密前將消息與隨機值混合，并保證m與n有相同的長度。RSA算法存在的安全威脅信息安全概述使用較小的d會產(chǎn)生窮盡解密攻擊的可能當(dāng)d為n的1/4長度時，而e小于n時，可