Повнота (криптографія)

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

В криптографії, булева функція є повною, якщо значення кожного біту на виході залежить від усіх бітів на вході.

Це бажана властивість шифру, бо якщо один біт на вході (відкритий текст) змінюється, кожен біт на виході (шифротекст) з імовірністю 50% зміниться також. Найлегший спосіб показати, що це добре такий: уявімо, що в нашому 8-байтному тексті ми змінили останній байт, і це вплинуло б лише на 8-й байт шифротексту. Це означало б, що якби супротивник отримав 256 різних пар відкритий текст-шифротекст, він би завжди знав останній байт кожної 8-ми байтної послідовності, що ми надсилали б (12.5% всіх даних). Віднайти 256 пар відкритий текст-шифротекст не складно у світі інтернету, ми використовуємо стандартний протокол, а стандартні протоколи мають стандартні заголовки і команди (наприклад, "get", "put", "mail from:" тощо), які супротивник може безпечно вгадати. З іншого боку, якщо наш шифр має таку властивість (і також безпечний з інших боків), супротивник мав би зібрати 264 (~1020) пар відкритий текст-шифротекст, щоб зламати шифр таким способом.