The presentation of magma and 2-gost block cipher semibyte substitutions by algebraic threshold functions.pdf В работе [1] вводится новый класс функций, который назван классом алгебраических пороговых функций. Определение 1. Функция k -значной логики yn • -^ ^fc называется алгебраической пороговой, если существуют целочисленные наборы (c0, c1,..., cn), (b0,b1,..., bk) и модуль m, такие, что для любого a G {0,... , k - 1} выполняется /n (xi, Х2,..., Xn) = a & ba ^ rm (co + C1X1 + C2X2 +-----+ CnXn) < ba+1, где rm (y) - функция взятия остатка при делении целого числа y на модуль m (rm(y) G {0,1,..., m - 1}); Пк = {0,1,...,k - 1}; Щ = ^ x ^k x • • • x . 4-v-' n Тройку ((co, c1, ... ,cn); (b0,b1,... ,bk); m ) назовём структурой алгебраической пороговой функции /!к. В [1] проведено исследование вопроса реализации булевых функций трёх переменных функциями из класса АПФ. Для этого доказана замкнутость данного класса относительно операций перестановки переменных, инвертирования переменных в смысле Лукашевича и инвертирования функции (геометрическая замкнутость). Геометрическим типом функции / назовём класс эквивалентности относительно указанных преобразований. Для булевых функций от трёх переменных доказано, что только геометрический тип с представителем /(x1,x2,x3) = x1x3 V х2Хз не задаётся через АПФ. Для булевых функций от четырёх переменных существует ровно 222 геометрических типа, и из них 70 представителей содержат в качестве подфункции функцию от трёх переменных, не имеющую представление в виде АПФ, и поэтому не относятся к классу АПФ. Для 99 из оставшихся 152 геометрических типов найдено задание в виде АПФ. Важно отметить, что класс АПФ замкнут относительно фиксации переменных и включает в себя все линейные функции k-значной логики. В стандарте ГОСТ Р 34.12-2015 [2] в качестве нелинейного биективного преобразования выступает набор подстановок , i = 0,... , 7. Обозначим через /3г), /2г), /1^, /0(i) координатные функции подстановки от старших разрядов к младшим соответственно. У каждой подстановки рассмотрены линейные комбинации координатных функций, и те, для которых нашлось АПФ-представление, приведены в табл. 1 со своими структурами. Таблица 1 Представление линейных комбинаций координатных функций подстановок ГОСТ Р 34.12-2015 через АПФ Лин. комбинации Структура АПФ f (1) J 3 ((0, 3,1, 3, 0) (0, 2, 4) 4) f W m f W m f (1) J 3 ф J 2 ф J 0 ((7, 5,1, 3, 6) (0,4, 8) 8) /3(1) ф /2(1) ((6,1, 3, 6, 3) (0,4, 8) 8) /2(1) ф /21) ((6, 3, 3,1, 6) (0,4, 8) 8) п2 / (2) J 2 ((0, 3, 7, 2, 5) (0,4, 8) 8) /12) ф /02) ((1, 2, 5, 6, 3) (0,4, 8) 8) /32) ф /02) ((7, 2, 5, 2,1) (0,4, 8) 8) п3 /33) ф /23) ((6, 7, 2, 3, 6) (0,4, 8) 8) /(3) m /(3^ /(3) J3 ф J2 ф J0 ((3, 2, 7, 2, 5) (0,4, 8) 8) п7 / (7) J0 ((4, 3, 7, 6, 5) (0,4, 8) 8) п Лин. комбинации Структура АПФ / (4) /3 ((0, 2,1, 3,0) (0, 2,4) /34) ф /24) ф /14) ((0, 5, 5, 6, 2) (0,4, 8) /(4) m /(4) m /(4) /3 ф /2 ф /0 ((0, 6,1, 6, 3) (0,4, 8) /25) ф /05) ((0, 3, 2, 5, 7) (0,4, 8) /25) ф /05) ((6, 7, 5, 2, 6) (0,4, 8) /35) ф /15) ((5, 5, 5, 7, 2) (0,4, 8) / (5) m / (5^ / (5) /3 ф /2 ф /0 ((0, 7, 5, 3, 2) (0,4, 8) /36) ф /16) ((7, 2, 7, 5, 2) (0,4, 8) /36) ф /2(6) ф /16) ((6,1, 6, 5, 6) (0,4, 8) 4 8 8 8 8 8 8 8 8 п п п Из табл. 1 видно, что функции /3^, /2(2), /34), /о7 являются алгебраическими пороговыми и имеют следующие задания: /з(1) = 1 ^ Г4 (3x1 + 1x2 + 3хз) ^ 2, /2(2) = 1 ^ Г8 (3X1 + 7x2 + 2хз + 5x4) ^ 4, /з(4) = 1 ^ Г4 (2x1 + 1x2 + 3x3) ^ 2, /07) = 1 ^ Г8 (4 + 3x1 + 7x2 + 6x3 + 5x4) ^ 4. Важно отметить, что функции /(1) и /(4) фиктивно зависят от переменной x4 (x4 - старший бит входного числа). Последнее влечёт ухудшение перемешивающих свойств нелинейного слоя. Подстановка п5 представляется в виде каскадного соединения АПФ ( /35) \ ( V(0) ф V(3) \ (5) (2) / /1( V (0) ф V V V (1) ф (2) (5) (3) V V (о) „ v(3) V(2) ф V v(3) /05)) / V Функции v(0) , V(1), V(2), V(3) задают соответствующие линейные комбинации /25) ф /25) ф /0(5) из табл. 1 следующим образом: ф /05), /2(5) ф /15), /35) ф /25), (5) /3 (1) 1 ^ Г8(6 + 7x1 + 5x2 + 2x3 + 6x4) ^ 4, V(0) = 1 ^ Г8(3x1 + 2x2 + 5x3 + 7x4) ^ 4, V V(2) = 1 ^ Г8(5 + 5x1 + 5x2 + 7x3 + 2x4) ^ 4, v(3) = 1 ^ Г8(7x1 + 5x2 + 3x3 + 2x4) ^ 4. В [3] предложен алгоритм блочного шифрования 2-ГОСТ, являющийся модификацией шифрсистемы ГОСТ 28147-89, отличающийся от последней лишь алгоритмом развертывания ключа, а также тем, что набор S-боксов фиксирован: по = п1 = п2 = = п3 = п', п4 = п5 = Пб = п7 = п", где п' и п" заданы нижними строками подстановок (табл. 2). Т а б л и ц а 2 Задание подстановок 2-ГОСТ i 0 1 2 3 4 5 6 7 8 9 A B C D E F 6 A F 4 3 8 5 0 D E 7 1 2 B C 9 n"(i) E 0 8 1 7 A 5 6 D 2 4 9 3 F C B В результате анализа подстановок п' и п'' каждую из них удалось задать через линейные комбинации пяти АПФ f fH\ f2'' f1'' VfOV ( V1 ф V2 \ V1 ф V3 V1 ф V4 V V4 ф V5 У g1 ф g2 gaф g4 ga g5 f2' f1' Vf0 7 п п где функции g1,g2,g3,g4,g5, v1, v2, v3, v4, v5 - алгебраические пороговые: g1 = 1 ^ rg (x1 + 5x2 + 2x3 + 2x4) ^ 6, V1 =1 g2 = 1 ^ r7 (5x1 + 5x2 + x3 + 6x4) ^ 2, V2 =1 g3 = 1 ^ r8 (7 + 6x1 + 5x2 + 6x3 + x4) ^ 4, V3 =1 g4 = 1 ^ r8 (2 + 5x1 + 7x2 + 3x3 + 2x4) ^ 4, V4 =1 g5 = 1 ^ r8 (3 + 5x1 + x2 + 2x3 + 3x4) ^ 4, V5 1 ^ r8 (3x1 + 2x2 + 2x3 + x4) ^ 4. Здесь x1 -младший бит входного числа, x4 - старший. Класс АПФ сохраняет простоту реализации функций, основная сложность которой сводится к подсчёту скалярного произведения, как и для пороговых функций.

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