C++ 具有相同 40 位散列值的两个不同字符串

Question

我在分配时遇到了一些问题，我要为给定的函数创建一个算法，该函数接受一个字符串并将其转换为 40 位散列。有了这个，我必须找到两个具有相同值的不同哈希值。在我得到一个合理的概率之前，助教给了我们一个关于使用生日悖论来找到不同字符串的数量的提示。我的问题是，在没有字符串且没有设定长度的情况下，我应该如何处理这个问题。

Answer 1

考虑到有关“生日悖论”的提示(这根本不是悖论)，我假设您的作业要求您生成许多字符串并对它们进行哈希处理并找到两个相冲突的字符串。

由于您使用的是 40 位散列函数，因此您预计必须尝试 2²⁰ 个字符串(平均)才能找到第一个冲突。解决它的一种方法是生成长度为零及以上的任何字符串并对其进行哈希处理。

这样做的一种方法是这样的:(我实际上还没有尝试过任何这段代码。)

using std::string;

template <typename F>
bool GenAllStrings_Worker (string & s, unsigned idx, string const & char_set,
                           unsigned long long & cnt, F f)
{
    if (idx >= s.size())
        return f(s, ++cnt);

    for (auto c : char_set)
    {
        s[idx] = c;
        if (GenAllStrings_Worker(s, idx + 1, char_set, cnt, f))
            return true;
    }

    return false;
}

// Continues generating successively longer strings until "f" returns true.
// Passes each generated string and number of strings generated so far to "f".
template <typename F>
void GenAllStrings (string const & char_set, F f)
{
    unsigned long long cnt = 0;

    for (unsigned len = 0; ; ++len)
    {
        string s (len, '?');
        if (GenAllStrings_Worker (s, 0, char_set, cnt, f))
            return;
    }
}

您可以像这样使用它:(不要忘记您需要提供 hash_code 类型和 MyHashFunction 函数。)

std::unordered_map<hash_code, string> generated_hashes;

GenAllStrings ("abcdef...ABCD...0123...whatever",
    [&](string const & s, unsigned long long cnt){
        hash_code h = MyHashFunction(s);
        if (generated_hashes.find(h) != generated_hashes.end())
        {
            std::cout << "#" << cnt << " - Found a collision: '" << s <<"'"
                 << " collides with '" << generated_hashes[h] << "'"
                 << ", with a hash of " << h << std::endl;
            return true;
        }
        h[h] = s;
        return false;
    });

我已经编写了传入 GenAllStrings 函数的 lambda，以便在第一次碰撞后停止；但是您可以生成任意数量的碰撞(或有时间)，在达到一定长度的字符串等后停止。