Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В. Основы криптографии
.pdfНаОежность шифров
|
р ( у - д о п /к ) = { 1, ^ Д ) = 1’ |
|
|||
|
|
[О, |
8 (у,к) = О, |
|
|
то |
|
|
|
|
|
|
Р(У ~ доп) = ^ |
8 (у,к) ■р (к ) . |
(33) |
||
|
|
к е К |
|
|
|
Представим вероятность р { у ) в виде |
|
|
|||
Р(У) = X |
Р(к) • р ( у ! к) |
р(к) • |
к ) - 8 ( у ,к ) . |
(34) |
|
йеЯ' |
|
кеК |
|
|
|
Второе равенство в (34) следует из того, что если
Р(к) ■р(у / к) ф 0, то 5(у,к) = 1.
Теперь мы можем получить границу Симмонса для ве роятности р ИК. Для этого введем функцию
Р(к ) - 8 (у, к)
р( у - доп)
Легко видеть, что ()у (к) — неотрицательная функция от
к , которая при суммировании по к |
(с учетом (33)) дает 1. |
|
Выражая р(к)- §{у,к) из (35) |
и подставляя его |
в (34), |
получаем: |
|
|
Р(У) = Р(У ~ Доп) • 5 ] ^ у (к) ■р ( у / к ) . |
(36) |
|
к е К |
|
|
Прологарифмировав (36) и умножив получившееся ра венство на р ( у ), получим выражение
191
|
|
|
/ лава 7 |
Р(У) 1°Е Р(У) = р ( у ) 1°ё Р(У - Доп) + |
|
||
|
+ р ( у ) 1о ^ Я у (к)р(у/к) . |
(37) |
|
|
|
кеК |
|
Второе слагаемое в правой части (37), с учетом (36), мож |
|||
но представить в виде |
|
|
|
ке К |
|
кеК |
|
Воспользуемся неравенством Иенсена [Бил69], взяв за ос |
|||
нову функцию / ( 1) = {1о |
: |
|
|
2 в у ( к ) р ( у 1 к) 1о§ р {у / к) > |
|
||
кеК |
|
|
|
^ 1 ^ Я у(к)р{у1к)\\щ[^ду(к)р{у1кУ\% |
|
||
кеК |
|
кеК |
|
откуда |
|
|
|
Р(У) 1о§ X |
(к )р{у / к ) * |
|
|
кеК |
|
|
|
< р ( у - Доп)]Г ^ |
(к)р(у / к) 1од р ( у / к) = |
|
|
|
кеК |
|
|
= X Р (к)р(у / к)д(у, к) 1од р ( у / к) = |
|
||
кеК |
|
|
|
= X Р(к)р(у / к) 1о§ р ( у / к). |
(3 8) |
||
кеК |
|
|
|
Здесь мы воспользовались определением (35), а также тем,
что из |
неравенства р ( у / к)р(к) Ф0 следует равенство |
8 ( у , к ) |
= 1 . |
Теперь, суммируя (37) по у и пользуясь оценкой (38) для второго слагаемого, получаем неравенство
192
Надежность шифров
- Н(У) < ^ [р ( у )1о§р( у - доп)] - Н ( Г / К ),
уеУ |
|
|
из которого, согласно (31), следует, что |
|
|
^ р ( у ) \ о % р ( у - щ т ) > - 1 { У , К ) . |
(39) |
|
Отсюда, наконец, получаем искомое неравенство: |
|
|
р ИЫ= 1о§[тах р ( у - доп)] = |
|
|
|
Д'еУ |
|
= Е |
Р(У)] ■1о§[тах р (у - доп)] > |
|
уеУ |
У |
|
^ ^ Р(У) • 1°§ Р(У - Доп) > -1(У , К).
уеУ
Утверждение 3 доказано.
Из приведенных рассуждений следует, что равенство в (32) достигается в том и только в том случае, когда одновре менно выполняются следующие два условия:
1. Вероятность р (у —доп) не зависит от у (поэтому
левые части в (32) и (39) равны); 2. Для каждой криптограммы у е У вероятность р(у/к)
одинакова при всех к , для которых 8(у,к) = 1 .
Из утверждения 3 следует оценка для логарифма вероят
ности навязывания р н : |
|
1оЕ/?н > ~1(У ,К ), |
(40) |
причем необходимыми (но уже не достаточными) условиями достижения равенства в (40) являются условия 1 и 2.
Согласно [Сим88], совершенная имитостожость опре деляется как равенство в (40). Следует, однако, отметить, что даже при достижении совершенной имитостойкости вероят ность навязывания мала лишь при большой величине
193
/лава 7
1(У,К), то есть в том случае, когда криптограмма дает зна
чительную информацию о ключе. Информация, которую дает У относительно К , есть мера того, в какой степени ключ используется для обеспечения имитостойкости.
В общем случае не известно, при каких условиях сущест вуют шифры, обеспечивающие совершенную имитостойкость, хотя и имеются соответствующие примеры [Сим88]. Любопытно отметить, что эти примеры свидетельствуют о том, что криптостойкость и имитостойкость шифра являются независимыми свойствами шифра.
§ 7.5. Шифры, не распространяющие искажений
Помимо целенаправленных искажений передаваемой шифрованной информации возможны также искажения, про исходящие за счет наличия помех в канале связи. Такие поме хи могут привести к искажениям или даже потере отдельных знаков используемого алфавита. Если искаженный знак не является знаком того же алфавита, то на приеме факт искаже ния легко установить. В противном случае факт искажения может быть установлен лишь при расшифровании, когда ис кажение в шифртексте приводит к потере части или даже все го открытого текста. Так же проявляется и потеря знаков шифртекста. Последствия искажений шифртекста при переда че могут быть различными для разных типов шифров. Нас будет интересовать вопрос о свойствах самого шифра, позво ляющих не распространять искажений при расшифровании. При этом мы ограничимся рассмотрением лишь эндоморфных шифров и искажений, которые либо заменяют знаки алфавита знаками того же алфавита (искажения типа “замена знаков”), либо приводят к потере знаков или появлению дополнитель ных знаков алфавита (искажения типа “пропуск-вставка зна ков”).
194
Надежность шифров
Шифры, не распространяющие искажений типа “ замена знаков”
Будем рассматривать шифры, для которых открытые и шифрованные тексты являются словами в некотором алфави те А и которые не изменяют длины сообщений при шифро вании. В терминологии, введенной в гл. 2, речь пойдет о шифрах, описываемых моделью = ( Х , К , У , Е , В ) , в кото-
I.
рой X = У = 1 М ' , причем для любых х € X и к е К длина
/=1
у = Ек(х) совпадает с длиной х .
Естественной мерой значительности последствий иска жений типа “замена знаков” является метрика на множестве сообщений X = У . По-видимому, простейшей является мет рика Хэмминга /л , определяемая формулой
|
|
Л |
|
|
М ( х , у ) |
= |
^ |
8 ( х 1, у 1 ), |
(41) |
|
|
/=1 |
|
|
где л; = (*!,...,хл ),у =0 ^,...,у л ) е Х , |
|
|||
ж ' |
ч |
I 1’ |
|
|
|
|
[О, |
Х{ = у { . |
|
Как мы знаем, для эндоморфного шифра каждое правило |
||||
зашифрования Ек представляет собой биекцию Ек : X |
—> X . |
В силу этого часто бывает удобно пользоваться подстановоч ной моделью шифра — Еп = ( Х , Е ) , в которой множество
Е = {ек :к е К} |
рассматривается как множество подстановок |
е :X - > X , е е |
Е . При этом индекс к можно опустить, имея |
в виду наличие взаимно однозначного соответствия между правилами Ек и подстановками е .
195
(лава 7
Далее в этом параграфе мы будем рассматривать именно подстановочную модель шифра.
Определение 1 . Будем говорить, что шифр Е п = ( Х 9Е)
не распространяет искажений типа замены знаков, если для
любых х 9у е Л л, 1 < Я < Ь9 и любого е е Е выполняется не
равенство
/и(е~хх,е~ху ) < ц { х , у ) . |
(42) |
Данное определение естественным образом формализу ет понятие “не распространения искажений”. Неравенство (42) означает, что число искажений в расшифрованном тексте не превышает числа искажений в передаваемом шифрованном тексте. Иногда говорят также, что шифр, удовлетворяющий условию (42), является помехоустойчивым (или помехостой ким) к искажениям рассматриваемого типа.
Утверждение 1 . Шифр не распространяет искаже
ний типа замены знаков тогда и только тогда, когда для лю
бого |
Л е 19Ь, любых х 9у е Л л и любого е е Е выполняется |
|||
равенство |
|
|
|
|
|
/и(е~'х,е~1у ) = м ( х , у ) . |
(43) |
||
|
Д оказательство. |
Действие |
преобразования е |
на |
множестве Дя = А л х А л , |
заданное |
формулой е(х, у ) = |
||
= ( е~1х,е~1у ) , определяет биекцию |
Ал -» Ал . Поэтому если |
|||
( х 9у ) |
пробегает Ал 9 то и (е~хх,е~1у) также пробегает |
Дя . |
||
Отсюда следует, что |
|
|
|
^ ^ ( е - ' х , е ~ 1у ) = ^ ц ( х , у )
ИЛИ
196
Набежностьшифров
^ [ / и ( х , у ) - / и ( е ~ 1х,е~[у)\ = 0. |
(44) |
(Х , у ) |
|
Если шифр не распространяет искажений, то, в силу (42), каждое слагаемое в (44) неотрицательно. Поэтому равенство (44) может выполняться лишь в случае, когда имеет место ус ловие (43), что и требуется.
Определение 2. Подстановки е € Е , удовлетворяющие условию (43), называются изометриями на X .
Утверждение 1 показывает, что для шифров, не распро страняющих искажений типа замены знаков, множество Е состоит из изометрий. Критерий того, что подстановка е е Е является изометрией на X , получен А. А. Марковым (см. [Баб97]). Для его формулировки введем следующие два пре образования множества X :
|
|
= (аЛ9—9а]л)> |
|
(45) |
|
К(ах,..., ал ) = |
(а{),..., Кл (ал )), |
(46) |
|
где 0 ‘1,.-5Уд) |
— перестановка чисел 1,2,..., Я; |
7?/ е 8 (А) — |
||
некоторые фиксированные |
подстановки множества |
А , |
||
а, е А , Л е 1,Ь, г е 1,А . |
|
|
|
|
Теорема (А. А. Маркова). Биекция е е Е |
является |
изо |
||
метрией на X |
тогда и только тогда, когда |
е = К • П ^ |
^ |
для подходящих преобразований, определенных формулами
(45), (46).
Д |
оказательство. Достаточность условия теоремы оче |
|
видна, |
поскольку преобразования К и П ^ |
являются |
изометриями и произведение изометрий также является изо метрией. Обратимся поэтому к доказательству необходимости условия теоремы.
197
|
|
|
I лава 7 |
Для фиксированного |
элемента |
(а],...,ад) е А X введем |
|
обозначение |
|
|
|
А Л = { |
( « |
! , . |
ад), а е А} |
и покажем, что если |
е(а|,...,ад) = (с|,...,сд), то для любого |
||
/ е 1,Я найдется у е 1, Л такое, что |
|
||
|
|
|
(47) |
|
|
Д |
отличаются лишь в од |
Любые элементы множества Аг |
ной позиции. Если бы равенство (47) не выполнялось, то на-
шлись бы х,у е е(А;) такие, что //(*,у) > 2. Это противоре
чит условию о том, что е — изометрия на X . Итак, (47) име ет место.
В (47) е осуществляет биекцию по соответствующим ко ординатам:
|
в(а] |
а?1 ,а, а,+1 |
а^) — |
(48) |
|
|
|
|
|
где К' |
— некоторая биекция множества А . Меняя значение 1 |
|||
от 1 до |
Я, получим перестановку |
( д ,...,/д) множества |
1,Л, |
|
такую, что |
|
|
|
|
|
е{ах,...,ал ) = (Кк{ (акх),...,Ккя (акя )), |
(49) |
||
где |
|
|
|
|
198
Надежность шифров |
|
|
|
|
г 1 |
2 ...Л л 1 |
/ 1 |
2 ... Л ^ |
|
ЧУ1 |
]2 ••• ]Х |
к\ |
к2 - кл , |
|
Покажем, что |
|
|
|
|
|
|
71- Л |
’ |
(50) |
|
|
|
||
где Я = |
— преобразование, полученное в (49). |
|
Для этого введем в рассмотрение “окрестность радиуса Г точки (а|,...,ад):
О, (в!,..., ад) = 0 4 *
/=1
Эта окрестность представляет собой множество точек из
отстоящих (по метрике Хэмминга) от данной точки не более чем на единицу. Аналогично можно ввести и окрестно сти От(«1 ,..., а^) большего радиуса.
Заметим вначале, что (50) выполняется на Ох(ах,...,ах) .
Это следует из (47) и (48). То же самое можно выразить в дру гой форме:
<Р = е - П к] кх • К "* = Ш Ах, |
(51) |
где Ш х — тождественное преобразование множества А л .
Докажем, что равенство (51) выполняется на всем А Л . Для этого рассмотрим произвольную точку (6],...,6д ) е А А и
систему окрестностей В1, / = 0,Л :
199
[ лава 7
В0 = 0 \(а \9...9а^)9 В\ =0\(Ъ\9а2 ад
Вл = °\
ииндукцией по г покажем, что <р =Ш % на каждом из них.
|
При / = 0 справедливость (51) уже проверена. Допус |
|||||||||||
тим, |
что |
утверждение |
верно |
для |
г = к |
и |
рассмотрим |
|||||
I — к + 1 . |
|
|
|
|
|
|
|
|
|
|
|
|
Пусть |
х е В ]+х=Ох(Ъъ ...,Ъ]+ьа]+2 ,...,ах ) |
и пусть </ = |
||||||||||
- (Ь^9...9Ь^9а^+^9...9а^) |
— |
“центр” |
окрестности |
В] . Ясно, |
||||||||
что |
//(х ,б /)< 2 . Если |
при |
этом |
/и(х9с1) = 1, |
то |
|
и |
|||||
ф(х) = х |
по предположению индукции. Пусть тогда |
|||||||||||
/л(х,<]) = 2 . Покажем, |
что |
для любого у е 0 2(с1) |
имеет |
|||||||||
место равенство <р(у) = у . |
|
|
|
|
|
|
|
|
||||
Без ограничения общности можно считать, что |
|
|||||||||||
|
|
У ~ (съ с2 '>Ъъ9...9Ъ]9а^ \ 9„.9ах ) 9 |
|
|
|
|||||||
где с, фЪХ9с2 фЬ2. Рассмотрим т о ч к и |
|
|
|
|
|
|||||||
и —(с|,Ъ2V»Ъ^ ,ауЧ1,...,йд ), |
V —(^1 ,^2563,...,Ъ] , ) |
• • |
• ) ) • |
|||||||||
Поскольку |
и, V е 2?у, |
то |
|
по |
предположению |
индукции |
||||||
<р(и) = и9 ^>(у) = V. В силу того что |
(р, очевидно, изомет |
|||||||||||
рия, получаем цепочку равенств |
|
|
|
|
|
|
|
|||||
|
|
Кф(у\у) = К<Р(У\Ф)) = |
= |
1 . |
|
|
||||||
Аналогично получаем равенство |
/и(<р(у)9и) = 1. Следо |
|||||||||||
вательно, |
е О, (и) п О, (у ). |
|
|
|
|
|
|
|
200