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


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

Расстояние единственности (в криптологии) — число символов шифротекста, при которых условная информационная энтропия ключа (а, следовательно, и открытого текста) равна нулю, а сам ключ определяется однозначно.

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

Содержание

Определение

Определим функцию надёжности ключа через условную информационную энтропию ключа 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. — 261 с.
  • Г. В. Басалова Расстояние единственности // Основы криптографии

Wikimedia Foundation. 2010.

Смотреть что такое "Расстояние единственности" в других словарях:

  • расстояние единственности — Расстоянием единственности называется количество знаков шифртекста, необходимое криптоаналитику для вскрытия шифра. [http://www.rfcmd.ru/glossword/1.8/index.php?a=index&d=4952] Тематики защита информации EN unicity distance …   Справочник технического переводчика

  • ПОТЕНЦИАЛА ТЕОРИИ ОБРАТНЫЕ ЗАДАЧИ — задачи, в к рых требуется найти форму и плотности притягивающего тела по заданным значениям внешнего (внутреннего) потенциала этого тела (см. Потенциала теория). В другой постановке одна из таких задач состоит в отыскании такого тела, чтобы его… …   Математическая энциклопедия

  • МАКСВЕЛЛА УРАВНЕНИЯ — фундаментальные ур ния классич. макроскопич. электродинамики, описывающие эл. магн. явления в любой среде (и в вакууме). Сформулированы в 60 х гг. 19 в. Дж. Максвеллом на основе обобщения эмпирич. законов электрич. и магн. явлений и развития идеи …   Физическая энциклопедия

  • ПОЧТИ ПЕРИОДИЧЕСКАЯ ФУНКЦИЯ — функция, к рая может быть представлена обобщенным рядом Фурье. Существуют различные способы определения классов П. п. ф., основанные на понятиях замыкания, почти периода, сдвига. Каждый из классов П. п. ф. получается в результате замыкания в том… …   Математическая энциклопедия

  • АНАЛИТИЧЕСКАЯ ФУНКЦИЯ — функция, к рая может быть представлена степенным рядом. Исключит, важность класса А. ф. определяется следующим. Во первых, этот класс достаточно ш и р о к: он охватывает большинство функций, встречающихся в основных вопросах математики и ее… …   Математическая энциклопедия

  • ПРОСТРАНСТВО — фундаментальное (наряду с временем) понятие человеческого мышления, отображающее множественный характер существования мира, его неоднородность. Множество предметов, объектов, данных в человеческом восприятии одновременно, формирует сложный… …   Философская энциклопедия

  • СПЛАЙН-АППРОКСИМАЦИЯ — приближенное представление функции или приближенное восстановление функции из заданного класса по неполной информации (напр., по значениям на сетке) с помощью сплайнов. Как и в классич. теории приближения функций, изучаются линейные методы С. а …   Математическая энциклопедия

  • Геометрия — (греч. geometria, от ge Земля и metreo мерю)         раздел математики, изучающий пространственные отношения и формы, а также другие отношений и формы, сходные с пространственными по своей структуре.          Происхождение термина «Г. , что… …   Большая советская энциклопедия

  • Выпуклое тело —         геометрическое тело, обладающее тем свойством, что соединяющий две его любые точки отрезок содержится в нём целиком. На рис. тело а выпукло, а тело б не выпукло. Шар, куб, шаровой сегмент, полупространство примеры В. т. Любая связная… …   Большая советская энциклопедия

  • Сжатых отображений принцип —         одно из основных положений теории метрических пространств (См. Метрическое пространство) о существовании и единственности неподвижной точки множества при некотором специальном («сжимающем») отображении его в себя. С. о. п. применяют… …   Большая советская энциклопедия