Полноцикловые преобразования. 
Криптографические методы защиты информации. 
Часть 1. Математические аспекты

Особый интерес в криптографии представляют преобразования с экстремальными периодическими свойствами. Подстановка ??-множества g называется полноцикловой (и.ц.), если ее граф T (g) есть единственный цикл длины п. В этом случае t_xg = t_g = n для любого х е X.

Теорема 8.4. Число различных п.ц. подстановок n-множества равно Оп — 1)!.

4 Рассмотрим полный цикл элементов я-множестваХ как перестановку элементов, размещенную на п точках окружности. Значит, число различных полных циклов равно п. В то же время циклы эквивалентны (реализуют одинаковые п.ц. подстановки) отличаются лишь сдвигом элементов по окружности. Каждый класс эквивалентности состоит из п циклов, тогда искомое число равно (п — 1)!. ?

Распознавание иолноцикловости подстановки по ее таблице требует в худшем случае просмотра всей таблицы. Сложность этой задачи характеризует и следующая теорема.

Теорема 8.5. Подстановка g п-множества X является п.ц. функции ф и? ф различны при любой отличной от константы функции ф: X —" У, где.

|у| >2.

4 Пусть ф (?(х)) = ф (х) для и.ц. подстановки g, для любого х е X и указанной функции ф. Тогда ф (Ж (х)) = ф (.г) для любого t е N, это в силу полноцикловости подстановки g означает, что функция ф — константа. Имеем противоречие, значит, отображения ф и gф различны.

Обратно, пусть подстановка g множества X не полноцикловая, и X' подмножество множества X, образующее цикл графа F (g). Определим отличную от константы функцию ф: X —> У, где Y = [у_{у у₂, …}: ф (зг) = у_{ для всех х е X' и ф (х) = у₂ для всех х е X X'. Тогда для любого х е X

выполнено равенство ф(g (x)) = ф (х). Следовательно, функции ф и g (p совпадают. ?

Пример 8.2. Линейный конгруэнтный генератор (ЛКГ) ЛКГ реализует преобразование g кольца вычетов Е_т, где g (x) = (ах + b)nodm для любого х е Е_т. Константы а_} Ь, т называются множителем, сдвигом и модулем соответствен но.

Длина периода t_g Для любого т имеются константы, а и Ь, при которых t_g= т, соответствующие генераторы называются ЛКГ полного периода. [>

Теорема 8.6 [3]. Для ЛКГ t_g = m выполнена система условий:

• 1) (Ь, т) = 1;
• 2) а — 1 кратно любому простому делителю числа т
• 3) а — 1 кратно 4, если т кратно 4.

В частности, t_g= т при т = 2' b — нечетное и а= l (mod4). О Пусть п > 1, g и |/ — преобразования множеств Х^п и Х^п~^{ соответственно, где х = к и |/ задано подсистемой системы g:

Докажем критерий нолноцикловости преобразования g (x^_f…, х_п) в случае X = {0, 1}, тогда k-2w функции /_1? — булевы. Доказательство более общего случая дано в [10].

Пусть у = (tfj, …, a_w__t) е s^(y) = (г/, |/(г/), …, Yiy)) ~ путь в Г (|/).

длины t > 0 из вершины у, где 5° {у) = |/°(г/) = у f_n(y, х_п) — подфункция функции f_n(x 1,…, при фиксации (х_1?= у.

Пути s^(y) соответствует булева функция 5[s{j,(z/)](x"), t > 0, где 8[$®(г/)].

(^хп) ⁼fn (y> ^Хп)^:

В данных условиях для любого у е V_n__{ и любого х_п е X, t > 1:

Теорема 8.7. Подстановка g на V_n является п.ц. vp — п.ц. подстановка на V_n_i и для гамильтонова цикла s*ⁿ~y) в Г (р) функция 8[5-" ^-1(г/)](х") есть п.ц. подстановка на {0, 1}.

4 Покажем корректность формулировки теоремы, ведь при п.ц. подстановке р для гамильтонова ну ги s™(y) можно взять 2^W₁ различных начальных вершин у. Убедимся, что биективность функции 8[s^(y)](x_n) не зависит от у.

Пусть s™(y₀) = (у₀, у_ь …, у_т__и у_т) и s™(y_{) = (y_t, у_ъ …, у_тУ у₀) — гамильтоновы пути в графе Г (|/) со смежными начальными вершинами, т = 2″ ^-1 — - 1. Если функция 8[л'" '(г/₀)](х") есть подстановка множества {0, 1}, то в силу (8.1) и с учетом следствия из утверждения 4.3 8[${"(г/₀)](х") — произведение подстановок: 5[s*(y₀)](*_B) =/"(у₀. x")f_n(y_u x")…f_rl(y_m__u х")

1п (Ут' ^х") — Следовательно, s"(y_t) = f"(y_v x")f"(y₂, x_n)…f"(y_m, x_n)f"(y_f), x") — также подстановка, при этом подстановки s™(y₀) и s™(y_x) подобны: s™(y_x) =.

= (/"(Уо> ^xn)Y^lsv (yo)fn (yo> *#")? Поскольку гамильтонов путь в графе Г (у) есть последовательность пар смежных вершин, то функция 8[${"(г/)](х_я) биективна при любом у е V_n__x.

Пусть х = (г/₀, х_п) е V_rv g_,(x) = (х, g (x), g²(x),…). Разобьем [0, 2^п — 1 ]-отрезок последовательности g_>(x) на два отрезка длины 2^й-1, которые обозначим g__>(x)₁ и g_>(x)₂. Из (8.2) следует, что.

Пусть |/ и 5[s™(y)](x_n) и.ц. подстановки, тогда огс1|/ = 2″ ^-1, значит,.

Последовательность {г/₀, |/(г/₀), •••> ^^т(у)} ^не содержит одинаковых членов, так как образует гамильтонов цикл в Г (|/). Значит, различны все члены как отрезка g__>(x)₁, так и отрезка g_>(x)₂. В то же время, 5[s* (г/₀)](х") Ф Ф Ь№^п-у₀)](х") при i = 0, 1, т, так как 8|s²" ^_1(z/)](x") — п.ц. подста новка. Тогда различны все члены [0, 2^п — 11-отрезка последовательности g_>(x). Отсюда g — п.ц. подстановка.

Обратно, если g — п.ц. подстановка множества V_n, то из (8.2) следует: 2^п = t_g < 21 . Тогда ty > 2^й" ¹, следовательно, = 2^я-1. Далее, если g, V|/ — п.ц. подстановки множеств V_n, V_n__{ соответственно, t — длина периода преобразования 8[5²««¹(г/)](х_и), то из (8.2) следует: 2^п= t_g = 2^п~Ч. Значит, t = 2, т. е. 5[s²«у)](х_п) — п.ц. преобразование. ?

Следствие 1. Подстановка g является п.ц. |/ — и.ц. подстановка на V_n__x и.

где вес функции й (х_1?х_п__х) нечетный.

Л В данных условиях 8[s²ⁿ" (у)](х_п) ^{= х}п ~ ^П-Дподстановка на {0, 1},.

и /(x_t, …, х_п) = /z (xj, …, х_п__{) © х_п, иначе преобразование g не инъективно. В соответствии с (8.1) 8[s²" ^-1 (у)](х_я) =х_п® © А (х₁,…, х_я-1) = х_п Ф.

(x_h…, x_n_0eV_n__{

© ||/г||шо (12. Отсюда вес функции h нечетный. ?

Следствие 2. Пусть треугольная подстановка g_n множества V_n задана системой координатных функций {hj (x^ …, х_м) © х_у, i = 1, п), где h_{ —

константа. Тогда подстановкаg_n п.ц. h_{ = 1 и ||/гу|| нечетный, i = 2,…, п.

А Индукция, но п с использованием следствия 8.1. ?

Замечание. В соответствии с теоремой 6.20 вес функции hj (x^ …, х_м) нечетный моном x₁…x_i_₁ входит в многочлен Жегалкина функции hj (x_v …, Xj_|), Z 2, …, 71.

Число и.ц. подстановок, реализуемых двоичными регистрами сдвига длины /2, равно 2²«~^1_я [ 1 ], вместе с тем, не известны легко проверяемые критерии иолноцикловости регистра, выраженные, например, через характеристики функции обратной связи. Вместе с тем п.ц. регистры небольшой длины можно строить с помощью принципа «склеивания-расклеивания».

Теорема 8.8. Пусть g и h — подстановки двоичных регистров сдвига длины п > 1 с обратными связями f (x_u …, х_п) и/(a:_lf…, х_п) © х%²…х"^п соответственно, где а₂уа_п е {0, 1}. Тогда граф Y (g) отличается от графа Г (/г) тем, что-либо один цикл из Y (g) распадается на два цикла в Г (/г), либо два цикла из Y (g) объединяются в один цикл в Y (h).

Ч По следствию теоремы 7.5 f (x_v …, х") =х^® f (x₂, х_п). Отсюда:

Значит, если вершины (0, а_ъ …, а_п) и (1, а₂,…, а_п) принадлежат одному циклу графа Y (g), то в графе Г (/?) они принадлежат разным циклам. И наоборот, если вершины (0, а₂, …, а_п) и (1, а₂, …, а_п) принадлежат разным циклам графа T (g), то в графе Y (h) они принадлежат одному циклу. На всех остальных вершинах преобразования g и h совпадают. ?

Для построения п.ц. регистровой подстановки на V_n из исходной регистровой подстановки путем «склеивания» циклов определяются пары наборов (0, а₂,…, а_п) и (1, а₂,…, а_п), соседних по 1-й координате и принадлежащих разным циклам, после чего к функции обратной связи добавляется конъюнкция х₂²…х"^п. Если граф исходного регистра состоит из г циклов, то для построения п.ц. регистра требуется выполнить г — 1 таких шагов.