網(wǎng)絡(luò)數(shù)字簽名技術(shù)研究與探索【畢業(yè)論文】

1、<p>　　本科畢業(yè)論文(設(shè)計(jì))</p><p>　題 目：網(wǎng)絡(luò)數(shù)字簽名技術(shù)研究與探索</p><p>　學(xué) 院：</p><p>　學(xué)生姓名：</p><p>　專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)</p><p>　班 級(jí)：</p><p>　指導(dǎo)教師：</p&g

2、t;<p>　起止日期：</p><p>　　網(wǎng)絡(luò)數(shù)字簽名技術(shù)研究與探索</p><p><b>　　摘 要</b></p><p>　　目前隨著因特網(wǎng)的普及和發(fā)展，越來(lái)越多的人離不開(kāi)網(wǎng)絡(luò)。網(wǎng)絡(luò)帶給了人們便捷，網(wǎng)上購(gòu)物的發(fā)展讓人們從此多了一種購(gòu)物的方式，方便快捷省事是它發(fā)展迅速的資本。</p><p>　

3、　由于網(wǎng)絡(luò)購(gòu)物涉及金錢(qián)，大家一方面對(duì)于網(wǎng)購(gòu)欲罷不能，另一方面卻在擔(dān)心自己的金錢(qián)會(huì)不會(huì)被他人取走。數(shù)字簽名插件的出現(xiàn)解決了這個(gè)問(wèn)題，即使你的密碼被他人獲取，對(duì)方依然無(wú)法取走你網(wǎng)銀中的錢(qián)。這種己方與對(duì)方互信的通訊讓網(wǎng)購(gòu)的安全性大大增加。</p><p>　　數(shù)字簽名有多種加密算法，如RSA，AES，DSS，MD5等。本文主要研究MD5，RSA和ECC在數(shù)字簽名中的應(yīng)用。MD5目前已經(jīng)廣泛應(yīng)用于對(duì)于文件的數(shù)據(jù)摘要。RS

4、A已經(jīng)在國(guó)際上廣泛驗(yàn)證，只要兩個(gè)素?cái)?shù)長(zhǎng)度夠大，破解是幾乎不可能的。ECC是目前已知的公鑰密碼體制中，對(duì)每一比特所提供加密強(qiáng)度最高的一種體制。</p><p>　　【關(guān)鍵詞】數(shù)字簽名，RSA，MD5，ECC</p><p>　　Network of digital signature technology research and explo

5、ration</p><p><b>　　Abstract</b></p><p>　　With the popularization and development of the Internet, more and more people are inseparable from the network. Netw

6、ork brings people convenient, the development of online shopping for people from now on a new shopping way,Convenient  and quick-turnaround is the rapidly developing capital.</p><p>　　As

7、the network shopping involves money, The one hand, online shopping unable to stop ，the other hand, they worried about their own money will be taken away by others. Digita

8、l certificates plug-in solves this problem, even if your password to be for others, the others still can not take away the money in your online banking. This kind of our mutual tru

9、st and communication with each other for the safety of the net buys increase greatly.</p><p>　　Digital signature have a variety of encryption algorithm,such as RSA, AES, the DSS，MD5.This paper makes a s

10、tudy of the MD5, RSA and ECC in digital signature of application.MD5 has been widely used in the data summary file.RSA has been widely verified in the international，aslongas&#

11、160;the length of the two prime numbers large enough，the crack is almost impossible.ECC is present known public key cryptosystems of, for each bit provided the highest strength encrypti

12、on system.</p><p>　　Keywords】digital signature，RSA，MD5，ECC</p><p><b>　　目錄</b></p><p><b>　　摘 要I</b></p><p>　　AbstractII</p><p>&l

13、t;b>　　1數(shù)字簽名簡(jiǎn)介1</b></p><p>　　1.1數(shù)字簽名的定義1</p><p>　　1.2 數(shù)字簽名的工作原理1</p><p>　　1.3 數(shù)字簽名的功能3</p><p>　　1.4數(shù)字簽名的問(wèn)題3</p><p>　　1.5數(shù)字簽名研究現(xiàn)狀4</p>

14、<p>　　2.Hash算法之MD55</p><p>　　2.1 MD5算法簡(jiǎn)介6</p><p>　　2.2 MD5算法原理6</p><p>　　2.3 MD5算法在數(shù)字簽名中應(yīng)用7</p><p>　　2.4 MD5算法的安全性9</p><p>　　3利用RSA的數(shù)字簽名方法和原理10

15、</p><p>　　3.1 RSA算法的基本原理10</p><p>　　3.2 RSA算法加密解密原理11</p><p>　　3.3 RSA算法在計(jì)算上的可行性12</p><p>　　3.4 RSA算法的安全性問(wèn)題12</p><p>　　3.4.1暴力破解13</p><p>

16、;　　3.4.2因子分解14</p><p>　　3.4.3選擇密文攻擊15</p><p>　　3.4.4共模攻擊15</p><p>　　3.4.5小指數(shù)攻擊16</p><p>　　3.4.6定時(shí)攻擊16</p><p>　　3.4.7RSA安全性防范16</p><p>　　

17、4橢圓曲線簽名算法18</p><p>　　4.1橢圓曲線密碼體制18</p><p>　　4.2基礎(chǔ)信息維護(hù)模塊的實(shí)現(xiàn)19</p><p>　　4.3實(shí)域R上橢圓曲線的點(diǎn)的加法運(yùn)算法則21</p><p>　　4.4有限域上橢圓曲線的運(yùn)算23</p><p><b>　　5總結(jié)25</b&

18、gt;</p><p><b>　　參考文獻(xiàn)26</b></p><p><b>　　1數(shù)字簽名簡(jiǎn)介</b></p><p>　　1.1數(shù)字簽名的定義</p><p>　　數(shù)字簽名，就是只有信息的發(fā)送者才能產(chǎn)生的別人無(wú)法偽造的一段數(shù)字串，這段數(shù)字串同時(shí)也是對(duì)信息的發(fā)送者發(fā)送信息真實(shí)性的一個(gè)有效證明

19、。</p><p>　　數(shù)字簽名是非對(duì)稱密鑰加密技術(shù)與數(shù)字摘要技術(shù)的應(yīng)用。</p><p>　　數(shù)字簽名了的文件的完整性是很容易驗(yàn)證的（不需要騎縫章，騎縫簽名，也不需要筆跡專(zhuān)家），而且數(shù)字簽名具有不可抵賴性（不需要筆跡專(zhuān)家來(lái)驗(yàn)證）。</p><p>　　簡(jiǎn)單地說(shuō),所謂數(shù)字簽名就是附加在數(shù)據(jù)單元上的一些數(shù)據(jù),或是對(duì)數(shù)據(jù)單元所作的密碼變換。這種數(shù)據(jù)或變換允許數(shù)據(jù)單元的接

20、收者用以確認(rèn)數(shù)據(jù)單元的發(fā)送起始點(diǎn)和數(shù)據(jù)單元是否完整一致并保護(hù)數(shù)據(jù)的安全,以防止被其他人篡改。數(shù)字簽名是對(duì)數(shù)據(jù)形式的信息內(nèi)容進(jìn)行簽名的一種方法,一個(gè)被簽名過(guò)的消息內(nèi)容能在一個(gè)通信網(wǎng)絡(luò)中傳輸。目前數(shù)字簽名普遍基于公鑰密碼模式，其中包括一般的數(shù)字簽名算法和特別的數(shù)字簽名算法。一般的數(shù)字簽名算法有Fiat-Shamir、ElGamal、Guillou- Quisquarte、RSA/DES/DSA數(shù)字簽名算法，橢圓曲線數(shù)字簽名算法。特別的數(shù)字簽

21、名算法有盲簽名、代理簽名、群簽名、不可否認(rèn)簽名、公平盲簽名、門(mén)限簽名、擁有信息復(fù)原功能的簽名算法等。很明顯,數(shù)字簽名的運(yùn)用觸及到法律問(wèn)題,美國(guó)政府在建立于有限域上的離散對(duì)數(shù)問(wèn)題規(guī)定了自己的數(shù)字簽名標(biāo)準(zhǔn)(DSS)。數(shù)字簽名的運(yùn)作模式是，信息內(nèi)容發(fā)送方利用自己的私鑰對(duì)原文件內(nèi)容使用HASH提取出來(lái)的信息摘要進(jìn)行加密處理，完成對(duì)信息內(nèi)容的合法簽名，信息內(nèi)容獲得方則利用發(fā)送方公開(kāi)的公鑰來(lái)解密獲到的數(shù)字簽名，并將解密后的結(jié)果作用于對(duì)信息內(nèi)容的完整

22、性的測(cè)</p><p>　　1.2 數(shù)字簽名的工作原理</p><p>　　發(fā)送報(bào)文時(shí)，發(fā)送方用一個(gè)哈希函數(shù)從報(bào)文文本中生成報(bào)文摘要,然后使用其私鑰對(duì)這個(gè)摘要進(jìn)行加密，這個(gè)加密后的摘要將作為報(bào)文的數(shù)字簽名和報(bào)文一起發(fā)送給接收方，接收方首先用與發(fā)送方一樣的哈希函數(shù)從接收到的原始報(bào)文中計(jì)算出報(bào)文摘要，接著再用發(fā)送方的公用密鑰來(lái)對(duì)報(bào)文附加的數(shù)字簽名進(jìn)行解密，如果這兩個(gè)摘要相同、那么接收方就能確

23、認(rèn)該數(shù)字簽名是發(fā)送方的。</p><p>　　運(yùn)用數(shù)字簽名一般要用到以下幾個(gè)步驟:</p><p>　　(1)個(gè)體生成或者獲得唯一的加密密碼組。</p><p>　　(2)信息發(fā)送方在計(jì)算機(jī)上備置一個(gè)文件內(nèi)容。</p><p>　　(3)信息發(fā)送方用一種安全的哈希函數(shù)對(duì)備置好的文件內(nèi)容使用生成信息摘要。數(shù)字簽名由一個(gè)信息摘要生成。該函數(shù)值由被

24、簽名的信息內(nèi)容以及信息發(fā)送方的私鑰生成,并對(duì)其而言是具有唯一性的。為了保證哈希函數(shù)生成的信息摘要的安全,應(yīng)該使利用任何消息和私鑰的組合而生成一模一樣的數(shù)字簽名的可能性為無(wú)。</p><p>　　(4)信息發(fā)送方通過(guò)運(yùn)用私鑰將信息摘要進(jìn)行加密。私鑰通過(guò)運(yùn)用一種特定的加密算法被運(yùn)用在信息摘要內(nèi)容中。</p><p>　　(5)信息發(fā)送方將數(shù)字簽名附著在信息內(nèi)容之后。</p>&l

25、t;p>　　(6)信息發(fā)送方將數(shù)字簽名和信息內(nèi)容(加過(guò)密或未經(jīng)加過(guò)密)發(fā)送給信息接收方。</p><p>　　(7)信息接收方使用信息發(fā)送方的公鑰確認(rèn)信息發(fā)送方的數(shù)子簽名的安全性。使用信息發(fā)送方的公鑰對(duì)數(shù)字簽名進(jìn)行解密，以確保信息來(lái)自發(fā)送方，并未經(jīng)修改。</p><p>　　(8)信息接收方使用同樣安全的哈希函數(shù)對(duì)信息內(nèi)容進(jìn)行運(yùn)算，以獲得信息摘要。</p><p&

26、gt;　　(9)信息接收方比較獲得的兩個(gè)信息摘要，如果兩者一樣,則信息接收方可以確認(rèn)信息內(nèi)容在簽名后并未被作任何修改。信息內(nèi)容被簽名后哪怕是僅僅一個(gè)字節(jié)的修改,信息接收方創(chuàng)建的數(shù)據(jù)摘都會(huì)和信息發(fā)送方創(chuàng)建的數(shù)據(jù)摘要有所區(qū)別。</p><p>　　(10)信息接收方從CA處獲得認(rèn)證證書(shū)(或者是通過(guò)信息發(fā)件人獲得),這個(gè)證書(shū)是用來(lái)確認(rèn)信息接收方發(fā)出的信息內(nèi)容上的數(shù)字簽名的真實(shí)性。CA在數(shù)字簽名系統(tǒng)中是一個(gè)典型的第三方受

27、委托管理證明業(yè)務(wù)。該證書(shū)包含信息發(fā)送方的公鑰以及其他可能附加的信息,由CA在該信息內(nèi)容上進(jìn)行數(shù)字簽名。</p><p>　　數(shù)字簽名有兩種功效：一是數(shù)字簽名能確定消息的完整性。二是能確定消息確實(shí)是由發(fā)送方簽名并發(fā)出來(lái)的，因?yàn)閯e人假冒不了發(fā)送方的簽名。因?yàn)閿?shù)字簽名的特點(diǎn)是它代表了文件的特征，文件如果發(fā)生改變，數(shù)字簽名的值也將發(fā)生變化。不同的文件將得到不同的數(shù)字簽名。一次數(shù)字簽名涉及到一個(gè)哈希函數(shù)、發(fā)送者的公鑰、發(fā)送

28、者的私鑰。</p><p>　　1.3 數(shù)字簽名的功能</p><p>　　歸納起來(lái)，數(shù)字簽名技術(shù)可以解決偽造、篡改、冒充、抵賴等問(wèn)題，其功能主要表現(xiàn)在以下幾方面:</p><p>　　(l)第一，簽名是可信的。因?yàn)楹灻呔褪乾F(xiàn)實(shí)中的那個(gè)人，數(shù)字簽名是根據(jù)文件的內(nèi)容而變，所以簽名的內(nèi)容就是簽名者想要表達(dá)的真實(shí)意愿。</p><p>　　(2)

29、第二，簽名是不可偽造。大家相信其他人不可能仿冒簽名者的簽名，因?yàn)楹灻借€只有簽名者知道，其他人不可能構(gòu)造出正確的簽名數(shù)據(jù)。</p><p>　　(3)簽名是不可重用的。其他人不可能將簽名動(dòng)到另外的文件上，因?yàn)楹灻歉鶕?jù)文件的內(nèi)容而產(chǎn)生的，即使被移動(dòng)，解密后的信息和原來(lái)的也是完全兩個(gè)意思，接收者可輕易發(fā)現(xiàn)。</p><p>　　(4)簽名后的文件是不可篡改的。人們確信不可對(duì)已經(jīng)簽名的文件作任

30、何更改，因?yàn)閿?shù)字簽名與原始文件內(nèi)容及其用函數(shù)產(chǎn)生的摘要一起發(fā)送給接收者，一旦消息被篡改，接收者可通過(guò)計(jì)算摘要和驗(yàn)證簽名來(lái)判斷該文件無(wú)效，從而保證了數(shù)據(jù)的正確性。</p><p>　　(5)簽名不可抵賴。數(shù)字簽名作為信息發(fā)送方簽名操作的證據(jù)，可以防止簽名者抵賴。要防止信息接收方的抵賴，可以在數(shù)字簽名中請(qǐng)求信息接收方發(fā)送一個(gè)己方簽名的表明已經(jīng)收到的信息，給信息發(fā)送方或雙方都信任的第三方機(jī)構(gòu)。假如信息接收方不返回任意消

31、息，則這次通信可結(jié)束或者重新開(kāi)始，信息發(fā)送方也沒(méi)有什么損失，因此雙方均不可抵賴。</p><p>　　(6)防多放攻擊。如在電子商務(wù)中，A向B發(fā)送了一筆物品訂單，如果有不法之徒中途獲取訂單并發(fā)送多筆訂單給B，這樣會(huì)引起B(yǎng)以為A購(gòu)買(mǎi)了多筆物品。在數(shù)字簽名中，通常采用對(duì)簽名文件附上時(shí)間戳或增加處理流水號(hào)等技術(shù)，這樣便可以阻止多放攻擊。</p><p>　　1.4數(shù)字簽名的問(wèn)題</p>

32、;<p>　　在生活中，有冒充簽名的，有私刻單位印章的。而數(shù)字簽名的引入，不可避免的也帶來(lái)一些新問(wèn)題:</p><p>　　(l)基礎(chǔ)設(shè)施的使用費(fèi)問(wèn)題。是收費(fèi)還是免費(fèi)，這些都將影響到該技術(shù)的推廣速度以及開(kāi)發(fā)者和民眾的接受程度。</p><p>　　(2)假設(shè)某人發(fā)送消息后脫離了其原屬組織，被取消了原先的數(shù)字簽名的權(quán)限，以往發(fā)送的數(shù)字簽名在鑒定時(shí)只能在取消確認(rèn)列表中找到原有確認(rèn)

33、信息，這樣就需要鑒定中心結(jié)合時(shí)間信息進(jìn)行鑒定，這需要鑒定中心的建立健全。</p><p>　　(3)要求數(shù)字簽名需要被認(rèn)可并被大量推廣，如果發(fā)送方的消息已經(jīng)進(jìn)行了數(shù)字簽名，那么接收方一定要有數(shù)字簽名相關(guān)軟件才可處理。</p><p>　　(4)需要立法機(jī)關(guān)對(duì)數(shù)字簽名有足夠重視，并且在法律建設(shè)上加快腳步，迅速制定相關(guān)法律，以充分實(shí)現(xiàn)數(shù)字簽名具有的作用。</p><p>

34、;　　數(shù)字簽名實(shí)際上就是使用了某些算法變換了所需傳輸?shù)南ⅲc傳統(tǒng)的手工簽名和印章有著根本的不同?，F(xiàn)實(shí)中手工簽名是模擬的，因人而異，不同的人，其寫(xiě)法必定是不同的，寫(xiě)出來(lái)的字當(dāng)然也會(huì)不同;數(shù)字簽名是針對(duì)文件內(nèi)容處理后的數(shù)據(jù)，即O和l的數(shù)據(jù)串，是因文件內(nèi)容而異的，同一個(gè)人，對(duì)不同的文件內(nèi)容，其簽名結(jié)果是完全不同的。</p><p>　　傳統(tǒng)手工簽名中，簽名與文件本身的內(nèi)容是互相分開(kāi)的;而數(shù)字簽名中，簽名是因文件內(nèi)容而

35、異的，換句話說(shuō)簽名與本身文件內(nèi)容已經(jīng)組成了一個(gè)混合的整體數(shù)據(jù)，原有文件內(nèi)容的修改必定會(huì)反映至數(shù)字簽名的改變。所以，數(shù)字簽名相比傳統(tǒng)手寫(xiě)簽名更具有可靠性。</p><p>　　1.5數(shù)字簽名研究現(xiàn)狀</p><p>　　本文主要以MD5和RSA以及ECC三個(gè)算法對(duì)數(shù)字簽名目前的加密技術(shù)進(jìn)行討論。</p><p>　　目前對(duì)消息提取摘要的一般為雜湊函數(shù)，構(gòu)造雜湊函數(shù)的方

36、法有兩種：一種是直接構(gòu)造，比如MD5雜湊算法和安全雜湊函數(shù)(SHA) ；另一種是非直接構(gòu)造，主要是利用目前已有的分組加密算法，諸如DES、AES等，對(duì)其稍加改造，采取通過(guò)它們加密的非線性變換構(gòu)造雜湊函數(shù)。</p><p>　　MD5雜湊算法可以說(shuō)是目前應(yīng)用最廣泛的Hash算法，而它是以MD4為基礎(chǔ)設(shè)計(jì)的。它在MD4的基礎(chǔ)上增加了"安全-帶子"（safety-belts）的概念。雖然MD5比MD

37、4復(fù)雜度大一些，但卻更為安全。</p><p>　　RSA以模算術(shù)方式將指數(shù)應(yīng)用于加密和解密之中，是非對(duì)稱密碼技術(shù)中最著名的一種。其安全性依賴于大數(shù)因子分解問(wèn)題。雖然在理論上RSA是可以被破解的，但經(jīng)過(guò)多年對(duì)于RSA安全性的密碼分析，我們既不能證明也不能否認(rèn)其安全性，這恰恰說(shuō)明該算法有一定的可信度。</p><p>　　ECC的主要優(yōu)勢(shì)是在某些情況下它比其他的方法使用更小的密鑰——比如RS

38、A加密算法——提供相當(dāng)?shù)幕蚋叩燃?jí)的安全。ECC的另一個(gè)優(yōu)勢(shì)是可以定義群之間的雙線性映射，基于Weil對(duì)或是Tate對(duì)；雙線性映射已經(jīng)在密碼學(xué)中發(fā)現(xiàn)了大量的應(yīng)用，例如基于身份的加密。</p><p>　　2.Hash算法之MD5</p><p>　　隨著信息安全技術(shù)的發(fā)展,Hash函數(shù)的重要性日益提高,它在公鑰密碼、數(shù)字簽名、完整性檢驗(yàn)、身份認(rèn)證等安全領(lǐng)域中有著廣泛的應(yīng)用。Hash函數(shù)是將

39、任意長(zhǎng)的數(shù)字串m映射成一個(gè)較短的定長(zhǎng)輸出的數(shù)字串H的函數(shù)，以h表承函數(shù)名，h(m) 易于計(jì)算，稱H = h(m) 為m的雜湊值。這個(gè)H又被稱為輸入m的數(shù)字指紋或消息摘要。h是多對(duì)一映射，因此無(wú)法從H來(lái)求解出原先的m，但可以證明任何給出序列m，是否與m有一模一樣的雜湊值。若雜湊函數(shù)h為單向性函數(shù)，則稱函數(shù)h是單向雜湊函數(shù)。適用于信息證明的雜湊函數(shù)全部都是單向雜湊函數(shù)。單向雜湊函數(shù)按照它是否有密鑰要求分為兩種：一種是有密鑰要求的，以h(k,

40、 m) 表示，是密鑰雜湊函數(shù)；另一種是無(wú)密鑰要求的，是一般雜湊函數(shù)。無(wú)密鑰要求的單向雜湊函數(shù)，其雜湊值只是輸入字串的函數(shù)，所有人均可計(jì)算，因而不具備身份驗(yàn)證功能，只適用于檢測(cè)獲得的數(shù)據(jù)的完整性。雜湊函數(shù)在實(shí)際中有廣泛應(yīng)用，在密碼學(xué)和信息安全技術(shù)中，它是實(shí)現(xiàn)安全數(shù)字簽名和驗(yàn)證的主要方法，是安全驗(yàn)證協(xié)議中的主要模塊。為了抵抗各種攻擊，所應(yīng)用的雜湊函數(shù)需滿足機(jī)密，鑒別，完整性，不可否認(rèn)性等密碼學(xué)性質(zhì)[2]。</p><p&

41、gt;　　其中消息摘要像現(xiàn)實(shí)生活中的指紋一樣可以驗(yàn)證一個(gè)人身份的唯一性一樣,Hash函數(shù)也可用于驗(yàn)證一個(gè)消息的唯一性。正是由于這個(gè)特性,Hash函數(shù)在信息安全的認(rèn)證領(lǐng)域中得到廣泛應(yīng)用。Hash函數(shù)主要有MDx系列和SHA系列, MDx系列包括MD4,MD5,HAVAL,RIPEMD等;SHA系列包括Sha-1,Sha-256,Sha-384等,這些 Hash 算法體現(xiàn)了目前主要的Hash 函數(shù)設(shè)計(jì)技術(shù)。那么這些Hash算法到底有什么用呢

42、?</p><p>　　Hash算法在信息安全方面的應(yīng)用主要體現(xiàn)在以下的3個(gè)方面：</p><p><b>　　1) 文件校驗(yàn) ；</b></p><p><b>　　2) 數(shù)字簽名 ；</b></p><p><b>　　3) 鑒權(quán)協(xié)議 。</b>

43、;</p><p>　　在信息安全領(lǐng)域中應(yīng)用的Hash算法，還需要滿足其他關(guān)鍵特性：</p><p><b>　　第一當(dāng)然是單向性；</b></p><p><b>　　第二是抗沖突性；</b></p><p>　　第三是映射分布均勻性和差分分布均勻性。</p><p>　　

44、在2004年國(guó)際密碼年會(huì)上,一種破解Hash函數(shù)的辦法被王小云等中國(guó)科研工作者發(fā)表,減少很多攻擊算法的繁雜性,而且有關(guān)于碰撞的實(shí)例在PC上運(yùn)算就可以找到。這個(gè)問(wèn)題對(duì)于目前的hash函數(shù)來(lái)說(shuō)是非常嚴(yán)峻,因此這也促進(jìn)了先進(jìn)的Hash算法的開(kāi)發(fā)。本文以MD5為例對(duì)其在數(shù)字簽名中的應(yīng)用進(jìn)行討論。</p><p>　　2.1 MD5算法簡(jiǎn)介</p><p>　　MD5可以說(shuō)是目前應(yīng)用最廣泛的Hash

45、算法，而它是以MD4為基礎(chǔ)設(shè)計(jì)的。</p><p>　　1) MD4 ：MD4是一種由麻省理工學(xué)院教授Ronald Rivest于1990年發(fā)明的信息摘要算法。它是一種密碼散列函數(shù)實(shí)行，可以用來(lái)測(cè)試信息的完整性。其摘要長(zhǎng)度為128位。這個(gè)算法后來(lái)影響了如MD5、SHA 家族和RIPEMD等。1991年Den Boer和Bosselaers發(fā)表了一篇文章指出MD4的不足之處，至今未能找到基于MD4以上改進(jìn)

46、的算法有任何可以用來(lái)進(jìn)攻的弱點(diǎn)。2004年8月王小云報(bào)告在計(jì)算MD4時(shí)可能發(fā)生雜湊沖撞[3]。</p><p>　　2) MD5：MD5即Message-Digest Algorithm 5（信息-摘要算法 5），用于確保信息傳輸完整一致。是計(jì)算機(jī)廣泛使用的雜湊算法之一（又譯摘要算法、哈希算法），主流編程語(yǔ)言普遍已有MD5實(shí)現(xiàn)。將數(shù)據(jù)（如漢字）運(yùn)算為另一固定長(zhǎng)度值，是雜湊算法的基礎(chǔ)原理，MD5的前身有M

47、D2、MD3和MD4[4]。它比MD4的進(jìn)步之處在于：</p><p>　　1) 每一個(gè)步驟都有一個(gè)獨(dú)一無(wú)二的加法常數(shù)；</p><p><b>　　2)第四輪被加入；</b></p><p>　　3) 對(duì)稱性的減少由第二輪中的G函數(shù)從((X ∧ Y) ∨ (X ∧ Z) ∨ (Y ∧ Z)) 變?yōu)?((X ∧ Z) ∨ (Y ∧～Z))來(lái)體現(xiàn)

48、；</p><p>　　4) 前一步的得出來(lái)的結(jié)果都被并入了下一步，以加快"雪崩效應(yīng)"；</p><p>　　5) 訪問(wèn)輸入子分組的順序在第2輪和第3輪中被改變了，減小了形式的相似度；</p><p>　　6) 每一輪的循環(huán)左移位移量被近似優(yōu)化了，以期加快"雪崩效應(yīng)"，各輪的循環(huán)左移都不同。雖然MD5比MD4要復(fù)雜一點(diǎn)，而且速

49、度也要慢一點(diǎn)，但是在抗差分和抗分析方面表現(xiàn)的更好[5]。</p><p>　　2.2 MD5算法原理</p><p>　　信息內(nèi)容一開(kāi)始被拆成若干個(gè)512位的分組，其中最后的512位分組是“消息尾+填充字節(jié)(100…0)+64位消息長(zhǎng)度”，以保證對(duì)于不同長(zhǎng)度的消息，該分組不相同。64位消息長(zhǎng)度的限制導(dǎo)致了MD5安全的輸入長(zhǎng)度必須小于264bit，因?yàn)榇笥?4位的長(zhǎng)度信息將被忽略。而4個(gè)32

50、位寄存器字初始化為A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210，它們將始終參與運(yùn)算并形成最終的散列結(jié)果。接著各個(gè)512位消息分組以16個(gè)32位字的形式進(jìn)入算法的主循環(huán)，512位消息分組的個(gè)數(shù)據(jù)決定了循環(huán)的次數(shù)。主循環(huán)有4輪，每輪分別用到了非線性函數(shù)F(X, Y, Z) = (X ∧ Y) ∨ (～X ∧ Z) G(X, Y, Z) = (X ∧ Z) ∨ (Y ∧～Z)

51、 H(X, Y, Z) =X ⊕ Y ⊕ Z I(X, Y, Z) = X ⊕ (Y ∨～Z) 這4輪變換是對(duì)進(jìn)入主循環(huán)的512位消息分組的16個(gè)32位字分別進(jìn)行如下操作：將A、B、C、D的副本a、b、c、d中的3個(gè)經(jīng)F、G、H、I運(yùn)算后的結(jié)果與第4個(gè)相加，再加上32位字和一個(gè)32位字的加法常數(shù)，并</p><p>　　2.3 MD5算法在數(shù)字簽名中應(yīng)用</p><

52、;p>　　數(shù)字簽名的核心內(nèi)容是保證簽名或者傳輸?shù)男畔](méi)有被人非法竄改過(guò), 從這種意義上來(lái)說(shuō), 數(shù)字簽名算法只需要提供一種機(jī)制來(lái)驗(yàn)證信息的完整性和原始性, 而不需要提供解密機(jī)制, 也就是說(shuō)數(shù)字簽名算法可以是非可逆的。</p><p>　　不過(guò)MD5算法是不可逆的。由于算法的某些不可逆特征, 在數(shù)字簽名上有較好的安全性。并且,MD5算法的使用不需要支付任何版權(quán)費(fèi)用。正是由于這些原因使得 MD5 算法成為人們?cè)O(shè)計(jì)

53、數(shù)字簽名算法時(shí)所最先考慮的算法。盡管目前有報(bào)道稱王小云教授破解了 MD5 算法, 但是這并不影響其安全性。因?yàn)?MD5和 SHA- 1屬于散列算法, 從設(shè)計(jì)原理來(lái)講, 就有產(chǎn)生碰撞的可能, 王小云教授的方法縮短了找到碰撞的時(shí)間, 是一項(xiàng)重要的成果。但她找到的是強(qiáng)無(wú)碰撞, 要能找到弱無(wú)碰撞,才算真正破解, 才有實(shí)際意義。碰撞分為強(qiáng)無(wú)碰撞和弱無(wú)碰撞。強(qiáng)無(wú)碰撞是無(wú)法產(chǎn)生有實(shí)際意義的原文的, 也就無(wú)法篡改和偽造出有意義的明文。通過(guò)強(qiáng)無(wú)碰撞偽造一

54、個(gè)誰(shuí)也看不懂的東西, 沒(méi)有實(shí)際意義。而數(shù)字簽名算法的用途不是對(duì)明文加密, 讓別人看不懂, 而是通過(guò)對(duì)信息摘要的比對(duì),防止對(duì)原文的篡改[7]。從這種意義上來(lái)講, MD5 算法依然是安全的。</p><p>　　MD5 算法是 MD4 算法的改進(jìn)算法。Ron Rivest于1990年提出 MD4 單向散列函數(shù), MD 表示消息摘要(Message Digest) , 對(duì)輸入消息, 算法產(chǎn)生 128位散列值。該算法首次

55、公布之后, Bert den Boer 和AntoonBosselaers對(duì)算法三輪中的后兩輪進(jìn)行了成功的密碼分析。在一個(gè)不相關(guān)的分析結(jié)果中,Ralph MerKle成功地攻擊了前兩輪。盡管這些攻擊都沒(méi)有擴(kuò)展到整個(gè)算法, 但Rivest還是改進(jìn)了其算法, 結(jié)果就是MD5 算法。MD5 算法是 MD4 的改進(jìn)算法, 它比 MD4 更復(fù)雜, 但設(shè)計(jì)思想相似, 輸入的消息可任意長(zhǎng), 輸出結(jié)果也仍為 128位, 特別適用于高速軟件實(shí)現(xiàn), 是基于

56、32- 位操作數(shù)的一些簡(jiǎn)單的位操作[8]。</p><p><b>　　算法描述:</b></p><p>　　該算法的輸入是一個(gè)字節(jié)串, 每個(gè)字節(jié) 8 個(gè)bit。算法的執(zhí)行分為以下幾個(gè)步驟:</p><p>　　第一步, 補(bǔ)位:MD5 算法先對(duì)輸入的數(shù)據(jù)進(jìn)行補(bǔ)位, 使得數(shù)據(jù)的長(zhǎng)度( 以 byte 為單位) 對(duì) 64 求余的結(jié)果是 56。即數(shù)據(jù)

57、擴(kuò)展至 LEN= K* 64+ 56 個(gè)字節(jié), K 為整數(shù)。補(bǔ)位方法: 補(bǔ)一個(gè) 1, 然后補(bǔ) 0 至滿足上述要求。相當(dāng)于補(bǔ)一個(gè) 0x80 的字節(jié), 再補(bǔ)值為 0 的字節(jié)。這一步里總共補(bǔ)充的字節(jié)數(shù)為0~ 63個(gè)。</p><p>　　第二步, 附加數(shù)據(jù)長(zhǎng)度:用一個(gè)64 位的整數(shù)表示數(shù)據(jù)的原始長(zhǎng)度( 以bit 為單位) , 將這個(gè)數(shù)字的 8 個(gè)字節(jié)按低位的在前, 高位在后的順序附加在補(bǔ)位后的數(shù)據(jù)后面。這時(shí), 數(shù)據(jù)被填

58、補(bǔ)后的總長(zhǎng)度為:LEN = K* 64+ 56+ 8= ( K+ 1) * 64 Bytes。# 注意那個(gè)64 位整數(shù)是輸入數(shù)據(jù)的原始長(zhǎng)度而不是填充字節(jié)后的長(zhǎng)度[9]。</p><p>　　第三步, 初始化 MD5參數(shù):有4 個(gè) 32 位整數(shù)變量 ( A, B, C, D) 用來(lái)計(jì)算信息摘要, 每一個(gè)變量被初始化成以下以十六進(jìn)制數(shù)表示的數(shù)值, 低位的字節(jié)在前面。</p><p>　　wor

59、d A: 01 23 45 67</p><p>　　word B: 89 ab cd ef</p><p>　　word C: fe dc ba 98</p><p>　　word D: 76 54 32 10</p><p>　　第四步, 定義四個(gè)MD5 基本的按位操作函數(shù):</p><p>　　X, Y, Z 為

60、 32 位整數(shù)。</p><p>　　F( X, Y, Z) = ( X and Y) or ( not( X) and Z)</p><p>　　G( X, Y, Z) = ( X and Z) or ( Y and not( Z) )</p><p>　　HH( a, b, c, d, Mj, s, ti) 表示 a= b+ ( ( a+ ( H ( b, c,

61、 d) +Mj+ ti) <<< s)</p><p>　　I( X, Y, Z) = Y xor ( X or not( Z) )</p><p>　　再定義四個(gè)分別用于四輪變換的函數(shù)。設(shè)Mj表示消息的第 j 個(gè)子分組( 從 0 到 15) ,<<< s 表示循環(huán)左移 s 位, 則四種操作為:</p><p>　　FF( a,

62、b, c, d, Mj, s, ti) 表示 a= b+ ( ( a + ( F( b, c, d) + Mj+ ti) <<< s)</p><p>　　G( X, Y, Z) = ( X and Z) or ( Y and not( Z) )</p><p>　　HH( a, b, c, d, Mj, s, ti) 表示 a= b+ ( ( a+ ( H ( b, c

63、, d) +Mj+ ti) <<< s)</p><p>　　II( a, b, c, d,M j, s, ti) 表示 a= b+ ( ( a+ ( I( b, c, d) + Mj+ti) <<< s)</p><p>　　第五步, 對(duì)輸入數(shù)據(jù)作變換:處理數(shù)據(jù),N 是總的字節(jié)數(shù), 以 64 個(gè)字節(jié)為一組, 每組作一次循環(huán), 每次循環(huán)進(jìn)行四輪操作。要變

64、換的 64 個(gè)字節(jié)用 16 個(gè) 32 位的整數(shù)數(shù)組 M[ 0. . . 15] 表示。而數(shù)組 T [ 1 . . . 64] 表示一組常數(shù), T[ i] 為 4294967296* abs( sin( i) ) 的 32 位整數(shù)部分, i的單位是弧度, i的取值從 1 到 64。MD5 的典型應(yīng)用是對(duì)一段信息( message) 產(chǎn)生信息摘要( message- digest) , 以防止被篡改[10]。比如,45在unix下有很多軟件

65、在下載的時(shí)候都有一個(gè)文件名相同, 文件擴(kuò)展名為. md5 的文件, 在這個(gè)文件中通常只有一行文本, 大致結(jié)構(gòu)如:</p><p>　　MD5 ( tanajiya. tar. gz)= 0ca175b9c0f726a831d895e269332461</p><p>　　這就是tanajiya. tar. gz文件的數(shù)字簽名。MD5將整個(gè)文件當(dāng)作一個(gè)大文本信息, 通過(guò)其不可逆的字符串變換算

66、法, 產(chǎn)生了這個(gè)唯一的MD5 信息摘要。如果在以后傳播這個(gè)文件的過(guò)程中, 無(wú)論文件的內(nèi)容發(fā)生了任何形式的改變( 包括人為修改或者下載過(guò)程中線路不穩(wěn)定引起的傳輸錯(cuò)誤等) , 只要你對(duì)這個(gè)文件重新計(jì)算MD5 時(shí)就會(huì)發(fā)現(xiàn)信息摘要不相同, 由此可以確定你得到的只是一個(gè)不正確的文件。如果再有一個(gè)第三方的認(rèn)證機(jī)構(gòu), 用 MD5還可以防止文件作者的抵賴,這就是所謂的數(shù)字簽名應(yīng)用[10]。</p><p>　　2.4 MD5算法

67、的安全性</p><p>　　從安全的角度講，MD5的輸出為128位，若采用純強(qiáng)力攻擊尋找一個(gè)消息具有給定Hash值的計(jì)算困難性為2128，用每秒可試驗(yàn)1000000000個(gè)消息的計(jì)算機(jī)需時(shí)1.07×1022年。若采用生日攻擊法，尋找有相同Hash值的兩個(gè)消息需要試驗(yàn)264個(gè)消息，用每秒可試驗(yàn)1000000000個(gè)消息的計(jì)算機(jī)需時(shí)585年。在目前的信息系統(tǒng)中，對(duì)md5加密方法的利用主要通過(guò)在腳本頁(yè)面中引

68、用包含md5加密函數(shù)代碼的文件，以asp腳本為例，在需要調(diào)用的頁(yè)面中加入，md5.asp為md5加密函數(shù)代碼文件，然后直接調(diào)用函數(shù)MD5(sMessage)即可，md5加密后的值有16位和32位之分，如果在md5加密函數(shù)中使用的是MD5 = LCase(WordToHex(a) &WordToHex(b) &WordToHex(c) &WordToHex(d))，則表示是32位，如果使用的是MD5=LCase(W

69、ordToHex(b) &WordToHex(c))，則表示是16位。</p><p>　　3利用RSA的數(shù)字簽名方法和原理</p><p>　　RSA加密算法是一種非對(duì)稱加密算法。在公鑰加密標(biāo)準(zhǔn)和電子商業(yè)中RSA被廣泛使用。RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonar

70、d Adleman）一起提出的。當(dāng)時(shí)他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_(kāi)頭字母拼在一起組成的。它是一個(gè)基于數(shù)論理論的非對(duì)稱密碼體制。</p><p>　　對(duì)極大整數(shù)做因數(shù)分解的難度決定了RSA算法的可靠性。換言之，對(duì)一極大整數(shù)做因數(shù)分解愈困難，RSA算法愈可靠。盡管如此，只有一些RSA算法的變種]被證明為其安全性依賴于因數(shù)分解。假如有人找到一種快速因數(shù)分解的算法的話，那么用RSA加密的信息的可靠

71、性就肯定會(huì)極度下降。但找到這樣的算法的可能性是非常小的。今天只有短的RSA鑰匙才可能被強(qiáng)力方式解破。到2008年為止，世界上還沒(méi)有任何可靠的攻擊RSA算法的方式。只要其鑰匙的長(zhǎng)度足夠長(zhǎng)，用RSA加密的信息實(shí)際上是不能被解破的。但在分布式計(jì)算和量子計(jì)算機(jī)理論日趨成熟的今天，RSA加密安全性受到了挑戰(zhàn)。RSA是第一個(gè)不僅能用于加密也能適用于數(shù)字簽名的算法，同時(shí)易于理解和操作。RSA是被研究得最廣泛的公鑰算法，從提出到現(xiàn)在己經(jīng)二十多年，經(jīng)歷了

72、各種攻擊的考驗(yàn)，逐漸為人們接受。普遍認(rèn)為是目前最優(yōu)秀的公鑰方案之一。RSA的安全性依賴于大數(shù)的因子分解，但并沒(méi)有從理論上證明破譯RSA的難度與大數(shù)分解難度等價(jià)，即RSA的重大缺陷是無(wú)法從理論上把握它的保密性能如何[11]。</p><p>　　RSA的缺點(diǎn)主要有:</p><p>　　(l)產(chǎn)生密鑰很麻煩。由于受到素?cái)?shù)產(chǎn)生技術(shù)的限制，因而難以做到一次一密。</p><p

73、>　　(2)分組長(zhǎng)度過(guò)大。為了保證密鑰安全性，至少也要600bits以上，使計(jì)算機(jī)的運(yùn)算代價(jià)很高，尤其是運(yùn)算速度較慢，較對(duì)稱密碼算法慢幾個(gè)數(shù)量級(jí)，且隨著大數(shù)分解技術(shù)的不斷發(fā)展，這個(gè)長(zhǎng)度還在相應(yīng)的增加，這不利于數(shù)據(jù)格式的標(biāo)準(zhǔn)化。</p><p>　　3.1 RSA算法的基本原理</p><p>　　假設(shè)Bob想給Alice送一個(gè)消息m，他知道Alice產(chǎn)生的N和e。他使用起先與Alic

74、e約好的格式將m轉(zhuǎn)換為一個(gè)小于N的整數(shù)n，比如他可以將每一個(gè)字轉(zhuǎn)換為這個(gè)字的Unicode碼，然后將這些數(shù)字連在一起組成一個(gè)數(shù)字。假如他的信息非常長(zhǎng)的話，他可以將這個(gè)信息分為幾段，然后將每一段轉(zhuǎn)換為n。利用公式他可以將n加密為c，計(jì)算c并不復(fù)雜。Bob算出c后就可以將它傳遞給Alice。Alice得到Bob的消息c后就可以利用她的密鑰d來(lái)解碼。她可以用公式來(lái)將c轉(zhuǎn)換為n，得到n后，她可以將原來(lái)的信息m重新復(fù)原。解碼的原理是 錯(cuò)誤!未找到

75、引用源。以及ed ≡ 1 (mod p-1)和ed ≡ 1 (mod q-1)[13]。</p><p>　　3.2 RSA算法加密解密原理</p><p>　　因?yàn)閑*d=1mod (n) 即e*d=k(n)+1所以：Med=Mk(n)+1</p><p>　　如果M和n互素，即gcd(M,n)=1那么，根據(jù)歐拉定理(如

76、果gcd(a,n)=1，則aФ(n)≡1 mod n：</p><p>　　有： M(n)≡1 mod n</p><p>　　所以：Med ≡ Mk(n)+1 ≡M[M(n) ]kmod n</p><p>　　≡M[1]kmod n</p><p><b>　　≡M mod n</b></p><

77、;p>　　如果M和n不互素，即gcd(M,n)≠1，即M和n有大于1的公約數(shù)。因?yàn)閚=pq，而p、q都是素?cái)?shù)，不可再分解，所以M一定包含了p或q為因子。又因?yàn)镸<n，所以M不可能既是p的倍數(shù)又是q的倍數(shù)。不妨設(shè)M是p的倍數(shù)，M=cp。由于M不是q的倍數(shù)，所以gcd(M,q)=1，則M(q) ≡1 mod q ，所以：</p><p>　　[M(q) ] (p)≡1 mod q 即</p>

78、<p>　　M(n) ≡1 mod n，即</p><p>　　M(n) =1+kqM(n)=1+kq兩邊同乘以M=cp，則：</p><p>　　M(n)+1=M+kqcp=M+kcn把kc看作一個(gè)常數(shù)，則：</p><p>　　M(n)+1=M+tn，即</p><p>　　M(n)+1≡M mod n，即</p>

79、<p>　　M(n) ≡1 mod n因?yàn)閑d=1 mod (n)，所以：</p><p>　　Med ≡ Mk(n)+1 ≡M[M(n) ]kmod n</p><p>　　≡ M[1]kmod n</p><p><b>　　≡ M mod n</b></p><p>　　綜上,這樣的e，d，n可以實(shí)

80、現(xiàn)加密C=Memod n和解密M=Cdmod n</p><p>　　3.3 RSA算法在計(jì)算上的可行性</p><p>　　無(wú)論是加密還是解密都需要計(jì)算某個(gè)整數(shù)的模n整數(shù)次冪，即C=Me mod n、M=Cd mod n。但不需要先求出整數(shù)的冪再對(duì)n取模，而可利用模運(yùn)算的性質(zhì)：(a mod n) * (b mod n)= (a*b) mod n</p><p>

81、;　　對(duì)于Me mod n，可先求出M1 mod n，M2 mod n，M4 mod n……，再求Me mod n</p><p>　　由于n是公開(kāi)的，為了避免攻擊者用窮舉法求出p和q（根據(jù)n=pq），應(yīng)該從足夠大的集合中選取p和q，即p和q必須是大素?cái)?shù)。</p><p>　　目前還沒(méi)有有效的方法可以產(chǎn)生任意大素?cái)?shù)，通常使用的方法是：隨機(jī)挑選一個(gè)期望大小的奇數(shù)，然后測(cè)試它是否是素?cái)?shù)，若不是

82、，則挑選下一個(gè)隨機(jī)數(shù)直至檢測(cè)到素?cái)?shù)為止。</p><p><b>　　例如：</b></p><p>　　選p=7，q=17。</p><p>　　求n=p×q=119，φ(n)=(p-1)(q-1)=96。</p><p>　　取e=5，滿足1<e<φ(n)，且gcd(φ(n),e)=1。確定滿足

83、d*e=1 mod 96且小于96的d，因?yàn)?7×5=385=4×96+1，所以d為77。</p><p>　　因此公開(kāi)鑰為{5，119}，秘密鑰為{77，119}。設(shè)明文m=19，則由加密過(guò)程得密文為</p><p>　　C=195mod 119≡2476099 mod 119=66</p><p>　　解密為6677mod 119=19<

84、;/p><p>　　3.4 RSA算法的安全性問(wèn)題</p><p>　　RSA算法的安全性就是基于大整數(shù)的因子分解困難之上的，雖然到目前其還是安全的，但是隨著人類(lèi)計(jì)算能力的不斷提高，RSA的安全性還是有待考證。由于分解算法的進(jìn)一步改進(jìn)。分解算法過(guò)去都采用二次篩法，如對(duì)RSA-129的分解。而對(duì)RSA-130的分解則采用了一個(gè)新算法，稱為推廣的數(shù)域篩法，該算法在分解RSA-130時(shí)所做的計(jì)算僅比

85、分解SA-129多10%。將來(lái)也可能還有更好的分解算法，因此在使用RSA算法時(shí)對(duì)其密鑰的選取要特別注意其大小。估計(jì)在未來(lái)一段比較長(zhǎng)的時(shí)期，密鑰長(zhǎng)度介于1024比特至2048比特之間的RSA是安全的。但是它本身卻存在著一些缺陷，綜合來(lái)說(shuō)，RSA算法的不足或者缺陷主要包括：</p><p>　?。ㄒ唬㏑SA算法所要求的n，p，q都要求為很大的整數(shù)或素?cái)?shù)，實(shí)現(xiàn)時(shí)采用的是重復(fù)平方求模和相乘后求模的迭代方法來(lái)實(shí)現(xiàn)，此方法在

86、進(jìn)行數(shù)據(jù)加密時(shí)耗費(fèi)時(shí)間過(guò)長(zhǎng)。　?。ǘ㏑SA算法中所用的p，q如果太接近的話，密碼分析者可以通過(guò)計(jì)算，然后在附近搜索p，q來(lái)分解n?！　。ㄈ?duì)于一個(gè)明文消息m（0≤m＜n),如果將其加密成m自身，稱m為RSA的不動(dòng)點(diǎn)，也成m為未隱匿的消息。對(duì)RSA算法來(lái)講其不動(dòng)點(diǎn)的個(gè)數(shù)為（1+gcd((e-1)，(p+1)))*(1+gcd((e-1)，(q-1))。由于e-1，p-1，q-1都是偶數(shù)，所以RSA不動(dòng)點(diǎn)的個(gè)數(shù)至少為9個(gè)?！　。ㄋ?/p>

87、）同態(tài)性。由RSA算法知對(duì)于一切x1，x2∈Zn，有E*k（x1，x2）≡E*k(x1)E*k(modn)是RSA算法的一個(gè)缺陷，因?yàn)楣粽咧繡1,C2的明文，就可以知道C1C2(modn)對(duì)應(yīng)明文m1m2（modn）[14]?！　』谝陨系娜毕?，攻擊者想來(lái)對(duì)RSA算法進(jìn)行攻擊的一系列攻擊方法，其中最常用的攻擊方法有因子分解攻擊、選擇密文攻擊、同模攻擊、小指數(shù)/指數(shù)攻擊、迭代循環(huán)攻擊、定時(shí)攻擊等。為了防止可以很容易地分解n，RS&l

88、t;/p><p>　　1.P和q的長(zhǎng)度應(yīng)僅相差幾位。對(duì)于1024位的密鑰而言，p和q都應(yīng)在1075到10100之間;</p><p>　　2.(p-1)和(q-1)都應(yīng)有一個(gè)大的素因子;</p><p>　　3.Gcd(p-1,q-1)應(yīng)該較小。</p><p>　　雖然目前是RSA只要密鑰長(zhǎng)度適合還是安全的，但是我們還是要注意目前存在的RSA攻

89、擊模式：</p><p>　　暴力破解:通過(guò)選取所有可能的私鑰來(lái)達(dá)到目的;</p><p>　　技巧類(lèi):通過(guò)使用數(shù)學(xué)技巧，分解n來(lái)達(dá)到目的;</p><p>　　時(shí)間攻擊:通過(guò)查看算法運(yùn)行的時(shí)間來(lái)達(dá)到目的。</p><p><b>　　3.4.1暴力破解</b></p><p>　　對(duì)于第一種暴力

90、破解，只要密鑰選取足夠的長(zhǎng)度，窮舉法是無(wú)能為力的。雖然對(duì)于算法的執(zhí)行速度有所影響，但相對(duì)于數(shù)據(jù)的安全性，還是值得犧牲的。</p><p><b>　　3.4.2因子分解</b></p><p>　　目前大部分進(jìn)行RSA密碼分析的討論都熱忠于對(duì)n進(jìn)行素因子分解。易知，若n=p*q被因子分解，則可以得到p(n)=(p-1)*(q-1)的值，從而利用e*d≡l(mod(Φ（

91、n）))解出d。較早出現(xiàn)的因子分解攻擊方法是試除法，即通過(guò)嘗試小于n的所有素?cái)?shù)，來(lái)找到因子。這種辦法理論上是有效的，但對(duì)于大數(shù)n，由于要花費(fèi)更多時(shí)間使其變得不可能完成。　　由于因子分解的時(shí)間復(fù)雜性并未降到多項(xiàng)式時(shí)間，所以仍是一個(gè)計(jì)算上的難題。但是隨著計(jì)算速度的提高，分解的速度會(huì)越來(lái)越快.因此我們通常把因子分解的性能作為評(píng)價(jià)RSA安全性的基準(zhǔn)。</p><p>　　對(duì)于比較大的密鑰的安全性的攻擊威脅主要來(lái)自兩個(gè)方

92、面:計(jì)算能力的增長(zhǎng)和因子分解算法的不斷改進(jìn)。</p><p>　　在計(jì)算機(jī)出現(xiàn)之前，對(duì)擁有比較大的素因子的數(shù)進(jìn)行因子分解是極其不容易的，不過(guò)計(jì)算機(jī)出現(xiàn)之后，特別是基于網(wǎng)絡(luò)的分布式計(jì)算機(jī)，略微降低了因子分解的困難程度和時(shí)間長(zhǎng)度。例如，Mirtin Gardner在1977年“Scientific American”的專(zhuān)欄文章中介紹了RSA碼。為了顯示這一技術(shù)的威力，RSA公司的研究人員用一個(gè)129位的數(shù)N和一個(gè)4位

93、數(shù)e 對(duì)這個(gè)關(guān)于禿鷹的消息作了編碼。Gardner刊登了那個(gè)密文，同時(shí)給出了N和e。RSA公司還懸賞100美元，獎(jiǎng)給第一個(gè)破譯這密碼的人。</p><p>　　96869 61375 46220 61477 14092 22543 55882 90575 99911 24574 31987 46951 20930 81629 82251 45708 35693 14766 22883 98962 80133 91

94、990 55182 99451 57815 154</p><p>　　一批松散組成的因子分解迷，大約有六百多人，分布在二十幾個(gè)國(guó)家。他們經(jīng)過(guò)八個(gè)月的努力最后于1994年4月為RSA-129找到了64位數(shù)和65位數(shù)兩個(gè)素?cái)?shù)因子。</p><p>　　11438 16257 57888 86766 92357 79976 14661 20102 18296 72124 23625 62561

95、 84293 57069 35245 73389 78305 97123 56395 87050 58989 07514 75992 90026 87954 3541 = 34905 29510 84765 09491 47849 61990 38981 33417 76463 84933 87843 99082 0577 * 32769 13299 32667 09549 96198 81908 34461 41317 76429 6

96、7992 94253 97982 88533 </p><p>　　“The magic words are squeamish ossifrage” </p><p>　　目前進(jìn)行因子分解，一般采用二次篩或廣義數(shù)域篩等算法。其中廣義數(shù)域篩是一種較新的算法，例如其對(duì)于比十進(jìn)制129位更大的整數(shù)只使用10%的計(jì)算量就可以進(jìn)行分解。還有一種稱為特殊數(shù)域篩的方法，對(duì)分解某種特殊形式的整數(shù)，比廣義

97、數(shù)域篩更加快速有效。隨著因子分解新方法的產(chǎn)生，目前使用的64位或128位密鑰已經(jīng)不安全了，有的學(xué)者建議使用1O24位或者更長(zhǎng)的模n。</p><p>　　3.4.3選擇密文攻擊</p><p>　　選擇密文攻擊是通過(guò)騙取掌握私鑰者的簽名實(shí)現(xiàn)攻擊，RSA在選擇密文攻擊面前很脆弱。一般攻擊者是將某一信息作一下偽裝 (Blind)，讓擁有私鑰的實(shí)體簽署。然后，經(jīng)過(guò)計(jì)算就可得到它所想要的信息。假設(shè)

98、攻擊者截獲了密文y，想得到明文x，可以采用如下方法：選擇一個(gè)隨機(jī)數(shù)r，r<n，然后使用收件人的公鑰加密r，假設(shè)得到的中間結(jié)果為t，顯然t=re(modn)；然后將中間結(jié)果t與截獲的密文相乘，假設(shè)得到O，O=t*Y(modn)，想辦法騙取收件人用私鑰d對(duì)O進(jìn)行簽名，假設(shè)簽名后的結(jié)果為u，u=O(modn)，得到u后，攻擊者計(jì)算值f=r-1(modn)，結(jié)合u就可以計(jì)算出明文X。</p><p>　　前面已經(jīng)提

99、到，這個(gè)問(wèn)題來(lái)自于公鑰密碼系統(tǒng)中最有用的特征——每個(gè)人都能使用公鑰，光從算法上無(wú)法解決這一難題，主要方法有兩條:一條是采用好的公鑰協(xié)議，保證工作過(guò)程中一個(gè)個(gè)體不對(duì)其他個(gè)體任意產(chǎn)生的信息解密，不對(duì)自己無(wú)法知曉的信息簽名;另一條是不對(duì)無(wú)法確認(rèn)的個(gè)體送來(lái)的隨機(jī)文檔簽名，簽名時(shí)優(yōu)先使用One- WayHashFunction對(duì)文檔作HASH處理，或同時(shí)使用不同的簽名算法。</p><p><b>　　3.4.4

100、共模攻擊</b></p><p>　　共模攻擊是由于在RSA體制的實(shí)現(xiàn)過(guò)程中，不同用戶使用相同的模n、不同的指數(shù)值e和d所引起的。由于出現(xiàn)這種情況可能導(dǎo)致下列三個(gè)主要問(wèn)題，所以會(huì)使得系統(tǒng)變得不再安全。</p><p>　　1.若相同的明文分送給兩個(gè)不同的使用者，且此二使用者的公開(kāi)密鑰為互素，則此系統(tǒng)并不安全。</p><p>　　2.擁有一對(duì)的加/解密密

101、鑰就能因子分解n。</p><p>　　3.擁有一對(duì)加/解密密鑰，能在不必分解n的情況下，求出另一對(duì)加解密密鑰。</p><p>　　若系統(tǒng)中共同擁有一個(gè)模數(shù)n，僅是不同的個(gè)體擁有不同的e和d，則系統(tǒng)將是不安全的。普遍情況是同一內(nèi)容用不同的公鑰加密，這些公鑰共模而且互質(zhì)，那么該內(nèi)容無(wú)需私鑰就可得到恢復(fù)?？傊绻澜o定模數(shù)的一對(duì)e和d，那么第一是有利于攻擊者計(jì)算出其它成對(duì)的e’和d’，而

102、無(wú)需分解模數(shù)，第二是有利于攻擊者分解模數(shù)。解決的方法只有一個(gè)，那就是不需要分享模數(shù)n。</p><p>　　3.4.5小指數(shù)攻擊</p><p>　　從計(jì)算速度角度考慮，為了提高RSA的運(yùn)算速度，公鑰指數(shù)e越小加密速度越快,有人建議使公鑰e取較小的值，這樣會(huì)使加密變得易于實(shí)現(xiàn)，速度提高。可是，當(dāng)明文也很小時(shí)就會(huì)出現(xiàn)問(wèn)題。比如我們?nèi)=3，明文x小于N 的三次方，密文y= 錯(cuò)誤!未找到引用源

103、。 (modN)= 錯(cuò)誤!未找到引用源。 (modN)= 錯(cuò)誤!未找到引用源。，這樣直接對(duì)密文y開(kāi)三次方就會(huì)得到明文x,對(duì)付辦法就是e和d都取較大的值。</p><p><b>　　3.4.6定時(shí)攻擊</b></p><p>　　定時(shí)攻擊主要針對(duì)RSA核心運(yùn)算是非常耗時(shí)間的模乘，只要能精確監(jiān)視RSA的解密過(guò)程，獲得解密時(shí)間，就可以估算出私有密鑰d。模指數(shù)運(yùn)算是通過(guò)一位

104、一位來(lái)計(jì)算的，每次迭代執(zhí)行一次模乘，并且如果當(dāng)前位是l，則還需要進(jìn)行一次模乘．對(duì)于有些密碼，后一次模乘執(zhí)行速度會(huì)極慢，攻擊者就可以在觀測(cè)數(shù)據(jù)解密時(shí)，根據(jù)執(zhí)行時(shí)間判斷當(dāng)前位是1還是0。</p><p>　　3.4.7 RSA安全性防范</p><p>　　針對(duì)RSA算法的固有缺陷和對(duì)RSA算法的常見(jiàn)攻擊方法，我們可以采取以下幾種措施對(duì)其進(jìn)行防范：</p><p>　　

105、（一）為了保證安全性，在選取p、q時(shí)使用較大的素?cái)?shù)，因式分解理論的研究現(xiàn)狀表明：使用RSA密鑰至少需要1024比特，才能有效的保證攻擊者無(wú)法在短時(shí)間破解得到因子。</p><p>　?。ǘ┩ㄟ^(guò)設(shè)計(jì)新的素?cái)?shù)生成方案，保證為每一用戶生成不同的大素?cái)?shù)，從而消除用戶共模，避免系統(tǒng)遭受共模攻擊。　?。ㄈ┕€e不可選得過(guò)小，使攻擊者很難通過(guò)開(kāi)方得到密文?！　。ㄋ模┩ㄟ^(guò)常數(shù)取冪時(shí)間，隨即延時(shí)，在加密前對(duì)數(shù)據(jù)做盲化處理盲

106、化等方法對(duì)定時(shí)攻擊進(jìn)行防范[15]?！　SA算法是第一個(gè)能同時(shí)用于加密和數(shù)字簽名的算法，也是被研究得最為廣泛的公鑰算法，從1978年提出到現(xiàn)在的三十多年里經(jīng)歷了各種攻擊的考驗(yàn)，被認(rèn)為是目前最優(yōu)秀的公鑰方案之一。但是， RSA的安全性還需要不斷的研究和改進(jìn)，這就使得我們?cè)趹?yīng)用時(shí)既要注意使用安全和環(huán)境安全，發(fā)揮RSA自身的優(yōu)勢(shì)，同時(shí)也要重視多種密碼體制并用，不斷研究和發(fā)現(xiàn)新的密碼體制，來(lái)滿足人們的通信安全保密需求。</p>

107、<p>　　目前，SET(SecureElectronic Transaction)協(xié)議中要求CA采用2048比特長(zhǎng)的密鑰，其他實(shí)體使用1024比特的密鑰。由于進(jìn)行的都是大數(shù)計(jì)算，使得RSA的速度相比同類(lèi)計(jì)算要慢，無(wú)論是軟件還是硬件實(shí)現(xiàn)。速度一直是RSA的缺陷。</p><p><b>　　4橢圓曲線簽名算法</b></p><p>　　橢圓曲線密碼學(xué)（E

108、lliptic curve cryptography，縮寫(xiě)為ECC）是基于橢圓曲線數(shù)學(xué)的一種公鑰密碼的方法。橢圓曲線在密碼學(xué)中的使用是在1985年由Neal Koblitz和Victor Miller分別獨(dú)立提出的。ECC的主要優(yōu)勢(shì)是在某些情況下它比其他的方法使用更小的密鑰——比如RSA加密算法——提供相當(dāng)?shù)幕蚋叩燃?jí)的安全。ECC的另一個(gè)優(yōu)勢(shì)是可以定義群之間的雙線性映射，基于Weil對(duì)或是Tate對(duì)；雙線性映射已經(jīng)在密碼學(xué)中發(fā)現(xiàn)了大量

109、的應(yīng)用，例如基于身份的加密。不過(guò)一個(gè)缺點(diǎn)是加密和解密操作的實(shí)現(xiàn)比其他機(jī)制花費(fèi)的時(shí)間長(zhǎng)[16]。</p><p>　　在數(shù)學(xué)上，橢圓曲線為一代數(shù)曲線，被下列式子所定義: 錯(cuò)誤!未找到引用源。其是無(wú)奇點(diǎn)的；亦即，其圖形沒(méi)有尖點(diǎn)或自相交。若 錯(cuò)誤!未找到引用源。，其中P為任一沒(méi)有重根的三次或四次多項(xiàng)式，然后可得到一虧格1的無(wú)奇點(diǎn)平面曲線，其通常亦被稱為橢圓曲線。更一般化地，虧格為1的代數(shù)曲線，如兩個(gè)三維二次曲面相交，即