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

311

зывают образом А при гомоморфизме ср. Если ф - биекция, то ф называют изо­ морфизмом алгебр А, А' по множеству К.

Очевидно, что если А - шифр, и ф - гомоморфизм шифра по К, то классы эквивалентных ключей шифра А являются объединением некоторого числа прообразов отображения ф.

Ниже нам необходимо рассматривать бинарное отношение эквива­ лентности е на К (т. е. бинарное отношение на К со свойствами рефлексивно­ сти, симметричности, и транзитивности). Факт того, что элементы %, %' нахо­ дятся в отношении е, будем записывать в виде Напомним, что любое от­ ношение эквивалентности на множестве К задает разбиение этого множества, то есть задает совокупность попарно непересекающихся подмножеств (бло­ ков) множества К, объединение которых дает К. Обратно, любое разбиение множества К задает бинарное отношение эквивалентности (элементы, лежащие водном блоке разбиения, эквивалентны).

К онгруэн цией на м нож ест ве К алгебры А называют бинарное отноше­ ние эквивалентности 8 на К, согласованное с операцией Г, то есть из условия щ ' для некоторых %,%'е К следует Нх,х)= Г(х,х') при любом хе’Х ,

Совокупность блоков К), Кг,..., Кь отношения эквивалентности е (конгруэнции с) наК называют ф акт орм нож ест вом и обозначают через К/е.

Ф акт оралгеброй алгебры А=(Х,К,У,1) по конгруэнции 8 на К называют алгебру А/8=(Х,К/е,У,0, где ^ХхК/е-УУ, именно, для хеХ : 1е(х,^)=у, 1б{1,...,Ь}, если при х е ^ Г(х,х)=у.

Гомоморфизм ф алгебры А на А ' индуцирует конгруэнцию еф на К, именно х^фХг тогда и только тогда, если эти элементы одновременно принад­ лежат некоторому прообразу ф''(х ), X е К \ Обратно, для любой конгруэнции 8 на К алгебры А строится отображение фе: К—»К/е, именно фе х)= К), если х*=К^ Легко проверяется, что фе - гомоморфизм А на А/е=(Х,К/е,У,С) по множеству К. При этом, конгруэнция на К, соответствующая гомоморфизму фе, совпадает с конгруэнцией е. Гомоморфизм фе алгебры А на факторалгебру А/б=(Х, К/е, У, 0 по множеству К называют естественным гомоморфизмом.

Очевидно, что при гомоморфизме ф алгебры А на А' факторалгебра А/е<р изоморфна алгебре А ' при изоморфизме Ф '(х И * Х >X ^ К ' (ф''(х') - класс эквивалентности бинарного отношения эквивалентности 8ф).

В общем случае под гомоморфизмом алгебр А=(Х,К,У,1), А '=(Х', К',У', Г) понимают тройку отображений Т=(\|/,ф,г|), соответственно X —»Х', К->К',У-УУ' со свойством: Г(ф(х),фх)= г|(Г(х,х)), хеХ , х^К.

Это свойство обычно записывают в виде коммутативной диаграммы:

312

у 4- 4кр	4гг)
	— ►
Х 'хК '	У'
	г

При сюрьективных отображениях тройку (ф,ф,г|) называют гомомор­ физмом А на А ' (в противном случае - гомоморфизм А в А'). Если отображе­ ния биективны, то говорят, что А и А' изоморфны.

В общем случае конгруэнцией алгебры А называют тройку бинарных отношений эквивалентностей (С,,е&) определенных, соответственно, на X, КД согласованных с операцией {, то есть из соотношений

Х,^х2, Х1БХ2

следует

Г(Х1,Х0 ^ Г(х2,Х 2).

Аналогично тому как ранее было введено фактормножество К/е, вво­ дятся фактормножества Х/С, , У/% и факторалгебра

А/(С е,^)=(Х/С К/е,У/$,&*).

Гомоморфизму (\|/,ф,г)) алгебры А на А' соответствует конгруэнция (^у,8ф,^п), для которой факторалгебра А/(^У,8Ф,^П) изоморфна алгебре А '. Ана­ логично тому как это сделано ранее для гомоморфизма ф, строится естествен­ ный гомоморфизм алгебры А на А/(^Ч,,8Ф,^,1).

Отметим, частный случай гомоморфизма алгебры А=(Х,К,У,1) на ал­ гебру А=(Х,К,У',Г) - гомоморфизм вида (Е,Е,Ф), где Ф :У —>У', Е - тождест­ венное отображение.

Все возможные гомоморфизмы и соответсвующие им гомоморфные об­ разы алгебры А=(Х,К,У,1) можно получить следующим образом.

Зададим на множествах X, К произвольные разбиения К* и К.к. Им от­ вечают бинарные отношения эквивалентности С,, е. Определим на У бинарное отношение эквивалентности 2, положив: у^уг, если найдутся Х],х2еХ , ХьХг6^ для которых

Х |^ Х 2 ,

Х16Х2, ®(Х1,Х1)=У15

®[Х2,Х2)=У2-

Легко проверяется, что (.^,е,%) - конгруэнция на алгебре А. Строя по этой кон­ груэнции естественный гомоморфизм (ф^,фе,Г1^) и соответсвующую факторалгебру А/(^,е,^), м ы получаем гомоморфный образ Г(К.хДк)-А/(^,е,&,) алгебрыА

313

Теперь несложно доказывается, что любой гомоморфный образ алгебры А (с точностью до изоморфизма) является гомоморфным образом при гомоморфиз­ ме вида (Е,Е,Ф) некоторой факторалгебры Г(ИхДк)=А/(^,е,^).

ЗАМЕЧАНИЕ. Как правило, шифр реализуется некоторым шифрато­ ром. Если функционирование этого шифратора моделируется конечным авто­ матом, то представляет интерес описание его (автомата) гомоморфных образов. Решение этой задачи широко известно, оно содержится во многих книгах по теории автоматов. Одно из обобщений понятия гомоморфизма шифра заключа­ ется в следующем. Пусть на множествах X, К заданы вероятностные распреде­ ления. Тогда для шифров А=(Х,К,У,1), А'=(Х',К',У',Г) и тройки отображений Т=(\|/,Ф,г|): ф:Х—>Х', ср:К—»К', г|:У—»У' при случайном выборе (х,х)еХхК опре­ делена вероятность события: Г(у|/(х),ф%)= г|(Г(х,х)). Тройку отображений с максимальной вероятностью иногда называют наилучшим вероятностным го­ моморфизмом шифра.

Параграф 6.3 Групповые шифры. Обратимые групповые шифры

Групповые минимальные шифры.' Ниже нам потребуется так называемое табличное задание шифра

А=(Х,К,У,1). Это таблица размера |Х|х|К|

•

У (А )= Х

столбцы которой пронумерованы элементами х из X, а строки - элементами % из К. На пересечении столбца с номером х и строки с номером х стоит элемент у=Г(х,х) из У. Отметим некоторые свойства табличного задания шифра:

1) в У(А) нет пустых строк;

2)объединение всех Г(х,х) дает У;

3)каждая строка таблицы не содержит одинаковых элементов.

Если шифр А транзитивен, то, очевидно, |Х|<|У|<|К|.

Шифр А=(Х,К,У,1) называют минимальным шифром, если он транзи­ тивен и |Х|=|У|=|К|.

314

Напомним, что эндоморфными шифрами называются шифры А=(Х,К,У,1), у которых Х=У. Для таких шифров ранее нами вводилась подста­ новочная модель эндоморфного шифра А - обозначение А=(Х, П(К,1)), где П(К,1)={ГХ: Xе К} - множество всех биекций X в X шифра-А. Уравнение шиф­ рования записывалось в виде: ях=у, я - ключ шифра - взаимно однозначное преобразование множества X, яеП(К,Г). Уравнение расшифрования записыва­ лось в виде: я''у=х.

Если множество П(К,1) подстановок на X является смежным классом по некоторой подгруппе в симметрической группе 3(Х) подстановок на множестве X, то эндоморфный шифр А=(Х, П(К,1)) называется групповым (по К. Шенно­ ну - «чистым»).

Для эндоморфного шифра его табличное задание У(А) представляет со­ бой таблицу, строки которой пронумерованы элементами я из П(К,1), а сами строки представляют собой нижние строки подстановок я на X.

Напомним, что латинским квадратом над алфавитом X называют квадратную таблицу размера |Х|х|Х| с элементами из X, такую, что в каждой строке таблицы и в каждом столбце таблицы нет одинаковых элементов, то есть каждая строка, как и каждый столбец такой таблицы, представляет собой нижнию строку некоторой подстановки на X.

Напомним, что квазигруппой (X,*) называют множество X с операци­

ей • для которых уравнение х*х'=х” однозначно разрешимо: 1) относительно х' при любой фиксации хи х" из X; 2) однозначно разрешимо относительно х при любой фиксации х' и х” из X. Таким образом, любая квазигруппа на X может быть задана некоторым отображением Р: ХхХ->Х, инъективным по ка­ ждой переменной, либо латинским квадратом, на пересечении строки с номе­ ром х и столбца с номером х' которого стоит элемент х*х'=х”=Р(х,х'). В свою очередь, каждый латинский квадрат или функция ХхХ—>Х, инъективная по ка­ ждой переменной, задает квазигруппу на X. Частным примером квазигруппы служит группа (X, •) - квазигруппа, где каждый элемент х имеет обратный х 1,

х- х'=Е, ЕеХ, х'еХ, Е - единичный элемент группы X.

Необходимость введения понятий латинского квадрата и квазигруппы диктуется тем, что табличное задание У(А) минимального эндоморфного шиф­ ра, А=(Х, П(К,1)) очевидно, представляет собой латинский квадрат (в силу транзитивности такого шифра) и ему соответствует квазигруппа (X, •).

Именно, пронумеруем подстановки яхеП(К,1): П(К,1)={яь....яп}, п=|Х|=|К|=|П(К,1)| и элементы из X: Х={хь...,хп}.

, х е Х

315

На множестве X определим операцию •, положив х_,«х= ^х. Тогда под­

становка щ может быть записана в виде

X: • X

Пусть (X,*) и (!,♦) квазигруппы. Тройка биекций (а, Р, у) множества X в I называется изотопией квазигруппы (Х,«) в (на) (I, ♦), если у(х«х')=а(х)4Р(х') при любых х, х'еХ.

Теорема. Минимальный эндоморфный шифр А=(Х,П(К,1)) является групповым тогда и только тогда, когда соответствующая ему квазигруппа (X,*) изотопна группе (X,-).

ДОКАЗАТЕЛЬСТВО. Пусть (Х,«) изотопна группе (X, ). Покажем, что П(К,1) - смежный класс по некоторой подгруппе в симметрической группе на

X. Имеем изотопию (а,р,у): у(х^х)=а(хрР(х) и подстановку	х
	. Рас­
, Х : * Х ,
V	1

смотрим суперпозицию я/у отображений Я] и у (на элемент хеХ сначала дейст­

	вуем а затем	у)
	я/у=		Г X ^ Г		X	> Г	X	] ( х ^
								II
				У= чу(х^ • х ), ча ( х ])-р(х);
		'	Р(*)	'	Г	х'	^
		ча(х^)-Р(х)>			= Р		=Рь
					ча (х ) ) ‘х'>
	где §=	х		элемент группы (группы подстановочного пред-
		а(Х:)-х'

ставления группы (X,-)). Откуда получаем Я]=Р§у'|=Р§Р'|ру|. Следовательно, П(К,1)= рор''Ру'‘, где О - некоторая группа подстановок на X. Далее П(К,Г)= рор 'Ру'^О'Ь, где 0'=р0Р'’ - некоторая группа подстановок на X, а Ь=Ру'' - подстановка на X. Таким образом, П(К,1) - смежный класс.

Обратно, пусть Г1(К,1) - смежный класс по некоторой подгруппе О в симметрической группе 5(Х), П(К,1)=ОЬ.

Рассмотрим для группы 0={§1,...,§„} (п=|П(К,1)|=|0|) латинский квад­ рат, строка с номером) которого определяет нижний ряд подстановки

>

			316
8г	О . Для шифра А=(Х,П(К,1)) строка с номером) его латинского квад-
	ЧХГ ХУ		( V
рата определяет подстановку ^=^Ь=
			X ; • X
	Имеем	\
	х		8)00
	бЬ= X: *Х		8 л ( х ) Д Ь ^ ( х» ; (Ь(хг х)

Откуда получаем

х^х=Ь(хух),

или

Ь''(х^х)=х^х

при любых х^хеХ.

Следовательно, тройка биекций (а=Е, Р=Е, у=Ь‘‘) множества X в X (Е- тождественное отображение) осуществляет изотопию квазигруппы (X,*) на

Эндоморфный шифр называется обратимым, если каждая его подста­ новка леП(К,П есть инволюция: л2 =Е (Е-тождественная подстановка).

Напомним, что шифр А=(Х,П(К,1)) называется транзитивным, если для любых х,х' бХ, (х^х') найдется ключ леП(К,1), при котором лх=х\

Групповые, транзитивные, обратимые шифры.

Напомним некоторые необходимые нам понятия из теории конечных групп подстановок.

Пусть О - подгруппа 8(Х), 0<8(Х). Группа подстановок О называется регулярной, если стабилизатор любого элемента хеХ совпадает с единицей «е» группы О, то есть {§: §(х)=х}={е}. Ниже будут использоваться следующие из­ вестные свойства регулярной группы О.

1). Транзитивная группа подстановок О регулярна тогда и только то­ гда, когда |0|=|Х|.

2). Транзитивная, абелева группа подстановок С регулярна.

Лемма. Пусть Н=01, 0<8(Х), 1е8(Х). Если Н - транзитивное множест­ во инволюций, то О - регулярная абелева группа.

ДОКАЗАТЕЛЬСТВО. Так как Н - транзитивное множество подстано­ вок на X, то группа О транзитивна. Для доказательства ее регулярности, со­

317

гласно 2), достаточно доказать ее абелевость. Докажем это. При любых ЬеН и ^еО имеем

Ь=Ь'1, §Ь§Ь=е,

Ь‘‘§ь= §'§ ь§ь=§'.

Следовательно, для В=В1В2» ёь&^О имеем Ь'181&Ь=(81&)'1-й '^ Г 1»

Ь'1§1§2Ь= Ь'1§1ЬЬ'1ё2Ь=ёГ1Е2'1,

„ -I -II. „ -1 -1 §2 §1 ~§1 §2 ,

то есть группа О абелева.

Теорема. Групповой, транзитивный шифр А=(Х,П(К,1) является обра­ тимым тогда и только тогда, если 1) А - минимальный шифр; 2) латинский квадрат, соответствующий табличному заданию шифра, таков, что определяе­ мая им квазигруппа (X, •) изотопна абелевой группе (X, +). Для любых элемен­ тов а,ЪеХ изотопия определяется равенствами а*Ъ=с-(а+Ъ), где с - фиксиро­ ванный элемент из X.

ДОКАЗАТЕЛЬСТВО. Необходимость условий. Шифр А групповой, транзитивный. Положим П(К,1)=ОГ=Н. Шифр обратим. Следовательно, по лем­ ме, О- абелева группа. Она транзитивная группа, так как Н - транзитивное множество подстановок. Тогда (см. свойство 2 перед леммой) |0|=|Х| и поэтому |Н|=|Х|, то есть транзитивный шифр А является минимальным.

Рассмотрим латинский квадрат для группы 0={§ь...,§„}, п=|Х|=|0|. Пусть его строка с номером ) определяет нижний ряд подстановки

; в этой записи мы использовали абелевость группы О. Латинский

квадрат шифра А таков, что его) -тая строка есть нижний ряд подстановки

, при этом Х|«х=1(§|(х)). Шифр А обратимый, то есть

8* 8*=е

при любых)е{1,...,п}. В частности, для тождественной подстановки §=Е, ЕеО имеем 12=Е, откуда получаем

1=Г‘

8* =(80* =*‘ 8* =*8' >

ИЛИ

318

		X; + X		X	«*) '
X: + X		1(Х ^ + X )		Ч1(х)у	- х ] +1(х)
1	У
Следовательно, для любого х € X и любого x^е X
		1( Х | + Х ) = 1 ( Х ) - Х |,
а , в с и л у с и м м е т р и ч н о с т и		в х о ж д е н и я	в р а в е н с т в о		х и Х], п о л у ч а е м и р а в е н с т в о

1(х+^)=1(х])-х.

Так как 1(х;+х)= 1(х+Х]), то

1(х)-Х]= 1 (^ )-х .

Следовательно, 1(х^= 1(х)-Х]+х при любом хеХ. Поэтому 1(х)+х=сопз1=с, сеХ.

И

1(Х])= С-Х|, x ^ € X = { x 1, . . . , x п}.

Возвращаясь к равенству Х).х=1:(§](х)) получаем

Х ].х= 1(а(х))= 1(х]+ х ) = с - ( ^ + х ) .

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

Итак, шифр А групповой минимальный и (X,*) изотопна (Х,+), при этом

'ХрХ = с-(х;+х) при любых х,х;еХ. Надо доказать, что шифр А обратим, то есть

8* 8*=Е при любых{1,...,п}. То есть надо показать, что

	(		\
	X : * Х	, X : * Х	=Е.
			У
	1	У V I

Проверим этот факт непосредственно: х по первой подстановке перейдет в х^х, а х^х по второй подстановке перейдет в х^( х^х). Используем соотношение Х]«х=с-^+х) справедливое при любых х, x^еX. Имеем

Х^(Х^Х)=С-(Х|+ Х]*х)= с-^ + (с-^+х))= с-x^-с+x^+x=x.

Таким образом, при действии подстановки	элемент х€Х перейдет в х, что
и требовалось доказать.

Параграф 6.4( Инварианты шифров

Пусть А=(Х,К,У,1) - шифр, О - некоторый алфавит, а \|/:Х—>0 и г|:У->0 - отображения, при которых при любых хеХ и х^К выполняется равенство

У(х)=т1(Т(х,х)).

319

Такие функции (ц/,г|) (в случае, когда они не являются константами) называют­ ся инвариантом шифра А. Для эндоморфного шифра иногда рассматривают

частный случай инварианта (\|/,г|), именно, случай \|/=г|.

Иногда под инвариантом эндоморфного шифра А понимают и некон­ стантную функцию \|/:УхУ—Ю, обладающую свойством

Ч'(ХХ,Хх)=Ч/(х'х,х'х )

при любых х,х' еХ и х,Х с К.

Инварианты специального типа. Ниже мы укажем путь к описанию

транзитивных эндоморфных шифров, обладающих инвариантом \р, инъектив­ ным по обеим переменным. Для этого приведем один известный результат из теории квазигрупп. Пусть (X,*) - некоторая квазигруппа на X. Подстановка

§е 8(Х) называется средней регулярной подстановкой квазигруппы (X ,*), если найдется подстановка §' еЗ(Х), для которой равенство

§(х)*х'=х*§'(х)

выполняется при любых х,х' еХ. В книге Белоусова В.Д. «Основы теории ква­ зигрупп и луп». Кишенев, 1969 г., в теореме 2.5 доказано утверждение о том, что множество М всех средних регулярных подстановок квазигруппы (X.*) яв­ ляетсягруппой и мощность |М| множества М делит |Х| (|М|||Х|). С помощью

этого результата несложно получается описание эндоморфных транзитивных шифров А=(Х,П(К,1) обладающих инвариантом ц/:УхУ->0

(Ч,(ХХ»ХХ')='1,(Х'Х»Х'Х') ПРИ любых х,х' еХ и	еК) инъективным по обеим
переменным.

Инварианты общего типа. Пусть А=(Х,К,У,1) - шифр. Укажем усло­ вия наличия для шифра А инвариантов общего типа, то есть наличия некон­ стантных функций У|/:Х—Ю и г|:У-»0 (О - некоторый алфавит), при которых при любых х е X и у е К выполняется равенство

у(х)=ц(Г(х,х)).

Введем на множестве X бинарное отношение ст, положив: хах', если найдутся х и х' из К, при которых Г(х,х)= Г(х',х )• Если некоторые функции \р, 11являются инвариантами шифра, то, очевидно, функция принимает одина­

ковые значения нахих'. Пусть а* - транзитивное замыкание бинарного отно­ шения отношения а, то есть Х1<т*хм, если найдутся х2,...,Х м -1 из X, при которых

Х1<тх2а...сгх>мсгхы.

Как известно, а* - будет бинарным отношением эквивалентности на X. Из сказанного выше следует, что функция \|/ инварианта (\р,г|) шифра А посто­ янна на классах бинарного отношения эквивалентности а*.

320

Перейдем к изучению свойств функции г) инварианта (\|/,г|). На множе­ стве У введем бинарное отношение, е положив: уеу', если найдутся х из X и

ключи х, %\ при которых Г(х, у)=у и Г(х,у')=у\ Для инварианта (у,г|) должно очевидно выполняться ч(У)=г1(У )• В связи с чем, функция г| должна принимать одинаковые значения на классах эквивалентности бинарного отношения экви­ валентности е* - транзитивного замыкания бинарного отношения е. Легко по­ казывается, что между фактормножествами Х/а* и У/е* существует биекция т, устанавливаемая с помощью равенства Дх, %)=у. Положим Х/а*={Хь...,Хь}, У/е*={Уь...,Уь}, где т(Х))=У ^е {1,...,Ь}. Произвольные неконстантные функции \р:Х—»0 и грУ—>0 являются инвариантом шифра А=(Х,К,У,1), если они постоянны на соответствующих классах Х^УЛиз Х/о*, У/е* и их значения одинаковы на каждом ] -ом блоке, \|/(х)= т|(у), при х€Х^ уеУ^

ЗАМЕЧАНИЕ. Аналогичным образом вводятся понятие инварианта ав­ томата (шифрующего автомата). При этом инварианты зависят от длины к рас­ сматриваемых входных и выходных слов автомата. Поэтому встает вопрос о существовании минимального к, при котором для заданного автомата сущест­ вует инвариант и проблема о существовании такого к для заданного автомата. Эти проблемы в настоящее время полностью решены одним из авторов посо­ бия. Одно из обобщений понятия инварианта шифра состоит в следующем. На множествах X и К вводится вероятностные распределения. Для заданных функций У|/:Х-Ю и грУ—>0 рассматривается вероятность события: \|/(х)=г|(Дх>х))- Ставится вопрос о нахождении функций, для которых вероят­ ность данного события максимальна.

Параграф 6.5 Введение в вопросы синтеза криптосхем

(

В настоящее время в открытой литературе много внимания уделяется вопросам синтеза и анализа криптосхем. В связи с чем дать полный обзор ти­ повых криптосхем или их блоков в рамках учебного пособия достаточно сложно. Прежде всего отметим, что описание наиболее популярного блочного шифра БЕЗ (Ба1а ЕпсгурПоп ЗШпёагТ) было дано в параграфе 1.4. Там же со­ держатся: описание блочного шифра ГОСТ 28147-89 - российского аналога американского стандарта шифрования БЕЗ; описание современного шифра гаммирования, ориентированного на программную реализацию - Алгоритм К.С-4 (разработка К8А Зесигйу 1псогрогаТес1). Более подробное и прекрасное описание шифров БЕЗ, 1БЕА, Гост28147-89 содержится в книге Ю.В. Роман-