Лавинный эффект
В криптографии лавинный эффект является желательным свойством криптографических алгоритмов , обычно блочных шифров [1] и криптографических хеш-функций , в которых, если ввод изменяется незначительно (например, переворачивание одного бита), выход изменяется значительно (например, наполовину). выходные биты переворачиваются). В случае высококачественных блочных шифров такое небольшое изменение либо в ключе , либо в открытом тексте должно вызвать резкое изменение зашифрованного текста . Фактический термин был впервые использован Хорстом Фейстелем , [1] хотя концепция восходит, по крайней мере , к Шеннону .диффузия .
Если блочный шифр или криптографическая хэш-функция не проявляет в значительной степени лавинный эффект, то у него плохая рандомизация, и, таким образом, криптоаналитик может делать прогнозы относительно входных данных, имея только выходные данные. Этого может быть достаточно, чтобы частично или полностью сломать алгоритм. Таким образом, лавинный эффект является желательным условием с точки зрения разработчика криптографического алгоритма или устройства.
Построение шифра или хэша, демонстрирующего существенный лавинный эффект, является одной из основных целей проектирования, и с математической точки зрения при построении используется эффект бабочки . [2] Вот почему большинство блочных шифров являются шифрами произведений . Именно поэтому хеш-функции имеют большие блоки данных. Обе эти функции позволяют небольшим изменениям быстро распространяться по итерациям алгоритма, так что каждый бит выходных данных должен зависеть от каждого бита входных данных до завершения работы алгоритма. [ нужна ссылка ]
Строгий лавинный критерий ( SAC ) представляет собой формализацию лавинного эффекта. Удовлетворительно, если всякий раз, когда дополняется один входной бит , каждый выходной бит изменяется с вероятностью 50%. SAC основан на концепциях полноты и лавинности и был представлен Вебстером и Таваресом в 1985 г. [3] .
Обобщения SAC более высокого порядка включают несколько входных битов. Булевы функции, которые удовлетворяют SAC высшего порядка, всегда являются изогнутыми функциями , также называемыми максимально нелинейными функциями, также называемыми «идеальными нелинейными» функциями. [4]
Критерий независимости битов ( BIC ) утверждает, что выходные биты j и k должны изменяться независимо, когда любой одиночный входной бит i инвертируется для всех i , j и k . [5]
