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

301

вектора (х( 1),...,х(]2)) - такие, что начальный подвектор (х(1),.. .,х(]])) является

решением первого уравнения и т.д.

В п р е д п о л о ж е н и и , ч т о ч и с л о р е ш е н и й к а ж д о г о у р а в н е н и я с о с т а в л я е т в

среднем п о л о в и н у о п р о б у е м ы х в е к т о р о в	(т о е с т ь		п о л о в и н а о п р о б у е м ы х в е к т о ­
ров к а ж д о го у р а в н е н и я с о с т а в л я е т м н о ж е с т в о		е г о	р е ш е н и й ), т р у д о е м к о с т ь д а н ­
ного м е т о д а (в о п р о б о в а н и я х ) с о с т а в л я е т	( 2 ^	+ 2-*2-1 + 2 " - 2 + ... ) .

Алгоритм приведения произвольной системы нелинейных уравнений надполем Р2

Г|(х(1),...,х(п))=у,, ) е 1, ш

к трапецеидальному виду относится к алгоритмам частичного перебора функ­

ций 0 1, т и является достаточно очевидным и трудно формализуемым.

Трудоемкость приведения системы к трапецеидальному виду Оценивается ве­ личиной ш2п.

Нахождение решений системы нелинейных уравнений специально­ го вида методом встречных атак.

Рассмотрим некоторый класс систем уравнений, нахождение решений которых проводится с использованием идей согласования (встречных атак). Пусть система уравнений имеет вид

ф](х(1),...,х(г),х(Н-1),..., х(г+у))+^(х( 1),...,х(г),х(г+у+1),..., х(п))=0,)е 1,щ ,

где <р] и ,) е 1, т - двоичные функции, “+” - в поле Р2. Требуется найти все решения данной системы уравнений. Предлагается следующий алгоритм нахо­ ждения всех решений.

Проводится перебор всех двоичных векторов е=81,е2,...ег. Для каждого фиксированного набора е=81,е2,..;ег выполняется процедура: для каждого набо­

ра бн-ь.-.Д+уб вычисляются значения 9^81,е2,...ег ,5г+ь..., б,+у)=а; и по адре­

су аь...,ат записывают набор 5=8г+|,..., 8,+у в память П. После заполнения памя­ ти элементами из Р \ >для каждого набора у=Уг+у+1>-..,у„еР2~г_у вычисляют значения 9/ 81,..., ег,уг+у.ц,..., у„)=Ь| и по адресу Ь1,... ,Ьт обращаются в память П. Вариант 8, 8',у, где 8'=8'г,,..,5'ц.у набор, содержащийся в П по адресу Ь1,...,Ьт, является решением рассматриваемой системы.

Объем адресной части памяти есть 2тш бит, а число наборов б, записы­

ваемых в память П, есть 2У, поэтому необходимый объем памяти не превосхо­ дит величины 2тт + 2'у бит.

Пусть С - трудоемкость вычисления значения функции ф] или на фиксированном наборе переменных. Тогда трудоемкость вычисления функций

302

равна величине 2г(тС2у+тС2п'у'г). Число обращений к памяти равно величине 2Г(2У+2П‘У'Г), поэтому общая трудоемкость метода есть

Т= тС(2у+г+2п'у)+2у+г+2п'у. Надежность метода равна единице.

Метод решения системы нелинейных уравнений над полем Гг? ос­ нованный на линеаризации путем введения новых переменных.

Пусть задана система нелиненых уравнений над полем Р2.

Г,( х ( 1 х ( п ) ) = у , Г2( х ( 1 х ( п ) ) = у 2

,Гт( х ( 1 х ( п ) ) = у т относительно двоичных переменных х(1),...,х(п). Предполагается, что функции

Г|(х(1),...,х(п)), )€ 1,шзаданы в виде полиномов Жегалкина.

Метод решения системы уравнений заключается в замене каждого не­ линейного члена х(11)х(12)...х(1к) на новое неизвестное 11(1112.. лк) и решении по­

лучившейся линейной системы уравнений относительно новых переменных, с последующим нахождением решений первоначальной системы путем решения систем специального вида х(11)х(12)...х(1к)= 11(1112.. лк) для каждого решения {11(1112.. .1К)} линейной системы.

Если степень нелинейности каждого уравнения не превосходит величи­ ны г, то число переменных полученной системы линейных уравнений не пре­

восходит величины Кп,г =С п +С п +.. -+С п - Так как трудоемкость нахождения решений такой системы линейных уравнений (если пользоваться алгоритмом Гаусса) оценивается величиной 0(КП,Г)3, то, пренебрегая трудоемкостью реше­ ния указанных систем специального вида, трудоемкость метода оценивают ве­

личиной 0(КП,Г)3.

У

Метод решения системы нелинейных уравнений над полем Г2, ос­ нованный на линеаризации путем опробования части неизвестных.

Пусть дана система нелинейных уравнений над полем Р2, левые части которых записаны в виде полиномов Жегалкина

р1(х(1),...,х(п))=у, Ъ ( х ( 1 х(п))=у2

Гт(х(1х(п))=уш .

Алгоритм определения всех решений рассматриваемой системы состоит в следующем. Находят минимальное число V - такое, что существует набор пе-

303

ременных Ху={х(1]),...,х(1у)}, 1,п е 1, V, что для любого набора Ь|,Ь2)...,ЬуеР 2 при фиксации переменных

Х(11)=Ь1,Х(12)=Ь2,...,Х(1У)=ЬУ указанная система становится линейной. Полученную систему линейных урав­

нений (при каждой фиксации переменных х ( ц х ( 1 у)) решают одним из из­ вестных способов (например, методом Гаусса).

Пусть Му - трудоемкость нахождения искомых номеров ц,..,,1У, С - тру­

доемкость получения из системы нелинейных уравнений системы линейных уравнений указанным способом задания значений фиксированных переменных, М(л) - трудоемкость решения получившейся системы линейных уравнений. Тогда трудоемкость данного метода есть МУ+(С+ М(л))2у.

Основной интерес для оценки сложности реализации данного алгорит­ ма представляют оценки величин V и Му. Для и х нахождения решают некото­

рые специальные задачи из теории графов.

Метод решения системы нелинейных уравнений над полем Г2, ос­ нованный на линеаризации с помощью редкого события.

Рассмотрим еще один алгоритм решения системы нелинейных уравне­ ний над полем Р2, левые части которых заданы в виде многочленов Жегалкина:

Т,(х(1),...,х(п))=у! Г2( х ( 1 х ( п ) ) = у 2

Гт(х(1),...,х(п))=ут.

Предполагается, что данная система имеет единственное решение. Находят минимальное число V, при котором существуют наборы

х(1]),.. .,х(1у) и Ь],Ь2,..,,ЪуеР 2 - такие, что при фиксации

Х ( 1 1) = Ъ 1 , . . . ,Х (1У) = ЪУ

каждая конъюнкция ранга больше единицы рассматриваемой системы уравне­ ний становится конъюнкцией ранга не более чем единица. Полученную таким образом систему уже линейных уравнений решают одним из известных мето­ дов.

Трудоемкость указанного метода решения системы нелинейных урав­ нений слагается из трудоемкостей: 1) Му - нахождения необходимых наборов х(11) , . . . , х ( 1у) и ЬьЬ2,...,Ьу; 2 ) трудоемкости построения линейной системы урав­

нений указанным способом; 3) трудоемкости нахождения решения этой линей­ ной системы уравнений, либо установления факта ее несовместности.

304

Если считать, что единственным решением исходной системы нелиней­ ных уравнений априори может быть с одинаковой вероятностью любой вектор

из Р ” , то надежность (вероятность нахождения решения) данного метода

1 есть — .

2У Основной интерес представляют попытки получения оценок для Му,

которые ранее проводились в случае специального выбора 1>1,Ъ2,...,ЬУ а именно Ь1=0, Ь2=0,..., Ьу=0.

В этом случае нахождение искомых номеров ц,...,1Уи даже значения V (естест­ венно минимального значения) сводятся, соответственно, к задаче нахождения наименьшего покрытия множества его подмножествами и задаче определения поперечника наименьшего покрытия гиперграфа.

Удачно подобранные примеры применения аналитйческих методов криптоанализа и расчета их трудоемкости содержатся книге Грушо А.А., Тимониной Е.Е., Применко Э.А. «Анализ и синтез криптоалгоритмов», 2000 г., 108 стр.

ГЛАВА 6. ВОПРОСЫ СИНТЕЗА ШИФРОВ И ИХ КРИПТОСХЕМ

Параграф 6.1 Шифры, близкие к совершенным

Пусть А=А1-А2=(ХьК1хК2,У2,1) - произведение шифров А1=(Х1,К1,У1,^) А2=(Х2,К2У2,Г2), У,=Х2 (см. параграф 1.3). Исходя из опреде­ ления совершенности шифра:

р(х/у)=р(х) при любых х, у, несложно доказывается следующее

УТВЕРЖДЕНИЕ. Шифр А=А|-А2=(ХьК1хК2,У2,1) является совершеным, если таковым является хотя бы один из сомножителей.

Произведение шифров, не являющихся совершенными может дать шифр «близкий» к совершенному шифру.

Действительно, пусть (Х,К,У,1) - шифр модульного гаммирования (Х=У) и распределение вероятностей Р(К)=(р(х), Xе К) такое, что р(%)>0, для каждого К. Тогда квадратная матрица условных вероятностей М =||р(у/х)||

являетсядважды стохастической и, следовательно, как известно из курса ал­ гебры существует предел

Г1	.1	.	1Л
1 .		.	1
Н щ м к = 1
I X |
',1	•	•	К

В частности, к-тая степень (Х,К,У,1)Кшифра представляет собой шифр, пере­ ходные вероятности которого стремятся к величине 1/||Х| при к—>ос, то есть шифр (Х,К,У,1)Кблизок к совершенному шифру при достаточно большом к.

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

Пусть Х= {0,1,... ,п-1}. Обозначим через Т= подстановку сдвига

У + 1

из симметрической группы подстановок 8„; наряду с Т будем рассматривать и ее степени Т“(|), в частности, единичную подстановку Е. Рассмотрим ш эндо­ морфных шифров Ак=(Х,П(Кк,Г,с), ке 0, ш - 1 , где П(Кк,Гк)=Пк={Е, Т'а(к)}. На множестве Пк ключей - подстановок задано вероятностное распределение

Р(Пк)=(рк(Е), Рк(Т'а(к))), рк(Е)+рк(Т'а(к))= 1.

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

1)|Х|=2‘, 1 - натуральное число;

2)т>1;

3)среди шифров Ак имеется I сомножителей А^;}, для которых а К0=Р.К0'2'>16 О, I 1, Рдо - нечетные числа;

4)для чисел Д1) из 3) выполняются равенства

. Рко(Е)=рКо(ТаК1))=1/2, 1б 0,1 -1 . ДОКАЗАТЕЛЬСТВО. Докажем сначала необходимость условий 1)-4).

Предварительно сформулируем и докажем вспомогательную лемму.

Лемма. Если шифр А совершенный, то |К|=|Х| и индуцированное, веро­ ятностными распределениями Р(ПК) на ключах шифров АК, вероятностное рас­ пределение Р(К) на ключах шифра А является равномерным.

ДОКАЗАТЕЛЬСТВО. Так как А - совершенный шифр, то он транзи­ тивный, поэтому |К|>|Х|. С другой стороны, множество его ключей П(К,1) явля­

306

ется подмножеством в группе <Т> подстановок, порожденной подстановкой Т. Поэтому |К|<|Х|. Следовательно, |К|=|Х|. Откуда следует, что П(К,1)=<Т>.

Покажем теперь, что р(х)=1/|П(К,!)|, для любого х^К. Имеем Р(у/х)= X Р(Х ) >0>УеУ >хеХ >(х = у )

Х :Х Х = У

и, в силу транзитивности А и равенства |К|=|Х|, существует единственный ключ Х=Х(Х):ХХ=У- Откуда: р(у/х)=р(х(х)). С другой стороны,

Х р (у 7*) = Е р (у ) Н х I р(у)-

X X

Следовательно,

2>(У/Х) = 5]Р(Х(Х)) = Н х 1р(уХ

X X

поэтому р(у/х)= р(х(х))=р(у)=1/|Х|= 1/|К|, что и требовалось доказать. Покажем теперь необходимость условия 1): |Х|=2*.

Любой элемент 7геП(К,Г) имеет вид Т'т, где у - определяется значением

случайной величины <^(т), представляющей собой сумму независимых случай­ ных величин

Рзу	-Р.
----------
где р)= р/Т""^),3€ 0 ,т - 1 . Это следует из того, что	...ят.ь где щ=Т >.

Пусть Р(^(ш))=(р(0),р(1),...,р(|Х|-1)) распределение вероятностей случайной

величины Ранее мы показали, что при любом 0, т —1

Р(0=1/|Х|.

Используем это равенство для доказательства того, что |Х|=2*. Введем аппарат характеристических чисел величины

ш '	V	2 л к у	. . 2 к к у
^ОНь+Р^к , где ек =соз			-Наш-—
		I X |	IX |
Напомним, что если Г(х)=Ме,х^ - характеристическая функция случай-
ной величины 2,, то ее значение Р(	2ттк	) называется к-ым характеристическим

I х I

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

307

т-1

ям - т о о -

]=°

2кк

Полагая в последней сумме х=

получаем формулу для к-того характери-

I X |

стического числа Ик:

| Х | - 1

Мк=Ык(0>...-Кк(ш-1)= Х рО К ' ]=0

Выразим для фиксированного г вероятность р(г) из предыдущего равенства че­

резЫк, К€ 0, | X | -1 . Для этого умножим это равенство на е~г и просуммируем

по ке 0,| X | —1. В левой части равенства получим 1X1-1 1X1-1

2 > ; Х = ^ ' н 0+ 2 х гм в ,

к = 0 к = 1

а в правой части получим

|Х [ — 1	(И-1	. ^ 1 Х |- 1
Е е к г	Е р	С ) ) е3к	= Е
к = 0	1-•IIО	V	к = б
1X 1 -1	| Х \ —1		( | Х | - 1

= Ер(г)+ Е р0) 2 ^

к = 0 1 = 0 V к = 0

	|Х | - 1
е к г	р С Ф к + Е р ^ ' ) е к
^	1 = 0
	У
. '
г	= р ( г ) | Х | .
у

	) * Г
В итоге получаем
.	1X 1 -1
1+	Е	^ ГМК=р(т)|Х|:
Откуда	к=1
Р(Г)=		1.+	2 ,	Г
	IX! V		к=1

Из этого равенства заключаем, что из условия р(г)=1/|Х| вытекает

'рд-1	Л
2 ч Ч	=0.

V к=1

308

Следовательно наша задача свелась к доказательству того, что из ра­

венств

'к м

I е кгн к =0, те 1,| X | -1

к=1

вытекает |Х|=2‘.

Рассмотрим предыдущие равенства как систему линейных уравнений относительно величин 1МК. Определитель этой системы равен

А=81 182'1...Е|Х|-1 'А',

где А' - определитель Ванндермонда:

1	1	.1	1
еГ1	821	•	Р-1
			|Х|—1
А'=			* 0.
р-(|Х|-2)	Р'-(|Х|-2)	•	Р—(|Х|—2)
1	2		|Х|—1

Отсюда следует, что рассматриваемая система линейных уравнение относи-

. тельно величин Ик имеет единственное решение:

N 1= N 2= —

| Х [ - 1 =0.

Выясним, чему равносильна данная цепочка равенств. Из того, что

К =Ы к(0)-... -Ык(ш-1)=0 следует, что для некоторогол

Нк(])=0.

Рассмотрим модуль комплексного числа 1ЯК(]). По определению

,„т ,-ч, ,

2тпс .

. 2тис

,

^к0)МЧ)+РЯО8-— 0(4- 1Р]81П— -<Х}|=

I "X |

|Л |

I/

2дк

ч2

2 - 2

2 п к

а г

а Р + Р ^ ш

щ

=

1 2

2

2 2лк

7

2 л к

2

• 2

2дк

/О ;+р ; С08

----- а : + 2 р : а =С08------- ОС: + р : 31П

(X: =

у

}

3

IXI

••

\Х \

}.

}

IXI -1

1 2

2

Л

2як

Г Г

~

2тск

Г

= ЛЧ з+Рл + 2 р ^

соз—

а.} = 1 1 - 2 р ^ ( 1 - соз—

с^) =

/1

л

.

2

ЛК

“ 1| 1-

4Р Л 81П

	309
Если	то р^^^<1/4, и поэтому
	7ИС
	Кк0)>|еоз— -о ^ |>0.
	I -л-1

Значит К кф =0 лишь в случае, когда р]=<^=1/2, при этом из последнего равенст­ вадля Ык(]) получаем

		7 С К	'
	|Нсб)Мсо8—		о^|=0,
откуда		I Л I
	71К	К п
	1X1	< Ч = т Р г
		’ ■2
где Рз - некоторое нечетное число. Тогда
4 •		2к а :
	|Х|=------

Р|

Пусть I- максимальная степень числа 2, при которой 2* делит число

|Х|: |Х|=2'р0, где Ро - нечетное число. Тогда
' .	IXI	Р,	РоР,
^	2	к	к

Покажем, что Р<»=1. В самом деле, если р0=2+у>3, то

	э д - ^ г 'р о - ^ '^ + у и ^ 1.
Номера к в N«(0 изменяются в пределах от 0 до |Х|-1.. При к=21+| (что меньше
IV! 4	^
|Х|-1)	из последнего равенства для получаем с^=—- — . Это не целое число,

тоесть получили противоречие, означающее, что Ро=1, откуда получаем |Х|=2*.

Необходимость условия 1) доказана.

Для доказательства остальных условий теоремы вернемся к анализу

полученных ранее условий:

N«=N„(0).... -М(т-1)=0.

Разобьем множество {1ЧК, ке 0,| X | —1} на непересекающиеся подмно­ жества: О0,...,О,.„ где Оу={Мк, к=2уиу, иу - нечетное число}.

Покажем, что если аргумент с^, зе 0, ш - 1 обнуляет элементы одного

из множеств 0 У, то этот аргумент не обнуляет ни один элемент из О^ , уфу'. Тем самым, для того чтобы обнулить по одному элементу из каждого Оуи, таким образом, добиться выполнения равенств: Кк= КЦО)-... -]Мк(т-1)=0, необходимо условие т>1.

Итак, ранее было доказано, что

				)
					310
				?1-1	РоРз
				а,= 2	--------- ир0=1,
то есть					к
				<^=21-1	.
					К
Если к=2гиг (т.е. ЫкеОг), то о^=2*‘г‘1и^, где						- нечетно. Такой аргумент обра­
щает в ноль лишь Ог. В самом деле, если т ф т \						то из ранее полученного равенст-
7ГК	71 п
ва	а := — р : следует
| X	| 3 2 И ]
	71К		712	_ +_р_|	,	Л	Л	71
		(Х;=-----------— 2 г и \ =				7г2 г Аи г и	\Ф — и ,
	| Х |	3	2 1		^		3	2

и поэтому N ^0 при ЫкеОГ'. Таким образом, необходимость условия 2) доказа­ на. Необходимость условий 3) и 4) бала получена попутно (из равенства 1^к0)|=0 и определения множеств Оу) .

Доказательство достаточности условий 1)-4) можно получить, просле­ живая проведенные рассуждения в обратную сторону.

Развитие и обобщение данной теоремы содержится в статье Б.В. Ряза­ нова, Т.П. Шанкина «Критерий равномерности распределения суммы незави­ симых случайных величин на примарной циклической группе». Дискретная математика. Т. 9, еРы п . 1, 1997, стр 95-102.

Параграф 6.2 Гомоморфизмы и конгруэнции шифров

Ряд методов криптоанализа шифров основан на наличии гомоморфного образа изучаемого шифра. С точки зрения синтеза шифров представляют инте­ рес шифры, не имеющие нетривиальных гомоморфных образов.

Понятие гомоморфизма алгебраической модели шифра сводится к по­ нятию гомоморфизма произвольной алгебры. Рассмотрим сначала частное по­ нятие гомоморфизма шифров по ключам.

Пусть имеются две алгебры А=(Х,К,У,1), А'=(Х, К ',У, Г). Отображение ф: К->К' со свойством: при любых хеХ , у е К

Г(х,Х)=Г(х,фх)

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