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

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

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

Визначення

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

$f_0=H\left(Z\right)$

$f_1=H(Z|y_1)$

$f_2=H(Z|y_1{y}_2)$

$\dots$ 

$f_n=H(Z|y_1{y}_2\dots y_n)$

$f_n\le f_{n-1}\le \dots \le f_1\le f_0$

Таке число перехваченых символів $u$, при якому $f_u=0$ і називається відстанню єдиності.

Приблизна формула

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

$H\left(Y\right)=N\log L$

де $N$ — загальне число символів шифротексту повідомлення, $L$ — алфавіт шифротексту, для простоти приймається рівним в тому числі й для відкритого тексту і ключа шифрування

$H(y_1\dots y_n)\approx n\log L$

$H(y_1\dots y_n|Z)\approx \frac{n}{N}H\left(X\right)$

останній вираз є «лінеаризацією» виразу$H(Y|Z)=H\left(X\right)$.

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

$H(y_1\dots y_n;Z)=H(y_1\dots y_n)+H(Z|y_1\dots y_n)\approx n\log L+f_n$

$H(y_1\dots y_n;Z)=H\left(Z\right)+H(y_1\dots y_n|Z)\approx H\left(Z\right)+\frac{n}{N}H\left(X\right)$

$n\log L+f_n\approx H\left(Z\right)+\frac{n}{N}H\left(X\right)$

$n\approx \frac{H\left(Z\right)-f_n}{\log L-H\left(X\right)/N}=\frac{H\left(Z\right)-f_n}{\log L\cdot \left(1-\frac{H\left(X\right)}{N\log L}\right)}$

Тоді згідно з визначенням відстані єдиності як $u:f_u=0$:

$u\approx \frac{H\left(Z\right)}{\log L-H\left(X\right)/N}=\frac{H\left(Z\right)}{\log L\cdot \left(1-\frac{H\left(X\right)}{N\log L}\right)}$

Вираз $\rho =1-\frac{H\left(X\right)}{N\log L}$ називають надлишковістю джерела. Якщо надмірність джерела дорівнює нулю, тобто з відкритого тексту неможливо визначити, чи є коректним чи ні (в ньому немає перевірочних контрольних сум або сигнатур), тоді відстань єдиності стає рівною нескінченності, а криптосистема — абсолютно надійною.

Приклад

Для російської мови надмірність дорівнює 3,5 біта на символ. Якщо використовується моноалфавітний шифр, то число можливих ключів в ньому дорівнює $33!\approx 8,68\cdot 10^{36}$, а ентропія ключа (при рівноймовірному виборі) $H\left(Z\right)={\log }_{2}33!\approx 122,7$біта.

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

$u=\frac{H\left(Z\right)}{\rho }\approx 35,1$

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

Література

• Шаблон:Cite Q
• Р. В. Басалова Відстань єдиності Шаблон:Webarchive // Основи криптографії Шаблон:Webarchive Шаблон:Ref-ru

Посилання

• Брюс Шнаєр: How to Recognize Plaintext Шаблон:Webarchive (Crypto-Gram Newsletter December 15, 1998) Шаблон:Ref-en
• Unicity Distance computed for common ciphers Шаблон:Webarchive Шаблон:Ref-en