Quote from: ZeroTheGreat on January 29, 2014, 11:13:21 PM

Quote from: ri on January 25, 2014, 02:28:54 PM

Вообще-то коллизии заведомо существуют для любого алгоритма хэширования - и не надо быть профессором математики, чтобы это доказать. Могу продемонстрировать доказательство, если хотите.

М? Я читал, что было доказано математически, что Keccak работает точно так же, как искомый "чёрный ящик". Была статья на Хабре. В таком случае коллизий существовать не должно по идее, или их нахождение ничего не даст (я не криптограф, не кидайтесь тапками).

Фишка в том, что ограничена длина хэша. Предположим, мы используем keccak - ну или абсолютно любой другой алгоритм с длиной хэша n бит. В этом случае максимально возможное количество значений хэша будет 2ⁿ. Возьмем 2ⁿ+1 сообщений и вычислим хэши для каждого из них. Очевидно, что поскольку количество сообщений больше, чем количество возможных значений хэша, то хотя бы у двух сообщений хэши окажутся одинаковыми - вот вам и коллизия.

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