Polynomials over primary residue rings with a small unique distance.pdf Пусть F (x) -унитарный многочлен степени m над кольцом R = Z2n. Через L r (F)будем обозначать множество всех линейных рекуррентных последовательностей над Rс характеристическим многочленом F(x) [1]. Каждой последовательности u из L r (F)сопоставим последовательности u0 ,... ,un - 1 , получающиеся из двоичного разложенияu(i) = u0(i) + 2u1(i) + ... + 2n - 1un - 1 , us(i) G {0,1},s = 0,... ,n - 1; i ^ 0. (1)При правильном выборе многочлена F (x) последовательности us обладают рядом важ-ных для криптографии свойств: большим периодом, высоким рангом, хорошими ча-стотными характеристиками. Одним из наименее изученных параметров является рас-стояние единственности.Определение 1. Назовем расстоянием единственности многочлена F(x) и обо-значим через Ud(F) минимум натуральных чисел l, таких, что для любых двух ре-куррент u,v G L r (F) , u = v, верно соотношениеun-1[0,l - 1] = Vn-1 [0, l - 1];если же таких натуральных l не существует, то будем писать Ud(F) = то.А. А. Нечаевым выдвинутаГипотеза 1. Параметр Ud(F) зависит линейно от величины mn.В настоящее время эта гипотеза не доказана, но и не опровергнута. Первым ша-гом в продвижении этой гипотезы стал результат А. А. Варфоломеева о расстоянииединственности многочлена x2 - x - 1 G Z2n[x] (устные сообщения). В дальнейшемвторому из авторов удалось частично подтвердить гипотезу 1 в случае, когда много-член F(x) G Z4 является трехчленом [2]. В частности, справедливаТеорема 1. Пусть F(x) = xm - x - 1, тогда Ud(F) = 3m.Далее n = 2, R = Z4. Конечность параметра Ud(F) означает, что начальный век-тор u[0,m - 1] последовательности u G (F) однозначно определяется по отрезкуu1[0, Ud(F) - 1]. Обширные вычислительные эксперименты на ЭВМ показали суще-ствование многочленов F(x) G R[x] со свойством Ud(F) = 2m.Для таких многочленов А. А. Нечаевым предложен способ построения подстанов-ки , действующей на множестве T = Z^". В этом случае отрезок u[0,m - 1] од-нозначно задается отрезком u1[0, 2m - 1]. Для каждого t G T зададим последова-тельность u G Lr(F) по правилу u0[0,m - 1] = t, u1[0,m - 1] = 0. В соответствиисо сказанным выше отрезок u1[0, 2m - 1] однозначно определяет начальный векторu[0,m - 1], а значит, и элемент t. Так как ui[0,m - 1] = 0, то t = u0[0,m - 1] од-нозначно определяется отрезком u1[m, 2m - 1]. Зададим подстановку равенством(t) = u1[m, 2m - 1 ].Достоинством таких подстановок является возможность их эффективной реализа-ции на современных микропроцессорах. Отметим, что некоторые координатные функ-ции имеют степень нелинейнсти 2. Рассмотрим узел блочного шифра c r раундамии набором раундовых ключей k - (ki,..., kr) е Tr , построенный на основе подстанов-ки . Исходное сообщение x е T преобразуется согласно равенствуy = Sk(x) = (. . . (^F(x + ki) + k2)... + kr).Зададим группу подстановок G = {gt : gt(x) = x ф t, x,t е T}. Тогда Sk е (^FG)r.В ходе экспериментов установлено, что в ряде случаев множество подстановок Gпорождает знакопеременную группу подстановок. Построены примеры, когда уже приk = m данный узел является стойким к методу дифференциального анализа.Тривиальными примерами многочленов с расстоянием единственности 2m явля-ются многочлены F(x), такие, что F(x) = xm + 1 (mod 2). Однако пока не обоснованосуществование нетривиальных многочленов со свойством Ud(F) = 2m произвольнойстепени m. Важным шагом в этом направлении являетсяТеорема 2. Пусть m = 2k + s, k е N, s нечетно, F(x) = F0(x) + 2F1 (x) -двоичноеразложение многочлена F(x), F0(x) = (x + 1)m (mod 2) и (F1(x) + xs ,x + 1) = 1. ТогдаUd(F) е {2m, ro}.Пусть R = Zp2, p > 2 - простое число, r(R) = {а е R : ap = a} - p-адическое коор-динатное множество. Известно [1], что каждый элемент а е R однозначно представля-ется в виде a = a0 +pa1, a0, a1 е r(R). Аналогично (1) каждую линейную рекуррентнуюпоследовательность u е Lr(F) можно представить в видеu(i) = u0(i) + pu1(i), u0(i),u1(i) е r(R), i ^ 0.Параметр Ud(F) определяется так же, как и в двоичном случае. Серия эксперимен-тов на ЭВМ показала, что результат теоремы 1 справедлив для p = 3 , m е 2, 9; p = 5,m е 2, 5. Экспериментально показано существование многочленов с расстоянием един-ственности 2m. Такие многочлены также позволяют задавать подстановки на множе-стве Z^. Степень нелинейности координатных функций соответствующих подстановокравна p.

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