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

	421
Рх= Рх'аак,	Р2 = а тс1Р2\

откуда получаем, что ()= РХР2 и лемма доказана.

Теперь можно перейти к формулировке и доказательству основ­ ного результата данного пункта.

	Теорема 4. Отображение <р:С1* —> О *	содержится в группе
	Сх(Г2, е) тогда и только тогда, когда (р(Р) для любого Р еО * имеет вид
	< р ( Р ) = Р °	(15)
	или
	<р{Р) = » ( Р ° )	(16)
	где а - фиксированная для данного (р подстановка из 5(П ), а ц - оператор
	обращения слов.
	ДОКАЗАТЕЛЬСТВО. Очевидно, что отображения (15), (16) содержать-
|	ся в Ох(П, ё) . Докажем обратное утверждение. Пусть П = {а,,... ап} и
	(р е <7,(П, ё) . Так как (р биективно, оно по предложению 3 сохраняет длины
|	слов, в частности, (р{Л) = Л и <р(ах) = <т(а,),/ е [1 ,и ], для некоторой подс-

!тановки <7 е 5 (0 ) . Покажем, что при этой подстановке <тотображение (р дей­

	ствует, как в (15) или как в (16), на всех словах Р длины 2.
|	Для п < 2 этот факт следует непосредственно из (12), биективности (р
	и сохранения им длин слов.
I,	Пусть п > 3 . Обозначим для краткости сг(а(.) = Ъ{, / е[1,я]. Так как
|	е ( а 1а ] ) = {а,.,ау} при / * , в силу (12)
I	= {(р{а1),<р{а] )} = {&,,*>,} .

Отсюда, учитывая биективность (р, находим, что
' (р{а1а ] ) = ЪхЬ] ,		(р{а]а 1) = Ъ]Ь1	(17)
ИЛИ
4о{аха ,.) =	,	<р(а]а 1) = Ъ1Ъ]	(18)

\

Докажем, что при выполнения условия (17) для некоторых фиксиро-

;ванных различных /, у е[1, п] необходимо выполняются равенства

<р(аха к) = Ь,Ьк

(19)

\

422

при любом к Ф/. Допустим. Что при некотором к Фг, кФ ] справедливо ра­ венство <р(аха к) = ЬкЬхи, значит (р(ака х) = Ь{Ьк. Рассмотрим слово

() = а1а]ак. Так как е ( ( ) ) = {а 1а ] , а 1а к , а ]а к} , в силу (12)

	= {Ь,Ь1,ЬкЬп <р(а]а к)} .
Отсюда однозначно находим, что
(р(0) = ЪкЪ!Ъ] ,	<р(а;а к) = ЪкЪ]	= 6 Д .

Теперь для слова 0,х= ахака^ е(<2\) = {а ,а к,а ,а ] , а ка ] }

и в силу (12) получаем, что

Однако нетрудно видеть, что слова ^ x, удовлетворяющего последнему

условию, не существует (так как ни одна из букв Ь( , Ь^, Ьк не может быть пе­ рвой буквой в слове <р(()х)). Значит, наше допущение невозможно, то есть верно (19). Из доказанного легко следует, что если равенства (17) выполняются для некоторых фиксированных различных 1,), то они выполняются для произ­

вольных /,у € [1,и] . Из соображений симметрии то же самое верно и относите­ льно условия (18). Заметим еще, что теперь равенства

(р{а1а 1) = ЪхЬ1, I е[1,и],

следуют непосредственно из условия (12).Таким образом, (р действует по пра­

вилу (15) или по правилу (16) на всех словах длины Ь < 2 .

Допустим, что последнее утверждение верно для всех слов длины Ь < 1 и докажем его для всех слов 1+1.

Пусть <р(Р) = Р а для всех Р еГ Т , а (7 - любое слово длины 1+1. Тог­

да, используя (13)	и очевидное равенство (е ((2 ))а —& (& *), получим, что
	* (9 > (0 ))	=	9 > (* (0 )) = ( * ( 0 ) У = ет( 0 * ) ■
Отсюда, в силу (14), (р ( () )			=	О а .
Если же (р( Р ) = /л {Р а )		для всех Р еГУ, то аналогично, используя
перестановочность преобразования /л				с отношением е и преобразованием
Р —> Р а , получим, что
	* ч е ) =	д	( б	ст)
для любого слова	е П г.
Теорема доказана.

I

423

Непосредственно из теорем 1, 3 получается следующее утверждение. Следствие 1. Справедливо включение

6 ,(0 ,* ) с С Д О ,^ .

5. Описанйе полугруппы О (О , р , е) .

Теорема 5. Инъективное отображение <р:0* —> О * содержится в

полугруппе С ( О , р , е) тогда и только тогда, когда для любого Р еО* отоб­ ражение (р{Р) имеет вид

<р(Р) = А Р аВ	(20)
или
ср(Р) = А р ( Р ° ) В	(21)
при фиксированных для заданного (р словах А, В еО*	и подстановке

<те5(П ).

ДОКАЗАТЕЛЬСТВО. Непосредственно из теорем 1- 4 видно, что отоб­ ражения вида (20) и (21) содержаться в полугруппе

С (О , р , ё ) = 0 ( 0 , р ) I С (О , е) . Докажем обратное утверждение. По предложению 2 для любого (р е С ( О , е) существует число А е N -такое, что для любого I е N справедливо включение <р(0! ) с: П'+л . Если Д = 0, то

(р биективно, и по теореме 3 имеет требуемый вид (20) или (21) при А = ВЛ . Пусть Д > 1. Согласно теореме 1 (при 1-1) ^р(а-) = А <т(а,)В для лю­ бой буквы а. из О , где А, В - фиксированные слова, а - фиксированная по­

дстановка из 3 ( 0 ). Так как а.еА , то <р(а1)е<р(Х) , / е[1,и]. Отсюда, учиты­ вая, что |П|= п > 2 , по лемме 4 получаем, что (р(Л) = А В . Таким образом, доказываемое относительно (р утверждение верно для всех слов Р длины

Ь < 1. Для общего индуктивного перехода нам понадобиться доказать его и для слов длины 2, поскольку на словах длины Ь < 1 преобразования (р, опре­

деляемые формулами (20) и (21), действуют одинаково. По теореме 1 (при 1=2) образ <р(Р) любого слова Р длины 2 находится по формуле

<р(Р) = Аха х{Р (ет})А2(т2( Р (8(2)))Аъ

при некоторых А,,А2, А3 е О *, сг,, сг2 е 5 (0 ), § е 82 • В зависимости от подс­ тановки § возможны два случая:

<»(/>) = М , ( Р " ' ) А 2а 2( Р т )А,-, р ( Р ) = Л , < г , ( Р т ) А1<г2( Р т ) А1 .

			424
В первом случае
	<р(Р(1 -> а)) = А,а1(а)А 2а 2( Р (2))А } ,
	<р(Р(2	а)) = Л1а 1( Р (,))Л2сг2(а)Л 3.
Так как Р ( /	—> а ) е	Р ( / —> Л) ,то
<р( Р( 1 —» а ) ) е ( р { Р { 1 —»		Л,)) . Отсюда, учитывая, что л > 2 , по лемме 4
получаем,чтоф ( Р ( \ —> Я))		=	А 1А 2а 2( Р (2)) А 3
	р ( Р ( 2 - >		Л » =	Л, <т, (Р(1>) Л2Л 3 .
с другой стороны по доказанному для 1=1
.	<р{Р(\	-»	Я ) ) =	А а ( Р (2)) В ,
	<р(Р(2		Я)) =	А а ( Р 0 ) ) В .

Приравнивая правые части соответствующих приведенных выше ра­ венств, получим, что А, = А, А2 = Я, А3 = В , сг, = <т2 = сг и, значит,

ф ( Р ) = А Р кВ.

Аналогично во втором случае получим, что

< р ( Р ) = Л ц ( Р ' ) В .

Далее в индуктивном переходе необходимо рассмотреть два случая, ко­ гда для всех слов длины I < Ь , где X > 3 , действие отображения <р задается

соответственно формулами (20), (21). В обоих случаях при рассмотрении слов длины X повторяются те же рассуждения, что и выше при 1=2. А именно, срав­ ниваются значения слова Р (/ —» Я ) , найденные по лемме 4 с использовани­

ем формулы (5) и по предположению индукции (при всех возможных Р еС1‘ , / е [1 ,ф . В обоих случаях получим, что

А1= А, Л2 = Л} = ...= Аг = Я , Л,+1 = Д , сг, = сг2 =...= сг, = сг,

а подстановка # в первом случае будет тождественной, а во втором она равна

	1 2		-	*-1	Л
	а	I - 1	-	2	I/
	Отсюда следует, что утверждение теоремы справедливо для всех слов
длины Ь < 1 , I > 3 . Теорема доказана.
	Описание полугруппы		С	(О.	, р ') . Заметим, что хотя значение
р	' на парах слов одной длины совпадает со значением р , включение
С	(О. , р ' ) С1 О ( Г2 , р	) непосредственно из определений 1,3 не еле-

425

дует, поскольку при определении множества 0 (0., р) на отображения

(р'.О * —» Г2 * налогалось дополнительное требование (1). Кроме того, непо­

средственно из определений С ( О , р 1) и 0 ( 0 , е) не следует также, что

6 ( О , р ' ) с С ( О , е ) . Дело в том, что из Р е () следует, что

р \ Р , 0 ) = 1 , однако обратная импликация неверна. Вместе с тем, имеет место следующее утверждение.

Теорема б. Если |0 | = п > Ъ,то Ст(П,/?)ПС7(П,г').

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

Пусть Р - фиксированное слово из Г2*. Множество слов М а О* на­ зовем Р —системой, а слова из М назовем1Р - совместимыми, если для лю­ бых А,В € М

0 ( А , В ) = 0 ( Р , А ) = 1.

Р - систему назовем максимальной, если она не входит ни в какую от-, личную от нее Р —систему.

Опишем максимальные Р —системы. Для Р —Я единственной такой

системой является. О . Пусть Р е О ‘, I > 1. В этом случае множество

0 ( Р ) = ( е е П ‘:^ (Л Ш = 1 } , содержащее все Р —системы, представляется в виде объединения

о (Р )= « (/> )Ц

		•	М = 1
Выясним вопрос о совместимости слов из различных компонент этого
объединения.
Лемма 5. Пусть А,В		- два различных Р - совместимых слова для
слова Р ф Л.
Тогда
(1)	А е е ( Р ) = > В	е Р ( 1 1 0 ) ,	г е[0,{];
(2)	А е е ( Р ) , В еР(1 -+ Г2)=> Р = РхаР2, А = РХР2,В = РХЬР2 при
некоторых Р1,Р2 еГ2*, а,6 е О, а Ф Ь ;
(3)	А,В & е(Р )=> Р = Р1аЬР2, А - Р ХР2,В = Р1ЬР2 при некоторых

РХ,Р2 е О \ а ,Ь е О , а ф Ь ;

(4) если некоторое слово С совместимое А,В и А,В,С е е ( Р ) , то

С = А или С - В \

	426
(5)	А е Р ( / 1 П ), В € Р(у -> О ) => Р = РХЪР2, А = РхаЪР2, В = />аР2
или Д = РхЪаР2,5 = РхаР2, а ф Ь \
(6 )если Л е Р ( « 1 П ) ,5 б Р и I О ) , то существует г е м 9 ПРИ
котором А,В е Р ( г 4 '0 ) ;
(7)	А € Р (/ —> П )=> В й Р(у —» П ) для у * /.
ДОКАЗАТЕЛЬСТВО. 1. Если А е е ( Р ) , В		еР (/^ Г 2 ),т о
^ Д ) —<т(у4) = 2 . Поэтому 0 ( А , В ) > 2 и ДШ не могут быть Р - совмести­
мыми.	Пусть А = Р(у -» Я), В е Р((	Ь ) . Если / = у , то утверждение
2.

рно. Пусть / < у . Тогда Р = К^К^сКз, Л = КхаК2К3, В = КхЪК2сК3, а * Ь .

Так как &(А) = д ( В ) —\ , при нахождении 0 (А, В) в слово А долж­

на вставляться особая буква г так, чтобы для полученного слова А выполня­ лось условие р ( А , В) = 1. Так как а ФЪ , буква 2 может быть вставлена толь­

ко в Кх. Значит, А = Кх 2," аК2Кг и из	условия р ( А , В ) = 1	получаем, что
р(гК х" ,/г," Ъ) = 1, р(аК2,З Д	= 0.
Отсюда, используя леммы 1 и 2, находим, что а = с,		К2 = ак , К = Ът .

Поставляя найденные результаты в РОЛ и В , замечаем, что утверждение 2 выполняется при Рх= Кх, Р2 = В2сК3. Справедливость утверждения 2 при

/ > у устанавливается аналогично.

3. Пусть А = Р (/ —» Я ), Р = Р (у —» Я). Так как Д ^ Р ,т о * * у . Пусть * < у .

Тогда

Р = КхаК2ЬК3, Л = КХК2ЬК3, В = КхаК2К3

Так как д ( А ) = д(.В), то (3(А,В) = р (А ,В ) , и из условия

р{ А ,В ) = 1 получаем, что р{ К2ЬаК2) = 1. Отсюда по лемме 2 находим, что

афЪ, К2 = а кЪт . Следовательно, утверждение 3 выполняется при Рх= Кха к,

Р2 = ЬтК3.

4. Допустим, что А, В , С попарно различны. В силу симметричност условий для слов А , В , С , не теряя общности, можно считать, что

Р = КхаК2ЪК3сК4, А = КхК2ЬК3сК4, В = КхаК2К3сК4, С = КхаК2ЪК3К4.

427

Применяя утверждение 3 к парам слов ( А ,В ), ( В , С ) , ( А , С ) , полу­ чим равенства К2 = акЪт , Р3 = Ъгс5, К2ЪКъ = арсч.

Отсюда видно, что Ъ= а или Ь = с. В первом случае А =В , во втором

В= С . Получим противоречие.

5.Это утверждение доказывается так же, как утверждение 2, с рассм рением двух подслучаев / < у , и г > у .

6.	Пусть. А = Р(г >1 а) , В е Р(у 6)		и / < у . Тогда
Р = Р,Р2Р3, А= КхаК2К3, Р = КхК2ЪКъ.
Отсюда и из условия р ( А , В ) = 1 по лемме 2			получаем, чтоР2= акЬт ,
афЬ, и утверждение 6 выполняется при		= Кха к,Р2 = ЪтК2 .
7.	Если Л е Р (/ —> О ), В е Р(у —> О ), то очевидно, что при г ^ у

справедливы равенства /У(А,В) = р ( А, В) = 2 и получаем противоречие.

Лемма доказана.

Лемма 6. Если Р е О*, |П| = л > 3 и I > 1, то максимальные по мощ­

ности Р-системы слов исчерпываются множествами вида

(a)	Р(г>10), / е[0,г];
(B)	Р ( / - » ( П \ { Р (')} У {Р (/ —> А ) } , / е[1,*];

ДОКАЗАТЕЛЬСТВО. Используем утверждения 1-7 леммы 5. Очевид­ но, что Р-системы типа (а) и (Ь) содержат по п элементов. Покажем, что лю­ бая другая Р -система слов содержит менее п элементов. Пусть Р е О! , I > 1

иМ - максимальная по мощности Р -система. По утверждению 4 леммы 5

Мсодержит не более двух различных слов из Р( е ) . В связи с этим возможны

три случая.

1.А , В е М I е ( Р ) , А Ф В . Тогда согласно утверждению 3

Р= РхаЬР2, А = РхаР2, В = РХЪР2, а ФЪ.

Кроме того, согласно утверждению 1 М I Р( / 4 П ) = 0 , / е М . а в силу утверждения 7 может существовать лишь единственное значение / , при котором М I Р (/ —> 0 ) ^ 0 . Пусть С € М I Р (/ 4 П ). Тогда в силу утверж­ дения 2

С = РхасР2 = РхйЪР2, с Ъ, й Ф а .

Получили противоречие. Значит, в этом случае М = 2 < п .

2. М1 г (Р )= {Л }. Здесь, как и выше, из утверждений 1 и 7 получим, что М может содержать слова лишь из Р(у —» П ) при некотором одном зна­

428

чении г е [1 у ]. В последнем случае, согласно утверждению 2, Р —РхаР2, и М состоит из слов РХР2, РХЪР2, Ь ^ а , ю есть М - Р -система типа (Ь).

3. М I е ( Р ) = 0 для всех г	. Здесь согласно утверждению 7
возможны два подслучая.
3.1 Р(г —» П)1 М = 0 для всех / « [ и ] . Тогда в силу утверждения 6
М € Р(у >1П ) для некоторого у е [0,(]	и значит, М есть Р -система типа (а).

3.2 Существует единственное значение I , при котором

Р(г —>Г2)1 М Ф 0 . Если М с Р(г —> О ), то \М\ <п . В противном случае

согласно утверждению 6 существует единственное значение у е[0у] такое,

что М I Р (у > 1 0 )* 0	. Тогда согласно утверждению 5 справедливо представ­
ление Р = РХЪР2, и М	может содержать лишь слова вида РхаР2, РхаЪР2 или

РхаР2, РхЬаР2, а Ф Ь . Так как при различных а, Ъ, с

/3(Р хаЬР2,РхсР2) = 2,

М не может содержать более двух слов, и поэтому \М\ < п . Лемма доказана. ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ 6. Из теоремы 5 следует, что

0 ( П , р )I С ( П , е ) ^ С ( П , / 3 ) .

Докажем обратное включение. Пусть <р е С(61,/3 ). Так как (р инъек-

тивно и не увеличивает значений функций (3 , то (р любую Р -систему слов

переводит в (р{ Р ) -систему для любого Р е П*. В частности, максимальные

Р -системы типов (а) и (Ь) переводится отображением <р в (р{ Р ) -системы ти­

пов (а) и (Ь).

Докажем, что Р -система типа (а) может отображаться лишь в <р{ Р ) -

систему типа (а) для любого слова Р .

Допустим, что для некоторого слова Р некоторая его Р -система М типа (а) отображается в <р(Р) -систему типа (Ъ). Тогда

Р = Р ХР2, М = {р ха1Р2Л е[1,л]}, <р(Р)= б,ат0 2,

<р(М) = {<2х0,2)ч{(2ха1<22. г е[1,л],/ Ф т}

и для фиксированного к е[1,и]

<Р(Р\акРг ) = в 1 @2 » <Р( РхаА ) - б А й г »* б[1,л], г * Ъ• 4

Заметим, что в последнем равенстве при изменении ах буква Ьх принимает все значения из Г2\ {ат} . Рассмотрим еще РхагР2- систему типа (а)

	429
М' = {р 1ага1Р2:г в[1,п]}
при фиксированном г е[1,л]	г Ф к . Для нее возможны два случая.
В первом случае ^ М	) есть (р( Р1агР2 ) -система типа (а). Тогда

62 = й ' 0-г » <Р(р^ га1Р2 ) = 0 А б 2' с,б 2" , * б [ 1,и]

ИЛИ

й=й'е,".*ч4вл4)=а'с,а"*,й,*е[1,в]

вобоих вариантах имеем противоречие с определением (р, поскольку

0 ( р1анрг ’ агакр2 )= 1>0(<Р(Р\аьРг ) М р^ ганР2 )) = 2.

Во втором случае (р{М ) есть <у>( Р, агР2 ) -система типа (Ь). Тогда в

силу симметрии можно считать, что с()" и при некотором фиксиро­

ванном 5 € [ 1 ,л]

^ 1 я л /> ) = (?,'2," 6гд 2, <р(Рхага] Р2 ) = ( ) х' с Д " Ь г()2, у е[1,я],

] ф в, с] Ф с.

Докажем, что к = в . Допустим, что это не так. Тогда из условия

& ( а г а н Р 2 > Р \ а ь Р 2 ) = 1

получаем, что

Отсюда точно так же, как в доказательстве утверждения 2 леммы 5, из

условия () ( А, В) = 1 получим, что Ьг —с и ОС' —ск при некотором к еЫ 0.

Используя эти равенства, приходим к соотношениям

<р( Р1ага$Р2) = 0 Хс с 0 2, <р( Рх(I/,Р2 ) = 0\ сс 0 2,

противоречащим инъективности <р. Таким образом, к = вФ г ив силу условия

п > 3 найдется у е[1,и ], у Ф к ,в,г. Тогда

^ ( Р 1а,.Р2,Р1ага1Р2) = 1 ,

Д ( ^ ^ а уР2),Р1агауР2) = ^ ( а ^ е / ' 6Д , е / с , . б 1м^ 2 ) = 2

что противоречит инъективности (р.

Итак, во всех логически возможных случаях наше допущение ведет к противоречию. Значит (р переводит Р-системы типа (а) в <р(Р) -системы типа

(а) и Р -системы типа (Ь) в <р( Р) -системы типа (Ъ) для любого слова Р е П*. Теперь, используя этот факт, покажем, что (р( Р ) € 0 ( 0 , е ) . Пусть для некоторых слов Р,(?еП * выполнено соотношение Ре<2, то есть Р , О, име­

ют вид

430

Р = РхаР2, <2 = РХР2

при некоторых Рх,Р2 еГ2*, а е О . Рассмотрим Р -систему типа (Ь)

По доказанному (р переводит ее в <р(Р) систему типа (Ь). Это означа­ ет, что<р(Р) = К = КХЬК2> <Р( М ) = {КхК2} 1^/?, Ъ]К2: Ф б|

Если при этом (р( РХР2) Ф КХК2, то

<р(К Р2) = К ЬЛ ’ <Р( Р\ а, Р2) = К1К2

при некоторых Ъ5 Ф Ъ, а аг Ф а .

Отсюда, учитывая, что <р(РхагР2) = КХЪК2, получаем, что (р перево­

дит РХР2-систему | Рха1Р2. а 1 е О | типа (а) в <р(РхР2) -систему типа (Ь). Полу­ ченное противоречие доказывает, что <р(РхР2) - КХК2, то есть (р{ О) = КХК2.

Следовательно, верно соотношение <р(Р)еф( ( ) ) , и поэтому <р е 0 ( 0 , е) .

Отсюда и из предложения 2 следует, в частности, что (р удовлетворяет

условию (2). А так как на словах одной длины функция () совпадает с р , то ~

(р е О ( 0 , р ) . Таким образом, (р е0(О ,/э)П С г(П ,^), и теорема доказана.

Замечание 1. В практических приложениях криптографии представляет интерес рассмотрение биективных отображений конечного множества

О0 ЦЮ.. в себя, не распространяющих искажений.

Из доказательств приведенных утверждений легко видеть, что и в этом случае вид таких отображений остается таким же (см. параграф 7.3).

Параграф 7.6 Основные понятия сетей засекреченной связи. Ком­

прометация абонентов

Под сетью засекреченной связи, далее более коротко, под сетью связи (СС) подразумевают совокупность объектов: шифр, используемый в сети, мно­ жество А абонентов сети, правила (протоколы) распределения ключей шифра между абонентами сети, правила (протоколы) вхождения в связь, протоколы восстановления СС после компрометации абонентов, протоколы синхрониза­ ции шифраторов в СС.