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

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

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

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

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

${\displaystyle \dots }$

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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}}$

${\displaystyle 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)}$

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

${\displaystyle 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)}}}$[3]

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

${\displaystyle 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)}}}$

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

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

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

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

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

• Габідулін Е. М., Кшевецкий А. С., Колибельников А. В. Відстань єдиності // Захист інформації: навчальний посібник — М: МФТІ, 2011. — 225 с. — ISBN 978-5-7417-0377-9
• Р. В. Басалова Відстань єдиності // Основи криптографії(рос.)

• Брюс Шнайер: How to Recognize Plaintext (Crypto-Gram Newsletter December 15, 1998)(англ.)
• Unicity Distance computed for common ciphers(англ.)