Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
195
ілава 7
Далее в этом параграфе мы будем рассматривать именно подстановочную модель шифра.
Определение 1. Будем говорить, что шифр Sn = (X9E) не распространяет искажений типа замены знаков, если для любых х9уєЛл, 1 < Я < L9 и любого е є E выполняется неравенство
ju(e~lx,e~ly)<^i(x,y). (42)
Данное определение естественным образом формализует понятие “не распространения искажений”. Неравенство (42) означает, что число искажений в расшифрованном тексте не превышает числа искажений в передаваемом шифрованном тексте. Иногда говорят также, что шифр, удовлетворяющий условию (42), является помехоустойчивым (или помехостойким) к искажениям рассматриваемого типа.
Утверждение 1. Шифр Zп не распространяет искажений типа замены знаков тогда и только тогда, когда для любого AgI9L, любых х9уєЛл и любого еєЕ выполняется равенство
ju(e~'x,e~ly) = м(х,у). (43)
Доказательство. Действие преобразования е на множестве Дя = Ал х Ax , заданное формулой е(х, у) =
= (е~1х,е~1у), определяет биекцию Ал -» Aa . Поэтому если
(,X9у) пробегает Ая, то и (е 1X9е~1 у) также пробегает Дя. Отсюда следует, что
Є~'у) = >0
ИЛИ
196
Набежностьшифров
Х[М*>-У)-Ме~‘*,е~'.у)] = 0- (44)
(Х,у)
Если шифр не распространяет искажений, то, в силу (42), каждое слагаемое в (44) неотрицательно. Поэтому равенство
(44) может выполняться лишь в случае, когда имеет место условие (43), что и требуется.
Определение 2. Подстановки е є E, удовлетворяющие условию (43), называются изометриями на X.
Утверждение 1 показывает, что для шифров, не распространяющих искажений типа замены знаков, множество E состоит из изометрий. Критерий того, что подстановка е є E является изометрией на X, получен А. А. Марковым (см. [Баб97]). Для его формулировки введем следующие два преобразования множества X:
= (aj\ '"-Ia
R(ax,..., ал ) = (Rx (ах),..., Rx (ал)), (46)
где (j\9...9j%) —перестановка чисел 1,2,...,Я; R1ES(A) — некоторые фиксированные подстановки множества А, at є A9 Леї ,L9 і є I9 Л.
Теорема (А. А. Маркова). Биекция е е E является изо-метрией на X тогда и только тогда, когда е = R • Пh ^
для подходящих преобразований, определенных формулами
(45), (46).
Доказательство. Достаточность условия теоремы очевидна, поскольку преобразования R и Tlh являются
изометриями и произведение изометрий также является изометрией. Обратимся поэтому к доказательству необходимости условия теоремы.
197
І лава 7
Л
Для фиксированного элемента (aj9...9a^) g A введем обозначение
Л
Ai = {(tfb-ая)9 a G А}
и покажем, что если е(а|,...,ад) = (с|,...,сд), то для любого і G X9 Л найдется j GX9X такое, что
&(Aj ) — (с\,...,су_j, A9Cj^i) . (47)
х
Любые элементы множества A1 отличаются лишь в одной позиции. Если бы равенство (47) не выполнялось, то на-шлись бы х9 у G е(Аі) такие, что ц(х9у) > 2. Это противоречит условию о том, что е — изометрия на X. Итак, (47) имеет место.
В (47) е осуществляет биекцию по соответствующим координатам:
є((Л\,..., Q1 і, Cl9 Q/+l,..., <2л ) —
(48)
= (с,,...,Cj^RXci),Cn,,...,сх),
где R1 — некоторая биекция множества А . Меняя значение і
от 1 до X9 получим перестановку Jл) множества XfX9
такую, что
е(ах>...,ал) = (Rkl (Qkx),...,Rkx (Qkx )), (49)
где
198
Надежность шифров
ґ I 2 ... /І л 1
ч./і 72 ••• Jx Покажем, что
/ 1 2 ... Л '
к\ к2 -кл,
e = R П
JX-JX ’
(50)
где R = (7?],...,Лд) — преобразование, полученное в (49).
Для этого введем в рассмотрение “окрестность радиуса Г точки (а|,...,ад):
1=1
Эта окрестность представляет собой множество точек из
отстоящих (по метрике Хэмминга) от данной точки не более чем на единицу. Аналогично можно ввести и окрестности Om(«і,...,ад) большего радиуса.
Заметим вначале, что (50) выполняется на Ol^al 9...9ал).
Это следует из (47) и (48). То же самое можно выразить в другой форме:
<Р = е-Пк^ h -R~x = idАх,
(51)
где idАх —тождественное преобразование множества Ax .
Л
Докажем, что равенство (51) выполняется на всем А .
X
Для этого рассмотрим произвольную точку (6],...,6д) є А и систему окрестностей B1, і = Of Я:
199
fлава 7
bO =Ol(a\, -,ax), Bi = 0\(b\9a29...9ax)9...9 bA =0I (Ъ\9—9Ъл)
и индукцией по і покажем, что <p = idна каждом из них.
При / = O справедливость (51) уже проверена. Допустим, что утверждение верно для і = к и рассмотрим і — к +1.
Пусть xgBj+i =Ox(bx,...,bj+x,aj+2,...,ax) и пусть d = = (bi,...9bj9aJ+i,...9ax) — “центр” окрестности Bj. Ясно, что ju(x9d) < 2. Если при этом ju(x9d) = 1, то хє Bj и <р(х) = х по предположению индукции. Пусть тогда ju(x,d) = 2. Покажем, что для любого ye02(d) имеет место равенство <р(у) = у.
Без ограничения общности можно считать, что
У ~ (c\->ci'>b^9.~9bj9aj+\9...9ax)9 где C1 ^bl9C2 ^b2. Рассмотрим точки
U — (C1, Ь2 ?•••> Ь j, Qj _j_j,..., йд ) , V — (Ь\9С2, Ь j, Qj _|_jQ^ ) .
Поскольку Ut V є Bj, то по предположению индукции
ф(и) = U9 (p(v) = V . В силу того что ф, очевидно, изометрия, получаем цепочку равенств
