Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Наибольший интерес представляет предельное значение W(N) при Ar -> со (то есть W(оо)), которое можно рассматривать как среднюю работу по дешифрованию при неограниченном объеме шифртекста. Практическое вычисление W(оо) представляет собой весьма сложную задачу. В связи с этим практическую стойкость шифра обычно оценивают с помощью величины Wjx (оо) ? которую можно назвать достигнутой
оценкой рабочей характеристики. Она определяется средней трудоемкостью наилучшего из известных методов вскрытия данного шифра. Если значение W (оо) вычисляет криптоаналитик, которому известны все имеющиеся в настоящее время методы анализа шифров, то полученная оценка практической стойкости шифра заслуживает доверия, особенно если вычисления сделаны с достаточным “запасом”. Имеется в виду правильный выбор нижнего порога сложности А, выделяющий практически стойкие шифры неравенством Wa (оо) > А.
Большое значение имеет математическая модель вычислений, используемая при оценке практической стойкости шифра. По сути, речь идет о модели гипотетической ЭВМ, которой располагает потенциальный противник и которая способна реализовать крупный фрагмент алгоритма вскрытия как одну элементарную операцию. Например, опробование одного ключа к є К и проверку результата расшифрования по критерию открытого текста (выполняется ли включение
181
Ілава 7
Dk(y) є X ?), в принципе, можно принять за одну элементарную операцию.
Более детальное исследование вопросов практической стойкости (выходящее за рамки данной книги) выводит на серьезные проблемы теории сложности алгоритмов и разработки методов криптоанализа.
§ 7.4. Вопросы имитостойкости шифров
Как мы уже отмечали в гл. 2, помимо пассивных действий со стороны потенциального противника, состоящих в подслушивании или перехвате передаваемой по каналу связи шифрованной информации, возможны также его активные действия, состоящие в попытках подмены или имитации сообщения.
Если передается шифрованное сообщение у є Y (полученное из открытого текста х є X на ключе к є К), то противник может его заменить на у', отличный от у . При этом
он будет рассчитывать на то, что на действующем ключе к новая криптограмма при расшифровании будет воспринята как некий осмысленный открытый текст X1, отличный от х. Конечно, это событие может произойти с некоторой вероятностью, и чем больше эта вероятность, тем успешнее будет попытка подмены.
Попытка имитации может быть предпринята противником в том случае, когда линия связи готова к работе (на приеме и передаче установлены действующие ключи), но в рассматриваемый момент никакого сообщения не передается. В таком случае противник может выбрать некий у є Y и послать его от имени законного отправителя. При этом он будет рассчитывать на то, что на действующем ключе его криптограмма при расшифровании будет воспринята как некий осмысленный открытый текст. Чем больше вероятность этого события, тем успешнее будет попытка имитации.
182
Надежность шифров____________________________________________
При теоретическом исследовании активных действий противника обычно ставят его в наиболее благоприятные условия, помещая между отправителем и получателем, как это указано на схеме (см. рис. 21).
Рис. 21
Имитостойкость шифра определим как его способность противостоять попыткам противника по имитации или подмене. Естественной мерой имитостойкости шифра служит вероятность соответствующего события:
Dk (у) є X — для попытки имитации сообщения;
(Dk (У) є X) л (У =? у) — для попытки подмены сообщения.
В соответствии с этим введем следующие обозначения: Рим *“
max p(Dk (у) є X), (22)
уеУ
Pnom = max P(Dk (У ) е Х) . (23)
у,у'еУ
У'*У
183
І лава і
которые назовем соответственно вероятностью имитации и
ту попытку, которая с большей вероятностью приводит к успеху, вводят также вероятность навязывания формулой
Ph ~~ m^X(Рим 5 Рподм } •
Для шифров с равновероятными ключами (в рамках введенной в гл. 2 модели) можно получить общие оценки введенных вероятностей.
Утверждение 1 .Для шифра с равновероятными клю-
Доказательство. Пусть К(у) = {кєК \ Dk(y) є X} . Тогда в силу условия равновероятности ключей
вероятностью подмены6. Полагая, что противник выбирает
нами имеет место достижимая оценка рим >
Согласно (22),
(24)
Заметим, что имеет место соотношение
(25)
ує?
6 В [Сим88] р подм определяется несколько иначе, однако утверждение 2 для него остается справедливым.
184
Надежность шифров
В самом деле, рассмотрим таблицу зашифрования, строки которой занумерованы ключами, столбцы — открытыми текстами, а на пересечении строки с номером к є К и столбца с номером х є X расположен шифрованный текст
из которого, с учетом (24), получаем требуемое неравенство. Остается доказать его достижимость. Приведем пример шиф-
Рассмотрим шифр определенный условием
E k\(x\)~ ^k2(xI) тогДа и только тогда, когда кх = к2 и
х\ = X2« Ясно, что для такого шифра выполняются равенства
Обратим внимание на то, что для эндоморфного шифра с равновероятными ключами (например, для шифра гаммирования с равновероятной гаммой) рИМ = 1. Это означает, что такой шифр максимально уязвим к угрозе имитации сообщения. Поэтому, несмотря на их многие положительные качества, эндоморфные шифры нуждаются в имитозащите. Утверждение 2 показывает, что имитостойкость шифра растет про-
