一千萬個為什麽

搜索

哈希函數是否與進化算法的創始假設相矛盾?

  1. 進化算法使用適應度函數來選擇跨代的生存候選者(“適者生存“)。我相信所有適應度函數都假設候選者的值越接近期望值,他們的輸入(“關鍵點”)必須越接近所需的輸入。

  2. 加密哈希函數具有“生成郵件不可行”的屬性有一個給定的哈希“。我理解這意味著值的“接近度”與鍵的“接近度”之間幾乎沒有相關性。

將這兩者放在一起,並不意味著“適者生存”假設對於加密哈希函數是錯誤的嗎? 意思是,如果你想使用進化算法來試圖找出密碼哈希值的反向,那麽適應度函數會把你推向錯誤的方向。值是否與“密切”之間的相關性密鑰的“接近程度”是進化算法的先決條件?

最佳答案

是的,根據所有三個(良好)加密哈希函數的輸出,構造一個始終告訴您值A比目標B更接近目標的適應度函數幾乎是不可能的。那是你提到的財產。因此,進化算法無法加速反轉加密哈希函數的平均情況。 然而,這不應該是一個驚喜:所述屬性僅在第一時間有用,因為它精確地打破了進化算法的方法(通過查看哈希值相似性來加速逆轉)。

推廣這一點,進化算法(像所有其他依靠啟發式指導搜索的算法,例如 A * )只有在你能定義一個有意義的適應度函數(啟發式)時才有用。顯然,有可能構造不允許這種情況的問題(例如,通過提供太少的信息),並且完全可以認為存在一些具有相同問題的更真實的應用程序。進化算法並不能治愈癌癥,但這並不奇怪(沒有什麽可以,否則我們會轉向另一種比喻)。

在旁註中,該適應度函數不必接近任何特定值,存在許多問題,其中適應度可無限增長,例如,在優化性能代碼時,適應度可以是每秒的操作次數。

轉載註明原文: 哈希函數是否與進化算法的創始假設相矛盾?