Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

411

описания инъективных отображений О* в- О*, не размножающих искажений определенных типов.

Приводимые ниже результаты инициированы одним полученным в 1956 году результатом А. А. Маркова о биективных преобразованиях <р

множества слов П* в конечном алфавите О , сохраняющих длины слов и не увеличивающих расстояния Хемминга между словами одной длины, то есть,не размножающих искажений типа замены букв в словах.

Рассмотренная А. А. Марковым задача имеет много различных вариаций. В частности, представляют интерес не только биективные но и инъектив­ ные отображения, наряду с искажениями типа замены букв могут происходит^.! искажения других типов, например, пропуски букв, по разному может опреде­ ляться понятие близости слов и т. д. Некоторые из таких вариаций и.рассматриваются ниже. В пункте 3 на основе идей А. А. Маркова описано множество

0 (0 , р ) всех инъективных отображений <р: О* —» О *, сопоставляющих сло­ вам одинаковой длины слова также одинаковой длины и не увеличивающих расстояние Хемминга р между словами. В качестве следствия этого описания получается и упомянутый выше результат А. А. Маркова. В пункте 4 рассмат­ ривается задача описания множества 0(0 ., е) инъективных отображений

(р'.О* —» Г2*, не размножающих искажений типа пропуска букв. Однако из них полностью описаны лишь биективные преобразования. В пункте 5 полнос­ тью описано пересечение 0 ( 0 , р ,е ) множеств 0 ( 0 , р ) и 0 ( 0 , е ) . В пункте 6 в качестве меры близости произвольных слов (а не только словодинаковой длины) рассматривается обобщенное расстояние Хемминга, функция />Дсовг падающая с р на парах слов одинаковой длины и принимающая значение к \

на парах, в которых одно слово получается из другого удалением к букр. Дот казывается, что при |П| > 3 множество всех 0 ( 0 , р') инъективное отображе­ ний, не увеличивающих значений функции р ' , совпадает с пересечением мно­ жеств 0 ( 0 , р ) и 0 ( 0 , е ) , хотя непосредственно из определений вклюден^

0 (0 , р') в каждое из этих множеств не усматривается. Заметим, что функция

р' не является метрикой: она не удовлетворяет известному свойству треуголь­ ника.

2. Основные понятия и обозначения.

Мы будем придерживаться следующих обозначений. N - множество натуральных чисел;

А0 - множество целых неотрицательных чисел;

412

- [у,*]= {5,5 + 1,...,?}, где 5,1 6 Л^0,5 < I

П - конечный алфавит из п букв п > 2; буквы алфавита П и слова в алфави­ те О будут обозначаться соответственно малыми и большими латинскими бу­ квами (с индексами и без индексов);

Р= 0, - графическое равенство слов Р и д ;

Л- пустое слово;

д(Р) - длина слова Р ;

О' - множество всех слов длины I е И 0 в алфавите П , в частности, П °={Л }; О ’ = 1 ) о ‘ - обозначает множество всех слов в алфавите 12;

<е Л Г ,

Рд - произведение (конкатенация) слов Р, (2;

Р ‘ - 1 - я степень слова Р (при любом I е ) причем Р° = Л для любого

Р е П * ; МН = { Р ( ) : Р е М ,д < = н } - произведение множеств слов М и Н ;

Р (,) - 1 -я буква слова Р при естественном упорядочении всех букв слова Р

от его начала к концу; Р(/ —» а) - слово, полученное из Р заменой его / -й буквы на букву а ;

Р(/ -» Л) - слово, полученное из Р удалением его г -й буквы;

Р(/ —» А/) = {р(г -> а ) : а е А/} - для любого подмножества М из П ;

р(/ >1 а) - слово, полученное вставкой буквы а после / -й буквы слова Р при и перед первой буквой слова Р при / = 0;

р ( /4 м ) = { р ( /1 а ) : а е м ] - для любого подмножества М из О ;

р { р ,0 ) - расстояние Хемминга между словами Р, д (одной длины), слова Р

ид , для которых р(Р, д ) = 1, будем называть соседними;

Б- бинарное отображение на множестве П*, Ред означает, что слово д по­ лучено из Р удалением одного вхождения некоторой его буквы;

е 1 - I -я степень бинарного отношения е ;

* (р )= {ббП * :Р е д \,

2 - особая буква, не содержащаяся в Г2;

р '{Р ,д ) - обобщенное расстояние Хемминга между словами Р и д , опреде­

ляемое как р ( Р , д ) при д(Р) = д (д ) и как шш р(Р , д , ) при д(Р)> д(д ) , где

•413

минимум берется по всем словам ();, полученным вставками в ^ ровно

д(Р)—д{0) вхождений особой буквы 2 (предполагается также, что ,

р'(Р,д)=р'(<2,Р);

(р{Р) - образ слова Р при отображении (р : О* —>П *;
< р {м )= {(р(р):Р еМ } - для любого подмножества слов М	множества Г2*;
8(М ) - симметрическая группа подстановок множества М	относительно
умножения подстановок, так что для §, к е $(М ) и х е М

§к(х) = к(§(х)); /л - оператор обращения слов, то есть р{Р ) = а как_х...ах для слова

Р = а1...ак_1ак;

РК - для слова Р = ах...ак_хак и подстановки <т е 5 (п ) обозначает слово ст{ах\..ст{ак_х)ст{ак);

8, - симметрическая группа подстановок множества [1,*].

Определение 1. Отображение (р:0 .* —» О* называется не размножа­

ющим искажений типа замены букв, если для любых слов Р,() е О* выполня­

ются условия
а(р)=е((2)=>0(р(/>))=г(«>(е)),	со
р(р ,а)± рМ г),< р(< 2})	(2)
Определение 2. Отображение (р : О	—» П называется не размножа­

ющим искажений типа пропуска букв, если для любых слов Р ,^ е П * и любо­ го к е М М ] найдется число тпе [1.*] - такое, что выполняется импликация

Река = х р { Р ) е т(р{0!). . • (3)

Множество всех инъективных отображений <р: О.* —>О *, не размно­ жающих искажений типа замены букв, обозначим через 0(0., р ) , а множество

всех инъективных отображений Г2* в Г2*, не размножающих искажений типа пропуска букв, обозначим через 0 ( 0 , в ) . Положим

с ( п ,А * ) = с ( а / ? ) П с ( М - Очевидно, что множества 0 ( 0 , р ) и С(С1, е ) являются подполугруп­

пами полугруппы = (Г2*) всех отображений П ’ в П *, Из них естественно

414

выделить подгруппы биективных отображений. Обозначим их, соответственно, через <7, (О, р ) и 0 2 (О, е ).

Определение 3. Отображение (р:0* —> О* называется не увеличива­

ющим обобщенного расстояния Хемминга между словами, если для любых

р'{р,0!)> р'{(р{р),<р(01)).

Множество всех инъективных и биективных от ображений - не увеличиваю­ щим обобщенного расстояния Хемминга между словами обозначим соответст­ венно через 0 (0 .;р') и 0 х(О ,р ') .

3.Описание полугруппы 0 ( 0 , р ). Так как преобразование

(р е 0(О , р ) инъективно и удовлетворяет условию (1), при любом ? е 7У0 оно

отображает множество О' в П'+д^ при некотором Д(/) е Ы0. Кроме того, из инъоктивности <р следует, что для (р выполняется условие: для любых

5, 1 е Ы0,5 * I ,
г + Д(г) = .у + Д ($)= 3> ^ (п ')р |^ (п *)=0.	(4)
Таким образом, описание полугруппы 0 ( 0 , р )	сводится к описанию

инъективных отображений <р,: О' —> 0 ,+А^ \{ е М0, удовлетворяющих услови­

ям (2) и (4).
	Опишем сначала инъективные отображения < р :0 ‘ —>П '+д, Д €	, с
условием (2).
,	Теорема 1. Инъективное отображение <р : О 1 —> 0 1+& удовлетворяет

условию (2) (не размножает искажений типа замены букв) тогда и только тогда, когда оно имеет вид: для любого слова Р е О!

^ ( р ) = 4 а 1( ^ (1)))^о-2(р(*(2))) ..4 а <(р(*('))) 4 +1, (5)

при фиксированных (не зависящих от слова Р ) словах АХ,...А1+Хе Г2 суммар­

ной длины 3 ( 4 - 4 . , ) = Д , подстановках	е 5(П ) и подстановке
8 * 8 , .

ДОКАЗАТЕЛЬСТВО. Очевидно, что любое отображение

( р : 0 ‘ —» П ,+д вида (5) инъективно и обладает свойством (2). Докажем обрат­ ное утверждение. Пусть (р инъективно и удовлетворяет условию (2). Зафикси­

415

руем слово Р е П' и рассмотрим множество слов Р(г —> О), / е [1, *]'. Так как при а Ф Ь

р{Р{} —> о), Р(/ —> &)) = 1,

в силу инъективности (р и свойства (1)

р (^ (^ (г а ))> ф {Р^ —■►^))) =1

и поэтому
«р(>(/ -> а)) = <р(Р(г(/) -» /г,,(а)))	(6)
при некоторых г(/) € [1, 1+ Д] и Л(. е $ ( п ) .

Ясно, что \Р(г —> П) ФР(у —> П) при ; ^ у и р(Р(г(/) -> а )) = р(Р(г(/') -» а )) при г(г) = г(у). Отсюда и из инъективности

<р получаем, что г есть инъективное отображение множества [ и ] ъ [м + 1 ].

Таким образом, по отображению (р каждому слову Р е О.1 сопоставлен набор

подстановок й,,..-А б 5 ( а ) и инъективное отображение так что для всех а еО. и / е [и]выполняется равенство (6). Подставляя

а = Р ^ в (6), находим, что
						(7)
Упорядочив числа г(г), / € [1,1+ А], в порядке возрастания
г(г,) < г(г'2) < ... < г(/,), мы можем записать слово <г>И в виде
«	. (	/	>	)	=	. .

где Ау(р^) есть г(у)-я буква слова ф { Р \] е [м ], а А1А2...А1+1 - слово, поду­ ченное из <р(Р) удалением букв с номерами г(г,),..., г(/,). Из формулы (6) сле­

дует также, что формула (8) остается верной при замене слова Р дюбым из слов множества Р(/ —» П) при любом / е [и ] . Подчеркнем еще, чггс нрн изме­ нении в Р буквы с номером у в слове <р{Р) изменится лишь букра с номером

*■(/)•	'	•
Теперь докажем, что подстановки Л	, Нг, отображение г и

А1,А 2,...,Аг+1 не зависят от выбора Р из О! .

Так как к любому слову <2 е О! можно перейти от Р , меня|1 последо­

вательно лишь по одной букве, указанный факт достаточно доказатьнишь дщг

416

соседних с Р слов. Пусть () е О.1, р{Р ,()) = 1 и сходное с (8) представление слова () имеет вид

	Л ) = в , Ф 0|)к / ф	ы )-.в д '(а а )К , ,	(?)
где	есть т'{г) -я буква слова <р(0) и отображение г ': [1,/] —> [1,1+ А]
определяется равенствами
	-> а)) =	й;(а))),г е [1 ,4 я е а .	(10)
Так как р { Р ,0 ) = 1, существует единственное число к е [1, ?] - такое, что
р(к) ф (^ь)	с лед0вательн0, Р{к —> а) = 0,{к —> а) при любом а е П . Отсюда

и из равенств (6), (10), учитывая, что р{(р{р\ <р{0^) = 1, получаем, что

т'(к) = т{к)ик'к = кк для указанного к . Далее рассмотрим слова

р 0 —» а),	—» а) при у * к . Очевидно, что р(Р(у —>
поэтому и р{(р{р{] —> а)),<р(		—> а))) = 1. Согласно формулам (8), (9) при

изменении у -й буквы в словах Р,(2 будут меняться соответственно по подс­ тановкам к^,к'^ только г(у)-яи г'(у)-я буквы слов <р(Р\ <^((2) • Отсюда легко следует, что г '(у) = г(у), /г' = к^ и Д. = 5,, / е [1,7 +1]. Этим и доказано утве­ рждение о независимости подстановок к^...Д , отображения г и слов

Д ,, А2 Д +1 от выбора слова Р из С1‘ . Таким образом, равенство (8) верно

для всех Р е О.1. Введя переобозначения /г, = = <?(■?)> мы получим из (8)

требуемую формулу (5). Теорема доказана.

Из всего вышесказанного в данном пункте следует, что для построения любого отображения из 0(0 ., р ) можно выбрать произвольную последовате­

льность чисел из И0 и для каждого I из задать указанным в

теореме 1 способом отображение (р1 :0.' —> 0 ' +д^ так, чтобы выполнялось условие (4). Если это возможно для выбранной последовательности

, то последовательность (р0,(рх,... определит отображение <р из 0 ( 0 , р ) , для которого ограничение (р | П' совпадает с (р( .

Покажем, как можно удовлетворить условие (4) при определении отоб­ ражений <рп ( & для заданной последовательности $>0, ч и с е л из Ы0. Для этого заметим сначала, что номера букв слова $>{Р) из формулы (8) делят­ ся на два класса: М,((р) - множество номеров, букв, изменяющихся при замене

’ г

417

слова Р другими словами из О' ,М 2 (<р) - множество остальных номеров (но­ меров неизменяющихся букв. Точнее,

М 2 {ф) = [м + 1]\ Л/1 {(р).

Из формулы (8) видно, что выбирая подходящим образом слово Р , мы можем получить в качестве Ъ-й буквы в слове (р{Р) любую букву из О . С другой

стороны, для любого к е М х{(р) буква (р(Р)^ является постоянной, независи­

мой от выбора слова Р (это буква слова Л1Л2...Л1_1). Следовательно, справед­ лива следующая теорема.

Теорема 2. Отображение <р:С1* —>€1* принадлежит С(С1, р ) тогда и

только тогда, когда

(1)ограничения (р( = (р |О.1 определен^ согласно теореме 1 для некоторых А(?), ^ е А^0;

(2)для любых 1,5 е Ы 0 , при которых I + Д(*) = 5 + Д(я), существу­

ет такое к е. М 2{<р1\ ^ М 2{<р5) что

	9,(р Г * 9 , ( а Г ,
где Р е	,"<2 ^ •

Отметим, что условие 2 данной теоремы вполне конструктивно.

В частном случае, когда все числа Д(^) равны нулю, получается следу­

ющая теорема А. А. Маркова.

Теорема 3. Биективное отображение (р: П* —» Г2* не размножает ис­

кажений типа замены букв в словах тогда и только тогда, когда для любого слова Р е ГУ, I е N , оно задается формулой

(р{Р) = а Х Р Ш ) \-<уХр Ш ) )^

где {<т(у : / е И ,] е [1,?]} - любой набор подстановок из 5(Г2), а ^,,^2,... - лю­

бой набор подстановок, соответственно, из 8Х,8 2,...

4.Описание группы Ох(О, е ) . Напомним, что <7,(0 , г) есть множест­

во всех биективных отображений

—» П *, удовлетворяющих условию

143ак. 5

418

(3). Докажем сначала несколько общих утверждений о преобразованиях из по­ лугруппы 0 ( 0 , в ) .

Предложение 1. Для любого (р е 0 (О ,в ), любых слов Р ,^ е О * и числа к е N справедлива импликация

(11) ДОКАЗАТЕЛЬСТВО. Согласно определению степени Е к бинарного отношения е , соотношение Р в к^ означает существование последовательно­ сти Р —Р\, Р2,..., Рк+1 = 2 - такой, что Рхв Р2е ... е Рм . Отсюда и из условия

(3), учитывая инъективность отображения (р, получаем, что

<р(Рх)в<р(Рг ) в ...в<р(Рк+,), что означает (р(Р) е к<р((2).

Предложение 2. Для любого <р ^ 0 ( 0 , в) существует. А = А(ф) € А 0 такое, что при каждом 1 е А0

^ (П ')с П '+4.

ДОКАЗАТЕЛЬСТВО. Пусть (р е 0 (О ,в ), <р(А) = Ри д(Р ) = А . Тогда для любого слова А е О 1 при I > 1 имеем А в‘А и в силу (11) получаем, что

<р(А)в' Р . Отсюда видно, что д(<р(А)) = I + д(Р) = д(А) + Д . Следовательно,

ф ( 0 ' ) ^ 0 ‘+А.

%

Предложение 3. Отображение (р из Сг(Г2, в) биективно тогда и только тогда, когда оно сохраняет длины слов.

ДОКАЗАТЕЛЬСТВО. Если (р еО (П ,г) сохраняет длины слов, то биективность (р следует из его инъективности. Если же оно биективно, то указан­ ное в предложении 2 число А(<р) равно нулю, а это и означает, что (р сохраня­ ет длины слов.

Предложение 4. Множество Ох(Г2, в) всех биективных отображений из

0 ( 0 , ё) является группой.

ДОКАЗАТЕЛЬСТВО. Замкнутость множества (7,(0, я) относительно операции умножения отображений очевидна. Поэтому достаточно показать, что

(р е <7,(О, ё) => (р~х 6 Ох(Г2, ё)

	419
то есть
Р е	ф ~ \Р )еф ~ \0 )

для любых Р, еП *. Из условия сохранения длин слов (предложение 3) отоб­ ражением ф следует, что для слов Р, <2 найдется натуральное число ш - такое,

что фт{Р) = Р ,ф т(0 ) = О . Тогда ф-'(Р) = фт- \ Р ), ф ~ \0 ) = фт~ \ 0 ) , и

доказываемая импликация является следствием замкнутости множества Сх(П, е) относительно произведения отображений.

Из предложений 1 и 4 следует, что любое отображение ф е С, (П, е)

перестановочно с отношением е , то есть для любого Р еС2*

ф(е(Р)) = е ( ф ( Р ) ) .

(12)

В дальнейшем нам понадобятся еще некоторые чисто технические утверждения о словах из П*.

Лемма 1. Если Р е П ', а,Ъ еО и аР=РЪ, то а=Ъ и Р = а ‘ .

Для ДОКАЗАТЕЛЬСТВА леммы 1 достаточно провести побуквенное

сравнение слов аР и РЬ.
Лемма 2. Если Р € О ', а,Ъ е С1 и
р(аР ,Р Ъ ) = 1	(13)

то а Ф Ь и Р —а кЪт при некоторых к,т е .

ДОКАЗАТЕЛЬСТВО. Из условия (13) следует существование единст­ венного значения / е[1,( +1], при котором (аР)(,) Ф(РЬ)(,). Пусть (аР)(,) = с , (РЬ)(|) = й . Тогда при г>1слово Р имеет вид РхсйР2, и из (13) получаем, что

аРхРхс , йРг = Р2Ь.

Отсюда и из леммы 1 следует утверждение леммы 2.

Лемма 3. Любое слово Р длины д ( Р ) > 3 однозначно определяется множеством слов е ( Р ) .

ДОКАЗАТЕЛЬСТВО. Для слова Р возможны три варианта:

Р= а‘;

Р= а кЪРх;

Р—аЬР2,

где а ,6 е П , аФ Ъ , РХ,Р2 е(1*, Р2 Ф А, 1>Ъ, к > 2. Они характеризуются следующими свойствами множества е ( Р ) :

14*

	420
■	в первом случае е ( Р ) состоит из одного слова а 1 1;
■	во втором случае все слова из е ( Р )		начинаются с буквы о, при­
чем одно из них есть а к~1ЪРх, все другие имеют начало ат,т > к;
■	в третьем случае е ( Р ) содержит слова аР2, ЬР2, а все остальные
слова, если они есть, имеют начало аЬ, при этом таких слов может не быть
лишь в том случае, когда Р2 = Ь Г.
Очевидно, что по указанной информации легко не только различить эти
три варианта, но и однозначно найти слово Р.
Из леммы 3, в частности, следует, что для любых слов				еГ2* длины
I > 3 выполняется импликация
	*(/> ) =	* ш ) = >	р = <2.	(Н)
Лемма 4. Если для некоторых слов Рх, Р2, () е О* и различных букв
а,Ъ е О выполняются соотношения
	РхаР2е($,	РхЪР2е<$,

то <2= рхр2:

ДОКАЗАТЕЛЬСТВО. По условию слово () получено удалением по од­ ной букве из слов РуаР2, Р\ЪР2. Если удалялось выделенное вхождение буквы а

и слова РуаР2или буквы Ь из РХЬР2, то утверждение верно. Кроме того, поско­ льку а фЬ, с л о в о () не могло получиться удаление из словРх.аР2, РХЪР2 по од­

ной букве из Рхили по одной букве из Р2. Следовательно, возможна лишь ситуация,где

Рх= Р х'сРх", Р2 ^ Р 2ЧР2п

и либо

а = Р х'Рх"аР2 = РхЪР2'Р2",

либо

<2=Рх'Р"ЬР2 = Р хаР2'Р2".

В силу симметрии достаточно рассмотреть один из указанных случаев. Пусть имеет место первый случай, то есть

0 = Рх'Рх"аР2'<1Р2" = Рх'сРх"ЬР2'Р2".

Тогда Рх'аР2 (1 = сРх" ЬР2 , в частности Рх" а - сР ", Рх й —ЬР2' . От­ сюда по лемме 1 получаем, что а=с, Рх" = а к,й=Ъ, Р2 —й т. Следовательно,

0 = Рх'ака<1т(1Р2''= Рх'аак<МтР2",