Комментарии 8
"Почему наш крипто-хэш — почти как настоящий" - нипочему. Он не имеет отношения к криптографии, скорее что-то типа CRC и он не имеет отношения к хэшам
Попробуйте подобрать исходную фразу для хешей 377, 777 или 333.
Для 333. Можно в уме.
Нам нужно 333 (mod 1000). Будем целить в 1333 - выглядит так, что можно столько набрать на трёх слагаемых. Запись искомого числа оканчивается на 3, значит оно равно 3 (mod 10). 3 (mod 10) можно получить несколькими способами. Действуя наобум и немного прикинув частотность имеющихся чисел, выбираем 8 + 8 + 7 == 23 == 3 (mod 10). То есть, нам подходят только числа, оканчивающиеся на 8 и 7, но их тут, похоже, достаточно. Выписываем такие числа: 927, 567, 797, 957, 987, 287, 198, 758, 678, 368. Вспоминаем, что нам нужно 8 + 8 + 7, но при этом должно быть 33 (mod 100). Это означает, что достаточно рассмотреть по две последних цифры записи. И у нас уже есть повторы. Удобно, что почти все двузначные числа, соответствующие выбранным, достаточно большие, то есть, при десятках - пять и более единиц. Поэтому 133 выглядит слишком малым целевым числом (уже 3 * 44 == 32), его недостаточно, чтобы обеспечить вариативность по трём слагаемым. Прицеливаемся на 233. Смотрим примерные числа и проверяем (должна быть сигнатура 8, 8, 7): 78 + 68 + 87 == 233. Сразу подходит, угадали. Проверяем результат для трёх цифр: 678 + 368 + 287 == 1333 == 333 (mod 1000). Готово. Нашли один из ответов: ЭЖУ.
(Подсказка: можно ещё проще.)
Отличное решение! Спасибо) Вообще, я старался придумать пример, чтобы выглядел очень простым, но в тоже время чтобы вот так, "в уме" было очень сложно подобрать коллизию. Но вы опровергли мою гипотезу) Значит надо выбрать число сложнее, например, 827. Или ещё лучше - усложнить алгоритм, сопоставив каждой букве число из 4-х цифр (а не из 3-х).
Вы опасно некомпетентны в криптографии. Берем расширенный алгоритм Евклида и считаем его для 1000 и буквы А (179)
Получаем: 1000*(-75) + 179 * 419 = 1
Тащим 1000 к 1 и домножаем все на 827.
827*1000*75 + 827 = 827*179*419
То есть, строка из 346513 букв А даст нужный "хэш". И я надеюсь, что вам очевидно, что дальше за О(1) я выберу для любого вашего "хэша" прообраз.
Так про это же есть в статье. Только там используется хеш( ГПФ ) = 001, а так та же самая логика, что вы озвучили.
Но если ограничить наш условный "пароль" допустим, 32 символами - то подобрать коллизию будет уже не так просто! Ну и самое главное - это же просто максимально упрощенный пример, подготовленный для понимания принципа. Понятно, что он обладает множеством недостатков.
Ну да. Куда уж универсальному алгоритму, который показывает нахождение прообразов для любой конфигурации вашего "хеша" до примера из статьи. Я уж молчу про нахождение парного прообраза.
Что касается расширенного алгоритма Евклида - вы абсолютно правы, что это эффективный системный метод поиска прообраза для подобных случаев. И прошу прощения за терминологию - мы проверяли стойкость к коллизиям первого рода. А лучший способ обучения - не рассказывать уже готовое решение, а дать его выработать самостоятельно.
Грокаем крипто-хеш: как разобраться за 5 минут