【正文】 y = (x * c) mod n （將臨時(shí)密文x與密文c相乘）t = r^(1) mod n。現(xiàn)在A想知道m(xù) = c^d mod n，但是他不想分解n。或者說(shuō)，密碼分析者能獲得解密服務(wù)。（1）RSA的選擇密文攻擊RSA在選擇密文攻擊面前很脆弱。（3）時(shí)間攻擊：通過(guò)觀察解密算法運(yùn)行的時(shí)間來(lái)達(dá)到目的?？偟膩?lái)分，RSA算法攻擊可以區(qū)分為三類(lèi)：（1）蠻力攻擊：它通過(guò)實(shí)驗(yàn)所用的可能私鑰，來(lái)達(dá)到目的。以當(dāng)前的計(jì)算機(jī)水平，如選擇1024位長(zhǎng)的密鑰（相當(dāng)于300位十進(jìn)制數(shù)字）就認(rèn)為是無(wú)法攻破的。（4）RSA算法面臨著數(shù)學(xué)方法的進(jìn)步和計(jì)算機(jī)技術(shù)飛躍發(fā)展帶來(lái)的破譯密碼能力日趨增強(qiáng)的嚴(yán)重挑戰(zhàn)。 （2）雖然提高N位數(shù)會(huì)大大提高RSA密碼體制的安全性，但其計(jì)算量呈指數(shù)增長(zhǎng)，以致使其實(shí)現(xiàn)的難度增大，實(shí)用性降低。 對(duì)于互素的a和n,有a^φ(n)=1(mod n) RSA安全性的分析在公布RSA算法之后，在使用RSA密碼體制和分析RSA算法發(fā)現(xiàn)了一系列的算法本身脆弱性及其存在的問(wèn)題。當(dāng)n是素?cái)?shù), φ(n)=n1。并把滿足這些條件的素?cái)?shù)稱為安全素?cái)?shù)。 RSA中的素?cái)?shù)都是上面位的十進(jìn)制數(shù)，怎樣才能選擇好的P和Q，怎樣才能生成這樣的數(shù)，并且判斷它是否為素?cái)?shù)，這是一個(gè)RSA系統(tǒng)關(guān)鍵的問(wèn)題。 RSA中素?cái)?shù)的選取在RSA中，因N=P*Q， 若P，Q被知道，即能將N因子分解，則由 Φ(n)=（P1）*(Q1)可以算出。（3）計(jì)算d,使e*d=1(mod (n)),稱d為e對(duì)模 (n)的逆，其中d為解密秘鑰，保密。 RSA加密的可行性雖然RSA加密運(yùn)算的速度十分慢,但是在PC性能越來(lái)越好的今天,對(duì)于幾千字節(jié)的數(shù)據(jù)進(jìn)行一次幾百位密鑰的RSA加密,所消耗的時(shí)間應(yīng)該是可以接受的?下面結(jié)合大數(shù)運(yùn)算程序的調(diào)試,從理論上簡(jiǎn)單的分析消耗時(shí)間?在一臺(tái)普通配置的PC機(jī)上對(duì)一個(gè)整數(shù)進(jìn)行冪模運(yùn)算,因?yàn)楣_(kāi)密鑰的e通常取的較小,所以指數(shù)取一個(gè)小整數(shù),比如C353,模一個(gè)70字節(jié)長(zhǎng)的整數(shù)(140位十六進(jìn)制,大數(shù)單元以線性組方式實(shí)現(xiàn),對(duì)應(yīng)到RSA算法中,這相當(dāng)于約560bit的n),調(diào)試一個(gè)函數(shù)測(cè)試,按初等數(shù)論中的知識(shí)對(duì)程序進(jìn)行算法優(yōu)化,最終在一臺(tái)配置為AMD Athron2800+,外頻333MHZ,物理內(nèi)存512MB的PC上測(cè)試需要約45毫秒時(shí)間?如果按這種速度,逐字節(jié)對(duì)1KB的數(shù)據(jù)進(jìn)行同樣的運(yùn)算,所消耗的時(shí)間理論上為45毫秒的1024倍即約45秒?這個(gè)時(shí)間并不是非常長(zhǎng)[12]?其實(shí)從一個(gè)簡(jiǎn)單的角度來(lái)說(shuō),既然RSA用于數(shù)字簽名可行,那就完全可以用于同樣大小的普通文件?對(duì)于較大的文件,如果分成與數(shù)字簽名同樣大小的段(這里假設(shè)數(shù)字簽名較短,不分段一次計(jì)算加密完成),分開(kāi)的各段逐一進(jìn)行加密運(yùn)算,那所需要的時(shí)間也只是按文件大小線性的增長(zhǎng)?通常數(shù)字簽名為幾十字節(jié),加密運(yùn)算并不需要很長(zhǎng)的等待,這就說(shuō)明對(duì)于幾百字節(jié)或一兩K字節(jié)大小的文件來(lái)說(shuō),如果進(jìn)行RSA加密,并不會(huì)是非常漫長(zhǎng)的工作?當(dāng)然,如果文件更大,加密就顯得十分漫長(zhǎng)了?比如按前面敘述的45毫秒大數(shù)運(yùn)算程序推理,加密1M字節(jié)大小的文件需要約1天的時(shí)間?所以,要在普通PC用幾百位以上的長(zhǎng)密鑰RSA加密文件,文件不能過(guò)大,一般可以接受的上限是幾KB?如果要在較短時(shí)間內(nèi)加密大文件,需要縮短密鑰長(zhǎng)度以減小運(yùn)算量,這將帶來(lái)安全性隱患?[13] RSA算法的介紹 RSA系統(tǒng)由以下幾部分組成：（1）隨機(jī)選取的在素?cái)?shù)P和Q，還有N ，其中N=P*Q ，P和Q保密，N公開(kāi)。因此,盡管先后出現(xiàn)了很多新的公鑰體制算法,但RSA仍然在不同應(yīng)用領(lǐng)域占據(jù)了重要的位置。實(shí)踐證明,在當(dāng)前的技術(shù)和方法下,密鑰不小于1 024 bit的RSA算法仍然是安全的?？煽啃耘c所用密鑰的長(zhǎng)度有很大關(guān)系, 假如有人找到一種很快的分解因子的算法, 即從一個(gè)公鑰中通過(guò)因數(shù)分解得到私鑰, 那么用RSA 加密的信息的可靠性肯定會(huì)極度下降。它基礎(chǔ)是數(shù)論的歐拉定理,素?cái)?shù)檢測(cè),它的安全性是基于大數(shù)分解,后者在數(shù)學(xué)上是一個(gè)困難問(wèn)題。[11]由此可看出,RSA 算法解決了大量網(wǎng)絡(luò)用戶密鑰管理的難題,這是公鑰密碼系統(tǒng)相對(duì)于對(duì)稱密碼系統(tǒng)最突出的優(yōu)點(diǎn)。如果某用戶想與另一用戶進(jìn)行保密通信,只需從公鑰簿上查出對(duì)方的加密密鑰,用它對(duì)所傳送的信息加密發(fā)出即可。而且它特別符合計(jì)算機(jī)網(wǎng)絡(luò)環(huán)境。因?yàn)樗瓤捎糜诩用?又可用于簽名,并為用戶的公開(kāi)密鑰簽發(fā)公鑰證書(shū)、發(fā)放證書(shū)、管理證書(shū)等,提高了服務(wù)質(zhì)量，所以, RSA 公開(kāi)密鑰密碼在當(dāng)今的信息交換過(guò)程中已得到廣泛的應(yīng)用和實(shí)踐，RSA 公鑰密碼體制在世界許多地方已經(jīng)成為事實(shí)上的標(biāo)準(zhǔn)。它是第一個(gè)既能用于數(shù)據(jù)加密也能用于數(shù)字簽名和密鑰分配與管理的算法。RSA 公鑰密碼算法是迄今為止在理論上最為成熟、完善的公鑰密碼體制。5 RSA算法及其數(shù)字簽名 RSA簡(jiǎn)述RSA加密體制是一種公開(kāi)的密碼體制。ECDSA可能面臨的攻擊：。在ECDLP不可破解及哈希函數(shù)足夠強(qiáng)的前提下，DSA和ECDSA的一些變形已被證明可以抵抗現(xiàn)有的任何選擇明文（密文）攻擊。而攻擊A的攻擊者的目標(biāo)是在截獲A的簽名后，可以生成對(duì)任何消息的合法簽名。（7）如果v=r，表示簽名無(wú)效；否則表示簽名有效。（5）計(jì)算X=u1G+u2Q。（3）計(jì)算w=s1mod n。3 ECDSA密鑰對(duì)驗(yàn)證過(guò)程獲得發(fā)送者的公鑰Q開(kāi)始驗(yàn)證： （1）檢查r，s，要求r，s∈(1，n1)。（4）計(jì)算s=k^1(e+d*r) mod n，如果s=O，則返回到步驟(1)。（2）計(jì)算k*G=(x1,y1)。其中q是域的階，F(xiàn)R指示域中元素的表示方法，a，b是兩個(gè)系數(shù)，G是基點(diǎn)，G的階為n，余因子h=E(Fq)／n，他是一個(gè)小的素?cái)?shù)。對(duì)于有限域上的橢圓曲線密碼系統(tǒng)，數(shù)字簽名標(biāo)準(zhǔn)建議采用橢圓曲線數(shù)字簽名算法ECDSA，下面給出該算法的過(guò)程。[9] 橢圓曲線代理簽名體制橢圓曲線簽名算法ECDSA是基于橢圓曲線密碼體制(ECC)的數(shù)字簽名算法。DSA安全性主要依賴于p和g，若選取不當(dāng)則簽名容易偽造，應(yīng)保證g對(duì)于p1的大素?cái)?shù)因子不可約。hellman算法的攻擊。RSA算法是做不到的。（3）比較r’= r 是否成立?若成立,則(r,s) 為合法簽名,則(r,s) 為簽名人對(duì)m的簽名 DSA的安全性DSA的安全性主要依賴于整數(shù)有限域離散對(duì)數(shù)難題。 （3）計(jì)算 s = k^1*(h(m)+x*r) mod q?則(r,s)為簽名人對(duì)m的簽名?3. 驗(yàn)證過(guò)程（1）首先檢查r和s是否屬于[0,q],若不是,則 (r,s)不是簽名。p,q,g 作為系統(tǒng)參數(shù),供所有用戶使用,在系統(tǒng)內(nèi)公開(kāi)?（2）用戶私鑰:用戶選取一個(gè)私鑰x,1x q,保密? （3）用戶公鑰:用戶的公鑰y,y = g^x mod p,公開(kāi)?對(duì)待簽消息m,設(shè) 0mp?簽名過(guò)程如下:（1）生成一隨機(jī)整數(shù) k, k ∈ Zp* 。 DSA數(shù)字簽名實(shí)現(xiàn)的三個(gè)步驟（1）參數(shù)與密鑰生成 （2）簽名的算法 （3）簽名的驗(yàn)證算法（1） 系統(tǒng)參數(shù):大素?cái)?shù)p, q且q為p1的因子, 并滿足2^511p2^1024, 2^159q2^160 ,以確保在 Zp中求解離散對(duì)數(shù)的困難性。它也用作于由第三方去確定簽名和所簽收數(shù)據(jù)的真實(shí)性。 DSA數(shù)字簽名算法.DSA是SChnorr和ELGAmal簽名算法的變種，被美NIST作為DSS是一種公開(kāi)密鑰算法，它不能用作加密，只能用作數(shù)字簽名。 （1）為保證簽名的速度，A先將原文進(jìn)行單向HASH運(yùn)算生成定長(zhǎng)的消息摘要A 用戶A原文消息摘要單向哈希值運(yùn)算圖31 生產(chǎn)摘要（2）利用自己的私鑰加密消息摘要得到數(shù)字簽名A，并將數(shù)字簽名附在原消息后面 用戶A原文數(shù)字簽名A用戶B用戶A原文數(shù)字簽名A用戶B 圖32 加密摘要（3）通訊時(shí)用戶A將自己的名文一起通過(guò)網(wǎng)絡(luò)送給通訊對(duì)方即用戶B數(shù)字簽名A消息摘要AA的私鑰實(shí)現(xiàn)簽名 圖33發(fā)送原文和摘要接收方B接收到發(fā)送方Ａ的簽名消息后，對(duì)Ａ的簽名消息進(jìn)行驗(yàn)證的過(guò)程如下：（1）將消息中的原消息與數(shù)字簽名分離出來(lái) 用戶B分離數(shù)字簽名A原文原文數(shù)字簽名A 圖34分離明文和數(shù)字簽名（2）使用A的公鑰解密數(shù)字簽名得到摘要解密消息摘要A數(shù)字簽名AA的私鑰A的摘要圖35得到摘要（3）利用與發(fā)送方A相同的散列函數(shù)重新計(jì)算原消息的摘要 用戶B原文消息摘要B單向哈希值運(yùn)算 圖36 接受方計(jì)算摘要（4）比較解密后獲得的消息摘要A與重新計(jì)算產(chǎn)生的消息摘要B，若相等則說(shuō)明消息在傳輸過(guò)程中沒(méi)有被篡改，否則消息不可靠。為了滿足上述4點(diǎn)要求，數(shù)字簽名體系必須滿足2條基本假設(shè)：（1）簽名密鑰是安全的，只有其擁有者才能使用。為了實(shí)現(xiàn)網(wǎng)絡(luò)環(huán)境下的身份鑒別、數(shù)據(jù)完整性認(rèn)證和抗否認(rèn)的功能，數(shù)字簽名應(yīng)滿足以下要求：（1）簽名者發(fā)出簽名的消息后，就不能再否認(rèn)自己所簽發(fā)的消息；（2）接收者能夠確認(rèn)或證實(shí)簽名者的簽名，但不能否認(rèn)；（3）任何人都不能偽造簽名；（4）第三方可以確認(rèn)收發(fā)雙方之間的消息傳送，但不能偽造這一過(guò)程，這樣，當(dāng)通信的雙方關(guān)于簽名的真?zhèn)伟l(fā)生爭(zhēng)執(zhí)時(shí)，可由第三方來(lái)解決雙方的爭(zhēng)執(zhí)。當(dāng)然，上述過(guò)程只是對(duì)報(bào)文進(jìn)行了簽名，對(duì)其傳送的報(bào)文本身并未保密。數(shù)字簽名的基本方式主要是：信息發(fā)送方首先通過(guò)運(yùn)行散列函數(shù)生成一個(gè)欲發(fā)送報(bào)文的信息摘要，然后用其私鑰對(duì)這個(gè)信息摘要進(jìn)行加密以形成發(fā)送方的數(shù)列簽名，這個(gè)數(shù)字簽名將作為報(bào)文的附件和報(bào)文一起發(fā)送給報(bào)文的接收方。以現(xiàn)在的計(jì)算機(jī)運(yùn)算能力，從一把密鑰推算出另一把密鑰是不大可能的。不同的是，非對(duì)稱密碼體系的加密和解密過(guò)程分別通過(guò)兩個(gè)不同的密鑰來(lái)實(shí)現(xiàn)，其中一個(gè)密鑰以公開(kāi)，稱為公開(kāi)密鑰，簡(jiǎn)稱公鑰，另一個(gè)有用戶自己秘密保管，稱為保密密鑰，簡(jiǎn)稱私鑰。這樣就保證了消息來(lái)源的真實(shí)性和數(shù)據(jù)傳輸?shù)耐暾浴?shù)字簽名是指用戶用自己的私鑰對(duì)原始數(shù)據(jù)的哈希摘要進(jìn)行加密所得的數(shù)據(jù)。數(shù)字簽字由公鑰密碼發(fā)展而來(lái)，它在網(wǎng)絡(luò)安全，包括身份認(rèn)證、數(shù)據(jù)完整性、不可否認(rèn)性以及匿名性等方面有著重要應(yīng)用。[6]3 數(shù)字簽名的基本概念和理論數(shù)字簽名是一種類(lèi)似寫(xiě)在紙上的普通的物理簽名，但是使用了公鑰加密領(lǐng)域的技術(shù)實(shí)現(xiàn)，用于鑒別數(shù)字信息的方法。而采用這種加密技術(shù)，即使使用最快的計(jì)算機(jī)執(zhí)行這種搜索，耗費(fèi)的時(shí)間也是相當(dāng)?shù)拈L(zhǎng)。對(duì)稱加密算法的優(yōu)點(diǎn)是保密強(qiáng)度高，加解密速度快，適合加密大量數(shù)據(jù)。對(duì)稱加密系統(tǒng)用鍵長(zhǎng)來(lái)衡量加密強(qiáng)度，40比特的鍵長(zhǎng)被認(rèn)為比較脆弱，128比特比較健壯。對(duì)稱加密有速度上的優(yōu)點(diǎn)，用軟件實(shí)現(xiàn)，對(duì)稱密鑰比非對(duì)稱密鑰快1001000倍。混亂指的是密鑰和明文及密文之間的依賴關(guān)系應(yīng)該盡量復(fù)雜，以破壞分組間的統(tǒng)計(jì)規(guī)律，通常依靠多輪迭代來(lái)實(shí)現(xiàn)；擴(kuò)散則應(yīng)使密鑰和明文的每一位影響密文中盡可能多的位數(shù)，這樣可以防止逐段破譯，并通過(guò)S盒的非線性變換來(lái)實(shí)現(xiàn)。對(duì)稱算法的加密和解密表示為： （21）對(duì)稱加密算法的典型代表有:DES，AES，3DES，RC2，RC4，RCS，RC6，IDEA等。如果當(dāng)不知道參數(shù)t是，計(jì)算的f逆函數(shù)是難解的，但但知道參數(shù)t時(shí)，計(jì)算f的逆函數(shù)是容易的，則稱f是一個(gè)單向陷門(mén)函數(shù)，參數(shù)稱為陷門(mén)。 1 單向函數(shù)（1）對(duì)于所有屬于f定義域的任一x,可以很容易算出f(x)=y.（2）對(duì)于幾乎所有屬于f值域的任一y,則在計(jì)算上不可能求出x，使得y=f(x).2 單向陷門(mén)函數(shù)設(shè)f是一個(gè)函數(shù)，t是與f有關(guān)的一個(gè)參數(shù)，對(duì)于任一給定的x。公鑰密碼體制的安全性主要取決于構(gòu)造公鑰算法所依賴的數(shù)學(xué)問(wèn)題，通常要求加密函數(shù)具有單向性，即求逆很困難。公鑰密碼算法具有如下特征：加密密鑰與解密密鑰時(shí)本質(zhì)上不通的，也就是