Лабораторная работа № 4

“ИССЛЕДОВАНИЕ АЛГЕБРАИЧЕСКИХ И ВЕРОЯТНОСТНЫХ СВОЙСТВ КРИПТОГРАФИЧЕСКИХ ПРИМИТИВОВ”

Контрольное программное обеспечение:

• Программа, реализующая преобразование Уолша-Адамара: “ПУА”;

• Программа преобразования таблицы истинности булевой функции в алгебраическую нормальную форму: “АНФ”;

Порядок выполнения работы

1. Сгенерировать случайную подстановку, осуществляющую преобразование Y=F(X) : GF(2)ⁿ GF(2)ⁿ, для n=4, 6 или 8.

2. Определить таблицу истинности для всех БФ, реализующих подстановку: f₁(X), f₂(X), …, f_n(X) : GF(2)ⁿGF(2).

3. Осуществить преобразование таблиц истинности всех БФ и их линейных комбинаций в алгебраическую нормальную форму. При выполнении данного пункта работы следует использовать программу “АНФ”.

4. Определить степень отклонений всех БФ и их линейных комбинаций от сбалансированности (количество 0 и 1).

5. Определить нелинейность и корреляционную иммунность всех БФ и их линейных комбинаций. При выполнении данного пункта работы следует использовать программу “ПУА”. Представить графически спектр Уолша-Адамара для всех БФ.

6. Найти автокорреляционную функцию всех БФ и их линейных комбинаций. Сделать вывод о выполнении критериев строгого лавинного эффекта и распространения для подстановки в целом.

7. Определить нелинейность подстановочного преобразования в целом.

8. Сделать вывод о качестве подстановочного преобразования как криптографического примитива.

Содержание отчета

1. Количественные результаты по каждому пункту работы, представленные в табличном или графическом виде.

2. Выводы по каждому пункту работы.

Приложение 1. Сведения из теории

Преобразование информации, осуществляемое криптографическими примитивами, можно формализовать в виде отображения некоторого пространства GF(2)ⁿ n-мерных векторов над полем GF(2) X = (x₁, x₂, …, x_n) в другое пространство GF(2)^m m-мерных двоичных векторов Y = (y₁, y₂, …, y_m), где для любого i{1, …, n} и любого j{1, ..., m}, x_iGF(2), y_jGF(2). Отображения такого рода будем задавать в виде векторной булевой функции (ВБФ) Y = (X): GF(2)ⁿ  GF(2)^m, которая является объединением компонентных БФ f_i(X), осуществляющих отображение GF(2)ⁿ  GF(2), то есть  (X) ={f₁(X), f₂(X), …, f_m(X)}.

Для описания БФ, будем использовать их представление в виде таблицы истинности и в виде алгебраической нормальной формы (АНФ). АНФ предполагает следующее описание БФ:

, (1)

где XGF(2)ⁿ, а все коэффициенты aGF(2). Таким образом, АНФ БФ над векторным пространством GF(2)ⁿ представляет собой сумму взятых с определенными коэффициентами всех возможных произведений переменных. Количество перемножаемых переменных (степень) в крайнем правом элементе АНФ является алгебраической степенью нелинейности БФ f(X) и обозначается как deg(f ).

Преобразование Уолша-Адамара

При проведении дифференциального и линейного криптоанализа, а также исследовании корреляционных свойств булевых функций (БФ), описывающих примитивы блочных алгоритмов шифрования основным аппаратом анализа является преобразование Уолша-Адамара – разновидность дискретного преобразования Фурье над конечным полем Галуа. Данное преобразование позволяет непосредственно оценить такие показатели качества БФ, как:

• сбалансированность;

• нелинейность;

• корреляционная иммунность.

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

Очевидно, что БФ не могут удовлетворять всем показателям одновременно, поэтому возникает задача некоторого компромисса (оптимизации) в выборе БФ, удовлетворяющих тем или иным показателям.

Под преобразованием Уолша-Адамара (ПУА) функции f(X), XGF(2)ⁿ, относительно вектора GF(2) понимается линейное преобразование GF(2)ⁿZ, принимающее значение в области действительных чисел и имеющее следующий вид:

(2)

где знак “ ” – обозначает скалярное произведение двух векторов.

Для сопряженной функции , осуществляющей отображение из GF(2)ⁿ в множество {-1, 1}, ПУА преобразуется к следующему виду:

. (3)

Обратное преобразование Уолша-Адамара (ОПУА) задается выражениями:

,  . (4)

Если 2ⁿ значений таблицы истинности S(f) БФ f(X) и 2ⁿ значений действительной функции U_(f ) записать в виде вектор-столбцов [S(f )] и [U_(f )], то линейное преобразование Уолша-Адамара задается матрицей Адамара H_n в следующем виде:

[U_(f )] = H_n[S(f)]. (5)

Аналогично .

Матрица H_n формируется итеративно:

,  H₀ = [1], (6)

где  – означает кронекеровское произведение матриц.

Кронекеровское произведение матрицы A размера mn и матрицы B размера st – это матрица размера msnt задаваемая как

, (7)

где a_ij – элемент i-ой строки и j-го столбца матрицы A.

Если записать матрицу Адамара с помощью ее строк h_i

,

то каждая строка h_i матрицы H_n является характеристической последовательностью линейной функции , где вектор _iGF(2)ⁿ, а его целочисленное представление равно i. В свою очередь каждая характеристическая последовательность линейной функции от n переменных является строкой матрицы H_n. Откуда следует, что строки матриц H_n и , охватывают последовательности всех аффинных функций над GF(2)ⁿ. Здесь - матрица, все элементы которой являются инверсией элементов матрицы H_n.

Обратное ПУА описывается следующими соотношениями:

[S(f)] = 2^-nH_n[U_(f )], .

Алгоритм преобразования Уолша-Адамара имеет сложность O(n2ⁿ) операций.