哈希碰撞

一、哈希函數

哈希函數是將任意長度的輸入（也稱為預映射， pre-image），壓縮成固定長度的輸出（稱為散列值， hash value），該映射的規則就是哈希演算法。

常見的哈希函數有MD5、SHA1、SHA256等。其中，MD5演算法將任意輸入（注意是任意的大小、格式）轉換為長度為128位的數據，因此它常常被用於解決碰撞的問題。

二、哈希碰撞的含義

哈希碰撞指的是在哈希函數中，兩個不同的預映射得到了相同的散列值。當兩個輸入得到了相同的散列值，就會發生衝突。

哈希碰撞是由於哈希函數產生的輸出值比輸入的長度小，因此會產生一些相同的輸出結果。人們期望的是，哈希函數會保證相同的輸入永遠產生相同的哈希值，但實際上，情況往往並不是這樣。

三、哈希碰撞的影響

哈希碰撞的出現，會影響用戶的隱私和系統的安全性。

在文件下載等場景中，哈希值用於校驗文件是否完整無損傳輸，如果哈希碰撞，那麼就會出現兩個不同的文件，而下載者會誤認為文件已經完整下載，導致文件損壞或數據泄露。

在密碼的安全性方面，如果密碼沒有經過合理的哈希處理，就可能會被惡意攻擊者破解，從而造成嚴重的信息泄露。

四、哈希碰撞的解決方案

為了解決哈希碰撞的問題，可以採用以下幾種方案：

1、使用更長的哈希值。較長的哈希值可以減少哈希碰撞的概率，但是也會在計算上產生更多的負擔。

2、設計更為複雜的哈希函數。較為複雜的哈希函數可以降低哈希碰撞的概率，但是也會增加計算複雜度，增加系統開銷。

3、增加鹽值。鹽值可以增加哈希值隨機性，進一步降低哈希碰撞的概率，但是也會增加系統開銷。

4、使用加密哈希演算法。加密哈希演算法可以增加哈希值的安全性，從而降低哈希碰撞的概率，但是也會增加系統開銷。

五、MD5演算法代碼示例

#include <stdio.h>
#include <stdlib.h>
#include <openssl/md5.h>

void MD5_Print(unsigned char *md){
    int i;
    for(i = 0; i < MD5_DIGEST_LENGTH; i++)
        printf("%02x", md[i]);
    printf("\n");
}

int main(){
    char message[] = "Hello, world!";
    unsigned char md[MD5_DIGEST_LENGTH];
    int i;

    MD5(message, sizeof(message)-1, md);
    MD5_Print(md);

    return 0;
}