數字簽名和哈希函數
問題的提出
懂得一點公鑰密碼基礎知識的人都知道，發信息的人用自己的私鑰對所發信息進行加密( Encryption )，接收信息者用發信者的公鑰來解密( Decryption )，就可以保證信息的真實性、完整性和不可否認性。（注：這里提到的加密、解密是指密碼運算，其目的并非信息保密。）那么，我們也可以籠統地說，以上方法就已經達到了數字簽名的目的。因為首先，私鑰是發信者唯一持有的，別的任何人不可能制造出這份密文來，所以可以相信這份密文以及對應的明文不是偽造的（當然，發信者身份的確定還要通過數字證書來保證）；出于同樣原因，發信者也不能抵賴、否認自己曾經發過這份信息；另外，信息在傳輸當中不可能被篡改，因為如果有人試圖篡改，密文就解不出來。這樣，用私鑰加密，公鑰解密的技術方法就可以代替傳統簽名、蓋章，保證了信息的真實性、完整性和不可否認性。
但是，這樣做在實際使用中卻存在一個問題：要發的信息可能很長，非對稱密碼又比較復雜，運算量大，而為了保證安全，私鑰通常保存在USB Key或IC卡中，加密運算也是在Key或卡中進行。一般來說，小小的USB Key或IC卡中的微處理器都做得比較簡單而處理能力較弱，這樣，加密所用的時間就會很長而導致無法實用。
另外，即使對于網站服務器而言，雖然它的處理能力很強，但服務器要同時處理許許多多簽名加密的事情，也同樣存在著加密耗時長系統效率低的問題。
有沒有解決這個問題的辦法呢？有的，常用的方法是使用哈希函數。
什么是哈希函數
哈希（Hash）函數在中文中有很多譯名，有些人根據Hash的英文原意譯為“散列函數”或“雜湊函數”，有些人干脆把它音譯為“哈希函數”，還有些人根據Hash函數的功能譯為“壓縮函數”、“消息摘要函數”、“指紋函數”、“單向散列函數”等等。
1、Hash算法是把任意長度的輸入數據經過算法壓縮，輸出一個尺寸小了很多的固定長度的數據，即哈希值。哈希值也稱為輸入數據的數字指紋（Digital Fingerprint）或消息摘要（Message Digest）等。Hash函數具備以下的性質：
2、給定輸入數據，很容易計算出它的哈希值；
3、反過來，給定哈希值，倒推出輸入數據則很難，計算上不可行。這就是哈希函數的單向性，在技術上稱為抗原像攻擊性；
4、給定哈希值，想要找出能夠產生同樣的哈希值的兩個不同的輸入數據，（這種情況稱為碰撞，Collision），這很難，計算上不可行，在技術上稱為抗碰撞攻擊性；
5、哈希值不表達任何關于輸入數據的信息。
哈希函數在實際中有多種應用，在信息安全領域中更受到重視。從哈希函數的特性，我們不難想象，我們可以在某些場合下，讓哈希值來“代表”信息本身。例如，檢驗哈希值是否發生改變，借以判斷信息本身是否發生了改變。`
怎樣構建數字簽名
好了，有了Hash函數，我們可以來構建真正實用的數字簽名了。
發信者在發信前使用哈希算法求出待發信息的數字摘要，然后用私鑰對這個數字摘要，而不是待發信息本身，進行加密而形成一段信息，這段信息稱為數字簽名。發信時將這個數字簽名信息附在待發信息后面，一起發送過去。收信者收到信息后，一方面用發信者的公鑰對數字簽名解密，得到一個摘要H；另一方面把收到的信息本身用哈希算法求出另一個摘要H’，再把H和H’相比較，看看兩者是否相同。根據哈希函數的特性，我們可以讓簡短的摘要來“代表”信息本身，如果兩個摘要H和H’完全符合，證明信息是完整的；如果不符合，就說明信息被人篡改了。
數字簽名也可以用在非通信，即離線的場合，同樣具有以上功能和特性。
由于摘要一般只有128位或160位比特，比信息本身要短許多倍，USB Key或IC卡中的微處理器對摘要進行加密就變得很容易，數字簽名的過程一般在一秒鐘內即可完成。
哈希函數的安全性
哈希函數的安全性直接關系到數字簽名的安全性，如果哈希函數被攻破，數字簽名的有效性就會受到質疑。
目前，已經發明的Hash函數有多種，如Snefru、N-Hash、LOKI、AR、GOST、MD、SHA等。它們在數學上實現的方法各有不同，安全性也各有不同。目前比較常用的Hash函數是MD5和SHA-1。 MD5哈希函數以512位來處理輸入數據，每一分組又劃分為16個32位的子分組。算法的輸出由4個32位分組組成，將它們級聯起來，形成一個128位的固定長度的哈希值，即輸入數據的摘要。SHA-1哈希函數在MD4的基礎上增加了數學運算的復雜程度，即SHA=MD4+擴展轉換+附加輪+更好的雪崩效應（哈希值中，為0的比特和為1的比特，其總數應該大致相等；輸入數據中一個比特的變化，將導致哈希值中一半以上的比特變化，這就叫做雪崩效應）。SHA能夠產生160位的哈希值。對SHA還沒有已知的密碼攻擊，并且由于它產生的哈希值位數長于MD5，所以它能更有效地抵抗窮舉攻擊（包括生日攻擊）。
但是，任何一種算法都有其漏洞和局限性。任何一個哈希函數都會存在碰撞——即在一些特定情況下，兩個不同的文件或信息會指向同一個數字摘要。在一般情況下，類似碰撞只能盡可能地減少，而不能完全避免。從理論上講，沒有攻不破的密碼。隨著密碼科學的發展，也許會找到攻破某一種密碼算法的途徑。
評價Hash算法的一個最好方法是看敵手找到一對碰撞消息所花的代價有多高。一般地，假設攻擊者知道Hash算法，攻擊者的主要攻擊目標是找到一對或更多對碰撞消息。目前已有一些攻擊Hash算法和計算碰撞消息的方法。在這些方法中，有些是一般的方法，可用于攻擊任何類型的Hash算法，比如“生日攻擊”；而另一些是特殊的方法，只能用于攻擊某些特殊的Hash算法，比如適合于攻擊具有分組鏈結構Hash算法的“中間相遇攻擊”，適用于攻擊基于模運算的Hash函數的“修正分組攻擊”。堅固的哈希函數可通過設計有效的碰撞處理機制，或增加數字摘要的位數來增加復雜度，以減少碰撞出現的概率，
2004年8月17日，在美國召開的國際密碼學會議（Crypto’ 2004）上，一些國家的密碼學者作了破譯Hash函數的新進展的報告，其中我國山東大學的王小云教授做了破譯MD5、HAVAL-128、MD4、和RIPE MD算法的報告。
到2005年2月，據王小云教授的研究報告，他們已經研究出了搜索SHA-1碰撞的一系列新技術。他們的分析表明，SHA-1的碰撞能在小于2^69次Hash操作中找到。對完整的80輪SHA-1的攻擊，這是第一次在小于2^80次Hash操作這個理論界限的情況下找到碰撞。根據他們的估計，對于縮減到70輪的SHA-1能夠用現在的超級計算機找出“實碰撞”。他們的研究方法，能自然地運用到SHA-0和縮減輪數的SHA-1的破譯分析上。
2005年3月6日，Arjen Lenstra，王小云，Benne de Weger 宣布，他們構造出一對基于MD5 Hash函數的X.509證書，產生了相同的簽名。他們提出了一種構造X.509證書的方法，在他們所構造出的證書對中，由于使用了MD5算法，簽名部分產生了碰撞。因此，當證書發布者使用MD5作為Hash函數時，發布者就會在證書中產生相同的簽名，導致PKI的基礎原理遭到可信性破壞。這意味著，從單獨某個證書無法確定是否存在另一個不同證書有著相同的簽名。由于第二個相同簽名證書存在的可能性，證書發布機構無法驗證私鑰的“擁有證明”，即無法驗證證書中的簽名。因此，使用“基于MD5函數”公鑰證書的任何一方都無法確保所謂的證書擁有者是否真實擁有相應的私鑰。
他們也想構造一對基于SHA-1的X.509證書，產生相同的簽名。然而，他們還做不到這一點。因為產生SHA-1碰撞還需要相當長一段時間的研究。
專家指出：A.Lenstra和王小云等人聲稱已經成功地構造了兩張符合X．509證書數據結構，擁有同樣簽名而內容卻不同的證書，但該構造方法對證書的部分域要有特殊安排，簽名算法RSA的密鑰也是按照特殊規律生成的，要用來攻擊某個實際應用的電子簽名系統仍需時日。而對于SHA-1算法，說其從理論上被破解都還為時過早，只能說其破解工作取得了重大突破，破解所需要運算次數已從原來設計時估算的2^80次降低為2^69次，這比窮舉法快了２０４８倍，但2^69次運算需要６０００年左右的時間，在實際計算上仍然是不可行的。
除了運算方面的瓶頸外，哈希函數的不可逆性決定了攻擊者無法輕易得手，沒有人可以保證通過這個發現的每個碰撞都是“可用”的碰撞。在漫長的運算后，你得到的也許包含一些有價值的信息，也許就是理論上存在的單純碰撞，運算瓶頸和信息匱乏都會使黑客們的種種努力成為徒勞……據業內人士估計，在當前的技術條件下，２^50或２^ ６０次運算量的范圍內的攻擊方法才會為我們帶來麻煩，即引發實際意義上的攻擊行為。在新研究成果發布前的一段時間內，SHA-1 算法只能被稱作不完美，但還是安全的。基于PKI技術進行電子簽名的最終用戶，目前還不用擔心自己的簽名被偽造或遭遇簽名人抵賴。
另外，安全專家強調：一種算法被破譯，和整個企業的安全系統被攻破，是兩個不同的概念。因為隨著攻擊技術和能力的提高，算法也會“水漲船高”，向前發展進步。王教授所取得的成就提醒密碼學家研究新的算法，提醒有關標準化機構要提前修改算法標準，也提醒有關CA和電子簽名產品開發商支持新的算法。當然，有些完全基于摘要算法的密押系統和電子貨幣系統，還需要盡早考慮替換方案。
美國國家技術與標準局（NIST）曾經發表如下評論：“研究結果說明SHA-1的安全性暫時沒有問題，但隨著技術的發展，技術與標準局計劃在2010年之前逐步淘汰SHA-1，換用其他更長更安全的算法（如：SHA-224, SHA-256, SHA-384和SHA-512）來代替。”