增加发现散列冲突的概率

admin

我正在尝试查找修改后的散列函数的散列冲突。假设我修改后的散列只输出SHA-1的前36位。我们知道，SHA-1是一个160位的哈希值，因此，我们只需要输出40个字符中的9个字符进行比较。

我如何开始我的程序是通过散列一个字符串(我有一个运行的SHA-1算法，我将它命名为sha1。我还确保了SHA-1算法的输出是正确的。)

首先，我会硬编码2个字符串，并从40个字符中提取出9个字符，因为我只需要SHA-1的前36位。如果发现冲突，则下面的函数基本上返回true，如果未找到冲突，则返回false

public static boolean findCollision(int x1, int x2) {

    String message1 = "I tried " + x1 + " iteration to find a collision";
    String message2 = "I tried " + x2 + " iteration to find a collision";       


    //hashing my string and extracting 9 characters
    String message_hash1 = sha1(message1);
    String message_hash2 = sha1(message2);

    String modified_hash1 = message_hash1.substring(0, 9);
    String modified_hash2 = message_hash2.substring(0, 9);

    if (modified_hash1.equals(modified_hash2))  
        return true; 
    else 
        return false;
}

最后，我将有一个主函数，它将在无限循环中随机直到MAX_VALUE的整数，并且当且仅当找到散列时才会中断。

public static void main(String[] args) {

    Random random = new Random();
    int x1 = 0;
    int x2 = 0;
    int counter = 0;

    while (true) {

        while(true){

            x1 = random.nextInt(Integer.MAX_VALUE);
            x2 = random.nextInt(Integer.MAX_VALUE);

            if (x1 != x2) 
                break;  
        } 

        if (findCollision(x1, x2) == true) {
            break;
        }
        counter++;
    }

    System.out.println("\nNumber of trials: " + counter);
}

如果我尝试只取SHA-1的前24位，我可以很容易地找到冲突。然而，尽管运行了几个小时，我还是无法找到36位的冲突。因此，我想知道还有什么替代方法可以让我找到只有36位SHA-1的冲突。

转载请注明出处:http://www.intsu.net/article/20230526/1743445.html