Cryptographic properties of branching of functions of vector spaces.pdf К основным задачам алгебраического анализа криптографических систем отно-сятся разработка методов решения систем алгебраических уравнений (САУ) и оценкавычислительной сложности их решения. Один из приёмов решения состоит в том, чтоот нелинейной САУ можно перейти к решению нескольких линейных систем (СЛАУ)путем фиксации константами нескольких переменных. Этот подход достаточно деталь-но рассмотрен в [1] на примере для разветвлений функций, реализуемых генератором«$-т шагов» и генератором с перемежающимся шагом. Вместе с тем не только ли-неаризация систем уравнений представляет интерес для анализа криптографическихсвойств. Более общий подход заключается в сведении САУ к системам уравнений опре-делённого вида, левая часть которых задает преобразования, имеющие заданный при-знак [2, гл. 9].Представим некоторые результаты исследования разветвлений криптографическихфункций векторных пространств над полем GF(2) на преобразования, имеющие задан-ный признак.При натуральных n, m рассмотрим множество Фп, т всех отображений Vn ^ Vm,n > m, V = {0,1}. Требуется решить нелинейную систему булевых уравненийg ( x b . . . ,xra) = а, (1)где g Е Фп,т и а Е Vm. Пусть функция g ( x i , . . . , xn) задается системой координатныхфункций { g i ( x i , . . . , x n ) , . . . , gm( x i , . . . , x n ) } . Определим умножение булева монома ^ == Xi1 . . . xip степени p на отображение g Е Фг а , т :Ц g ( x i , . . . ,Xn) = {^ gi ( x i , . . . ,Xn), . . . gm(xi, . . . , X n ) } .Обозначим через gO^'''''^ (xfc+ъ . . . , xn) ограничение функции g на множество( а 1 , . . . , а, x^+1,... , xn). Здесь а 1 , . . . , а - фиксированные значения; x&+1, ..., xn - бу-левы переменные. Возможность разветвления функции на подфункции определённоговида вытекает из обобщения теоремы о разложении булевой функции по переменным.Теорема 1. Для любой функции g Е Фга,т выполнено равенствоg ( x 1 , . . . , x „ ) = ф x1 1 . . . x f c f e (xf c + b . . . , x n ) .Итак, функция g : Vn ^ Vm однозначно задана при любом k и всевозможных набо-рах фиксаций переменных x 1 , . . . , x^ множеством подфункций |g(a1,..., а^, xfc+1,..., xn):(а1 , . . . , ak) Е Vk } , реализующих отображения Vra-fc ^ Vm. При таком представленииговорят, что отображение g Е Фга,т разветвляется на отображения gO^'''''^ (xfc+ъ... , xn).Множество решений системы (1) содержится в объединении множеств решений системуравненийg ( a b . . . , a f c , xf c+b . . . , xra) = a. (2)Если g ( a 1 , . . . , afc, x^+1,... , xn) есть линейные преобразования множества Vra-fc ран-га n - k, то каждая из последних систем может быть решена с полиномиальной отn - k сложностью. Принципиальная сложность реализации такого подхода состоитв построении соответствующего разветвления функции g ( x 1 , . . . , xn). Вместе с тем име-ются случаи, когда такое построение практически возможно.Пусть фиксируется k = n - m переменных, без потери для общности считаем, чтофиксируются переменные x 1 , . . . , x n - m , тогда функция g разветвляется на преобразо-вания множества Vm.Определение 1. Степенью разветвления отображения g Е Фг а , т называется чис-ло различных преобразований Vm ^ Vm, полученных при фиксации всевозможныминаборами двоичных констант набора переменных x 1 , . . . , x n - m ; обозначается как ffi(g).Определение 2. Пусть при всех фиксациях набора переменных x 1 , . . . , x n -mфункция g разветвляется только на преобразования, имеющие признак H (линей-ный признак). Тогда набор (x1 , . . . , x n - m ) назовем вполне H-сводящим (вполне ли-неаризующим) функцию g, а число различных преобразований Vm ^ Vm, имеющихпризнак H, полученных при различных фиксациях переменных, назовем степеньюH-разветвления (линейного разветвления) функции g. Эти величины, обозначаемыеffi(g, H) и A(g), определяют число различных систем уравнений вида (2), к которымсводится решение системы (1).Для любой функции g Е Фп^, которая разветвляется только на преобразования,имеющие признак H, справедлива универсальная оценка степени H-разветвления1 ^ ffi(g,H) ^ min(2n-m, |H|).Отметим, что нижние и верхние границы достижимы:1) ffi(g, H) = 1, если функция g при любом опробовании сводится к единственномупреобразованию из множества H;2) ffi(g, H) = 2n - m , если 2 n - m ^ |H| и различны все преобразования из множе-ства H, на которые разветвляется функция g;3) ffi(g) = |H|, если 2 n - m ^ |H| и каждое преобразование из множества H соответ-ствует хотя бы одному опробованию набора переменных x 1 , . . . , x n - m .Для криптографических приложений представляет интерес описание класса функ-ций из Фп,т , для которых оценка степени H-разветвления существенно ниже данныхоценок. В частности, в [1] показано, что при фиксации l переменных, соответствующихзнакам управляющей последовательности, преобразование генерирующих регистровгенератора «$-т шагов» [2, с. 316] и преобразование генератора с перемежающимсяшагом [2, с. 318] имеют степени линейного разветвления, не превышающие l + 1.Представим также другой важный для приложений подход к построению разветв-лений преобразований множества X n , где X - конечное множество.Будем говорить, что преобразование ^ имеет признак H на множестве Y, гдеY С Xn , если найдётся преобразование ф с признаком H, такое, что

Скачать электронную версию публикации