數(shù)字簽名和哈希函數(shù)

1、數(shù)字簽名和哈希函數(shù)懂得一點(diǎn)公鑰密碼基礎(chǔ)知識的人都知道，發(fā)信息的人用自己的私鑰對所發(fā)信息進(jìn)行加密（Encryption）,接收信息者用發(fā)信者的公鑰來解密（Decryption）,就可以保證信息的真實(shí)性、完整性和不可否認(rèn)性。（注：這里提到的加密、解密是指密碼運(yùn)算，其目的并非信息保密。）那么，我們也可以籠統(tǒng)地說，以上方法就已經(jīng)達(dá)到了數(shù)字簽名的目的。因?yàn)槭紫龋借€是發(fā)信者唯一持有的，別的任何人不可能制造出這份密文來，所以可以相信這份密文以及對應(yīng)的明文不是偽造的（當(dāng)然，發(fā)信者身份的確定還要通過數(shù)字證書來保證）；出于同樣原因，發(fā)信者也不能抵賴、否認(rèn)自己曾經(jīng)發(fā)過這份信息；另外，信息在傳輸當(dāng)中不可能被篡改，因

2、為如果有人試圖篡改，密文就解不出來。這樣，用私鑰加密，公鑰解密的技術(shù)方法就可以代替?zhèn)鹘y(tǒng)簽名、蓋章，保證了信息的真實(shí)性、完整性和不可否認(rèn)性。但是，這樣做在實(shí)際使用中卻存在一個(gè)問題：要發(fā)的信息可能很長，非對稱密碼又比較復(fù)雜，運(yùn)算量大，而為了保證安全，私鑰通常保存在USBKey或IC卡中，加密運(yùn)算也是在Key或卡中進(jìn)行。一般來說，小小的USBKey或IC卡中的微處理器都做得比較簡單而處理能力較弱，這樣，加密所用的時(shí)間就會很長而導(dǎo)致無法實(shí)用。另外，即使對于網(wǎng)站服務(wù)器而言，雖然它的處理能力很強(qiáng)，但服務(wù)器要同時(shí)處理許許多多簽名加密的事情，也同樣存在著加密耗時(shí)長系統(tǒng)效率低的問題。有沒有解決這個(gè)問題的辦法呢？

3、有的，常用的方法是使用哈希函數(shù)。什么是哈希函數(shù)哈希（Hash）函數(shù)在中文中有很多譯名，有些人根據(jù)Hash的英文原意譯為“散列函數(shù)”或“雜湊函數(shù)”,有些人干脆把它音譯為“哈希函數(shù)”,還有些人根據(jù)Hash函數(shù)的功能譯為“壓縮函數(shù)”、“消息摘要函數(shù)”、“指紋函數(shù)”、“單向散列函數(shù)”等等。1、Hash算法是把任意長度的輸入數(shù)據(jù)經(jīng)過算法壓縮，輸出一個(gè)尺寸小了很多的固定長度的數(shù)據(jù)，即哈希值。哈希值也稱為輸入數(shù)據(jù)的數(shù)字指紋（DigitalFingerprint）或消息摘要MMessageDigest）等。Hash函數(shù)具備以下的性質(zhì)：2、給定輸入數(shù)據(jù)，很容易計(jì)算出它的哈希值；3、反過來，給定哈希值，倒推出輸入

4、數(shù)據(jù)則很難，計(jì)算上不可行。這就是哈希函數(shù)的單向性，在技術(shù)上稱為抗原像攻擊性；4、給定哈希值，想要找出能夠產(chǎn)生同樣的哈希值的兩個(gè)不同的輸入數(shù)據(jù)，（這種情況稱為碰撞，Collision）,這很難，計(jì)算上不可行，在技術(shù)上稱為抗碰撞攻擊性；5、哈希值不表達(dá)任何關(guān)于輸入數(shù)據(jù)的信息。哈希函數(shù)在實(shí)際中有多種應(yīng)用，在信息安全領(lǐng)域中更受到重視。從哈希函數(shù)的特性，我們不難想象，我們可以在某些場合下，讓哈希值來“代表”信息本身。例如，檢驗(yàn)哈希值是否發(fā)生改變，借以判斷信息本身是否發(fā)生了改變。怎樣構(gòu)建數(shù)字簽名好了，有了Hash函數(shù)，我們可以來構(gòu)建真正實(shí)用的數(shù)字簽名了。發(fā)信者在發(fā)信前使用哈希算法求出待發(fā)信息的數(shù)字摘要，然

5、后用私鑰對這個(gè)數(shù)字摘要，而不是待發(fā)信息本身，進(jìn)行加密而形成一段信息，這段信息稱為數(shù)字簽名。發(fā)信時(shí)將這個(gè)數(shù)字簽名信息附在待發(fā)信息后面，一起發(fā)送過去。收信者收到信息后，一方面用發(fā)信者的公鑰對數(shù)字簽名解密，得到一個(gè)摘要H;另一方面把收到的信息本身用哈希算法求出另一個(gè)摘要H',再把H和H'相比較，看看兩者是否相同。根據(jù)哈希函數(shù)的特性，我們可以讓簡短的摘要來“代表”信息本身，如果兩個(gè)摘要H和H'完全符合，證明信息是完整的；如果不玄，就說明信息被人篡改了。數(shù)字簽名也可以用在非通信，即離線的場合，同樣具有以上功能和特性。由于摘要一般只有128位或160位比特，比信息本身要短許多倍，U

6、SBKey或IC卡心的微處理器對摘要進(jìn)行加密就變得很容易,數(shù)字簽名的過程一般在一秒鐘內(nèi)即可完成。一數(shù)字摘要TQ哈希送篁數(shù)字簽名=在1起稽了I有人篡改!兩者相同嗎？g公鑰解密不同仁哈希運(yùn)算哈希函數(shù)的安全性哈希函數(shù)的安全性直接關(guān)系到數(shù)字簽名的安全性，如果哈希函數(shù)被攻破，數(shù)字簽名的彳藪性就會受到質(zhì)疑。目前，已經(jīng)發(fā)明的Hash函數(shù)有多種，如Snefru、N-Hash、LOKI、AR、GOST、MD、SHA等。它們在數(shù)學(xué)上實(shí)現(xiàn)的方法各有不同，安全性也各有不同。目前比較常用的Hash函數(shù)是MD5和SHA-1。MD5哈希函數(shù)以512位來處理輸入數(shù)據(jù)，每一分組又劃分為16個(gè)32位的子分組。算法的輸出由4個(gè)32

7、位分組組成，將它們級聯(lián)起來，形成一加了數(shù)學(xué)運(yùn)算的復(fù)雜程度，即SHA=MD4+擴(kuò)展轉(zhuǎn)換+附加輪+更好的雪崩效應(yīng)（哈希值中，個(gè)128位的固定長度的哈希值，即輸入數(shù)據(jù)的摘要。SHA-1哈希函數(shù)在MD4的基礎(chǔ)上增為0的比特和為1的比特，其總數(shù)應(yīng)該大致相等；輸入數(shù)據(jù)中一個(gè)比特的變化，將導(dǎo)致哈希值中一半以上的比特變化，這就叫做雪崩效應(yīng)）。SHA能夠產(chǎn)生160位的哈希值。對SHA還沒有已知的密碼攻擊，并且由于它產(chǎn)生的哈希值位數(shù)長于MD5,所以它能更有效地抵抗窮舉攻擊（包括生日攻擊）。但是，任何一種算法都有其漏洞和局限性。任何一個(gè)哈希函數(shù)都會存在碰撞一一即在一些特定情況下，兩個(gè)不同的文件或信息會指向同一個(gè)數(shù)字

8、摘要。在一般情況下，類似碰撞只能盡可能地減少，而不能完全避免。從理論上講，沒有攻不破的密碼。隨著密碼科學(xué)的發(fā)展，也許會找到攻破某一種密碼算法的途徑。評彳HHash算法的一個(gè)最好方法是看敵手找到一對碰撞消息所花的代價(jià)有多高。一般地，假設(shè)攻擊者知道Hash算法，攻擊者的主要攻擊目標(biāo)是找到一對或更多對碰撞消息。目前已有一些攻擊Hash算法和計(jì)算碰撞消息的方法。在這些方法中，有些是一般的方法，可用于攻擊任何類型的Hash算法，比如“生日攻擊”；而另一些是特殊的方法，只能用于攻擊某些特殊的Hash算法，比如適合于攻擊具有分組鏈結(jié)構(gòu)Hash算法的“中間相遇攻擊”，適用于攻擊基于模運(yùn)算的Hash函數(shù)的“修正

9、分組攻擊”。堅(jiān)固的哈希函數(shù)可通過設(shè)計(jì)有效的碰撞處理機(jī)制，或增加數(shù)字摘要的位數(shù)來增加復(fù)雜度，以減少碰撞出現(xiàn)的概率，2004年8月17日，在美國召開的國際密碼學(xué)會議（Crypto'2004）上，一些國家的密碼學(xué)者作了破譯Hash函數(shù)的新進(jìn)展的報(bào)告，其中我國山東大學(xué)的王小云教授做了破譯MD5、HAVAL-128、MD4、和RIPEMD算法的報(bào)告。到2005年2月，據(jù)王小云教授的研究報(bào)告，他們已經(jīng)研究出了搜索SHA-1碰撞的一系列新技術(shù)。他們的分析表明，SHA-1的碰撞能在小于2A69次Hash操作中找到。對完整的80輪SHA-1的攻擊，這是第一次在小于2A80次Hash操作這個(gè)理論界限的情況

10、下找到碰撞。根據(jù)他們的估計(jì)，對于縮減到70輪的SHA-1能夠用現(xiàn)在的超級計(jì)算機(jī)找出“實(shí)碰撞”。他們的研究方法，能自然地運(yùn)用到SHA-0和縮減輪數(shù)的SHA-1的破譯分析上。2005年3月6日，ArjenLenstra,王小云，BennedeWeger宣布，他們構(gòu)造出一對基于MD5Hash函數(shù)的X.509證書，產(chǎn)生了相同的簽名。他們提出了一種構(gòu)造X.509證書的方法，在他們所構(gòu)造出的證書對中，由于使用了MD5算法，簽名部分產(chǎn)生了碰撞。因此，當(dāng)證書發(fā)布者使用MD5作為Hash函數(shù)時(shí)，發(fā)布者就會在證書中產(chǎn)生相同的簽名，導(dǎo)致PKI的基礎(chǔ)原理遭到可信性破壞。這意味著，從單獨(dú)某個(gè)證書無法確定是否存在另一個(gè)不

11、同證書有著相同的簽名。由于第二個(gè)相同簽名證書存在的可能性，證書發(fā)布機(jī)構(gòu)無法驗(yàn)證私鑰的“擁有證明”，即無法驗(yàn)證證書中的簽名。因此，使用“基于MD5函數(shù)”公鑰證書的任何一方都無法確保所謂的證書擁有者是否真實(shí)擁有相應(yīng)的私鑰。他們也想構(gòu)造一對基于SHA-1的X.509證書，產(chǎn)生相同的簽名。然而，他們還做不到這一點(diǎn)。因?yàn)楫a(chǎn)生SHA-1碰撞還需要相當(dāng)長一段時(shí)間的研究。專家指出：A.Lenstra和王小云等人聲稱已經(jīng)成功地構(gòu)造了兩張符合X.509證書數(shù)據(jù)結(jié)構(gòu)，擁有同樣簽名而內(nèi)容卻不同的證書，但該構(gòu)造方法對證書的部分域要有特殊安排，簽名算法RSA的密鑰也是按照特殊規(guī)律生成的，要用來攻擊某個(gè)實(shí)際應(yīng)用的電子簽名系

12、統(tǒng)仍需時(shí)日。而對于SHA-1算法，說其從理論上被破解都還為時(shí)過早，只能說其破解工作取得了重大突破，破解所需要運(yùn)算次數(shù)已從原來設(shè)計(jì)時(shí)估算的2A80次降低為2A69、次,這比窮舉法快了2048倍，但2A69次運(yùn)算需要600。年左右的時(shí)間，在實(shí)際計(jì)算上仍然是不可行的。除了運(yùn)算方面的瓶頸外，哈希函數(shù)的不可逆性決定了攻擊者無法輕易得手，沒有人可以保證通過這個(gè)發(fā)現(xiàn)的每個(gè)碰撞都是“可用”的碰撞。在漫長的運(yùn)算后，你得到的也許包含一些有價(jià)值的信息，也許就是理論上存在的單純碰撞，運(yùn)算瓶頸和信息匱乏都會使黑客們的種種努力成為徒勞據(jù)業(yè)內(nèi)人士估計(jì)，在當(dāng)前的技術(shù)條件下，2A50或2A60次運(yùn)算量的范圍內(nèi)的攻擊方法才會為我們帶來麻煩，即引發(fā)實(shí)際意義上的攻擊行為。在新研究成果發(fā)布前的一段時(shí)間內(nèi)，SHA-1算法只能被稱作不完美，但還是安全的?；赑KI技術(shù)進(jìn)行電子簽名的最終用戶，目前還不用擔(dān)心自己的簽名被偽造或遭遇簽名人抵賴。另外，安全專家強(qiáng)調(diào)：一種算法被破譯，和整個(gè)企業(yè)的安全系統(tǒng)被攻破，是兩個(gè)不同的概念。因?yàn)殡S著攻擊技術(shù)和能力的提高，算法也會“水漲船高”，向前發(fā)展進(jìn)步。王教授所取得的成就提醒密碼學(xué)家研究新的算法，提醒有關(guān)標(biāo)準(zhǔn)化機(jī)構(gòu)要提前修改算法