То, что вы ищете, - это решение проблемы столкновения (см. Также атака столкновения ). Хорошо спроектированная и мощная криптографическая хеш-функция разработана с намерением максимально запутать математику, насколько это возможно, чтобы сделать эту задачу как можно более сложной.
Фактически, одной из мер хорошей хеш-функции является сложность обнаружения столкновений. (Среди других мер, сложность обращения хэш-функции)
Следует отметить, что в хешах, где на входе указана любая длина строки, а на выходе - строка фиксированной длины, Принцип Pigeonhole гарантирует, что по крайней мере одно столкновение для любой заданной строки. Тем не менее, найти эту строку не так просто, так как это потребовало бы в основном слепого предположения и проверки по практически бесконечному набору строк.
Может быть полезно прочитать об идеальных хеш-функциях. Хеш-функции предназначены для функций, где
- Небольшие изменения на входе вызывают радикальные, хаотические изменения на выходе
- Столкновения сведены к минимуму
- Трудно или, в идеале, невозможно повернуть вспять
- Нет хэшированных значений, которые невозможно получить с помощью каких-либо входных данных (это значение значительно меньше для криптографических целей)
Теоретический «идеальный» алгоритм хеширования будет «случайным оракулом» - то есть для каждого входа он выводит идеально случайный вывод при условии, что для того же входа вывод будет идентичным (это условие выполняется магией, рукой Зевса и фей Пикси, или таким образом, что ни один человек никогда не сможет понять или понять)
К сожалению, это в значительной степени невозможно, и в конечном итоге все хэши оцениваются как "сильные" в зависимости от того, какими из этих качеств они обладают и в какой степени.
Хеш, такой как SHA1 или MD5, будет довольно сильным, и более или менее вычислительно невозможно найти коллизии (в течение разумного периода времени). В конечном счете, вам не нужно находить хеш, для которого невозможно найти коллизии. Вам практически нужен только тот, где его сложность достаточно велика, чтобы его можно было вычислить слишком дорого (т. Е. Порядка миллиарда или триллионов лет, чтобы найти столкновение)
Из-за того, что все хеши были несовершенными, можно было проанализировать его внутреннюю работу, увидеть математические закономерности и эвристику и попытаться найти столкновения вдоль этого рисунка. Это похоже на хеш-функцию% 7 ... Хеширование числа 13 будет 13% 7 = 6, 89% 7 = 5. Если вы увидели хеш-функцию 3, вы можете использовать свое математическое понимание функции модуля для легко найти столкновение (т. е. 10) 1 . К счастью для нас, более сильные хеш-функции намного сложнее понять математическую основу. (В идеале, так сильно, что ни один человек не сможет этого понять!)
Некоторые цифры:
- Нахождение коллизии для одного заданного хэша SHA-0 занимает около 13 полных дней выполнения вычислений на лучших суперкомпьютерах мира с использованием шаблонов, присущих математике.
- По словам полезного комментатора, коллизии MD5 могут генерироваться "достаточно быстро", чтобы быть не идеальными для чувствительных целей.
- До настоящего времени не было найдено или доказано, что возможный или практичный / пригодный метод обнаружения столкновений для SHA-1, хотя, как указано в комментариях, есть некоторые слабые стороны, которые были обнаружены.
Вот аналогичный вопрос SO , ответы на который гораздо мудрее, чем у меня.
1 обратите внимание, что, хотя эта хэш-функция слаба для столкновений, очень важно, что совершенно невозможно вернуться назад и найти заданный ключ, если ваш хэш, скажем, 4. Существует бесконечное количество (то есть 4, 11, 18, 25 ...)