Результат хеширования всегда совпадает с исходным значением?
Это скорее вопрос теории криптографии, но возможно ли, что результат алгоритма хеширования будет всегда иметь то же значение, что и источник? Например, скажем, у меня есть строка:
baf34551fecb48acc3da868eb85e1b6dac9de356
Если я получу хэш SHA1, результат будет:
4d2f72adbafddfe49a726990a1bcb8d34d3da162
Теоретически, когда-нибудь встречались эти два значения? Я не спрашиваю конкретно о SHA1 - это всего лишь мой пример. Мне просто интересно, если алгоритмы хеширования построены таким образом, чтобы предотвратить это.
4 ответа
Ну, это будет зависеть от алгоритма хеширования - но я был бы удивлен, увидев, что что-то явно помешает этому. В конце концов, это действительно не должно иметь значения.
Я подозреваю, что это очень маловероятно (конечно, для криптографических хэшей)... но даже если это произойдет, это не должно вызывать проблем.
Для нешифрованных хешей (используемых в хеш-таблицах и т. Д.) Было бы вполне разумным возвращать исходное значение в некоторых случаях. Например, в Java Integer.hashCode() просто возвращает вложенное значение.
Учитывая хороший алгоритм хеширования, который возвращает, казалось бы, случайный вывод, я считаю, что в среднем должен быть один вход, который дает себя в качестве вывода. Допустим, хеш может дать N возможных выходных данных. Это означает, что есть N возможных входов, для которых это возможно. Для каждого из них шансы выхода, совпадающего с входом, равны 1/N, поэтому ожидаемое количество фиксированных точек равно N*1/N или 1.
Конечно, алгоритм хеширования Python для целых чисел возвращает значение целого числа. Итак, hash(1) == 1.
Хеш-функция может быть определена, чтобы избежать "фиксированных точек", где хэш (x)==x, но ваша хеш-квиня немного отличается тем, что вы берете строковое представление в шестнадцатеричном хеш-коде, а не в необработанном двоичном файле. Я думаю, что было бы невозможно создать хеш, который мог бы расстроить это, и это математически менее интересно, поскольку оно зависит от произвольного отображения 0-F в коды символов ASCII.
См. Есть ли фиксированная точка MD5, где md5(x) == x? для обсуждения фиксированных точек в MD5. Вычисление вероятности будет одинаково верно для шестнадцатеричных хеш-кешей и любой другой хеш-функции со 128 битами вывода.