РегистрацияСуществуют ли абсолютно случайные алгоритмы?
Возьмем хеш-функцию и бильярд. На столе есть некоторое количество шаров. Общее число вариантов расположения шаров может быть просто невероятным. Причем новое число получается с каждым новым ударом по битку, при этом за всю историю бильярда и, видимо, за все время его существования в будущем. Кажется у нас получилась идеальная функция – внесение одного нового возмущения дает неповторимую последовательность бит. Но столь ли случайно все-таки новое число? Ведь новая последовательность получена за счет изменения позиции не всех, а двух или трех, реже четырех – пяти шаров. В остальном никакой новой энтропии нет и ее можно просто не брать в расчет. Теоретически для получения абсолютно новой последовательности бит нужно каждому шару придать свое независимое возмущение, но для реальных хешей часто встречается ситуация, когда изменение входного значения как раз очень не велико. Следует ли из этого, что в любой из хеш функций существуют уязвимости подобного рода? Или же существует теория о возможности создания совершенного алгоритма...?
комментариев: 9796 документов: 488 редакций: 5664
Бильярд — это недерминированная система. Из одного исходного расположения шаров всегда получается разный конечный результат, который нельзя точно воспроизвести. Можно сказать, что бильярд — это генератор истинно случайных чисел — TRNG (неважно насколько аккуратный), который за определённое число раундов извлекает случайные числа из реакций человека с механическими предметами и из шумов окружающей среды (вибрации, микропотоки воздуха и прочие главным образом механические взаимодействия.).
Хэш-функция детерминирована и работает с дискретными величинами. Это как если бы вместо шариков расположили шашки на шахматной доске и двигали их по строго определённому правилу — каждое новое положение в зависимости от предыдущего без возможности игроков делать свободный выбор и самим вносить случайность в процесс.
Для того, чтобы малое изменение давало такой же эффект, как и большое, в хэш-функциях и блочных шифрах есть диффузия и лавинный эффект (что не так эффективно проявляется в бильярде). Даже если за один раунд изменение неполное, то за много раундов оно становится всё более идеальным. За полное число раундов поиск отличий от идеала должен требовать больше затрат, чем перебор грубой силой. Как если бы в бильярде случайное число считали после множества ударов.
Или тогда уж барабан с лотерейными шариками. Пусть их исходно засыпят туда упорядоченно. После одного раунда прокручивания барабана, если высыпать шарики, то они будут не слишком хорошо перемешаны, но чем больше прокручиваний — тем ближе к идеалу. После определённого числа раундов можно добиться, чтобы затраты на поиск отличий от случайного распределения были 2128, например (если все остальные параметры машинки не дают отклонений). Вообще сравнение всё равно слишком некорректно.
Алгоритм может быть детерминированным (stateful), когда на вход поступают только определённые данные; рандомизированным (randomised), когда на вход поступают обрабатываемые данные и вторым потоком — случайные (которые нельзя произвольно воспроизвести и повторить по собственному желанию).
Случайный оракул не укладывается в эту классификацию (он попеременно то stateful, то randomised, в зависимости от поступающих значений и состояния памяти). Хэши (которые в общем случа stateful) сравнивают с ним. Бильярд (который ближе к true random, чем даже randomised) нельзя сравнивать со случайным оракулом. Что в такой терминологии будет "случайный алгоритм" — неясно.
Если на поиск любого различителя от RO требуется меньше времени, чем на простой перебор, то да. Можно ли на основании последних новостей утверждать, что такая ситуация неизбежна и построение идеального алгоритма невозможно в принципе?
Это потребует серьёзных доказательств (кстати, недоказано и обратное):
В криптографии принято (бездоказательно) считать, что по мере накопления знаний происходит движение к созданию идеального алгоритма (асимптотически, с периодами и колебаниями). Т.е. несмотря на увеличения числа знаний и скорость их накопления, возможностей осуществления практических взломов будет всё меньше и они будут происходить всё реже.
P. S. Общие модели построения систем и самая общая терминология описаны в /FAQ/Криптография: общие вопросы.