Расстояние уникальности

Для сообщения длиной n число различных ключей, которые расшифруют шифротекст сообщения в какой-то осмысленный открытый текст на языке оригинального открытого текста (например, английском), определяется следующей формулой [712, 95]:

2^H(K)-nD-1

Шеннон определил расстояние уникальности, U, называемое также точкой уникальности, как такое приближенное количество шифротекста, для которого сумма реальной информации (энтропия) в соответствующем открытом тексте плюс энтропия ключа шифрования равняется числу используемых битов шифротекста. Затем он показал, что имеет смысл считать, что шифротексты, которые длиннее расстояния уникальности, можно расшифровать только одним осмысленным способом. Шифротексты, которые заметно короче расстояния уникальности, скорее всего, можно расшифровать несколькими способами, каждый из которых может быть правилен, и таким образом обеспечить безопасность, поставив противника перед выбором правильного открытого текста.

Для большинства симметричных криптосистем расстояние уникальности определяется как энтропия криптосистемы деленная на избыточность языка. U = H(К)/D

Расстояние уникальности является не точным, а вероятностным значением. Оно позволяет оценить минимальное количество шифротекста, при вскрытии которого грубой силой имеется, вероятно, только один разумный способ дешифрирования. Обычно чем больше расстояние уникальности, тем лучше криптосистема. Для DES с 56-битовым ключом и англоязычного сообщения, записанного символами ASCII, расстояние уникальности приблизительно равно 8.2 символа ASCII или 66 бит. В таблице приведены расстояния уникальности для различных длин ключа.

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

Расстояния уникальности текста ASCII, зашифрованного алгоритмами с различной длиной ключа

Длина ключа (в битах)	Расстояние уникальности (в символах)
40	5.9
56	8.2
64	9.4
80	11.8
128	18.8
256	37.6

Шеннон определил криптосистему с бесконечным расстоянием уникальности, как обладающую идеальной тайной. Обратите внимание, что идеальная криптосистема не обязательно является совершенной, хотя совершенная криптосистема обязательно будет и идеальной. Если криптосистема обладает идеальной тайной, то даже при успешном криптоанализе останется некоторая неопределенность, является ли восстановленный открытый текст реальным открытым текстом.

Вопрос 18.2. Открытое распределение ключей. Схема Меркля, Диффи - Хеллмана, Месси - Омуры Открытое распределение ключей в схемах Диффи-Хеллмана

Diffie-Hellman, первый в истории алгоритм с открытым ключом, был изобретен 1976 году. Его безопасность опирается на трудность вычисления дискретных логарифмов в конечном поле.

- однонаправленная функция, (p - большое простое число) (a примитив mod p???)

А	В
Секретные ключи
Открытые ключи
К	К

Злоумышленник может узнать из открытого канала величины р, α, у_А , у_В -> задача злоумышленника - получить ключ по этим величинам. Эта задача известна как проблема Диффи-Хелмана и ее сложность T(DH-problem) ≤ T(DLP) (задачи дискретного логарифмирования)

Схема Диффи-Хелмана обеспечивает секретность, но не обеспечивает аутентичность.