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

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

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

Визначення

Визначимо функцію надійності ключа через умовну інформаційну ентропію ключа ${\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}$ і називається відстанню єдиності.

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

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

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

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

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

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

${\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}}}$ називають надлишковістю джерела. Якщо надмірність джерела дорівнює нулю, тобто з відкритого тексту неможливо визначити, чи є коректним чи ні (в ньому немає перевірочних контрольних сум або сигнатур), тоді відстань єдиності стає рівною нескінченності, а криптосистема — абсолютно надійною.

Приклад

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

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

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

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

Примітки

1. . Архів оригіналу за 24 листопада 2020. Процитовано 21 квітня 2018.
2. Защита информации. Учебное пособие. Версия от 21 ноября 2017 года
3. . Архів оригіналу за 1 квітня 2018. Процитовано 21 квітня 2018.

Література

• Габидулин Э. М., Кшевецкий А. С., Колыбельников А. И. Расстояние единственности // Защита информации: учебное пособие — Москва: МФТИ, 2011. — 225 с. —
  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.] (англ.)