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

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

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

Визначення

Визначимо функцію надійності ключа через умовну інформаційну ентропію ключа $Z$ і символів шифротексту $y_{1},y_{2},\dots ,y_{n}$, які перехоплює криптоаналітик:

$f_{0}=H\left(Z\right)$

$f_{1}=H\left(Z|y_{1}\right)$

$f_{2}=H\left(Z|y_{1}y_{2}\right)$

$\dots$ 

$f_{n}=H\left(Z|y_{1}y_{2}\dots y_{n}\right)$

$f_{n}\leq f_{n-1}\leq \dots \leq f_{1}\leq f_{0}$

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

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

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

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

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

$H\left(y_{1}\dots y_{n}\right)\approx n\log L$

$H\left(y_{1}\dots y_{n}|Z\right)\approx {n \over N}H\left(X\right)$

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

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

$H\left(y_{1}\dots y_{n};Z\right)=H\left(y_{1}\dots y_{n}\right)+H\left(Z|y_{1}\dots y_{n}\right)\approx n\log L+f_{n}$

$H\left(y_{1}\dots y_{n};Z\right)=H\left(Z\right)+H\left(y_{1}\dots y_{n}|Z\right)\approx H\left(Z\right)+{n \over N}H\left(X\right)$

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

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

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

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

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

Приклад

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

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

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

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

Література

• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Расстояние единственности // Защита информации: учебное пособие — Москва: МФТИ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
  d:Track:Q26887242d:Track:Q4130888d:Track:Q26887244d:Track:Q649d:Track:Q26887236
• Р. В. Басалова Відстань єдиності [Архівовано 1 квітня 2018 у Wayback Machine.] // Основи криптографії [Архівовано 1 квітня 2018 у Wayback Machine.] (рос.)

Посилання

• Брюс Шнаєр: How to Recognize Plaintext [Архівовано 17 червня 2018 у Wayback Machine.] (Crypto-Gram Newsletter December 15, 1998) (англ.)
• Unicity Distance computed for common ciphers [Архівовано 22 квітня 2018 у Wayback Machine.] (англ.)