MD5是滿射嗎？

01-25

沒聽說過。

首先確定一下這裡的陪域應該是所128位二進位數構成的集合。如果說陪域就是函數的輸出的集合（值域）那討論滿射與否就沒有意義了。

至今沒有被證明MD5是滿射的或者不是滿射的。當然我這裡有一篇文章比較厲害[1]一口咬定MD5作為MAC碼的構造函數就是滿射的，就差沒說有興趣的讀者可以自己證明一下了，我也沒有找到它這麼說的根據。所以接到這個消息你們也要自己判斷一下不能聽見風就是雨。

作為蛤希（hash）函數必須保證單向性和強/弱抗碰撞性（也是單射的要求），而且輸出的長度是確定的（MD5的輸出是128位）。並沒有明確要求過必須是滿射函數，甚至滿射/非滿射這個性質的確定反而對於一個偽隨機函數來說很不安全，給選擇明文/密文攻擊創造了一定的條件。

要證明MD5是否滿射可以從兩個方向入手

1.數學分析

從演算法流程來分析是否有值域並沒有覆蓋整個128位數集合。這個暫時沒聽說過。

2.實驗

思想很簡單，值域是一個有限集合，定義域是無限的（任意輸入都可以得到對應的MD5碼）

且函數還是單射的，那麼很有可能是不滿足滿射的，那麼抗碰撞性可能也是不滿足的，無法保證每個128位的bit串都有一個對應的輸入。那麼進行窮舉搜索，假設抗碰撞性仍然成立那麼2^128個輸入跑完以後應該有2^128個不同的輸出，如果其中沒有重複的，那可以說是滿射，因為值域確實與陪域相同。如果有，那也不能說明不是滿射。這個實驗資源消耗量太大，且證明結果意義不大。

不過在05年的時候MD5就被證明了不抗碰撞[2]，當時在密碼學領域弄了個大新聞。但即使在這個單射條件不成立的前提下，是否滿射還是無可奉告，大家一句話也不說。