Эффект лавины - Avalanche effect

Эта статья о криптография. Для использования в других целях см. Эффект снежного кома и Лавина (значения).

В криптография, то лавинный эффект желаемое свойство криптографических алгоритмы, обычно блочные шифры[1] и криптографические хеш-функции, при этом, если вход изменяется незначительно (например, переворачивается один бит), выход значительно изменяется (например, половина выходных битов переворачивается). В случае высококачественных блочных шифров такое небольшое изменение либо в ключ или простой текст должно вызвать резкое изменение зашифрованный текст. Фактический термин был впервые использован Хорст Фейстель,[1] хотя концепция восходит как минимум к Шеннон с распространение.

В SHA-1 хэш-функция показывает хороший лавинный эффект. Когда изменяется один бит, хеш-сумма становится совершенно другой.

Если блочный шифр или криптографическая хеш-функция не демонстрируют в значительной степени лавинного эффекта, то он имеет плохую рандомизацию и, следовательно, криптоаналитик может делать прогнозы о вводе, получая только вывод. Этого может быть достаточно, чтобы частично или полностью нарушить алгоритм. Таким образом, лавинный эффект является желательным условием с точки зрения разработчика криптографического алгоритма или устройства.

Построение шифра или хэша для демонстрации существенного лавинного эффекта является одной из основных задач проектирования, и математически при построении используются преимущества эффект бабочки.[2] Вот почему большинство блочных шифров товарные шифры. По этой же причине хэш-функции имеют большие блоки данных. Обе эти функции позволяют небольшим изменениям быстро распространяться по итерациям алгоритма, так что каждый кусочек вывода должна зависеть от каждого бита ввода до завершения алгоритма.[нужна цитата ]

Строгий лавинный критерий

В строгий лавинный критерий (SAC) является формализацией лавинного эффекта. Он удовлетворен, если всякий раз, когда один входной бит дополнен, каждый из выходных битов изменяется с вероятностью 50%. SAC основывается на концепции полнота и лавина, и была представлена ​​Вебстером и Таваресом в 1985 году.[3]

Обобщения SAC более высокого порядка включают несколько входных битов. Булевы функции, которые удовлетворяют SAC высшего порядка, всегда изогнутые функции, также называемые максимально нелинейными функциями, также называемые «совершенными нелинейными» функциями.[4]

Критерий битовой независимости

В критерий битовой независимости (BIC) утверждает, что выходные биты j и k должен изменяться независимо, когда любой единственный входной бит я инвертировано, для всех я, j и k.[5]

Смотрите также

Рекомендации

  1. ^ а б Фейстель, Хорст (1973). «Криптография и компьютерная конфиденциальность». Scientific American. 228 (5): 15–23. Bibcode:1973SciAm.228e..15F. Дои:10.1038 / scientificamerican0573-15.
  2. ^ Аль-Кувари, Саиф; Давенпорт, Джеймс Х .; Брэдфорд, Рассел Дж. (2011). Криптографические хеш-функции: последние тенденции дизайна и концепции безопасности. Inscrypt '10.
  3. ^ Вебстер, А. Ф .; Таварес, Стаффорд Э. (1985). «О конструкции S-боксов». Достижения в криптологии - Crypto '85. Конспект лекций по информатике. 218. Нью-Йорк, штат Нью-Йорк: Springer-Verlag New York, Inc., стр. 523–534. ISBN  0-387-16463-4.
  4. ^ Адамс, К.; Таварес, С.Э. (Январь 1990 г.). Использование изогнутых последовательностей для достижения строгого критерия лавинности более высокого порядка в дизайне S-box (отчет). Технический отчет TR 90-013. Королевский университет. CiteSeerX  10.1.1.41.8374.
  5. ^ Уильям, Столлингс (2016). Криптография и сетевая безопасность: принципы и практика (Седьмое изд.). Бостон. п. 136. ISBN  9780134444284. OCLC  933863805.