【文章內(nèi)容簡介】 ECDSA的理論模型很堅固，但是人們?nèi)匝芯亢芏啻胧┮蕴岣逧CDSA的安全性。在ECDLP不可破解及哈希函數(shù)足夠強的前提下，DSA和ECDSA的一些變形已被證明可以抵抗現(xiàn)有的任何選擇明文（密文）攻擊。在橢圓曲線所在群是一般群并且哈希函數(shù)能夠抗碰撞攻擊的前提下，ECDSA本身的安全性已經(jīng)得到證明。ECDSA可能面臨的攻擊：。ECDMA的優(yōu)點（1）安全性能高（2）計算機量小和計算機速度快（3）存儲空間占有量?。?）帶寬要求低。5 RSA算法及其數(shù)字簽名 RSA簡述RSA加密體制是一種公開的密碼體制。由于RSA算法很完善，即可用于數(shù)據(jù)加密，又可用于數(shù)字簽名，安全性良好，易于實現(xiàn)和理解，所以已經(jīng)成為一種應用極廣的公匙密碼算法，目前，RSA在許多場合有廣泛的應用。RSA 公鑰密碼算法是迄今為止在理論上最為成熟、完善的公鑰密碼體制。 從提出到現(xiàn)在已經(jīng)歷了各種攻擊的考驗，逐漸為人們接受，普遍認為是目前最優(yōu)秀的公鑰方案之一。它是第一個既能用于數(shù)據(jù)加密也能用于數(shù)字簽名和密鑰分配與管理的算法。它易于理解和操作，也很流行。因為它既可用于加密,又可用于簽名,并為用戶的公開密鑰簽發(fā)公鑰證書、發(fā)放證書、管理證書等,提高了服務(wù)質(zhì)量，所以, RSA 公開密鑰密碼在當今的信息交換過程中已得到廣泛的應用和實踐，RSA 公鑰密碼體制在世界許多地方已經(jīng)成為事實上的標準。該算法的加密密鑰和加密算法分開,使得密鑰分配更為方便。而且它特別符合計算機網(wǎng)絡(luò)環(huán)境。對于網(wǎng)上的大量用戶,可以將加密密鑰用電話簿的方式印出。如果某用戶想與另一用戶進行保密通信,只需從公鑰簿上查出對方的加密密鑰,用它對所傳送的信息加密發(fā)出即可。對方收到信息后,用僅為自己所知的解密密鑰將信息解密,了解明文的內(nèi)容。[11]由此可看出,RSA 算法解決了大量網(wǎng)絡(luò)用戶密鑰管理的難題,這是公鑰密碼系統(tǒng)相對于對稱密碼系統(tǒng)最突出的優(yōu)點。RSA 是一個基于數(shù)論的非對稱密碼體制,是一種分組密碼體制，是一種基于因子分解的指數(shù)函數(shù)作為單向陷門函數(shù)的公鑰體制算法。它基礎(chǔ)是數(shù)論的歐拉定理,素數(shù)檢測,它的安全性是基于大數(shù)分解,后者在數(shù)學上是一個困難問題。 RSA 的安全性基于復雜性理論中的計算安全性, 依賴于大整數(shù)分解這一NP 難題?？煽啃耘c所用密鑰的長度有很大關(guān)系, 假如有人找到一種很快的分解因子的算法, 即從一個公鑰中通過因數(shù)分解得到私鑰, 那么用RSA 加密的信息的可靠性肯定會極度下降。但由于其工作量巨大,按目前計算機的處理能力是不可能實現(xiàn)的。實踐證明,在當前的技術(shù)和方法下,密鑰不小于1 024 bit的RSA算法仍然是安全的。這充分說明RSA 系統(tǒng)具有良好的保密性能。因此,盡管先后出現(xiàn)了很多新的公鑰體制算法,但RSA仍然在不同應用領(lǐng)域占據(jù)了重要的位置。隨著計算機運算速度的提高以及因子分解算法的突破, RSA 的密鑰長度將越來越大, 其軟硬件實現(xiàn)速度將成為制約其使用的重要因素。 RSA加密的可行性雖然RSA加密運算的速度十分慢,但是在PC性能越來越好的今天,對于幾千字節(jié)的數(shù)據(jù)進行一次幾百位密鑰的RSA加密,所消耗的時間應該是可以接受的?下面結(jié)合大數(shù)運算程序的調(diào)試,從理論上簡單的分析消耗時間?在一臺普通配置的PC機上對一個整數(shù)進行冪模運算,因為公開密鑰的e通常取的較小,所以指數(shù)取一個小整數(shù),比如C353,模一個70字節(jié)長的整數(shù)(140位十六進制,大數(shù)單元以線性組方式實現(xiàn),對應到RSA算法中,這相當于約560bit的n),調(diào)試一個函數(shù)測試,按初等數(shù)論中的知識對程序進行算法優(yōu)化,最終在一臺配置為AMD Athron2800+,外頻333MHZ,物理內(nèi)存512MB的PC上測試需要約45毫秒時間?如果按這種速度,逐字節(jié)對1KB的數(shù)據(jù)進行同樣的運算,所消耗的時間理論上為45毫秒的1024倍即約45秒?這個時間并不是非常長[12]?其實從一個簡單的角度來說,既然RSA用于數(shù)字簽名可行,那就完全可以用于同樣大小的普通文件?對于較大的文件,如果分成與數(shù)字簽名同樣大小的段(這里假設(shè)數(shù)字簽名較短,不分段一次計算加密完成),分開的各段逐一進行加密運算,那所需要的時間也只是按文件大小線性的增長?通常數(shù)字簽名為幾十字節(jié),加密運算并不需要很長的等待,這就說明對于幾百字節(jié)或一兩K字節(jié)大小的文件來說,如果進行RSA加密,并不會是非常漫長的工作?當然,如果文件更大,加密就顯得十分漫長了?比如按前面敘述的45毫秒大數(shù)運算程序推理,加密1M字節(jié)大小的文件需要約1天的時間?所以,要在普通PC用幾百位以上的長密鑰RSA加密文件,文件不能過大,一般可以接受的上限是幾KB?如果要在較短時間內(nèi)加密大文件,需要縮短密鑰長度以減小運算量,這將帶來安全性隱患?[13] RSA算法的介紹 RSA系統(tǒng)由以下幾部分組成：（1）隨機選取的在素數(shù)P和Q，還有N ，其中N=P*Q ，P和Q保密，N公開。（2）任取Φ(n)=（P1）*(Q1)，其中 (n)表示比n小的素數(shù)的個數(shù)，任取2=e= (n),且(e, (n))=1,e為加密密鑰，公開。（3）計算d,使e*d=1(mod (n)),稱d為e對模 (n)的逆，其中d為解密秘鑰，保密。在RSA系統(tǒng)中，設(shè)m為明文，且明文塊的數(shù)值大于n,c為密文，則其加密和解密算法如為：加密算法 C=E(m)=m^e(mod n) 解密算法 m=D(c)=c^d(mod n) 在RSA系統(tǒng)中(e,n)構(gòu)成加密秘鑰，即公鑰，(d,n) 構(gòu)成解密秘鑰，即私鑰。 RSA中素數(shù)的選取在RSA中，因N=P*Q， 若P，Q被知道，即能將N因子分解，則由 Φ(n)=（P1）*(Q1)可以算出。由于e是公開密鑰，且解密秘鑰D關(guān)于E滿足 D*E=1 (mod Φ(n))則D也不難求得，這樣RSA系統(tǒng)便被完全攻破。 RSA中的素數(shù)都是上面位的十進制數(shù)，怎樣才能選擇好的P和Q，怎樣才能生成這樣的數(shù)，并且判斷它是否為素數(shù)，這是一個RSA系統(tǒng)關(guān)鍵的問題。針對素數(shù)P和Q的選擇，1978年Rivest等人在正式發(fā)表的RSA公開密鑰的論文中，就建議對素數(shù)P和Q的選擇應當滿足：（1）P、Q要足夠在，在長度上應相差幾位，且二者之差與P、Q位數(shù)相近；（2）P1與Q1的最大公約數(shù)GCD(P1,Q1)就盡量??；（3）P1與Q1均應至少含有一個大的素數(shù)因子。并把滿足這些條件的素數(shù)稱為安全素數(shù)。 RSA用到的公式和定理（1）數(shù)和互為素數(shù) 任何大于1的整數(shù)a能被因式分解為如下唯一形式： a=p1p2…pl(p1,p2,…,pl為素數(shù)) （2）模運算 ①{[a(modn)][b(mod n)]}modn≡(ab)(mod n) ②如果（ab）=（ac）(mod n),a與n互素，則 b=c(mod n) （3）費馬定理 若p是素數(shù)，a與p互素，則a ^(p1)=1 mod p （4）歐拉定理 歐拉函數(shù)φ(n)表示不大于n且與n互素的正整數(shù)的個數(shù)。當n是素數(shù), φ(n)=n1。n=p*q,p,q均為素數(shù)時,則φ(n)=φ(n)φ(n)=(p1)(q1)。 對于互素的a和n,有a^φ(n)=1(mod n) RSA安全性的分析在公布RSA算法之后，在使用RSA密碼體制和分析RSA算法發(fā)現(xiàn)了一系列的算法本身脆弱性及其存在的問題。 （1）RSA公鑰密碼體制在加密或解密中涉及大量的數(shù)值計算，其加密和解密的運算時間比較長，以致于實際使用RSA密碼體制無法應用到軟件產(chǎn)品，必須用超大規(guī)模集成電路的硬件產(chǎn)品。 （2）雖然提高N位數(shù)會大大提高RSA密碼體制的安全性，但其計算量呈指數(shù)增長，以致使其實現(xiàn)的難度增大，實用性降低。 （3）RSA公鑰密碼體制的算法完整性（指密鑰控制加密或解密變換的唯一性）和安全性（指密碼算法除密鑰本身外，不應該存在其它可破譯密碼體制的可能性）沿有等進一步完善。（4）RSA算法面臨著數(shù)學方法的進步和計算機技術(shù)飛躍發(fā)展帶來的破譯密碼能力日趨增強的嚴重挑戰(zhàn)。RSA公開密鑰密碼算法在信息交換過程中使用比較廣泛，安全性比較高。以當前的計算機水平，如選擇1024位長的密鑰（相當于300位十進制數(shù)字）就認為是無法攻破的。 RSA的攻擊RSA算法的安全性就是基于大整數(shù)的因子分解困難之上的，到目前其還是安全的，要分析RSA算法的安全性，我們從攻擊RSA的角度來審視。總的來分，RSA算法攻擊可以區(qū)分為三類：（1）蠻力攻擊：它通過實驗所用的可能私鑰，來達到目的。（2）數(shù)字攻擊：使用數(shù)學技巧，類似于分解N來達到目的。（3）時間攻擊：通過觀察解密算法運行的時間來達到目的。其中抵抗蠻力攻擊的方法，與其它加密系統(tǒng)是一致的，使用大的密鑰空間，是窮舉無能無力，因此E和D的位數(shù)越長則越安全，但是加解密速度會越慢，所以E和d位數(shù)的長度應與實際應用系統(tǒng)有綜合的權(quán)衡。（1）RSA的選擇密文攻擊RSA在選擇密文攻擊面前很脆弱。所謂密碼分析者并不知道解密的密鑰，但是給出任意的消息，密碼分析者可以將其加密，再解密?；蛘哒f，密碼分析者能獲得解密服務(wù)。設(shè)攻擊者為A，密文接受者為T，公鑰對為（e,n）,私鑰為d,T收到的密文為c，c對應的明文為m?，F(xiàn)在A想知道m(xù) = c^d mod n，但是他不想分解n。于是T找了一個隨機數(shù)r，r n。他進行如下計算： x = r^e mod n （對r用T的公鑰加密，得到臨時密文x），y = (x * c) mod n （將臨時密文x與密文c相乘）t = r^(1) mod n。A利用了RSA加密和解密過程的特點，即：如果x = r^e mod n，那么 r = x^d mod n現(xiàn)在A要做的是使T用d對t簽名：u = t^d mod n。A需要獲得u，然后計算m = (t * u) mod n計算結(jié)果是這樣推導的：t *u mod n = [r^(1) * y^d] mod n= [r^(1) * x^d * c^d] mod n= c^d mod n= m[14]（2）RSA的公共模數(shù)攻擊若系統(tǒng)中共有一個模數(shù)，只是不同的人擁有不同的e和d，系統(tǒng)將是危險的。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那么該信息無需私鑰就可得到恢復。設(shè)P為信息明文，兩個加密密鑰為e1和e2，公共模數(shù)是n，則： C1 = P^e1 mod n C2 = P^e2 mod n密碼分析者知道n、eeC1和C2，就能得到P。因為e1和e2互質(zhì)，故用Euclidean算法能找到r和s，滿足：r * e1 + s * e2 = 1假設(shè)r為負數(shù)，需再用Euclidean算法計算C1^(1)，則 ( C1^(1) )^(r) * C2^s = P mod n 。 RSA的缺點（1）RSA產(chǎn)生密鑰很麻煩,受到素數(shù)產(chǎn)生技術(shù)的限制,因而難以做到一次一密 （2）安全性, RSA的安全性依賴于大數(shù)的因子分解，但并沒有從理論上證明破譯RSA的難度與大數(shù)分解難度等價，而且密碼學界多數(shù)人士傾向于因子分解不是NPC問題。目前，人們已能分解140多個十進制位的大素數(shù)，這就要求使用更長的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁 有私鑰的實體簽署。然后，經(jīng)過計算就可得到它所想要的信息。實際上，攻擊利用的都是同一個弱點，即存在這樣一個事實：乘冪保留了輸入的乘法結(jié)構(gòu)： XM )d = Xd *Md mod n 前面已經(jīng)提到，這個固有的問題來自于公鑰密碼系統(tǒng)的最有用的特征每個人都能使用公鑰。但從算法上無法解決這一問題，主要措施有兩條：一條是采用好的公鑰協(xié)議，保證工作過程中實體不對其他實體任意產(chǎn)生的信息解密，不對自己一無所知的信息簽名；另一條是決不對陌生人送來的隨機文檔簽名，簽名時首先使用OneWay Hash Function對文檔作HASH處理，或同時使用不同的簽名算法。除了利用公共模數(shù)，人們還嘗試一些利用解密指數(shù)或φ（n）等等攻擊. （3）速度太慢,由于RSA 的分組長度太大，為保證安全性，n 至少也要 600 bitx以上，使運算代價很高，尤其是速度較慢，較對稱密碼算法慢幾個數(shù)量級；且隨著大數(shù)分解技術(shù)的發(fā)展，這個長度還在增加，不利于數(shù)據(jù)格式的標準化。目前，SET(Secure Electronic Transaction)協(xié)議中要求CA采用2048比特長的密鑰，其他實體使用1024比特的密鑰。為了速度問題,目前人們廣泛使用單,公鑰密碼結(jié)合使用的方法,優(yōu)缺點互補:單鑰密碼加密速度快,人們用它來加密較長的文件,然后用RSA來給文件密鑰加密,極好的解決了單鑰密碼的密鑰分發(fā)問題。[15] RSA的優(yōu)點 （1）數(shù)學表達式簡單?（2）RSA的安全性基于大數(shù)分解的困難性?（3）RSA公鑰密碼體制具有一些傳統(tǒng)密碼體制不能實現(xiàn)的一些功能,如認證,鑒別和數(shù)字簽名等,特別適合于現(xiàn)代密碼通信? RSA數(shù)字簽名 RSA數(shù)字簽名的過程首先產(chǎn)生密鑰，過程如下：（1）隨機產(chǎn)生兩個等長度為K/2位的素數(shù)P 和 Q（2）然后計算公鑰 publicKey=P*Q；(publicKey 是k位的長度)（3）隨機產(chǎn)生一個加密密鑰 keyE, 2=keyE=Φ(n)1其GCD(keyE, Φ(n))=1。注意這是保證解密密鑰keyE *keyD mod Φ(n)=1 有解的充要條件，Φ(n)稱為n的歐拉函數(shù)，值為：Φ(n)=(P1)*(Q1)（4）求解解密密鑰keyD=keyE1 mod (n) ，keyE1為解密密鑰keyD的逆元 ，此公式原方程為 (keyE*keyD mod (n)=1) 由此公鑰，加密密鑰，解密密鑰全部產(chǎn)生。其次 對明文加密或?qū)γ芪倪M行解密,過程如下；（1）加密：C = Mkey^E mod publicKey；其中M表示明文,C表示密文。（2）解密：M = Ckey^D mod publicKey.；其中M表示明文,C表示密文。 RSA數(shù)字簽名算法實現(xiàn)步驟 （1）簽名算法（包括兩步：消息摘要計算，RSA加密）1 消息摘要MD的計算： 消息在簽