Применение системы Sage для поиска алгебраической иммунности булевых функций и отображений

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Применение системы Sage для поиска алгебраической иммунности булевых функций и отображений

А.Н. Благовисная, И.О. Симуськова Оренбургский государственный университет

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

Функции или их системы, применяемые при синтезе криптографических объектов, называются криптографическими функциями. Развитие методов и средств криптографического анализа привело к формулировке ряда требований, предъявляемых к криптографическим функциям. Эти требования получили название криптографических свойств. Булевы функции, удовлетворяющие специальным криптографическим характеристикам, вносят существенный вклад в стойкость криптографических алгоритмов. Исследование криптографических характеристик, методов и алгоритмов создания булевых функций с криптографическими характеристиками являются актуальными задачами современной криптографии.

Основным свойством булевых функций, характеризующим способность шифра противостоять алгебраическим атакам, является алгебраическая иммунность. Существует множество публикаций как отечественных, так и зарубежных авторов, посвященных различным проблемам теории и практики применения криптографических булевых функций. В статьях, монографиях и книгах, в которых рассматриваются вопросы криптографических приложений булевых функций, отражаются следующие направления исследований, связанные с понятием алгебраической иммунности:

- получение оценок и разработка алгоритмов вычисления значения алгебраической иммунности булевых функций;

- исследование оптимальных сочетаний криптографических свойств булевых функций;

- разработка методов и алгоритмов построения криптографических булевых функций с оптимальными сочетаниями свойств, включая алгебраическую иммунность;

- реализация алгебраических атак на криптографические конструкции.

Рассмотрим булеву функцию f от n переменных. Булева функция g от n переменных называется аннигилятором функции f, если fg=0.

Алгебраической иммунностью AI(f) булевой функции f называется минимальное число d такое, что существует булева функция g (аннигилятор) степени d, не тождественно равная нулю, для которой выполняется одно из равенств или [6].

Для создания криптографических булевых функций важно уметь находить значение алгебраической иммунности булевой функции.

Известно, что для любой булевой функции от n переменных [6].

В работах [1, 2, 5, 6] описаны алгоритмы, позволяющие получать значения алгебраической иммунности булевых функций.

Продемонстрируем поиск алгебраической иммунности для функции .

Так как , то нам достаточно выяснить, существуют ли аннигиляторы g для булевой функции f, степень которых . Представим функцию g в виде , где .

По определению

(1)

(2)

Выясним, при каких выполняются данные соотношения.

В левой части равенства (1) раскроем скобки и приведем подобные слагаемые. Получим

(3)

Значения , при которых равенство (3) является верным, найдем из системы уравнений:

(4)

На данном этапе поиска значения алгебраической иммунности достаточно найти хотя бы одно ненулевое решение системы (4) или доказать, что система (4) имеет единственное тривиальное решение.

Система (4) имеет нетривиальные решения. Например, , , , , . Это означает, что существует аннигилятор, степень которого равна 1. Итак, алгебраическая иммунность булевой функции равна 1.

Исследование криптографических булевых функций невозможно без применения программных средств, позволяющих автоматизировать процессы нахождения числовых характеристик булевой функции. К таким программным средствам относят математические пакеты, имеющие широкий спектр возможностей для работы в различных областях математики: Maple, Matlab, REDUCE, MACSYMA, MuPAD и другие. Математические системы данного типа включают в себя большое количество средств работы с различными математическими объектами, в том числе позволяют организовать работу с многочленами и осуществлять поиск решения системы алгебраических уравнений.

Среди математических пакетов существует бесплатное и доступное математическое программное обеспечение, например, система компьютерной алгебры Sage, относящаяся к свободному программному обеспечению, распространяемому по условиям лицензии GNU General Public License. Система Sage позволяет решать задачи из различных областей математики, в том числе решать задачи теории многочленов, заданных над конечными полями [4]. На данный момент нам не удалось найти доступных инструментов пакета Sage, осуществляющих процесс формирования систем булевых уравнений, получающихся в процессе выполнения некоторых этапов алгоритма поиска алгебраической иммунности. Однако решение систем линейных уравнений над конечными полями в пакете Sage осуществить возможно. В качестве примера рассмотрим решение системы булевых уравнений (4).

Так как необходимо решить однородную систему булевых уравнений, то можно задать матрицу системы одним из известных способов задания матриц над конечными полями и привести её к ступенчатому виду:

sage: M = MatrixSpace(GF(2),4,5)

sage: A = M([0,1,1,1,1, 0,0,1,1,1, 1,0,0,0,0, 0,0,1,1,1])

sage: A.rref()

В результате система Sage выдает ступенчатую матрицу в следующем виде:

[1 0 0 0 0]

[0 1 0 0 0]

[0 0 1 1 1]

[0 0 0 0 0]

Полученная матрица соответствует системе

откуда можно найти как общее, так и частное решения.

Другой подход к решению системы булевых уравнений заключается в том, чтобы найти базисные векторы пространства решений:

sage: A = matrix(GF(2),[[0,1,1,1,1], [0,0,1,1,1], [1,0,0,0,0], [0,0,1,1,1]])

sage: B = vector(GF(2),[0,0,0,1])

sage: X = A.right_kernel(basis='pivot')

sage: X

Результат выполнения данных команд следующий:

Vector space of degree 5 and 2 over Finite Field of size 2

User basis matrix:

[0 0 1 1 0]

[0 0 1 0 1]

Таким образом, можно сделать вывод о существовании ненулевых решений системы (4) и существовании аннигилятора булевой функции, степень которого равна 1.

При построении нелинейных узлов (S-блоков) блочных симметричных шифров используются криптографические булевы отображения .

Понятие алгебраической иммунности булевых функций можно обобщить на случай булевых отображений (векторных булевых функций). Более подробную информацию об обобщениях понятия алгебраической иммунности можно найти, например, в [7]. Рассмотрим определение алгебраической иммунности булевых отображений в соответствии с работой [5].

S-блок задается системой алгебраических уравнений над полем :

(5)

С системой (5) связан идеал, порожденный булевыми многочленами:

.(6)

Алгебраическая иммунность нелинейного узла блочного симметричного шифра определяется как минимальная степень многочлена из идеала .

Для вычисления алгебраической иммунности необходимо построить минимальный редуцированный базис Грёбнера идеала системы (5) и среди элементов базиса найти многочлен минимальной степени.

Продемонстрируем поиск алгебраической иммунности булевых отображений, задающих S-блок шифра Baby-Rijndael в системе Sage. Булевы функции и отображения S-блока данного шифра рассмотрены в статье [3]. Согласно восстановленным АНФ для компонентных булевых функций S-блок шифра Baby-Rijndael можно представить в виде следующей системы:

алгебраический иммунность криптографический булевый

(7)

С этой системой связан следующий идеал:

Для полученного идеала найдем минимальный редуцированный базис Грёбнера в системе Sage.

Сначала задаем кольцо многочленов и идеал системы (7):

sage: P.<x1,x2,x3,x4, y1,y2,y3,y4> = PolynomialRing(GF(2), 8, order = 'degrevlex')

sage: q = P.base_ring().order()

sage: Q = P.quotient_ring(ideal([var**q - var for var in P.gens()]))

sage: f1 = y1+x1*x2*x4+x1*x3*x4+x2*x3*x4+x2*x3+x3*x4+x2+x4

sage: f2 = y2+x1*x2*x3+x1*x3*x4+x1*x2+x2*x4+x3*x4+x1+x3+x4+1

sage: f3 = y3+x1*x2*x3+x1*x2*x4+x1*x2+x1*x4+x3*x4+x1+x4

sage: f4 = y4+x1*x2*x3+x1*x2*x4+x1*x3*x4+x2*x3*x4+ \

x1*x3+x1*x4+x2*x4+x1+x2+x4+1

sage: I = (f1,f2,f3,f4)*P

Выясняем, образует ли идеал I базис Грёбнера:

sage: I. basis_is_groebner ()

Получаем результат:

False

Таким образом, идеал системы (7) базисом Грёбнера не является.

Находим базис Грёбнера:

sage: B = I.groebner_basis(); B

В результате получаем сообщение:

Polynomial Sequence with 60 Polynomials in 8 Variables

Изучая все многочлены базиса Грёбнера, находим, что многочленом минимальной степени является многочлен степени 2. Например:

sage: B = I.groebner_basis()

sage: Q(B[56])

x1bar*x3bar + x2bar*x3bar + x3bar*x4bar + x1bar*y1bar + x4bar*y1bar + x1bar*y2bar + x1bar*y3bar + x4bar*y4bar + x2bar + x3bar + x4bar + y1bar + y2bar +1

Таким образом, алгебраическая иммунность S-блока, задаваемого системой (7), равна 2.

Заметим, что поиск алгебраической иммунности булевых функций и отображений с помощью средств системы Sage удобен для решения учебных задач, содержащих небольшое количество входных данных и направленных на понимание определений и алгоритмов поиска алгебраической иммунности. Для работы с булевыми функциями криптографических конструкций необходимы программные инструменты, реализующие работу с большими объемами данных и учитывающие специфику кольца булевых функций.

алгебраический иммунность криптографический булевый

Список литературы

1. Баев В.В. О некоторых алгоритмах построения аннигиляторов низкой степени для булевых функций // Дискретная математика. - 2006. - Т. 18. - № 3. - С. 138-151.

2. Баев В.В. Усовершенствованный алгоритм поиска аннигиляторов низкой степени для многочлена Жегалкина // Дискретная математика. - 2007. - Т. 19. - № 4. - С. 132-138.

3. Долгов В.И. Исследование криптографических свойств нелинейных узлов замены уменьшенных версий некоторых шифров / В.И. Долгов [и др.] // Прикладная радиоэлектроника. - 2009. - Т. 8. - № 3. - С.268-277.

4. Голубков А.Ю. Компьютерная алгебра в системе Sage: учебное пособие / А.Ю. Голубков, А.И. Зобнин, О.В. Соколова. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2013. - 79 с.

5. Кузнецов А.А. Алгебраический иммунитет нелинейных узлов симметричных шифров / А.А. Кузнецов [и др.] // Прикладная радиоэлектроника. - 2016. - № 4 (4). - С. 42-55.

6. Логачёв О.А. Булевы функции в теории кодирования и криптологии / О.А. Логачёв [и др.]. - М.: МЦНМО, 2012. - 583 с.

7. Покрасенко Д.П. Об алгебраической иммунности векторных булевых функций / Д.П. Покрасенко // ПДМ. Приложение. - 2015. - №8. - С. 37-39.

Размещено на Allbest.ru