On the representation of s-boxes in block ciphers.pdf Многие криптографические алгоритмы уязвимы к атакам по сторонним каналам, направленным на слабости в практической реализации алгоритма. В качестве мер противодействия используются методы, маскирующие входные данные так, чтобы вычисления не зависели от них в явном виде. В [1] предложен следующий способ маскирующей реализации S-блока. Рассмотрим S-блок n x n. Пусть x = (x1,... ,xn), где xj G Z2. Рассмотрим векторную функцию S : Zn ^ Zn, S = (/1,...,/n), где /1,...,/n — булевы функции от n переменных. r Разбиваем переменные xj каждую на r булевых переменных: xj = Е xj. Пусть j=1 v = (x11,... ,xnr). Разбиваем функцию S на r векторных функций Sj : Znr ^ Zn так, чтобы выполнялось S(x) = Е Sj(v). Такое разбиение векторной функции S обоj значим P(S). Введём следующие условия для разбиения. 1. Неполнота: блок Sj не должен зависеть от переменных xkj, k = 1,..., n. 2. Взаимная однозначность: функция S* : Znr ^ Znr, S* = (S1,... , Sr), является взаимно однозначной. Разбиение P(S), удовлетворяющее этим двум условиям, называется допустимым. Две векторных функции S и S называются аффинно эквивалентными, если существует пара невырожденных аффинных преобразований A и B, таких, что S = BoSoA. Отношение аффинной эквивалентности разбивает множество всех взаимно однозначных S-блоков на непересекающиеся классы. Множество S-блоков 3 x 3 содержит 4 класса, A], Q1, Q], Q]j. В таблице приведены их представители. Класс Представитель a1 (x,y,z) q1 (x,y,xy + z) q2 (x, y + xz, z + xy + xz) q3 (xy + xz + yz, x + y + xy + yz, x + z + yz) Теорема 1 [1]. Если для некоторой векторной функции существует допустимое разбиение, то для любой аффинно эквивалентной ей функции также существует допустимое разбиение. Построить разбиение и добиться выполнения условия неполноты нетрудно; сложность представляет свойство взаимной однозначности, которое требует отдельной проверки для каждого полученного разбиения. Для классов A1, Q и Q3 допустимые разбиения найдены в работе [1]. Чтобы достигнуть взаимной однозначности, в функции из разбиения S-блока добавляются пары так называемых корректирующих слагаемых, комбинацией которых можно получить всевозможные разбиения P (S), удовлетворяющие условию 1. Для S-блоков 3 х 3 существует всего 54 таких слагаемых. Рассмотрим, например, S-блок (x,y + xz,z + xy + xz) из класса Q2 и его разбиение P(S), удовлетворяющее условию неполноты: #1 (v) = (x2, У2 + x2Z2 + x2Z3 + x3Z2, Z2 + x2y2 + x2y3 + x3y2 + x2Z2 + x2Z3 + x3Z2); 52 (v) = (x3,y3 + x3Z3 + x1Z3 + x3 Z1,Z3 + x3y3 + x1y3 + x3y1 + x3Z3 + x1 Z3 + x3Z1); 53 (v) = (x1,y1 + x1Z1 + x1Z2 + x2 Z1,Z1 + x1y1 + x^2 + x2y1 + x1Z1 + x1 Z2 + x2Z1). Условие 2 не выполняется. Однако при добавлении следующей комбинации корректирующих слагаемых (выделены подчеркиванием) разбиение становится допустимым: #1(v) = (x2, y2+x2Z2+x2Z3+x3Z2+Z2, Z2+x2y2+x2y3+x3y2+x2Z2+x2Z3+x3 Z2+y3+Z2); S2 (v)=(x3, y3+x3Z3+x1Z3+x3Z1+Z1, Z3+x3y3+x1y3+x3y1+x3Z3+x1Z3+x3Z1+y3+Z1); S3(v) = (x1, y1+x1Z1+x1 Z2+x2Z1+Z1+Z2, Z1+x1y1+x1y2+x2y1+x1Z1+x1Z2+x2Z1+Z1+Z2). Для класса Q3 допустимое разбиение так и не было найдено, а большой перебор комбинаций корректирующих переменных делает поиск трудным, поэтому в [1] авторы обозначили открытый вопрос: существует ли для S-блоков из класса Q^ допустимое разбиение? Пусть S = (f1,..., /n), S : Zn ^ Zn и P (S) — непосредственное разбиение S-бло-ка S на r частей #i = (/1i,... , /ni). Рассмотрим векторную функцию F = (f11,... , Zn1,...,/1r,... , /nr). Будем говорить, что функция Cf = (С11, ... , Cn1,... , C1r,..., Cnr), cij : Znr ^ Z2 — корректирующая функция для F, если функция F + CF обладает следующими свойствами: r 1) /i = E (/ij + cij) для каждого i = 1,..., n; j=1 2) /ij + cij не зависит от переменных x1j,...,xnj для каждого i = 1,...,n, j = 1,...,r. Пусть k Е {1,...,nr}, (i1j1,...,ikjk) —набор индексов длины k из множества {11,... , n1,... , 1r,... , nr}. Определим множество Cik1j1)... ifcjk = {Cf : (/i1j1 + Ci1j1,... , /ifcjfc + Cikjk ) — сбалансированная функция из Znr в Zkk}. Пусть C ^ П П C'i1j1,...,ikjk . k i1j1,...,ikjk Теорема 2. Функция F + Cf взаимно однозначна, если и только если Cf Е C. Теорема 2 даёт алгоритм отыскания возможного допустимого разбиения, так как для любой функции CF Е C разбиение S1 = (/11 + c11,..., /n1 + cn1),... , Sr = (/1r + c1r, ... , /nr + cnr) по теореме 2 является допустимым. Для S-блока из Q3 доказано, что множество C пусто. Следовательно, не существует допустимого разбиения данного S-блока, и доказана следующая Теорема 3. Для S-блоков из класса Q3 не существует допустимого разбиения.

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