四、RSA的公共模數(shù)攻擊
#p#分頁標(biāo)題#e#

五、RSA 加密算法的缺點(diǎn)

RSA公鑰加密算法是1977年由Ron Rivest、Adi Shamirh和LenAdleman在（美國麻省理工學(xué)院）開發(fā)的。RSA取名來自開發(fā)他們?nèi)叩拿?。RSA是目前最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的所有密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。  
　　
　　
　　前面已經(jīng)提到，這個(gè)固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征--每個(gè)人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過程中實(shí)體不對其他實(shí)體任意產(chǎn)生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機(jī)文檔簽名，簽名時(shí)首先使用One-Way Hash Function對文檔作HASH處理，或同時(shí)使用不同的簽名算法。除了利用公共模數(shù)，人們還嘗試一些利用解密指數(shù)或φ（n）等等攻擊.
    ( XM )^d = X^d *M^d mod n
    RSA的算法涉及三個(gè)參數(shù)，n、e1、e2。
　　
　　
    RSA的缺點(diǎn)主要有：A)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。B)分組長度太大，為保證安全性，n 至少也要 600 bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對稱密碼算法慢幾個(gè)數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前，SET(Secure Electronic Transaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實(shí)體使用1024比特的密鑰。
　　C2 = P^e2 mod n
    一、RSA 的安全性
　　
　　
　　

    由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA最快的情況也比DES慢上好幾倍，無論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。一般來說只用于少量數(shù)據(jù)加密。
　　r * e1 + s * e2 = 1
    RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝( Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過計(jì)算就可得到它所想要的信息。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)：
　　另外，還有其它幾種利用公共模數(shù)攻擊的方法。總之，如果知道給定模數(shù)的一對e和d，一是有利于攻擊者分解模數(shù)，一是有利于攻擊者計(jì)算出其它成對的e’和d’，而無需分解模數(shù)。解決辦法只有一個(gè)，那就是不要共享模數(shù)n。

　　
    1)產(chǎn)生密鑰很麻煩，受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。
    2)安全性， RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題。目前，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過計(jì)算就可得到它所想要的信息。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)：
　　
　　( C1^(-1) )^(-r) * C2^s = P mod n
　　3)速度太慢，由于RSA 的分組長度太大，為保證安全性，n 至少也要 600 bitx以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對稱密碼算法慢幾個(gè)數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。目前，SET(Secure Electronic Transaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實(shí)體使用1024比特的密鑰。為了速度問題，目前人們廣泛使用單，公鑰密碼結(jié)合使用的方法，優(yōu)缺點(diǎn)互補(bǔ):單鑰密碼加密速度快，人們用它來加密較長的文件，然后用RSA來給文件密鑰加密，極好的解決了單鑰密碼的密鑰分發(fā)問題。
　　
    RSA加解密的算法完全相同，設(shè)A為明文，B為密文，則：A=B^e1 mod n；B=A^e2 mod n；
    三、RSA的選擇密文攻擊
    RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在已近二十年，經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)。即RSA的重大缺陷是無法從理論上把握它的保密性能如何，而且密碼學(xué)界多數(shù)人士傾向于因子分解不是NPC問題。
　　
    二、RSA的速度
    RSA算法是一種非對稱密碼算法，所謂非對稱，就是指該算法需要一對密鑰，使用其中一個(gè)加密，則需要用另一個(gè)才能解密。

    若系統(tǒng)中共有一個(gè)模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險(xiǎn)的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那末該信息無需私鑰就可得到恢復(fù)。設(shè)P為信息明文，兩個(gè)加密密鑰為e1和e2，公共模數(shù)是n，則：
    A=B^e2 mod n；B=A^e1 mod n;
    RSA算法基于一個(gè)十分簡單的數(shù)論事實(shí)：將兩個(gè)大素?cái)?shù)相乘十分容易，但那時(shí)想要對其乘積進(jìn)行因式分解卻極其困難，因此可以將乘積公開作為加密密鑰。
　　
　　假設(shè)r為負(fù)數(shù)，需再用Euclidean算法計(jì)算C1^(-1)，則
　　因?yàn)閑1和e2互質(zhì)，故用Euclidean算法能找到r和s，滿足：
　　
　　( XM )d = Xd *Md mod n