Лекція №5 2) тема лекції «умови реалізації та приклади шифрів» Навчальні питання

5.2 Відстань єдності для шифру.
У системі шифрування символи криптограми в шифраторі зашифруються за правилом:
, (1.9)
де Мi – i-й символ повідомлення , , а Кі – і-й символ ключа, Сі - i-й символ криптограми, m – розмір алфавіту, що використовується.
Відмінною рисою системи Вернама є те, що символи ключа Кi мають генеруватись(породжуватися) випадково, рівно ймовірно та незалежно. У такій системі символів ключа (довжина ключа) має бути не менше довжини повідомлення, тобто
. (1.10)
Розшифрування в системі Вернама здійснюється згідно з правилом
. (1.11)
Аналіз (1.9) і (1.10) показує, що для зашифрування і розшифрування потрібно використовувати однакову випадкову послідовність (ключ).
Можна показати, що для системи, яка розглядається, умовна ентропія [7]:
, (1.12)
де l – довжина криптограми, d – надмірність алфавіту повідомлень.
Визначимо умову, при якій реалізується безумовна стійкість, тобто знайдемо число символів криптограми, при якому не можна здійснити крипто аналіз.
Задача крипто аналізу може бути розв’язана, коли:
.
Тоді із (1.12) випливає, що
. (1.13 )
Розв’язавши рівняння (1.13) отримаємо, що відстань єдності l₀ визначається як
. (1.14)
Фізично параметр l₀ означає мінімальну кількість символів криптограми при правильному отриманні яких можна сподіватися на успішний крипто аналіз. Якщо l₀, то система безумовно стійка. Це друга умова реалізації безумовно стійкої системи.
Очевидно, що успіх крипто аналітика у розв’язанні задачі крипто аналізу залежить від обсягу криптограм, який він отримав. При цьому крипто аналітик знаходиться в невизначеності , причому
. (1.15)
Найкращий випадок, якщо .
Використовуючи функції ненадійності Шеннона [7]:
, (1.16)
де l – загальний обсяг символів криптограми, який необхідно перехопити для розв’язання задачі крипто аналізу, а також враховуючи, що при l₀ , можна скласти і вирішити систему лінійних рівнянь і вона матиме одне розв’язання. При цьому вирішення самої задачі може бути дуже складним, але воно є і єдине.
Для деякого класу лінійних (групових) шифрів, у яких використовуються природні мови (російська, англійська, С++, графіка) Кл. Шеннон отримав розв’язок рівняння (1.16), якщо
,
, (1.17)
(1.18)
і апостеріорна ентропія визначається через умовну апостеріорну імовірність ,
то
, (1.19)
, (1.20)
.
Далі можна розрахувати за (1.19), знаючи статистики Р(Сj) і .
Надмірність d визначається залежністю символів мови між собою та різними ймовірностями появи їх в тексті. Вона може бути визначена, як
, (1.21)
де Н₀(М) – ентропія мови, де всі символи порівняно ймовірні і незалежні.
Якщо
, (1.22)
то
, (1.23)
тому
. (1.24)
Використовуючи рівняння (1.18), маємо для мови з m алфавітом
. (1.25)
Для двійкового алфавіту (m=2)
. (1.26)