Відстань єдиності

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

Відстань єдиності (в криптології) — число символів шифротексту, при яких умовна інформаційна ентропія ключа (а, отже, і відкритого тексту) дорівнює нулю, а сам ключ визначається однозначно.

Досягнення відстані єдиності ще не означає, що ключ (або відкритий текст) можна знайти на практиці, так як визначення не враховує практичне обчислення ключа, але лише постулює, що його можна знайти, наприклад, за допомогою повного перебору.

Визначення[ред. | ред. код]

Визначимо функцію надійності ключа через умовну інформаційну ентропію ключа і символів шифротексту , які перехоплює криптоаналітик:

Таке число перехваченых символів , при якому і називається відстанню єдиності[1].

Приблизна формула[ред. | ред. код]

Виведення формули відстані єдиності можливо для деякої «хорошої» криптосистеми, у якої інформаційна ентропія шифротексту володіє певними властивостями «лінійності»:

де  — загальне число символів шфротексту повідомлення,  — алфавіт шифротексту, для простоти приймається рівним в тому числі й для відкритого тексту і ключа шифрування
останній вираз є «лінеаризацією» виразу[1].

Тоді з виразів для спільної інформаційної ентропії:

[1]

Тоді згідно з визначенням відстані єдиності як f_u = 0</math>:

Вираз називають надлишковістю джерела. Якщо надмірність джерела дорівнює нулю, тобто з відкритого тексту неможливо визначити, чи є коректним чи ні (в ньому немає перевірочних контрольних сум або сигнатур), тоді відстань єдиності стає рівнию нескінченності, а криптосистема — абсолютно надійною[1].

Приклад[ред. | ред. код]

Для російської мови надмірність дорівнює 3,5 біта на символ. Якщо використовується моноалфавітний шифр, то число можливих ключів в ньому дорівнює , а ентропія ключа (при рівноймовірному виборі) біта[2].

Тоді відстань єдиності для російського тексту, зашифрованого шифром простої заміни, дорівнює:

Тобто, якщо криптоаналітик перехопить більше 35 символів шифротексту, це з великим ступенем ймовірності дозволить (наприклад, повним перебором) відновити вихідний відкритий текст. Якщо ж буде перехоплено меншу кількість символів, то відновлення тексту буде неоднозначним (можуть бути декілька різних варіантів відкритого тексту)[3].

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

Література[ред. | ред. код]

Посилання[ред. | ред. код]