密碼學(三):數位簽章

雜湊、數位簽章

還記的非對稱加密嗎? Alice使用Bob的公鑰加密後傳給Bob，因為公鑰大家都可以拿，那如果今天有心人也拿Bob的公鑰加密後傳給Bob，Bob怎麼知道這是Alice傳的呢?

這時候數位簽章就得出馬了!

在講數位簽章前先談談甚麼是雜湊函數(hash)吧!

雜湊函數(Hash)

• 單向 (由雜湊值是無法反推出原來的訊息)
• 無論原文的內容長短，透過雜湊演算法運算完的輸出都會是固定的長度，即輸出的長度不受原文長度影響
• 兩個原文的內容即便只差一個字，雜湊演算法產生的兩個輸出內容卻會差非常多(Avalanche effect)
• 好的雜湊函式在輸入域中很少出現雜湊碰撞（collision）
• 常見的雜湊函數md5, sha256

https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97

碰撞 (Collision)

兩個相同輸入值得到的雜湊值卻相同，可能會發生，但機率要很小很小

用途

• 驗證資料完整性

訊息接受者確認訊息是否被篡改的性質叫資料的真實性(完整性)

發信人通過將原訊息和雜湊值一起傳送，可以保證真實性

• 在不取得明文的情況下驗證資料正確性 (ex: password)
• 語音辨識: ex: Shazam

介紹完雜湊函數後就進入電子簽章吧!

數位簽章（Digital Signature）

數位簽章是為了判斷是否是本人傳遞訊息，達到完整性(Integrity)與不可否認性(Non-Reputation)

整個流程是:

也就是今天如果Alice要傳訊息給Bob

• Alice 將訊息通過雜湊函數後產生雜湊值，在利用自己的私鑰將雜湊值加密，成為數位簽章(digital signature)
• 此時Alice 在將原始訊息利用Bob的公鑰加密，並一併把秘文與數位簽章 一起傳給Bob
• Bob收到後用自己的私鑰解密原始訊息，再用Alice的公鑰解密數位簽章拿到雜湊值，這時再將原始訊息通過雜湊函數，如果兩者的雜湊值相同，就可以證明這封訊息是Alice本人傳的

數位憑證（Digital Certificate）

可以把數位簽章想像成印章，在資料上面蓋章證明確實是某人發出的
而 憑證 則可以想像成 “公鑰的保證書”，以此為憑來驗證拿到的公鑰真的是某人的公鑰

數位憑證是一份電子性的文件，被用來證明持有人的身分證明，其中至少包含著持有人的姓名、郵政地址、電子郵件地址、以及公開鑰匙，並且必須經過具權威的單位(憑證授權（Certificate Authority, CA）中心)證明其有效期限

數位憑證

所以完整的傳送訊息過程須比對該公鑰是否與憑證方一致，亦須比對數位簽章是否與訊息雜湊值一致，才能達到加密完整

>下一篇: 比特幣(一): 基本訊息與數位簽章

參考資料:

1. 第七章 數位簽章與數位憑證
2. 數位簽章、數位信封、數位憑證
3. 瞭解電子簽章
4. How does Shazam work? Music Recognition Algorithms, Fingerprinting, and Processing
5. How Shazam Works To Identify (Nearly) Every Song You Throw At It