Создайте две разные строки с одним и тем же хэш-кодом

Я хочу сделать несколько тестов, для которых требуются некоторые строки с одним и тем же хэш-кодом, но не с теми же строками. Я не мог найти примеров, поэтому решил написать простую программу, чтобы сделать это для меня.

Нижеприведенный код генерирует две случайные строки снова и снова, пока они не сгенерируют один и тот же хэш-код.

    static Random r = new Random();
    static void Main(string[] args)
    {
        string str1, str2;
        do
        {
            str1 = GenerateString();
            str2 = GenerateString();
        } while (str1.GetHashCode() != str2.GetHashCode() && str1 != str2);

        Console.WriteLine("{0}\n{1}", str1, str2);
    }

    static string GenerateString()
    {
        string s = "";
        while (s.Length < 6)
        {
            s += (char)r.Next(char.MaxValue);
        }
        return s;
    }

Этот код, кажется, работает (теоретически), но может потребоваться столетия. Поэтому я думал о том, чтобы делать наоборот и генерировать две строки из одного хеш-кода.

Я знаю, что невозможно извлечь строку из хэш-кода, но можно ли генерировать из нее возможные строки?

Я использую Visual Studio 2015 Community Edition. Версия: 14.0.23107.0D14REL.

.NET Framework: 4.6.00081.

Ответы

Ответ 1

Поиск двух строк путем многократного сравнения случайных строк займет практически бесконечно. Вместо этого генерируйте строки и храните их в словаре по hashcode. Затем посмотрите каждый. Матч найден довольно быстро.

МАТЧА НАЙТИ!! xqzrbn и krumld хэш-код 80425224

void Main()
{

    var lookup = new Dictionary<int,string>();

    while(true) {
        var s = RandomString();        
        var h = s.GetHashCode();
        string s2;
        if (lookup.TryGetValue(h, out s2) && s2 != s) {
            Console.WriteLine("MATCH FOUND!! {0} and {1} hash code {2}",
                lookup[h],
                s,
                h);
            break;
        }
        lookup[h] = s;

        if (lookup.Count % 1000 == 0) {
            Console.WriteLine(lookup.Count);
        }
    }
}

static Random r = new Random();

// Define other methods and classes here
static string RandomString() {

    var s = ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString() +
            ((char)r.Next((int)'a',((int)'z')+1)).ToString();

    return s;
}

Ответ 2

Воспользуйтесь Парадокс дня рождения. Вместо того, чтобы тестировать сразу две строки, проверьте все строки, которые вы видели раньше.

using System;
using System.Collections.Generic;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {
            var words = new Dictionary<int, string>();

            int i = 0;
            string teststring;
            while (true)
            {
                i++;
                teststring = i.ToString();
                try
                {
                    words.Add(teststring.GetHashCode(), teststring);
                }
                catch (Exception)
                {
                    break;
                }
            }

            var collisionHash = teststring.GetHashCode();
            Console.WriteLine("\"{0}\" and \"{1}\" have the same hash code {2}", words[collisionHash], teststring, collisionHash);
            Console.ReadLine();
        }
    }
}

Для моей машины он производит вывод

"699391" и "1241308" имеют одинаковый хэш-код -1612916492

почти мгновенно.

Из-за того, как строки хэшируются в .NET, вы можете не получить тот же самый результат, что и я, но он должен быть таким же быстрым.