1
Рассмотрим наивную функцию хэша: HASH = INPUT % 4. Эта функция периодична в том смысле, что если мы назовем ее последовательными числами 0, 1, 2, 3, 4, 5, ..., то полученная хешированная последовательность будет иметь периодичность четыре: 0, 1, 2, 3, 0, 1, 2, 3, 0, ....Периодичность хеш-функций
Вопрос в том, являются ли современные криптографические хэш-функции, такие как SHA256, периодическими в этом смысле? Другими словами, существуют ли целые числа 0 <= n и 0 < k такие, что HASH(n + b) = HASH(n + b + ak) для всех целых чисел b в [0, k - 1] и все положительные целые числа a? Например, будет ли последовательность SHA256(0), SHA256(1), SHA256(2), SHA256(3), ... периодической после некоторой точки?
Это очень хороший момент, спасибо. Это теоретически доказано или только практически так? Например, если 'k' и' n' чрезвычайно велики (и в настоящее время неизвестны), было бы практически невозможно найти столкновения, но теоретически мы могли бы. –
Вы должны спросить об этом из-за переполнения математики :) Я думаю, что если k конечно, вы можете это доказать. Но на бесконечности, когда Хэш идет от реальной до пары цифр, я думаю, что на самом деле нужно быть k. – starmole
У меня может быть эскиз, который работает: вам нужно показать, что не существует k, так что для всех a: Hash (a) == Hash (a + k). Итак, нам нужно показать, что существует один a для каждого k, где Hash (a)! = Hash (a + k). Теперь мы требуем, чтобы Hash (x)! = Hash (x '), если x' равно x, с одним щелчком. Тривиальный хэш-бит, который будет делать это, - это взять все биты в x и xor. Итак, чтобы найти a для любого k, просто выберите a так, чтобы a = (a + k) с одним битом перевернулся. Это может быть a = 1 << maximumbitindex (k). – starmole