【正文】 解密密鑰keyD的逆元 ，此公式原方程為 (keyE*keyD mod (n)=1) 由此公鑰，加密密鑰，解密密鑰全部產(chǎn)生。為了速度問(wèn)題,目前人們廣泛使用單,公鑰密碼結(jié)合使用的方法,優(yōu)缺點(diǎn)互補(bǔ):單鑰密碼加密速度快,人們用它來(lái)加密較長(zhǎng)的文件,然后用RSA來(lái)給文件密鑰加密,極好的解決了單鑰密碼的密鑰分發(fā)問(wèn)題。除了利用公共模數(shù)，人們還嘗試一些利用解密指數(shù)或φ（n）等等攻擊. （3）速度太慢,由于RSA 的分組長(zhǎng)度太大，為保證安全性，n 至少也要 600 bitx以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)；且隨著大數(shù)分解技術(shù)的發(fā)展，這個(gè)長(zhǎng)度還在增加，不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。實(shí)際上，攻擊利用的都是同一個(gè)弱點(diǎn)，即存在這樣一個(gè)事實(shí)：乘冪保留了輸入的乘法結(jié)構(gòu)： XM )d = Xd *Md mod n 前面已經(jīng)提到，這個(gè)固有的問(wèn)題來(lái)自于公鑰密碼系統(tǒng)的最有用的特征每個(gè)人都能使用公鑰。目前，人們已能分解140多個(gè)十進(jìn)制位的大素?cái)?shù)，這就要求使用更長(zhǎng)的密鑰，速度更慢；另外，目前人們正在積極尋找攻擊RSA的方法，如選擇密文攻擊，一般攻擊者是將某一信息作一下偽裝(Blind)，讓擁 有私鑰的實(shí)體簽署。因?yàn)閑1和e2互質(zhì)，故用Euclidean算法能找到r和s，滿足：r * e1 + s * e2 = 1假設(shè)r為負(fù)數(shù)，需再用Euclidean算法計(jì)算C1^(1)，則 ( C1^(1) )^(r) * C2^s = P mod n 。最普遍的情況是同一信息用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那么該信息無(wú)需私鑰就可得到恢復(fù)。A利用了RSA加密和解密過(guò)程的特點(diǎn)，即：如果x = r^e mod n，那么 r = x^d mod n現(xiàn)在A要做的是使T用d對(duì)t簽名：u = t^d mod n。于是T找了一個(gè)隨機(jī)數(shù)r，r n。設(shè)攻擊者為A，密文接受者為T，公鑰對(duì)為（e,n）,私鑰為d,T收到的密文為c，c對(duì)應(yīng)的明文為m。所謂密碼分析者并不知道解密的密鑰，但是給出任意的消息，密碼分析者可以將其加密，再解密。其中抵抗蠻力攻擊的方法，與其它加密系統(tǒng)是一致的，使用大的密鑰空間，是窮舉無(wú)能無(wú)力，因此E和D的位數(shù)越長(zhǎng)則越安全，但是加解密速度會(huì)越慢，所以E和d位數(shù)的長(zhǎng)度應(yīng)與實(shí)際應(yīng)用系統(tǒng)有綜合的權(quán)衡。（2）數(shù)字攻擊：使用數(shù)學(xué)技巧，類似于分解N來(lái)達(dá)到目的。 RSA的攻擊RSA算法的安全性就是基于大整數(shù)的因子分解困難之上的，到目前其還是安全的，要分析RSA算法的安全性，我們從攻擊RSA的角度來(lái)審視。RSA公開(kāi)密鑰密碼算法在信息交換過(guò)程中使用比較廣泛，安全性比較高。 （3）RSA公鑰密碼體制的算法完整性（指密鑰控制加密或解密變換的唯一性）和安全性（指密碼算法除密鑰本身外，不應(yīng)該存在其它可破譯密碼體制的可能性）沿有等進(jìn)一步完善。 （1）RSA公鑰密碼體制在加密或解密中涉及大量的數(shù)值計(jì)算，其加密和解密的運(yùn)算時(shí)間比較長(zhǎng)，以致于實(shí)際使用RSA密碼體制無(wú)法應(yīng)用到軟件產(chǎn)品，必須用超大規(guī)模集成電路的硬件產(chǎn)品。n=p*q,p,q均為素?cái)?shù)時(shí),則φ(n)=φ(n)φ(n)=(p1)(q1)。 RSA用到的公式和定理（1）數(shù)和互為素?cái)?shù) 任何大于1的整數(shù)a能被因式分解為如下唯一形式： a=p1p2…pl(p1,p2,…,pl為素?cái)?shù)) （2）模運(yùn)算 ①{[a(modn)][b(mod n)]}modn≡(ab)(mod n) ②如果（ab）=（ac）(mod n),a與n互素，則 b=c(mod n) （3）費(fèi)馬定理 若p是素?cái)?shù)，a與p互素，則a ^(p1)=1 mod p （4）歐拉定理 歐拉函數(shù)φ(n)表示不大于n且與n互素的正整數(shù)的個(gè)數(shù)。針對(duì)素?cái)?shù)P和Q的選擇，1978年Rivest等人在正式發(fā)表的RSA公開(kāi)密鑰的論文中，就建議對(duì)素?cái)?shù)P和Q的選擇應(yīng)當(dāng)滿足：（1）P、Q要足夠在，在長(zhǎng)度上應(yīng)相差幾位，且二者之差與P、Q位數(shù)相近；（2）P1與Q1的最大公約數(shù)GCD(P1,Q1)就盡量??；（3）P1與Q1均應(yīng)至少含有一個(gè)大的素?cái)?shù)因子。由于e是公開(kāi)密鑰，且解密秘鑰D關(guān)于E滿足 D*E=1 (mod Φ(n))則D也不難求得，這樣RSA系統(tǒng)便被完全攻破。在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)成解密秘鑰，即私鑰。（2）任取Φ(n)=（P1）*(Q1)，其中 (n)表示比n小的素?cái)?shù)的個(gè)數(shù)，任取2=e= (n),且(e, (n))=1,e為加密密鑰，公開(kāi)。隨著計(jì)算機(jī)運(yùn)算速度的提高以及因子分解算法的突破, RSA 的密鑰長(zhǎng)度將越來(lái)越大, 其軟硬件實(shí)現(xiàn)速度將成為制約其使用的重要因素。這充分說(shuō)明RSA 系統(tǒng)具有良好的保密性能。但由于其工作量巨大,按目前計(jì)算機(jī)的處理能力是不可能實(shí)現(xiàn)的。 RSA 的安全性基于復(fù)雜性理論中的計(jì)算安全性, 依賴于大整數(shù)分解這一NP 難題。RSA 是一個(gè)基于數(shù)論的非對(duì)稱密碼體制,是一種分組密碼體制，是一種基于因子分解的指數(shù)函數(shù)作為單向陷門函數(shù)的公鑰體制算法。對(duì)方收到信息后,用僅為自己所知的解密密鑰將信息解密,了解明文的內(nèi)容。對(duì)于網(wǎng)上的大量用戶,可以將加密密鑰用電話簿的方式印出。該算法的加密密鑰和加密算法分開(kāi),使得密鑰分配更為方便。它易于理解和操作，也很流行。 從提出到現(xiàn)在已經(jīng)歷了各種攻擊的考驗(yàn)，逐漸為人們接受，普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。由于RSA算法很完善，即可用于數(shù)據(jù)加密，又可用于數(shù)字簽名，安全性良好，易于實(shí)現(xiàn)和理解，所以已經(jīng)成為一種應(yīng)用極廣的公匙密碼算法，目前，RSA在許多場(chǎng)合有廣泛的應(yīng)用。ECDMA的優(yōu)點(diǎn)（1）安全性能高（2）計(jì)算機(jī)量小和計(jì)算機(jī)速度快（3）存儲(chǔ)空間占有量?。?）帶寬要求低。在橢圓曲線所在群是一般群并且哈希函數(shù)能夠抗碰撞攻擊的前提下，ECDSA本身的安全性已經(jīng)得到證明。盡管ECDSA的理論模型很堅(jiān)固，但是人們?nèi)匝芯亢芏啻胧┮蕴岣逧CDSA的安全性。[10]ECDSA在安全性方面的目標(biāo)是能抵抗選擇明文（密文）攻擊。（6）如果X=O，表示簽名無(wú)效；否則，X=(x1，y1)，計(jì)算v=x1 mod n。（4）計(jì)算u1=e*w mod n；u2=r*w mod n。（2）計(jì)算e=SHA1(m)。（5）對(duì)消息的簽名為(r，s)，最后簽名者把消息m和簽名(r，s)發(fā)送給接收者。（3）計(jì)算r=x1 mod n；如果r=O，則返回到步驟(1)。1 ECDSA密鑰對(duì)生成過(guò)程（1）選擇一個(gè)隨機(jī)數(shù)d,d∈(1,n1)?（2）計(jì)算Q,Q=d*G?（3）那么公鑰為Q,私鑰為整數(shù)d?2 ECDSA簽名過(guò)程假設(shè)待簽名的消息為，m；（1）選擇一個(gè)隨機(jī)數(shù)k，k∈(1，n1)。假設(shè)一組橢圓曲線的參數(shù)組為(q，F(xiàn)R，a，b，G，n，h)。DSA是美國(guó)國(guó)家標(biāo)準(zhǔn)局制定的數(shù)字簽名算法，他是建立在有限域乘法群上的。DSA的一個(gè)主要特點(diǎn)是兩個(gè)素?cái)?shù)公開(kāi)，這樣，當(dāng)使用別人的p和g，即使不知道私鑰，你也能確認(rèn)他們是隨機(jī)產(chǎn)生的。M一般都應(yīng)采用信息HASH的值。素?cái)?shù)P必須足夠大，且p1至少包含一個(gè)大素?cái)?shù)因子以抵抗Pohligamp。其安全性與RSA相比差不多，DSA的一個(gè)重要特點(diǎn)是兩個(gè)素?cái)?shù)公開(kāi)，這樣，當(dāng)使用別人的P和Q是，即使不知道私鑰，你也能確認(rèn)他們是否是隨機(jī)產(chǎn)生的，還是做了手腳的。（2）計(jì)算t= s^1mod q , r’=(g^h(m) t mod q (y^r*t mod q )mod p) mod q 。（2）計(jì)算 r = (g^k mod p) mod q。g ∈ Zp , 且滿足 g =h ^(p1)/q mod p,其中h是一整數(shù), 1 h p1且h^(p1)/q modp1 。信息交流中，接受方希望收到的信息未被篡改，還希望收到的信息確實(shí)是自己認(rèn)定的發(fā)送方所發(fā)，那么接受方和發(fā)送方就可以約定，共同使用DSA來(lái)實(shí)現(xiàn)。DSA使用公開(kāi)公鑰，為接受者驗(yàn)證數(shù)據(jù)的完整性和數(shù)據(jù)發(fā)送者的身份。 驗(yàn)證失敗驗(yàn)證成功相等嗎消息摘要B消息摘要A 圖37驗(yàn)證數(shù)字簽名A的私鑰加密后的摘要加密后的摘要散列函數(shù)消息散列函數(shù)摘要加密后的摘要消息解密后的摘要解密算法摘要加密算法消息A的私鑰 圖38數(shù)字簽名流程圖 4 數(shù)字簽名常見(jiàn)的算法及其數(shù)字簽名數(shù)字簽名的方法有很多，現(xiàn)在主要應(yīng)用的數(shù)字簽名主要有：RSA，DSA以及橢圓曲線數(shù)字簽名。（2）使用簽名密鑰是產(chǎn)生數(shù)字簽名的唯一途徑。[8]對(duì)于一個(gè)典型的數(shù)字簽名體系而言，它必須包含2個(gè)重要的組成部分：即簽名算法(Signature Algorithm)和驗(yàn)證算法(Verification Algorithm)。為了同時(shí)實(shí)現(xiàn)數(shù)字簽名和秘密通信，發(fā)送者可以用接收方的公鑰對(duì)發(fā)送的信息進(jìn)行加密，這樣，只有接收方才能通過(guò)自己的私鑰對(duì)報(bào)文進(jìn)行接么，其它人即使獲得報(bào)文并知道發(fā)送者的身份，由于沒(méi)有接收方的密鑰也無(wú)法理解報(bào)文。接收方在收到信息后首先運(yùn)行和發(fā)送相同的散列函數(shù)生成接收?qǐng)?bào)文的信息摘要，然后再用發(fā)送方的公鑰進(jìn)行解密，產(chǎn)生原始報(bào)文的信息摘要，通過(guò)比較兩個(gè)信息摘要是否相同就可以確認(rèn)發(fā)送方和報(bào)文的準(zhǔn)確性。所以，數(shù)字簽名具有很大的安全性，這是它的一個(gè)優(yōu)點(diǎn)。只有相應(yīng)的公鑰能夠?qū)τ盟借€加密的信息進(jìn)行解密，反之亦然。[7] 數(shù)字簽名理論數(shù)字簽名的實(shí)現(xiàn)通常采用非對(duì)稱密碼與對(duì)稱密碼體系。信息接收方使用信息發(fā)送方的公鑰對(duì)附在原始信息后的數(shù)字簽名進(jìn)行解密后獲得哈希摘要，并通過(guò)與自己用收到的原始數(shù)據(jù)產(chǎn)生的哈希摘要對(duì)照，便可確信原始數(shù)據(jù)信息是否被篡改。特別是在大型網(wǎng)絡(luò)安全通信中的密鑰分配、認(rèn)證以及電子商務(wù)系統(tǒng)中都有重要的作用，數(shù)字簽名的安全性日益受到高度重視。一套數(shù)字簽名通常定義兩種互補(bǔ)的運(yùn)算，一個(gè)用于簽名，另一個(gè)用于驗(yàn)證。如果使用較大的密鑰，破譯將會(huì)更加的困難。攻擊 者如果對(duì)加密后的數(shù)據(jù)進(jìn)行破譯，唯一的辦法就是對(duì)每個(gè)可能的密鑰執(zhí)行窮搜索。對(duì)稱加密算法的缺點(diǎn)則是密鑰分發(fā)困難，密鑰管理難，無(wú)法實(shí)現(xiàn)數(shù)字簽名。然而，如果一個(gè)消息想以密文的形式傳到接收者，我們應(yīng)該找到一個(gè)方法安全傳輸密鑰。實(shí)際上，所有的對(duì)稱密鑰加密算法都采用Feistel網(wǎng)、S盒及多次迭代等思想。以DES為代表的對(duì)稱密鑰加密算法的設(shè)計(jì)原則主要基于信息論的混亂和擴(kuò)散。[5] 對(duì)稱加密體制 對(duì)稱加密算法，又稱私鑰加密算法，就是加密密鑰能夠從解密密鑰中推出來(lái)，反過(guò)來(lái)也成立，在大多數(shù)對(duì)稱算法中，加密解密密鑰是相同的。計(jì)算y，使得y=f(x)是容易的。因此，公鑰密碼的理論基礎(chǔ)是陷門單向函數(shù)。如RSA算法，密鑰對(duì)中的一個(gè)用于加密，另一個(gè)用于解密。數(shù)字簽名是用私鑰對(duì)數(shù)字摘要進(jìn)行加密，用公鑰進(jìn)行解密和驗(yàn)證[4]公鑰密碼算法使用兩個(gè)密鑰，其中一個(gè)用于加密(加密密鑰)，另外一個(gè)用于解密(解密密鑰)。該密碼算法也稱單向散列運(yùn)算，其運(yùn)算結(jié)果稱為哈希值，或稱數(shù)字摘要，也有人將其稱為“數(shù)字指紋”。而用私鑰加密文件公鑰解密則是用于簽名，即發(fā)方向收方簽發(fā)文件時(shí)，發(fā)方用自己的私鑰加密文件傳送給收方，收方用發(fā)方的公鑰進(jìn)行解密。但是，若想用這個(gè)乘積來(lái)求出另一個(gè)質(zhì)數(shù)，就要進(jìn)行對(duì)大數(shù)分解質(zhì)因子，分解一個(gè)大數(shù)的質(zhì)因子是十分困難的，若選用的質(zhì)數(shù)足夠大，這種求解幾乎是不可能的。而公鑰算法利用的是非對(duì)稱的密鑰，即利用兩個(gè)足夠大的質(zhì)數(shù)與被加密原文相乘生產(chǎn)的積來(lái)加/解密。 公鑰密碼原理公開(kāi)密鑰密碼常用的、成熟的公鑰算法是RSA。(3) 基于橢圓曲線離散對(duì)數(shù)問(wèn)題的：橢圓曲線密碼系統(tǒng)。根據(jù)所基于的數(shù)學(xué)難題來(lái)分類，有以下三類系統(tǒng)目前被認(rèn)為是安全和有效的：(1) 基于大整數(shù)因子分解的：RSA和RabinWilliams。公鑰密碼體制的提出首先是為了解決利用傳統(tǒng)密碼體制進(jìn)行密鑰分發(fā)時(shí)遇到的問(wèn)題，數(shù)字簽名也是其重要應(yīng)用之一。把明文加密為密文: C=E(M,Ke) 密文解密為明文：M=D(C,Kd)=D(E(M,Ke),Kd)。明文、密文、密鑰空間分別表示全體明文、全體密文、全體密鑰的集合；加密與解密算法通常是一些公式、法則或程序，規(guī)定了明文與密文之間的數(shù)學(xué)變換規(guī)則。相同時(shí)稱為對(duì)稱型或單鑰的，不相同時(shí)稱為非對(duì)成型或雙鑰的。加密時(shí)使用的為加密密碼(加密密鑰)，解密時(shí)使用的為解密密碼(解密密鑰)。把密文還原成明文的過(guò)程稱為解密(decryption)，該過(guò)程使用的數(shù)學(xué)變換，通常是加密時(shí)數(shù)學(xué)變換的逆變換，就是解密算法。偽裝(變換)之前的信息是原始信息，成為明文；偽裝之后的消息，看起來(lái)是一串無(wú)意義的亂碼，稱為密文。密碼分析學(xué)是為了取得秘密的消息，而對(duì)密碼系統(tǒng)及其流動(dòng)數(shù)據(jù)進(jìn)行分析，是對(duì)密碼原理、手段和方法進(jìn)行分析、攻擊的技術(shù)和科學(xué)。[2]2密碼學(xué)基本概念密碼學(xué)包括兩個(gè)方面：密碼編碼學(xué)和密碼分析學(xué)。（3）存在問(wèn)題目前普遍采用的數(shù)字簽名算法，都是基于下面三個(gè)數(shù)學(xué)難題的基礎(chǔ)之上：(1)整數(shù)的因式分解(Integer Factorization)問(wèn)題，如RSA算法。信息系統(tǒng)的應(yīng)用，加速了社會(huì)自動(dòng)化的進(jìn)程，減輕了日常繁雜的重復(fù)勞動(dòng)，同時(shí)也提高了生產(chǎn)率，創(chuàng)造了經(jīng)濟(jì)效益。（2）分組長(zhǎng)度太大，為保證安全性，n 至少也要 600 bits以上，使運(yùn)算代價(jià)很高，尤其是速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)。RSA目前是最有影響力的公鑰加密算法，它能夠抵抗到目前為止已知的所有密碼攻擊，已被ISO推薦為公鑰數(shù)據(jù)加密標(biāo)準(zhǔn)。RSA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也易于理解和操作。RSA在軟件方面的應(yīng)用，主要集中在Internet上。（1）研究主要成果RSA作為最重要的公開(kāi)密鑰算法，在各領(lǐng)域的應(yīng)用數(shù)不勝數(shù)。VISA、MasterCard、IBM、Microsoft等公司協(xié)力制定的安全電子交易標(biāo)準(zhǔn)（Secure Electronic Transactions，SET）就采用了標(biāo)準(zhǔn)R