Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Рассмотрение вопросов надежности шифрования невозможно без введения качественной и количественной мер. В криптографии рассматривают два подхода к стойкости — теоретическую стойкость и практическую (или вычислительную) стойкость.
Теоретическая стойкость шифров
При рассмотрении вопроса о теоретической стойкости шифров отвлекаются от реальных временных и сложностных затрат по вскрытию шифра (что определяет подход к практической стойкости). Во главу угла ставится принципиальная
172
Надежность шифров
ВОЗМОЖНОСТЬ получения некоторой информации об открытом тексте или использованном ключе. Впервые такой подход исследовал К. Шеннон [ШенбЗ]. Он рассматривал уже знакомую нам модель шифра и единственную криптоатаку на основе шифртекста. Проследим за его рассуждениями.
Как мы указывали, конечной целью работы криптоаналитика является текст сообщения или ключ шифрования. Однако весьма полезной может быть даже некоторая вероятностная информация об открытом тексте. Например, уже предположение о том, что открытый текст написан по-английски, предоставляет криптоаналитику определенную априорную информацию об этом сообщении даже до того, как он увидит шифртекст. Так, например, он заранее знает, что слово “hello” является более вероятным началом сообщения, чем, скажем, набор букв “abcde”. Поэтому первая цель криптоанализа состоит в том, чтобы увеличить количество этой априорной информации, относящейся к каждому возможному открытому тексту таким образом, чтобы истинный открытый текст сделать более вероятным после получения шифртекста, хотя, конечно, и не обязательно точным.
Пусть, например, криптоаналитик перехватил текст “abccd” и знает (или предполагает), что он был зашифрован при помощи шифра простой замены. Этот шифртекст говорит ему о том, что открытый текст состоит из пяти букв, третья и четвертая из которых являются одинаковыми, а остальные отличными от этой буквы и разными. Хотя он не может быть уверенным, что этим словом является “hello” (это может быть еще “lessy” или что-то подобное), тем не менее апостериорные вероятности таких открытых текстов возрастают относительно их априорных вероятностей. Криптоаналитик, кроме того, полностью уверен (в предположении, что использовалась именно простая замена) в том, что этот открытый текст не может быть ни словом “after”, ни словом “catch”, и, таким образом, апостериорная вероятность обоих этих открытых
173
fлава 7
текстов сокращается до нуля, даже вне зависимости от их априорных вероятностей.
Шеннон назвал шифр совершенным, если для любого открытого текста знания, которые могут быть получены из соответствующего ему шифртекста, не раскрывают никакой информации об открытом тексте, за исключением, возможно, его длины. Другими словами, для совершенных шифров апостериорные вероятности открытых текстов (вычисленные после получения криптограммы) совпадают с их априорными вероятностями.
Вспомним о введенной нами модели шифра T1 в, в которой фигурировали распределения вероятностей P(X)9 P(K). Они как раз и являются наборами априорных вероятностей Px(*),XG X и рк(к)9 к є К. Будем предполагать, что Px (*) > 0, Pk (к) > 0 для любых х є X, к є К.
Далее мы будем рассматривать лишь такие шифры, для которых выбор ключа и выбор открытого текста являются независимыми событиями. Это равносильно тому, что распределения P(X)9 P(K) являются независимыми. Эти распределения естественным образом индуцируют распределение вероятностей P(Y) = {pY(y)*y е Y} на множестве возможных шифртекстов по формуле
Priy)= Y*Px(xY рЛк)- О4)
(*,*)
1ч(х)=У
Поясним корректность такого определения. Нужно проверить, что
YiPviy) = 1-
уеУ
174
Наоежность шифров
Рассмотрим отображение /: X х К -» Y, определенное условием /| = Ek для любого к є К . Тогда, поскольку
Г\У) = ХхК,
получаем:
Pxix)'Рк(к) =
уеУ уеУ (х,к)
Ек(*)=У
= Z Z Px(X)-PAk)= Z Pxix)' Рк(к) =
уеУ (х,к)є/(~\ (х,к)еХ*К
=Z Z^w-^w=Z^w,Z^(A:)=L
Естественным образом вводятся и условные вероятности Pr/X (у/х)> Py/к ІУ/к) > определяемые формулами:
P Y/ X О /*)= (15)
кеК:
Ек(х)=у
Ру/к(у/к)= Z (16>
д:єХ:
Ek(x)=y
Несложно проверить, что формулы (15) и (16) задают вероятностные распределения, то есть что при любом х є Х
Z РуIX (У Iх) =1 >
и при любом А: є А
Е^/И-У/*) = 1-
кеУ
175
І лава 7
С целью упрощения записи нижние индексы в обозначениях Р\іх(УІх)* Py/к(У/к) будем опускать и записывать
их в виде р(у/х), р(у/к) соответственно.
Отметим, что с помощью формулы для условной вероятности
p(a/b) = S^R (17)
p(b)
мы можем вычислить и условные вероятности р(х/у), Рік/у) :
) = MfhPOVti
PrOO
p(k/y)=pAk)p(y/t).
Pr (у)
(18)
Следующее определение лишь формализует предложенный выше подход к теоретической стойкости шифра (только по отношению к атаке на основе единственного шифртекста).
Определение. Назовем шифр Yb совершенным, если для любых X є X9 у gY выполняется равенство
р(х/у) = Рх(х). (19)
Отметим одно очевидное свойство совершенного шифра. Утверждение 1. Если шифр Yb — совершенный, то
