Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
Второе равенство в (34) следует из того, что если
р(к)-р(у/к) ф 0, то S(y,k) = I.
Теперь мы можем получить границу Симмонса для вероятности pKti. Для этого введем функцию
P(k)-S(y, к) р(у- доп)
Легко видеть, что Qy (к) — неотрицательная функция от
к, которая при суммировании по к (с учетом (33)) дает 1.
Выражая р(к)- S(y,k) из (35) и подставляя его в (34), получаем:
Р(У) = РІУ - Доп) • Y Qy (к) ‘ РІУ1 к) • (36>
кеК
Прологарифмировав (36) и умножив получившееся равенство на р(у), получим выражение
191
Ілава 7
р(у) log р(у) = р(у) log р(у - доп) +
+ РІУ) log Y Qy (к)РІУ / к). (37)
кеК
Второе слагаемое в правой части (37), с учетом (36), можно представить в виде
p(y-»ii)[X0,(*)p(.y/*:)]log[?g,(*)pO</*)].
кеК кеК
Воспользуемся неравенством Иенсена [Бил69], взяв за основу функцию f(t) = tlogt:
Y Qy (ЇЇР(У1 k) loS РІУ/ *) -
keK
^ YQyik^piyf *)L
keK keK
откуда
ріу) log Y Qy ik)piy/ k) ^
keK
— РІУ ~ Доп) ^ Qy (k)p(y / k) log p(y / k) =
keK
= Y Pik^Piy1 k)siy>k) 1Og РІУ1 k) =
кєК
= Y p(k)p(y1 k) lo§ ріу 1 k)• (3 8)
keK
Здесь мы воспользовались определением (35), а также тем, что из неравенства р(у/ k)p(k) Ф О следует равенство
S(y,k) = \.
Теперь, суммируя (37) по у и пользуясь оценкой (38) для второго слагаемого, получаем неравенство
192
Надежность шифров
- H(Y) < Y [РІУ) bg р(у - доп)] -H(YfK),
уеУ
из которого, согласно (31), следует, что
Y Р(У) log РІУ~ Доп) > -I(Y, К). (39)
Отсюда, наконец, получаем искомое неравенство: log Pm = log [max р(у - доп)] =
Д'єУ
= E РІУ)] ¦ log [max р(у - доп)] >
VeY У
^ Y РІУ) ‘ І08 РІУ ~ ДОП) - ~JiY’ К)*
yeY
Утверждение 3 доказано.
Из приведенных рассуждений следует, что равенство в (32) достигается в том и только в том случае, когда одновременно выполняются следующие два условия:
1. Вероятность р(у — доп) не зависит от у (поэтому левые части в (32) и (39) равны);
2. Для каждой криптограммы у є Y вероятность р(у/к) одинакова при всех к, для которых S(у, к) = 1.
Из утверждения 3 следует оценка для логарифма вероятности навязывания рн:
log/?н >-IiY,К), (40)
причем необходимыми (но уже не достаточными) условиями достижения равенства в (40) являются условия 1 и 2.
Согласно [Сим88], совершенная имитостожость определяется как равенство в (40). Следует, однако, отметить, что даже при достижении совершенной имитостойкости вероятность навязывания мала лишь при большой величине
193
І лава 7
I(Y9K)9 то есть в том случае, когда криптограмма дает значительную информацию о ключе. Информация, которую дает
Y относительно K9 есть мера того, в какой степени ключ используется для обеспечения имитостойкости.
В общем случае не известно, при каких условиях существуют шифры, обеспечивающие совершенную имитостой-кость, хотя и имеются соответствующие примеры [Сим88]. Любопытно отметить, что эти примеры свидетельствуют о том, что криптостойкость и имитостойкость шифра являются независимыми свойствами шифра.
§ 7.5. Шифры, не распространяющие искажений
Помимо целенаправленных искажений передаваемой шифрованной информации возможны также искажения, происходящие за счет наличия помех в канале связи. Такие помехи могут привести к искажениям или даже потере отдельных знаков используемого алфавита. Если искаженный знак не является знаком того же алфавита, то на приеме факт искажения легко установить. В противном случае факт искажения может быть установлен лишь при расшифровании, когда искажение в шифртексте приводит к потере части или даже всего открытого текста. Так же проявляется и потеря знаков шифртекста. Последствия искажений шифртекста при передаче могут быть различными для разных типов шифров. Нас будет интересовать вопрос о свойствах самого шифра, позволяющих не распространять искажений при расшифровании. При этом мы ограничимся рассмотрением лишь эндоморфных шифров и искажений, которые либо заменяют знаки алфавита знаками того же алфавита (искажения типа “замена знаков”), либо приводят к потере знаков или появлению дополнительных знаков алфавита (искажения типа “пропуск-вставка знаков”).
194
Надежность шифров
Шифры, не распространяющие искажений типа “замена знаков”
Будем рассматривать шифры, для которых открытые и шифрованные тексты являются словами в некотором алфавите А и которые не изменяют длины сообщений при шифровании. В терминологии, введенной в гл. 2, речь пойдет о шифрах, описываемых моделью S0 =(X,K,Y,E,D), в кото-
I.
рой X = Y = IM' , причем для любых X є X и ке К длина
/=і
у = Ek (х) совпадает с длиной х.
Естественной мерой значительности последствий искажений типа “замена знаков” является метрика на множестве сообщений X = Y. По-видимому, простейшей является метрика Хэмминга //, определяемая формулой
Л
м(х,у) = Z Я(хі’Уі )’ (41)
/¦=1
где л; = (Jc1хл),у = (^1ул)еХ,
Sti ' ч Iі’ хі*Уі>
3(хі>Уі) = \п
[О, Xt= у,.
Как мы знаем, для эндоморфного шифра каждое правило зашифрования Ek представляет собой биекцию Ek: X —> X. В силу этого часто бывает удобно пользоваться подстановочной моделью шифра — Sn = (Х,Е), в которой множество E = {ек :к є К} рассматривается как множество подстановок е :X ->X, ее E. При этом индекс к можно опустить, имея в виду наличие взаимно однозначного соответствия между правилами Ek и подстановками е.
