Расстояние единственности

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:08, 5 июня 2016.

Шаблон:Проверка+

Задачи Шеннона

  • Задача совершенной секретности
  • Задача количественной меры информации
  • Задача практической надежности

Расстояние единственности

- множества

Тогда существуют отображения:

И вероятности:

Тогда порожд. распределения на шифр:

формула Вайеса для условной вероятности

Задача получения открытого текста решена, когда одна из P=1, а все остальные 0. Пример:

  • ALICE
  • BETTY +
  • BOBBY
  • DOLLY + ABCCD
  • FREDY
  • MICKY
  • TOMMY +

Hello [имя] - вариант когда имя определить легко.

Так как мы знаем что 1-ое слово в сообщении было Hello (где есть две повторяющиеся буквы L), то мы можем точно сказать что сообщение предназначалось DOLLY.

Для некоторых шифров:

Такое L называется - расстоянием единственности.

  • L зависит от шифра
  • L зависит от открытых текстов (от множества, из которых текст выбирается)

Анализ вероятностей имеет смысл только если не все открытые тексты возможны

TemplateExampleIcon.svg Пример Пример:
В случае если шифруется случайное сообщение, то мы не можем отличить правильный ключ от неправильного. Даже если мы имеем контрольную сумму.


Случайные данные - ключи шифрования.

Расчет расстояния единственности для шифра простой замены

- длина сообщения.

- мощность алфавита.

- избыточность языка.

Число открытых текстов длины N

- количество сообщения длины N.

- шифруем открытый текст х ключем k и получаем шифртекст y.

- пробуем расшифровать шифртекст при помощи случайного ключа.

- среднее число ложных ключей, результат которых случайно будет осмысленным.

где - осмысленных слов - всего слов.

до этой величины текст не единственен, после можно предположить что текст единственен.

Любой блочный шифр можно расшифровать как шифр простой замены представляя блоки как алфавиты.

Избыточность текста не меняется от вида шифрования, также это относится к файлам, сетевым протоколам. Режим простой замены - ECB (Electronic Code Book)

Если режимы связи то задача нахождения единственности становится сложной.

Возвращаясь к длине сообщения :

- зависимость которая связывает расстояние единственности с тем, что передается - чем меньше передается, тем больше нужно перехватить информации. Чем больше расстояние единственности, тем стойче шифр. Если избыточность велика, то L мало, тогда код легко расшифровать для предотвращения нужно уменьшить избыточность.

Архивация решает две задачи:

  • передается меньше материала
  • уменьшается избыточность

Сначала Архивация потом Шифрование!