Задание подстановок алгоритмов блочного шифрования Магма и 2-ГОСТ с помощью алгебраических пороговых функций | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/4

Задание подстановок алгоритмов блочного шифрования Магма и 2-ГОСТ с помощью алгебраических пороговых функций

Предложено задание подстановок алгоритмов блочного шифрования Магма и 2-ГОСТ через линейные комбинации алгебраических пороговых функций (АПФ). Для этого приведены полученные автором результаты представимости геометрических типов булевых функций от четырёх переменных через АПФ.

The implementation of Magma and 2-GOST block cipher substitutions by algebraic threshold functions.pdf Введение Пороговые функции представляют интерес с точки зрения синтеза узлов переработки информации [1] благодаря простой логике их задания и возможности быстрого выполнения операций в перспективной элементной базе, например в оптической [2]. Работы [3 - 5] посвящены изучению способов синтеза подстановок на основе классических пороговых функций. В данной работе предложено задание подстановок алгоритмов блочного шифрования Магма [6] и 2-ГОСТ [7] с помощью так называемых алгебраических пороговых функций. Класс АПФ предложен в работах [8, 9] и отличается от пороговых функций добавлением свободного члена к линейной форме и приведением её по определённому модулю до выполнения операций сравнения. Основным результатом первой работы является описание некоторого класса сбалансированных АПФ, а второй - доказательство того, что только один геометрический тип булевых функций от трёх переменных не принадлежит классу АПФ. Координатные функции указанных подстановок зависят от четырёх переменных, поэтому в работе приведены представления геометрических типов булевых функций четырёх переменных через АПФ. Полученный каталог позволил изучить представимость линейных комбинаций координатных функций исследуемых подстановок. Через линейные комбинации, являющиеся АПФ, выразилась только одна подстановка. Остальные подстановки удалось задать через линейные комбинации пяти АПФ, полученных добавлением к координатным функциям специально выбранной АПФ. Отметим, что линейные функции содержатся в классе АПФ, поэтому полученные задания подстановок реализуются на единой элементной базе. 1. Представление геометрических типов булевых функций от четырёх переменных через АПФ Определение 1. Функцию k-значной логики /П : ^П -^ назовём алгебраической пороговой, если существуют целочисленные наборы с = (со, c1,..., cn), b = (bo, b1,... , bk) и модуль m Е N, такие, что для любого а Е ^k выполняется /П(Х1,Х2, . . . ,Xn) = а ^ ba ^ Гт(Со + C1X1 + C2X2 +-----+ CnXn) 8, то следует искать соответствующего представителя с весом менее 8 (||/1| < 8). Номер b отвечает за количество компонент связности в графе Gf = (X, U) функции /. Вершинами X графа связности Gf являются точки множества в которых функция принимает значение 1 (носитель функции): X = {(a1, a2, a3, a4) Е ^ : /(a1, a2, a3, a4) = 1}, а множеством рёбер U является множество рёбер куба, соединяющих соседние вершины графа: U = {((aba2,a3,a4), (bb b2, Ьз, b4)) Е X2| x ((«1, «2, аз, ak), (b1, b2, Ьз, b4)) = 1} где х - расстояние Хемминга между точками (а1, а2, а3, а4) и (b1, 62, 63, 64): 4 X ((аьа2,а3,а4), (61,62,63,64)) = Е Ind(a* = 6j), i=1 J 1, если а» = 6i, Ind(ai = 6i) = < 10, если aj = 6j. Номер c - порядковый номер графа связности с числом вершин а и количеством компонент связности 6; d - порядковый номер геометрического типа с графом связности a.6.c. Стоит отметить, что предложенный каталог составлен в 1994 г. вручную и был впоследствии полностью подтверждён при сверке с результатами работы компьютера. Далее сохранена введённая нумерация, и читатель может обратиться к указанному каталогу, но представитель геометрического типа будет предложен другой, а именно минимальный по лексикографическому номеру, либо f в случае, если первый представитель геометрического типа с минимальным номером f имеет вес более 8. В [9] доказано, что класс АПФ замкнут относительно фиксации переменных и среди булевых функций от трёх переменных только один геометрический тип не принадлежит классу АПФ (для удобства представителя данного типа будем обозначать f*). Функция f * задаётся вектор-строкой f* = (1,1,1, 0, 0,1, 0, 0). (1) В табл. 1 приведены геометрические типы булевых функций от четырёх переменных с указанием фиксации переменной, при которой подфункция эквивалентна функции (1). Из 222 геометрических типов 70 обладают указанным свойством. Отметим, что если в каталоге представитель f некоторого геометрического типа не содержит подфункцию f *, то искать её среди подфункций f нет смысла, поскольку инвертирование подфункции не выводит за геометрический тип. Утверждение 1. Геометрические типы булевых функций от четырёх переменных, представленные в табл. 1, не принадлежат классу АПФ. Для оставшихся 152 геометрических типов была написана программа, которая нашла структуры 101 представителя. Логика работы программы заключается в переборе всевозможных АПФ, у которых коэффициенты линейной формы (c0, c1, c2, c3, c4) ограничены некоторой константой, а модуль m и порог 6 ограничивались максимальным значением c0 + c1 + c2 + c3 + c4 + 1 текущей линейной формы. Для каждой из полученных АПФ проверяется её наличие среди представителей геометрических типов. Программа опробовала все задания АПФ, у которых коэффициенты линейной формы не превосходили значения 40. Результаты работы программы приведены в табл. 2. Среди полученных 101 структур представителей геометрических типов максимальный коэффициент линейной формы равен 8, а максимальный модуль - 9. Доказать, что есть соответствующие ограничения, начиная с которых новые АПФ перестанут появляться, не удалось. Подходы, предложенные для подсчёта асимптотики пороговых функций в работах [11-13], на данный момент результатов не дали. I = (o'o'o'i 'o'l 'i 'o'l 'o'l 'o'l 'i 'o'l) rg'g'8 0 = ^x (o'o'o'i 'i 'o'l 'i 'i 'i 'i 'o'o'i 'o'o) VZZ'Z'S I = £x (o'o'o'l 'o'l 'i 'o'l 'o'o'i 'i 'i 'i 'o) I '91 S'8 \ = Ьх (o'o'o'i 'o'l 'i 'o'l 'o'l 'i 'i 'i 'o'o) l'Zl'Z'2 I = T-x (o'o'o'i 'o'l 'i 'o'l 'o'o'i 'i 'o'l 'l) T'OT'S'8 0=Tx (o'o'o'o'o'i 'i 'o'l 'o'l 'i 'i 'i 'o'l) I'S'2'8 I = £x (o'o'o'o'o'i 'i 'i 'i 'o'l 'i 'i 'i 'o'o) ГТСТ8 0 = ^x (o'o'o'i 'i 'o'l 'i 'i 'i 'o'l 'i 'o'o'o) Г0СТ8 0 = ^x (o'o'o'i 'o'l 'i 'i 'i 'o'l 'o'l 'i 'o'o) Z'SZ'YS I = Tx (o'o'o'o'o'i 'i 'i 'i 'o'l 'i 'o'l 'i 'o) Г82Т8 I = T-x (o'o'o'i 'o'l 'i 'i 'i 'o'o'i 'i 'o'l 'o) T'ZS'T'8 0=Tx (o'o'o'o'o'i 'i 'o'l 'o'o'i 'i 'i 'i 'l) Г92Т8 0 = еж (o'o'o'o'o'i 'i 'i 'i 'i 'i 'i 'o'o'i 'o) T'SS'T'8 I = Tx (o'o'o'o'o'o'i 'i 'i 'i 'o'l 'i 'i 'i 'o) I = T-x (o'o'o'o'o'i 'i 'i 'i 'i 'i 'o'o'o'i 'i) гегт8 0=Tx (o'o'o'o'o'i 'i 'o'l 'o'l 'i 'o'l 'i 'l) T'TS'T'8 0=Tx (o'o'o'o'o'i 'i 'o'l 'i 'i 'i 'o'l 'i 'o) Г6ГГ8 0=Tx (o'o'o'o'o'i 'i 'i 'i 'i 'i 'o'o'i 'i 'o) Г6ГГ8 0=Tx (o'o'o'i 'o'l 'i 'i 'i 'o'o'o'i 'i 'i 'o) Г9ГГ8 0=Tx (o'o'o'o'o'i 'i 'o'o'i 'i 'i 'i 'i 'i 'o) I'fTI'8 0=Tx (o'o'0'O'O'o'l 'I 'I 'I 'o'l 'I 'o'l 'l) T'TT'T'8 0=Zx (o'o'o'o'o'o'i 'i 'i 'i 'o'l 'i 'i 'o'l) Г6Т8 0=Tx (o'o'0'O'O'o'l 'I 'I 'I 'O'O'I 'I 'I 'l) Г8Т8 0=Tx (o'o'o'o'o'o'i 'i 'o'l 'i 'o'l 'i 'i 'l) T'Z'T'8 0=Tx (o'o'0'O'O'0'o'l 'i 'i 'i 'o'l 'i 'i 'l) ГГГ8 I = Tx (o'o'o'i 'o'l 'i 'o'l 'o'o'i 'i 'o'l 'o) T'S'E'Z 0 = т?х (o'o'o'i 'o'l 'i 'o'l 'o'l 'o'l 'i 'o'o) Г VZ'L Q = T'x (o'o'o'i 'o'l 'I 'o'l 'o'o'o'i 'o'l 'l) rc'cz 0 = еж (o'o'O'O'o'l 'i 'i 'i 'o'l 'i 'o'l 'o'o) Г9Г2'2 0=Zx (o'o'O'O'o'l 'i 'o'l 'o'l 'i 'o'l 'i 'o) S'ST'S'Z 0 = Zx (o'o'o'i 'o'l 'i 'i 'i 'o'o'i 'i 'o'o'o) I'ST'S'Z 0=Tx (o'o'O'O'o'l 'i 'o'l 'o'l 'i 'o'l 'o'l) Т'6'S'Z 0=£x (o'o'O'O'o'l 'i 'o'l 'i 'i 'i 'o'o'i 'o) I'8'S'Z I = ^x (o'o'o'i 'o'l 'i 'o'l 'o'o'o'i 'i 'i 'o) S'9'S'Z 0=Zx (o'o'O'O'o'l 'i 'o'l 'O'O'i 'o'l 'i 'l) I'9'S'Z 0=Zx (o'o'O'O'o'l 'I 'O'O'I 'I 'I 'I 'o'l 'o) S'9'S'Z 0=Tx (o'o'o'o'O'O'i 'i 'o'l 'i 'o'l 'i 'o'l) T'S'S'Z I = Tx (o'o'O'O'o'l 'i 'o'l 'o'l 'i 'o'o'i 'i) TZ'Z'L 0=£x (o'o'O'O'o'l 'i 'O'O'i 'i 'i 'o'l 'i 'o) r9T'T'Z 0=Zx (o'o'o'o'O'O'i 'i 'i 'i 'o'l 'i 'o'o'i) Z'9VVL 0 = T'x (o'o'O'O'o'l 'i 'i 'i 'i 'i 'o'o'o'i 'O) T'ST'T'Z 0=Zx (o'o'o'o'O'O'i 'i 'o'l 'i 'o'l 'i 'i 'o) TSTT "Z 0 = T'x (o'o'o'o'o'l 'I 'I 'I 'o'l 'I 'o'o'o'i) rirrz 0=Tx (o'o'o'o'O'O'I 'I 'I 'I 'o'o'o'i 'I 'l) T'OT'T'Z 0=£x (o'o'o'o'o'o'o'l 'o'l 'i 'o'l 'i 'i 'l) T'6'T'Z 0=Zx (o'o'o'o'O'O'i 'i 'i 'i 'o'l 'o'l 'o'l) S'8'T'Z 0=Zx (o'o'o'o'O'O'o'l 'i 'i 'i 'o'l 'o'l 'l) T'8'T'Z 0=Tx (o'o'o'o'O'O'i 'i 'o'l 'o'l 'i 'o'l 'l) T'Z'T'Z 0=zx (o'o'o'o'O'O'o'l 'i 'o'l 'i 'i 'i 'o'l) T'S'T'Z 0=Zx (o'o'o'o'O'O'o'l 'i 'o'l 'o'l 'i 'i 'l) T'C'T'Z 0 = т?х (o'o'O'O'o'l 'I 'o'l 'o'l 'I 'o'o'o'i) 0=Zx (o'o'O'O'o'l 'i 'o'l 'o'o'i 'o'o'i 'i) T'£'£'9 0 = ^x (o'o'o'o'O'O'I 'I 'I 'I 'o'l 'I 'o'o'o) Z'L'Z'9 0 = еж (o'o'o'o'O'O'i 'i 'o'l 'o'l 'i 'o'l 'o) T'Z'S'9 0=zx (o'o'o'o'O'O'I 'I 'o'l 'o'l 'I 'o'o'i) 9'VZ'9 0 = Zx (o'o'O'O'o'l 'I 'O'O'I 'I 'I 'o'o'i 'o) ГГг'9 0=£x (o'o'O'O'o'l 'I 'o'l 'o'l 'I 'o'o'i 'o) Z'Z'Z'9 0=Zx (o'o'o'o'O'O'i 'i 'o'l 'i 'o'l 'o'l 'o) 0=zx (o'o'o'o'o'o'o'l 'o'l 'I 'o'l 'o'l 'l) VZ'Z'9 0 = еж (o'o'o'o'O'O'o'l 'i 'o'l 'o'l 'i 'o'l) S'6'T'9 0 = ^x (o'o'o'o'O'O'I 'I 'I 'I 'o'o'o'i 'o'l) T'6'1'9 0 = Zx (o'o'o'o'O'O'o'l 'I 'o'l 'o'l 'o'l 'l) T'8'T'9 0 = еж (o'o'o'o'o'o'o'l 'o'o'i 'i 'i 'i 'o'l) T'9'T'9 0 = еж (o'o'o'o'O'O'o'l 'I 'O'O'I 'I 'o'l 'l) T'S'T'9 0 = Zx (o'o'o'o'o'o'o'l 'o'o'i 'o'l 'i 'i 'l) TST'9 0 = ^x (o'o'o'o'O'O'o'l 'I 'o'l 'o'l 'I 'o'o) Z'Z'Z'9 0 = еж (o'o'o'o'o'o'o'l 'o'o'i 'o'l 'I 'o'l) VZ'Z'9 0 = ^x (o'o'o'o'O'O'o'l 'I 'o'o'o'i 'o'l 'l) Z'Vl'9 0 = ^x (o'o'o'o'o'o'o'l 'o'o'o'i 'I 'o'l 'l) T'E'T'S 0 = T'x (o'o'o'o'o'o'o'o'O'O'o'l 'I 'o'l 'l) I'E'l'f ю = ?ж BHtl -вэмиф p'O'q'v тзних оломээьисЬэиоэл виэх -HaBiotfadn Iragiroxo-doxMag p'O'q'v dawopj ю = ?ж biin -вэмиф p'O'q'v 12них оломээь^хэиоэл Birax -HaBiotfadn tiagiroxo-doxjiag p-Q-q-jy dawopj ФПУ ^ЭЭВ1ГМ oiX'niBMfairb'BHHdn эн 'ош'пмнАф ии'пмнХфЬ'оп эялээызм я эи'гггеж^эЬ'оэ 'xraHHawadaii xadraiah io ии'пмнАф xraaaifAg нпих aHMoahndiawoaj l в ti и if g в x 9S Hnmoj у-ft (8 9 (9'9'9'Z'O)) (о'о'о'о'о'о'о'т'о'о'т'т'т'т'т'о) £'VZ'9 Z9 (8 9 (l'Z' 9'9'T)) (о'о'о'о'о'о'о'т'о'т'т'о'т'т'т'о) Z'VZ'9 те (f ^ (c'c'c'c's)) (т'т'т'о'т'о'о'о'т'о'о'о'о'о'о'т) Z'Z'Z'9 OS (l f (c'9'9's'l)) (о'о'о'о'о'о'о'т'т'т'т'о'т'о'т'о) Z'VZ'9 61 (9 f (g'g'g'g'o)) (о'о'о'о'о'о'о'о'о'т'т'т'т'т'т'о) T'Z'T'9 81 (z f (z'z'i'i't)) (о'о'о'о'о'о'о'т'о'о'о'т'т'т'т'т) l'Z'1'9 If (s £ (г'т'т'о'с)) (о'о'о'о'о'о'о'о'о'о'т'т'т'т'т'т) T'T'T'9 9f (z 9 (g'g'C'C's)) (о'о'о'о'о'т'т'о'о'т'т'о'о'о'о'т) C'I'9'9 Qf (с Z (zcicicicz)) (о'о'о'т'о'т'т'о'т'о'о'о'о'о'о'т) Z'V9'9 ff (z 9 (9'f'f'f'l)) (о'о'о'о'о'о'о'т'т'о'о'т'о'т'т'о) T'T'S'S £f (i 9 (g'i 'c'c's)) (о'о'о'о'о'т'т'о'т'о'о'т'о'о'о'т) СТГ9 Zf (9 f (c'S'S'l'l)) (о'о'о'о'о'о'т'т'о'т'т'о'т'о'о'о) Z'Vf'9 If и 9 (T 'f'f'f'9)) (о'о'о'о'о'о'о'т'о'т'т'о'т'о'о'т) VVV9 Of (i 9 (9'f'f'l'l)) (о'о'о'о'о'о'о'т'о'о'т'т'т'т'о'о) VZ'£'9 6£ (б 9 (z'z'f'9'l)) (о'о'о'о'о'т'т'о'о'т'т'о'о'о'т'о) VVV9 8C (9 f (cVS Vl)) (о'о'о'о'о'о'о'т'о'т'т'о'т'о'т'о) VVV9 zc (9 f (t't'9'9'0)) (о'о'о'о'о'о'о'т'о'о'о'т'т'т'т'о) TIC'S 9C (8 9 {Zl9l9lLl9)) (о'о'о'о'о'о'т'т'т'т'о'о'о'о'о'т) £'VZ'9 ec (б 9 (Z'l '9'9'9)) (о'о'о'о'о'о'о'т'т'о'о'т'т'о'о'т) Z'VZ'9 1С (я £ (c'l'l'l'l)) (о'о'о'о'о'о'о'т'т'т'т'о'т'о'о'о) £'Z'Z'9 cc (8 9 (S'T'T'C'S)) (о'о'о'о'о'о'о'т'т'о'т'о'т'о'т'о) l'l'Z'9 sc (б 9 (l'S'S'8'9)) (о'о'о'о'о'о'о'о'о'о'т'т'т'т'о'т) VVV9 1С (s £ (т'т'т'т'с)) (о'о'о'о'о'о'о'т'о'о'о'т'о'т'т'т) I'Z'1'9 ОС (8 9 (C'S'T'T'S)) (о'о'о'о'о'о'о'о'о'о'о'т'т'т'т'т) TIT'S 6Z (f £ (г'г'т'т'о)) (о'о'о'о'о'т'т'о'о'т'т'о'о'о'о'о) 9'Vf'f 8Z (f £ (т 'C'S'S'O)) (о'о'о'о'о'т'т'о'т'о'о'т'о'о'о'о) 9'1'f'f LZ (s f (f'z'z'z'o)) (о'о'о'о'о'о'о'т'о'т'т'о'т'о'о'о) VVVf 9Z (8 9 (9 Vs's'l)) (о'о'о'о'о'о'о'т'т'о'о'о'о'т'т'о) VVVf 9Z (f £ (c'c'c'c'o)) (о'о'о'о'о'о'о'т'о'о'о'т'о'т'т'о) Z'l'Vf fZ (f £ (t lzlzlzl£)) (о'о'о'о'о'о'о'о'о'т'т'о'т'о'о'т) VVVf £Z (Z 9 (g'9'e'e'o)) (о'о'о'о'о'о'о'т'т'о'о'т'т'о'о'о) VVVf zz (8 9 (9 VS'T'T)) (о'о'о'о'о'о'о'т'о'о'т'о'т'т'о'о) Z'l'Vf IZ (8 9 (g'g 'z'9'т)) (о'о'о'о'о'о'о'т'о'о'о'т'т'о'т'о) VVVf oz (с Z (s'i'i'o'o)) (о'о'о'о'о'о'т'т'т'т'о'о'о'о'о'о) VZ'Z'f 61 (f £ (s'c'c'o'o)) (о'о'о'о'о'о'о'о'о'о'т'т'т'т'о'о) VZ'Z'f 8T (i 9 (l 'I 'l Vs)) (о'о'о'о'о'о'о'т'о'о'о'т'т'о'о'т) VVZ'f ZT (9 f (I'T'T'S'T)) (о'о'о'о'о'о'о'т'т'о'т'о'т'о'о'о) Z'VZ'f 9T (z 9 (^'9 '9'9'0)) (о'о'о'о'о'о'о'о'о'о'о'т'т'т'т'о) VVZ'f ST (9 f (Z 'l 't7)) (о'о'о'о'о'о'о'о'о'о'о'т'о'т'т'т) VZ'l'f fl (с Z (T'T 'O'O'S)) (о'о'о'о'о'о'о'о'о'о'о'о'т'т'т'т) VVl'f CT (б (Z '9'9'9'T)) (о '0 '0 '0 '0 '0 'о 'т 'т '0 '0 '0 '0 'о 'т 'о) £'V£'£ Zl (s f (f'f'Z'Z'o)) (о '0 '0 '0 '0 '0 '0 'т '0 '0 'о 'т 'т '0 'о 'о) Z'V£'£ TT (s f (C Vl Vo)) (о '0 '0 '0 '0 '0 '0 '0 '0 '0 'о 'т 'о 'т 'т 'о) Ties от (z 9 (l l9l9l9l9)) (о '0 '0 '0 '0 '0 'о 'т 'т '0 '0 '0 '0 '0 'о 'т) Z'VZ'£ 6 (б (i't 'z'c'z)) (о '0 '0 '0 '0 '0 '0 '0 '0 '0 'о 'т 'т '0 'о 'т) VVZ'£ 8 и 9 {ZlZlllll9)) (о '0 '0 '0 '0 '0 '0 '0 '0 '0 '0 '0 'о 'т 'т 'т) II'I'S z (f £ (с'т'т'т'о)) (о '0 '0 '0 '0 '0 'о 'т 'т '0 '0 '0 '0 '0 'о 'о) VVZ'Z 9 (9 9 (c's Vi'o)) (о '0 '0 '0 '0 '0 '0 '0 '0 '0 'о 'т 'т '0 'о 'о) Z'VZ'Z e (9 9 (z 'Z '9 '9 'о)) (о '0 '0 '0 '0 '0 '0 '0 '0 '0 '0 '0 'о 'т 'т 'о) VVZ'Z f (l £ (т'т'т'о'с)) (о '0 '0 '0 '0 '0 '0 '0 '0 '0 '0 '0 '0 'о 'т 'т) II'I'S с (s f (т 'т 'т 'T 'f7)) (о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'т) T'T'T'T г (T I (о'о'о'о'о)) (о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о 'о) T'T'0'0 т fo'q'o впих oJOMoabHdxawoaj Bifaxna'Bxo'n'adn BdAxMAdxQ p'O'q'v впих оломээыкТхэиоэл Bifaxna'Bxo'n'adn Iragiroxo-doxMag p'O'q'v вээв1тя dawopj ц/ц «к ФПУ ^ЭЭВ1ГМ О И tTTV3>KOL"t/V311 и dn 'xMHHawadan xadraiah io ии^ганАф xraaairXg ииих aroioahndiawoaj 1 в ti и if g в x iq 0LIV C4qtnoiAiou э j_JOJ~Z и ewjej/\i aowindcuve >i090Heuif0u эинеНе£ Окончание табл. 2 № п/п Номер класса a.b.c.d Вектор-столбец представителя геометрического типа a.b.c.d Структура представителя геометрического типа a.b.c.d 53 6.2.5.1 (1,1,0,0, 0, 0,1,1,1,1, 0,0,0,0, 0, 0) ((3,0, 3, 3,1) 3 5) 54 6.2.6.2 (0,0,1,0,1, 0,1,1,1,1, 0,0,0,0, 0, 0) ((1,1, 5, 5, 3) 4 7) 55 6.2.8.1 (0,1,1,0, 0,1,1,0,0,1,1,0,0,0, 0, 0) ((1, 3, 3,1,1) 4 6) 56 6.2.8.3 (0,0,0,0, 0,1,1,1,1,1,1,0,0,0, 0, 0) ((0,1,1, 2, 3) 3 5) 57 6.3.4.1 (0,0,1,1, 0,1,1,0,1,1, 0,0,0,0, 0, 0) ((2,1, 3, 2, 4) 5 8) 58 6.3.5.1 (0,0,1,1,1,1,0,0,1,1, 0,0,0,0, 0, 0) ((0,0, 2, 2, 2) 2 3) 59 6.4.1.2 (0,0,0,1,1,1,1,0,0,1,1,0,0,0, 0, 0) ((1, 2, 2, 4, 3) 5 8) 60 6.4.1.3 (1,1,0,0, 0, 0,0,1,0,1,1,0,1,0, 0, 0) ((3,1, 2, 2, 4) 3 5) 61 6.4.2.1 (0,1,1,0,1, 0,0,1,0,1,1,0,0,0, 0, 0) ((1, 3, 3, 4,1) 4 6) 62 6.4.2.2 (0,1,1,0, 0, 0,0,1,0,1,1,0,1,0, 0, 0) ((0,4,4, 3,1) 4 6) 63 6.5.1.1 (1,0,0,1, 0, 0,0,1,0,1,1,0,1,0, 0, 0) ((3, 3, 3, 4, 2) 3 5) 64 6.6.1.1 (1,0,0,1, 0,1,1,0,0,1,1,0,0,0, 0, 0) ((4, 3, 3, 4, 4) 4 6) 65 6.6.1.2 (0,0,0,1, 0,1,1,0,0,1,1,0,1,0, 0, 0) ((0,1,1,1,1) 2 3) 66 7.1.1.1 (1,1,1,1,1,1,1,0,0, 0, 0,0,0,0, 0, 0) ((4,1,1,1, 3) 4 7) 67 7.1.2.1 (1,1,1,1,1,1,0,0,1, 0, 0,0,0,0, 0, 0) ((5,1, 2, 2, 3) 5 9) 68 7.1.14.1 (1,0,1,1,1,1,0,0,1,1, 0,0,0,0, 0, 0) ((4, 6, 2, 2, 2) 4 7) 69 7.2.1.1 (0,1,1,1, 0,1,1,1,1, 0, 0,0,0,0, 0, 0) ((1, 7, 7, 8, 4) 5 9) 70 7.2.2.2 (1,0,0,0, 0, 0,0,1,0, 0, 0,1,1,1,1,1) ((3, 5, 5, 4, 4) 3 6) 71 7.2.7.1 (0,1,1,1,1,1,1,0,1, 0, 0,0,0,0, 0, 0) ((0,4,4, 4, 3) 3 5) 72 7.2.10.1 (0,0,1,1,1, 0,1,1,1,1, 0,0,0,0, 0, 0) ((1,1, 6, 7, 4) 5 9) 73 7.2.11.1 (1,0,0,0, 0, 0,0,1,1, 0, 0,1,0,1,1,1) ((4, 2, 2, 2,1) 3 6) 74 7.2.13.1 (0,0,1,1,1,1,1,0,1,1, 0,0,0,0, 0, 0) ((1, 6, 5, 5, 4) 4 7) 75 7.2.14.1 (0,0,0,0,1,1,1,1,1,1,1,0,0,0, 0, 0) ((1,1,1, 3, 4) 4 7) 76 7.2.15.1 (1,0,0,0, 0,1,1,1,1,1,1,0,0,0, 0, 0) ((5, 7, 7, 5, 3) 5 9) 77 7.3.4.3 (1,1,1,0, 0, 0,0,1,0,1,1,0,1,0, 0, 0) ((4, 2, 2, 3, 6) 4 7) 78 7.3.6.1 (0,0,0,1,1,1,1,0,1,1,1,0,0,0, 0, 0) ((1,1,1, 2, 2) 3 5) 79 7.4.1.2 (0,1,0,1, 0,1,1,0,0,1,1,0,1,0, 0, 0) ((1, 3, 2, 2, 2) 4 7) 80 7.4.2.1 (1,0,0,1,1, 0,0,1,0,1,1,0,1,0, 0, 0) ((5, 3, 3,1, 5) 4 7) 81 7.4.3.1 (0,1,1,0,1, 0,0,1,0,1,1,0,1,0, 0, 0) ((0, 3, 3, 3,1) 3 5) 82 7.5.1.1 (1,0,0,1, 0,1,0,1,0,1,1,0,1,0, 0, 0) ((4,4, 5, 5, 3) 4 7) 83 7.7.1.1 (1,0,0,1, 0,1,1,0,0,1,1,0,1,0, 0, 0) ((3, 3, 3, 3, 3) 3 5) 84 8.1.1.1 (1,1,1,1,1,1,1,1,0, 0, 0,0,0,0, 0, 0) ((1,0,0, 0,1) 1 2) 85 8.1.2.1 (1,1,1,1,1,1,1,0,1, 0, 0,0,0,0, 0, 0) ((3,1,1,1, 2) 3 6) 86 8.1.5.1 (1,1,1,1,1,1,0,0,1,1, 0,0,0,0, 0, 0) ((2,0,1,1,1) 2 4) 87 8.1.16.1 (0,1,1,1,1,1,1,0,1,1, 0,0,0,0, 0, 0) ((0, 7, 6, 6, 5) 4 8) 88 8.1.29.1 (0,1,0,1,1,1,1,0,1,1,1,0,0,0, 0, 0) ((1, 6, 7, 5, 5) 4 8) 89 8.2.1.1 (0,1,1,1,1,1,1,1,1, 0, 0,0,0,0, 0, 0) ((0, 5, 5, 5, 3) 3 6) 90 8.2.9.2 (0,1,1,1, 0,1,1,0,0,1,1,0,1,0, 0, 0) ((1, 3, 3, 2, 2) 4 8) 91 8.2.11.1 (1,1,1,0,1, 0,0,1,0,1,1,0,1,0, 0, 0) ((3, 2, 2, 2, 5) 3 6) 92 8.2.13.1 (0,0,1,1,1,1,1,1,1,1, 0,0,0,0, 0, 0) ((0,0, 3, 3, 2) 2 4) 93 8.2.17.1 (0,0,0,1,1,1,1,1,1,1,1,0,0,0, 0, 0) ((1,1,1, 2, 3) 3 6) 94 8.2.20.1 (0,0,0,0,1,1,1,1,1,1,1,1,0,0, 0, 0) ((0,0,0,1,1) 1 2) 95 8.2.21.1 (0,0,0,1, 0,1,1,1,1,1,1,0,1,0, 0, 0) ((0,1,1,1, 2) 2 4) 96 8.3.4.1 (1,1,1,0, 0,1,1,1,0, 0, 0,1,1,0, 0, 0) ((2,1,1, 3, 2) 2 4) 97 8.3.5.1 (0,1,1,0, 0,1,1,1,1, 0, 0,1,1,0, 0, 0) ((0,4,4,1, 3) 3 6) 98 8.4.2.1 (1,0,0,0, 0,1,1,1,0,1,1,1,1,0, 0, 0) ((2, 3, 3, 2, 2) 2 4) 99 8.4.3.1 (1,1,0,0, 0, 0,1,1,0, 0,1,1,1,1, 0, 0) ((1,0,1,1,1) 1 2) 100 8.5.1.1 (1,0,0,1, 0,1,1,1,0,1,1,0,1,0, 0, 0) ((3,4,4, 4, 3) 3 6) 101 8.8.1.1 (0,1,1,0,1, 0,0,1,1, 0, 0,1,0,1,1, 0) ((0,1,1,1,1) 1 2) Например, в [11, 14] предлагается использовать векторы параметров Чоу. Если f - булева функция от n переменных, то, сложив как векторы все наборы x, на которых f (x) = 0, получим целочисленный n-мерный вектор (si, s2,... , sn). Дополнив его нулевой координатой s0 = |f-1(0)|, равной числу наборов x, на которых f (x) = 0, получим (n + 1)-мерный вектор параметров Чоу. В работе [11] приведено одно из доказательств того, что если две пороговые функции различны, то они имеют разные векторы параметров Чоу. Булевы функции от двух переменных f = x1 + x2 и g = x1 + x2 + 1 имеют одинаковые векторы параметров Чоу, в то время как в работе [9] доказано, что любая линейная функция k-значной логики принадлежит классу АПФ. Поэтому использование подхода на основе векторов параметров Чоу невозможно. В связи с тем, что ограничение на коэффициенты линейной формы не получено и гарантии, что на компьютере построены все представители геометрических типов булевых функций от четырёх переменных, нет, для оставшихся 51 геометрических типов (табл. 3) выдвигается гипотеза об их непринадлежности классу АПФ. Т а б л и ц а 3 Геометрические типы булевых функций от четырёх переменных, по отношению к которым выдвигается гипотеза об их непринадлежности к классу АПФ Номер a.b.c.d Вектор-столбец представителя геометрического типа a.b.c.d Номер a.b.c.d Вектор-столбец представителя геометрического типа a.b.c.d 4.2.1.3 (1,1,0, 0, 0, 0,0,1,1, 0, 0,0,0, 0, 0,0) 4.2.2.2 (1, 0, 0,1,0,0, 0,1,1,0,0, 0, 0,0,0,0) 5.2.2.1 (1,1,0,1, 0,1,1,0, 0, 0, 0,0,0, 0, 0,0) 5.2.2.2 (1,1,1, 0,0,0, 0,1,1,0,0, 0, 0,0,0,0) 5.2.4.1 (1,0,0,1, 0,1,0,1,1, 0, 0,0,0, 0, 0,0) 5.3.1.2 (0,1, 0,1,1,0, 0,1,1,0,0, 0, 0,0,0,0) 5.3.1.5 (0,0,0, 0,1,1,0,1, 0,1,1,0,0, 0, 0,0) 5.3.2.2 (0, 0, 0,1,1,0,1, 0,1,1,0, 0, 0,0,0,0) 6.1.4.1 (1,1,1,1, 0,1,1,0, 0, 0, 0,0,0, 0, 0,0) 6.1.4.2 (1,1,1,1,0,0, 0,1,1,0,0, 0, 0,0,0,0) 6.2.1.1 (0,1,1,1, 0,1,0,1,1, 0, 0,0,0, 0, 0,0) 6.2.2.1 (1,1,1, 0,1,0, 0,1,1,0,0, 0, 0,0,0,0) 6.2.4.1 (0,0,1,1,1,1,0,1,1, 0, 0,0,0, 0, 0,0) 6.2.6.1 (1, 0, 0,1,0,1,1,1,1,0,0, 0, 0,0,0,0) 6.2.8.2 (0,0,0, 0,1,1,0,1,1,1,1,0,0, 0, 0,0) 6.2.8.4 (0,1,1, 0,0,0,1,1,1,1,0, 0, 0,0,0,0) 6.2.8.5 (0,1,1, 0,1, 0,1,0,1,1, 0,0,0, 0, 0,0) 6.3.1.1 (0, 0, 0, 0,1,1,1,1,0,1,1, 0, 0,0,0,0) 6.3.2.1 (1,1,0, 0, 0,1,1,0, 0,1,1,0,0, 0, 0,0) 6.3.2.2 (0,1,1,1,1,0, 0,1,1,0,0, 0, 0,0,0,0) 6.3.4.2 (0,0,1, 0,1,1,0,1, 0,1,1,0,0, 0, 0,0) 6.4.1.1 (1, 0, 0,1,0,1,1, 0,1,1,0, 0, 0,0,0,0) 6.4.2.3 (0,0,0,1,1, 0,0,1, 0,1,1,0,1, 0, 0,0) 7.1.4.1 (1,1,1, 0,1,0,1, 0,1,1,0, 0, 0,0,0,0) 7.1.6.1 (1,1,1,1,1, 0,0,1,1, 0, 0,0,0, 0, 0,0) 7.1.12.1 (1,1,1, 0,0,1,1, 0,0,1,1, 0, 0,0,0,0) 7.1.15.3 (0,1,1,1,1, 0,1,0,1,1, 0,0,0, 0, 0,0) 7.2.2.1 (1,1, 0,1,0,1,1, 0,1,1,0, 0, 0,0,0,0) 7.2.4.1 (0,1,1,1,1,1,0,1,1, 0, 0,0,0, 0, 0,0) 7.2.4.2 (1,1, 0, 0,1,1,1, 0,0,1,1, 0, 0,0,0,0) 7.2.15.2 (0,1,1, 0,1, 0,1,1,1,1, 0,0,0, 0, 0,0) 7.3.1.1 (1, 0, 0, 0,1,1,1,1,0,1,1, 0, 0,0,0,0) 7.3.2.1 (1,1,0,1, 0,1,1,0, 0,1,1,0,0, 0, 0,0) 7.3.4.2 (1, 0, 0,1,1,1, 0,1,0,1,1, 0, 0,0,0,0) 7.3.6.2 (1,0,0, 0, 0,1,1,1,1, 0, 0,1,1, 0, 0,0) 7.4.1.1 (1, 0, 0,1,1,1,1, 0,0,1,1, 0, 0,0,0,0) 8.1.3.1 (1,1,1,1,1,1,0,1,1, 0, 0,0,0, 0, 0,0) 8.1.6.1 (1,1,1,1,1,0,1, 0,1,1,0, 0, 0,0,0,0) 8.1.10.1 (1,1,1, 0,1, 0,1,1,1,1, 0,0,0, 0, 0,0) 8.1.17.1 (1,1,1,1,0,1,1, 0,0,1,1, 0, 0,0,0,0) 8.1.20.1 (1,0,1, 0,1,1,0,1,1,1,1,0,0, 0, 0,0) 8.1.22.1 (1, 0,1,1,1,1,1, 0,1,1,0, 0, 0,0,0,0) 8.1.24.1 (1,0,0, 0,1,1,1,1,1,1,1,0,0, 0, 0,0) 8.1.30.2 (0,1,1, 0,1,1,1, 0,1,1,1, 0, 0,0,0,0) 8.2.6.1 (1,1,0,1,1,1,1,0, 0,1,1,0,0, 0, 0,0) 8.2.9.1 (1, 0, 0,1,1,1,1, 0,1,1,1, 0, 0,0,0,0) 8.2.11.2 (0,1,1, 0,1, 0,0,1,1,1,1,0,1, 0, 0,0) 8.2.12.2 (1,1, 0, 0,0,1,1,1,1,0,0,1,1,0,0,0) 8.2.21.2 (1,0,0,1, 0,1,1,1,1,1,1,0,0, 0, 0,0) 8.3.2.1 (1, 0, 0,1,1,1,1,1,0,1,1, 0, 0,0,0,0) 8.4.1.1 (1,1,0,1, 0,1,1,0, 0,1,1,0,1, 0, 0,0) Вероятно, для каждого геометрического типа можно доказать его непринадлежность классу АПФ, но случай булевых функций от трёх переменных [9] показал, что данный процесс весьма затруднителен. 2. Представление подстановок алгоритма блочного шифрования Магма линейными комбинациями АПФ В стандарте ГОСТ Р 34.12-2015 [6] в качестве нелинейного биективного преобразования выступает набор подстановок ni, i = 0,1, 2,... , 7. Они заданы в виде массивов по = (12, 4, 6, 2,10, 5,11, 9,14, 8,13, 7, 0, 3,15,1); п1 = (6,8, 2, 3, 9,10, 5,12,1,14, 4, 7,11,13,0,15); П2 = (11, 3, 5, 8, 2,15,10,13,14,1, 7, 4,12, 9, 6, 0); пз = (12, 8, 2,1,13, 4,15, 6, 7,0,10, 5, 3,14,9,11); п4 = (7,15, 5,10, 8,1,6,13, 0,9, 3,14,11, 4, 2,12); П5 = (5,13,15, 6, 9, 2,12,10,11, 7,8,1, 4, 3,14, 0); п6 = (8,14, 2, 5, 6, 9,1,12,15,4,11, 0,13,10, 3, 7); п7 = (1, 7,14,13, 0, 5,8, 3, 4,15,10, 6, 9,12,11, 2). Представим подстановки в виде координатных функций, обозначив через /3, /2, /1, /0 координатные функции подстановки ni, i = 0,... , 7, от старших разрядов к младшим соответственно: / n 0 0 0 1 0 1 1 1 1 1 0 0 0 1 0) //з\ 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1) /0 1 1 1 0 0 1 0 0 1 0 1 1 0 0 1 0 /2i 1 0 0 0 0 0 1 1 0 1 1 1 0 101 по = /0 = 0 0 1 1 1 0 1 0 1 0 0 1 0 1 1 0 ; ni - /1 = 1 0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 /) \0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 1 0) U) 0 0 0 1 1 0 1 0 1 0 0 1 1 101 f/i\ /1 0 0 1 0 1 1 1 1 0 0 0 1 1 0 /33 1 1 0 0 1 0 1 0 0 0 1 0 0 11 Л /2 0 0 1 0 0 1 0 1 1 0 1 1 1 0 1 0 /23 1 0 0 0 1 1 1 1 1 0 0 1 0 100 П2 = /2 = 1 1 0 0 1 1 1 0 1 0 1 0 0 0 1 0 ; пз - /3 = 0 0 1 0 0 0 1 1 1 0 1 0 1 1 0 1 U2) 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1) /о3) 0 0 0 1 1 0 1 0 1 0 0 1 1 0 1 1/ / 0 1 0 1 1 0 0 1 0 1 0 1 1 0 0 /35 0 1 1 0 1 0 1 1 1 0 1 0 0 0 1 0\ /2 1 1 1 0 0 0 1 1 0 0 0 1 0 1 0 1 /25 1 1 1 1 0 0 1 0 0 1 0 0 1 010 П 4 = /4 = 1 1 0 1 0 0 1 0 0 0 1 1 1 0 1 0 ; п5 = /5 = 0 0 1 1 0 1 0 1 1 1 0 0 0 1 1 0 W) 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 0 0) U) 1 1 1 0 1 0 0 0 1 1 0 1 0 100 / 1 1 0 0 0 1 0 1 1 1 1 0 1 1 0 / 0 0 1 1 0 0 1 0 0 1 1 0 1 1 1 04 /26 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 /7 0 1 1 1 0 1 0 0 1 1 0 1 0 100 П6 = /6 = 0 1 1 0 1 0 0 0 1 1 1 0 0 1 1 1 ; п7 - /7 = 0 1 1 0 0 0 0 1 0 1 1 1 0 0 1 1 /о6 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 1 Uv 1 1 0 1 0 1 0 1 0 1 0 0 1 010 Задача данного пункта - представить подстановки п0,п1,...,п7 через линейные комбинации функций из класса АПФ, использовав при этом для каждой подстановки минимальное количество таких функций, а значит, и минимальное количество пороговых элементов при технической реализации. Минимальное количество функций, через линейные комбинации которых можно реализовать подстановки, равно 4. В этом случае соответствующие АПФ лежат в подпространстве, порождённом координатными функциями подстановок. На первом этапе была исследована представимость каждой подстановки через АПФ линейных комбинаций координатных функций. Результаты приведены в табл. 4. Таблица 4 Представление линейных комбинаций координатных функций подстановок ГОСТ Р 34.12-2015 через АПФ ni Линейные ком Структура АПФ, ni Линейные ком- Структура АПФ, бинации коорди задающей линейную бинации коордизадающей линейную натных функций комбинацию коорнатных функций комбинацию координатных функций динатных функций f (1) ((0, 3,1, 3, 0) 2 4) П4 / (4) /3 ((0, 2,1, 3,0) 2 4) f w m f w m f (1) f3 Ф f2 Ф f0 ((7, 5,1, 3, 6) 4 8) /34) Ф /2(4) Ф /1(4) ((0, 5, 5, 6, 2) 4 8) /31) Ф /2(1) ((6,1, 3, 6, 3) 4 8) /3 Ф /2 Ф /0 ((0, 6,1, 6, 3) 4 8) /2(1) ф /21) ((6, 3, 3,1, 6) 4 8) П5 /25) Ф /05) ((0, 3, 2, 5, 7) 4 8) П2 f (2) J 2 ((0, 3, 7, 2, 5) 4 8) /25) Ф /05) ((6, 7, 5, 2, 6) 4 8) /((2) Ф /02) ((1, 2, 5, 6, 3) 4 8) /35) Ф /15) ((5, 5, 5, 7, 2) 4 8) /32) Ф /02) ((7, 2, 5, 2,1) 4 8) /(5) m /(5) m /(5) /3 Ф /2 Ф /0 ((0, 7, 5, 3, 2) 4 8) пз /33) Ф /23) ((6, 7, 2, 3, 6) 4 8) П6 /36) Ф /1(6) ((7, 2, 7, 5, 2) 4 8) П7 / (7) J0 ((4, 3, 7, 6, 5) 4 8) /36) Ф /16) Ф /16) ((6,1, 6, 5, 6) 4 8) Из табл.4 видно, что функции /3^, /22), /34), /07) являются алгебраическими пороговыми и имеют следующие задания: /3(1) = 1 ^ r4 (3xi + x2 + 3x3) ^ 2, /22) = 1 ^ r8 (3xi + 7x2 + 2x3 + 5x4) ^ 4, /3(4) = 1 ^ r4 (2ж1 + x2 + 3x3) ^ 2, /07) = 1 ^ r8 (4 + 3x1 + 7x2 + 6x3 + 5x4) ^ 4. Важно отметить, что функции /31) и /34) фиктивно зависят от переменной x4 (x4 - старший бит входного числа). Последнее влечёт ухудшение перемешивающих свойств нелинейного слоя. У подстановки п5 найдено 4 независимых линейных комбинаций, представимых функциями из класса АПФ. Найдём выражение координатных функций через соответствующие АПФ. Для этого разрешим относительно /05), /15), /2, /35) следующую систему: /25) Ф /(5) /о \ (5) f Vo) \ /25) Ф /15) (5) /35) Ф /(5) /2 (5) ф /25) Ф /05) / (5) V v3) I / (5) /3 где функции ^05), ^15), #, ^35) задают соответствующие линейные комбинации из табл. 4: (5) 1 ^ r8 (3x1 + 2x2 + 5x3 + 7x4) ^ 4, ^15) = 1 ^ r8 (6 + 7x1 + 5x2 + 2x3 + 6x4) ^ 4, ^25) = 1 ^ r8 (5 + 5x1 + 5x2 + 7x3 + 2x4) ^ 4, ^35) = 1 ^ r8 (7x1 + 5x2 + 3x3 + 2x4) ^ 4. Решение системы и подстановка в целом задаются следующим образом: ( /35) \ ( V5) Ф v(5) \ (5) v05) Ф v35) v05) ф v25) Ф v35) / /1( (5) v05) ф v15) v25) V /05) ) П5 v25) ф v35) v35) Данное представление позволяет реализовать подстановку, используя пороговые элементы, поскольку модульное сложение также принадлежит классу АПФ. Отметим, что структуры АПФ в табл. 4 получены с помощью структур, найденных в табл. 2. Основная сложность использования данной таблицы заключается в определении преобразований, переводящих представителя в заданную функцию геометрического типа. Изменения структуры при действии указанных преобразований эквивалентности описаны в [9]. Определение самого геометрического типа не вызывает затруднений при использовании оригинального каталога геометрических типов, опубликованного в [10]. У остальных подстановок подпространство, порождённое координатными функциями, не содержит базис из класса АПФ. В предположении, что все геометрические типы из табл. 3 не являются АПФ, получаем, что только одна из восьми подстановок реализуется через линейные комбинации четырёх АПФ. Для остальных подстановок выбиралась некоторая функция из класса АПФ произвольного веса, не лежащая в подпространстве, порождённом координатными функциями. Получив базис из пяти функций, мы искали АПФ из расширенного подпространства. Из линейных комбинаций, принадлежащих классу АПФ, составлялась расширенная система, аналогичная полученной при задании подстановки п5, и решалась относительно координатных функций подстановки. Благоприятным исходом была разрешимость данной системы и соответственно представление подстановки через линейные комбинации пяти АПФ. Пятая функция выбиралась так, чтобы две или три координатные функции при сложении с ней образовывали функцию из класса АПФ. Один из таких способов - взять произведение двух координатных функций. Произведение функций и их дополнение до исходных имеют вес четыре, а значит, с высокой вероятностью мы получим три функции из класса АПФ. Высокая вероятность обусловливается тем, что из всех 19 геометрических типов, представители которых имеют вес 4, только 3 типа не принадлежат классу АПФ. Кроме того, функция веса 4 не лежит среди линейных комбинаций координатных функций, а значит, линейно не выражается через них. Второй подход - выбор системы вершин куба, на которых пятая функция принимает единичные значения, так, чтобы при её булевом суммировании (в случае, если эта функция из класса АПФ) с координатными функциями подфункции результирующих функций не были эквивалентны f * - функции от трёх переменных, которая не представляется через АПФ. Если эта функция имеет вес менее 8, то она также линейно не выражается через линейные комбинации координатных функций. Второй подход обеспечивает получение функций из геометрических типов, перечисленных в табл. 2 и 3. С учётом того, что количество геометрических типов в табл. 2 преобладает, велика вероятность набрать необходимое количество линейных комбинаций из класса АПФ. Применение предложенных подходов позволило получить задания всех оставшихся подстановок через линейные комбинации пяти АПФ, а если верно предположение, что в табл.3 нет геометрических типов из класса АПФ, то данные представления минимальны по количеству используемых функций. Ниже приведены реализации подстановок через АПФ без подробного описания способа получения пятой функции: ф°0) : ((5, 4, 7, 3, 2); 5; 8) ф(10) : ((1, 5, 5, 7, 2); 4; 8) ф20) : ((1, 6, 5, 3,1); 6; 8) ф30) : ((0,1,1, 3, 2); 3; 5) ф0) : ((0, 3,1, 3, 3); 2; 5) ^ е ^ ^ е ^ V ^(11) е ^ у (2) (2) (2) (2) (2) П2 = (3) (3) (3) (3) (3) (3) ^3 Пз = (4) (4) (4) (4) (4) 4 ( ^02) е ^2) \ ^02) ^22) е ^2) \ ^22) е # е

Ключевые слова

алгебраические пороговые функции, геометрические типы, подстановки, блочные шифры, algebraic threshold functions, geometric types, substitutions, block ciphers

Авторы

ФИООрганизацияДополнительноE-mail
Сошин Данил АндреевичНИИ «Квант»сотрудникdanil_re@list.ru
Всего: 1

Ссылки

Дертоузос М. Пороговая логика. М.: Мир, 1967.
Морага К. Многозначная пороговая логика // Оптические вычисления. М.: Мир, 1993. С.162-182.
Никонов В. Г., Сидоров Е. С. О способе построения взаимно однозначных отображений при помощи квазиадамаровых матриц // Вестник Московского государственного университета леса - Лесной вестник. 2009. №2(65). С. 155-157.
Никонов В. Г., Сошин Д. А. Геометрический метод построения сбалансированных k-знач-ных пороговых функций и синтез подстановок на их основе // Образовательные ресурсы и технологии. 2014. №2(5). С. 76-80.
Сошин Д. А. Построение подстановок на основе пороговых функций многозначной логики // Прикладная дискретная математика. 2016. №2(32). С. 20-32.
ГОСТ Р 34.12-2015 Информационная технология. Криптографическая защита информации. Блочные шифры. М.: Стандартинформ, 2015.
Dmukh A. A, Dygin D. M., and Marshalko G. B. A lightweight-friendly modification of GOST block cipher // Математические вопросы криптографии. 2014. Т. 5. №2. С. 47-55.
Сошин Д. А. Конструктивный метод синтеза сбалансированных k-значных алгебраических пороговых функций // Comp. Nanotechnol. 2015. №4. С. 31-36.
Сошин Д. А. Представление геометрических типов булевых функций от трех переменных алгебраическими пороговыми функциями // Прикладная дискретная математика. 2016. №1(31). С. 32-45.
Никонов В. Г. Классификация минимальных базисных представлений всех булевых функций от четырех переменных // Обозрение прикладной и промышленной математики. Сер. Дискретная математика. 1994. Т. 1. №3. С. 458-545.
Зуев Ю. А. Комбинаторно-вероятностные и геометрические методы в пороговой логике // Дискретная математика. 1991. Т. 3. №2. С. 47-57.
Ирматов А. А. Оценки числа пороговых функций // Дискретная математика. 1996. Т. 8. №4. С. 92-107.
Ирматов А. А., Ковиянич Ж. Д. Об асимптотике логарифма числа пороговых функций K-значной логики // Дискретная математика. 1998. Т. 10. №3. С. 35-56.
Winder R. O. Show parametrs in threshold logic //J. Association for Computing Machinery. 1971. V. 18. No. 2. P. 265-289.
 Задание подстановок алгоритмов блочного шифрования Магма и 2-ГОСТ с помощью алгебраических пороговых функций | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/4

Задание подстановок алгоритмов блочного шифрования Магма и 2-ГОСТ с помощью алгебраических пороговых функций | ПДМ. 2016. № 3(33). DOI: 10.17223/20710410/33/4