Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Шенноновскую энтропию Яд, приходящуюся на букву текста, можно определить тем условием, что для п -буквенного алфавита число текстов длины L, удовлетворяющих заданным статистическим ограничениям, равно (при достаточно больших L ) не Yi1 = 27 log2" = 2і н° , как это было бы, если мы имели бы право брать любые наборы из L букв, а всего лишь
M(L) = Il h*. (5)
По сути, это и есть асимптотика числа осмысленных открытых текстов длины L для данного языка А . Исходя из этого, можно определить энтропию Яд языка формулой
Hk =Iimihog1M(L)\
J
161
І лава 7
не зависящей ни от каких теоретико-вероятностных представлений. Величину M(L) можно оценивать с помощью подсчета числа возможных продолжений литературного текста.
§ 7.2. Расстояние единственности
Попытки определения истинного ключа шифра по данной криптограмме путем ее расшифрования на всех возможных ключах могут привести к тому, что критерий на открытый текст примет несколько претендентов за открытый текст. Это объясняется не только недостатками критерия. При небольших длинах криптограмм результат ее расшифрования может дать несколько осмысленных текстов. Например, криптограмму WNAJW5 полученную при использовании сдвигового шифра (см. гл. 5) для английского языка, порождают два открытых текста RIVER и ARENA, отвечающих ключам F (=5) и W (=22). При этом один из ключей является истинным, а другой — ложным. Аналогичная ситуация может иметь место для любого другого шифра.
Найдем оценку для числа ложных ключей. Для этого рассмотрим связь между энтропиями вероятностных распределений P(X)yP(K)9P(Y), заданных на компонентах X9K9Y
произвольного шифра Eb (см. гл. 2). Нам понадобятся некоторые дополнительные сведения об условной энтропии двух вероятностных распределений.
Пусть имеются дискретные случайные величины И TJ9 заданные вероятностными распределениями P(Z)9 P(Tj) . Для них можно вычислить совместное распределение P(Z9Tj) и условные распределения P(Zly)9P(TjIx) для любых фиксированных значений х G <%9 у GTJ .
Определим условную энтропию H(Zfy) формулой
162
Надежность шифров
H(Zly) = -Yd P(xIy) • 1о§2 P(xIy) ¦
хе!;
Усредненная (по всем yerj) величина H(^fy) называется условной энтропией двух вероятностных распределений:
17) = ~Y YР(У) • J') • І0§2 Р(Х/у) ¦ (6)
У*П
(При этом в (6) по определению полагаем log2р(х/у) - 0, если Р(х/у) = О.)
Величина (6) измеряет среднее количество информации о ?, обнаруживаемое с помощью Г]. Известно (см. [ШенбЗ]),
что имеет место неравенство H(^frj) < Н(%) , причем равенство = H(?) выполняется тогда и только тогда, ко-
гда ?,77 —независимые случайные величины.
Назовем условную энтропию H(KfY) неопределенностью шифра по ключу. Она измеряет среднее количество
информации о ключе, которую дает шифртекст. Аналогично вводится неопеределенностъ шифра по открытому тексту H(XfY). Эти величины являются мерой теоретической стойкости шифра. В этом можно убедиться на основании следующих рассуждений.
Минимально возможным значением неопределенности шифра по открытому тексту H(XfY) является 0. Что можно сказать о шифре в этом случае? Ясно, что равенство H(XfY) = 0 выполняется лишь тогда, когда каждое слагаемое
в выражении для H(XfY) равно нулю:
р(у) ¦ P(xIy) ¦ Iog2 р(х/у) = О
для всех х,у. Согласно принятой договоренности это возможно лишь в случаях, когда (log2р(х/у) = 0 или когда
163
fлава 7
l°g2 р(х/у) = O, то есть если р(х/у) = 1 при некоторых X9 у. Это означает, что по данному у можно получить существенную информацию о X9 что свидетельствует о слабости шифра. Чем больше H(XfY)9 тем меньше информации получает противник об открытом тексте по криптограмме. Идеальной является ситуация, когда H(XjY) = H(X). Именно в этом случае шифр можно было бы назвать идеальным или со-вершенным. Заметим, что (в силу сделанного выше замечания) такое представление полностью соответствует определению совершенного по К. Шеннону шифра (см. § 7.3).
Связь между энтропиями компонент шифра дает известная [ШенбЗ] формула для неопределенности шифра по ключу:
H(KfY) = H(X) + H(K) - H(Y), (7)
полученная К. Шенноном. Эта формула позволит нам получить оценку среднего числа ложных ключей.
Рассмотрим произвольный поточный шифр замены, для которого множество X открытых текстов представляет собой множество возможных осмысленных текстов в данном алфавите А (например, русском, английском или некотором другом), состоящим из п букв. Зафиксируем некоторое число LgN и будем интересоваться числом ложных ключей, отвечающих данной криптограмме уеА1. Предполагается, что
А служит также алфавитом шифрованного текста. Введем обозначение
K(y) = {keK:3xeX, Ek(x) = y}.
К(у) есть множество ключей, для каждого из которых у является результатом зашифрования некоторого осмысленного открытого текста длины L.
Если мы располагаем криптограммой у, то число ложных ключей равно [Ar(^)I-I, так как лишь один из допусти-164
Надежность шифров
мых ключей является истинным. Определим среднее число ложных ключей к j (относительно всех возможных шифртек-стов длины L ) формулой,
