雜湊、訊息鑑別碼與簽章

最近剛翻完Understanding Cryptography這本書，內容真的是淺顯易懂，每章的最後也都會附上相關的參考跟深入研究可讀的參考資料，是本適合當入門的好書，看完之後，想通了雜湊、訊息鑑別碼與簽章三者的差別，在這裡筆記一下，這三個對應的英文分別是 Hash, Message Authentication Code (MAC) 和 Signature，都是訊息傳遞時，用來檢查訊息內容有無「問題」的演算法，三者相似但有些許不同，主要是要對付的問題不一樣。

當我們要傳送一大筆資料時，我們必須要驗證傳送的正確性，沒有錯誤或遭人修改，最基本的就是使用Hash 雜湊，概念就是把傳送端的資料攪一攪，吐出一段代表這份資料的值，接收端再把收到的資料攪一攪，看看出來的值是否一樣。

我們要求Hash 至少要有這些特性：
* 任意長度的輸入，固定長度的輸出
* 要快：如果傳資料要花一秒，算Hash 要十秒，有人要用嗎
* 輸入少量——即便是一個bit 的變動——也應該要讓output 完全不一樣
拿果汁機當比喻，好的果汁機要能攪拌任何輸入的食物並給你一杯新鮮可口的果汁，還要很快攪好，最後，當你攪蘋果汁時加了一些些咖哩，它也要把咖哩分子均勻散佈到每一口蘋果汁裡，打成一杯美味的咖哩蘋果汁(X

另外有Hash三個安全性的要求：
* 從輸出推不出輸入(preimage resistance)
* 給定一個輸入和它的輸出，攻擊者無法產生另一個輸入有同樣的輸出(second preimage resistance)
* 攻擊者無法產生兩個輸入有同樣的輸出(conllision resistance)

知名的Hash如md5, SHA-2，在傳檔案不希望有毀損時，用這些雜湊驗一下是不錯的檢查。

要注意的是，hash 的演算法都是公開的，所以如果有心人Oscar偽造一筆資料跟它的Hash值送給接收端，這筆資料會被誤信為真的資料，Hash 無法對付有心的第三方偽造的攻擊，要對付這種狀況就需要MAC。
MAC和hash 一樣，對一組輸入產生代表的輸出，但MAC除了Hash 的特性外，還會要求一把key，在共同擁有這把的key 的雙方，能驗證訊息完整(integrity)，也能確定訊息無法被沒有key的第三方偽造，因此MAC 有時又稱為Keyed Hash Function。
再拿果汁機當例子，共有的key 就像某種獨門配方…像金克拉吧，攪咖哩蘋果汁的時候放點金克拉進去，只有用了金克拉才能吸收土壤兩米下的氮磷鉀攪出金克拉風味咖哩蘋果汁，其他人就無法偽造出這獨特的金克拉風味。

但再進一步，MAC並不提供”不可否認性”，MAC雙方共有這把key，他們都可以產生可被驗證的MAC訊息，這就像有人可以故意打出「有杏仁味的金克拉風味咖哩蘋果汁」然後說是我打的，那我不是冤大頭？這時我們就需要簽章Signature：
簽章跟MAC差異不大，只是我們把hash value 用非對稱演算法的私錀加密過，並公布它的結果，這樣所有有公錀的人都能驗證這份資料是我簽的，卻無法偽造這份簽章；另一方面，我也無法否認這份資料是我簽的，這就是”不可否認性”，這在晶片卡、網路交易上有極大的應用。
就像攪果汁的時候，吐點口水進去，所有人都能驗我的DNA，證實是我攪的果汁；但DNA就只有我有，任何人都無法偽造。

簡而言之，如果你拿訊息過來攪一攪，那是雜湊；攪一攪的同時加上一把通常是對稱性的金錀，這變成MAC；如果產生的過程用上你的私錀，用非對稱加密演算法處理過，就成了簽章。