Лавиновий ефект

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Лавиновий ефект (англ. avalanche effect) — посилається на бажану властивість криптографічного алгоритму, зазвичай блочних шифрів і криптографічних геш-функцій. Лавиновий ефект очевидний у разі якщо, коли дані вході ледве змінюються (наприклад, змінився один біт) вихідні дані змінюються значно (наприклад, змінюється половина бітів). У випадку якісних блочних шифрів, подібна маленька зміна або в ключі, або в відкритому тексті повинна спричинити значну зміну шифротексту. Цей термін вперше використав Хорст Фейстель,[1] хоча сама поняття поринає назад щонайменше до поширення Шеннона.

Геш-функція SHA-1 показує хороший лавиновий ефект. При зміні одного біту на вході геш-сума стає зовсім іншою

Якщо блочні шифри або криптографічні геш-функції не проявляють лавиновий ефект значного ступеня, тоді це недостатнє перемішування, і звідси криптоаналітик, маючи лише вихідні дані, може зробити передбачення щодо вхідних даних. Цього може вистачити, щоб частково або повністю зламати алгоритм. Отже лавиновий ефект є бажаним з точки зору розробника криптографічного алгоритму.

Розробка шифру або гешу, що виявляв би значний лавиновий ефект становить одну з першочергових цілей дизайну. Саме через це більшість блочних шифрів є послідовністю перетворень таких як заміна, переставка або модульна арифметика. Через це й геш-функції мають великий розмір блоків. Обидві ці властивості дозволяють маленьким змінам через ітерації алгоритму швидко поширитись так, що кожен біт вихідних даних залежатиме від усіх бітів даних на вході ще до завершення алгоритму.[Джерело?]

Сувора умова лавиновості[ред.ред. код]

Сувора умова лавиновості (англ. strict avalanche criterion) — це узагальнення лавинового ефекту. Вона виконується якщо, завжди коли один вхідний біт був змінений, кожен біт на виході змінюється з імовірністю 50%. Умова покладається на концепцію повноти і лавиновість і була введена Вебстером і Таваресом (англ. Webster, Tavares) 1985.[2]

Умова незалежності бітів[ред.ред. код]

Умова незалежності бітів (англ. bit independence criterion) стверджує, що біти j і k мають змінюватись незалежно при зміні одного вхідного біту i, для всіх i, j і k.

Див. також[ред.ред. код]

Примітки[ред.ред. код]

  1. Feistel Horst Cryptography and Computer Privacy // Scientific American. — 228 (1973) (5).
  2. Webster, A. F.; Tavares, Stafford E. (1985). «On the design of S-boxes». Advances in Cryptology - Crypto '85. Lecture Notes in Computer Science 219. New York, NY,: Springer-Verlag New York, Inc. с. 523–534. ISBN 0-387-16463-4.