Преобразование Уолша-Адамара
При проведении дифференциального и линейного криптоанализа, а также исследовании корреляционных свойств булевых функций (БФ), описывающих примитивы блочных алгоритмов шифрования основным аппаратом анализа является преобразование Уолша-Адамара – разновидность дискретного преобразования Фурье над конечным полем Галуа. Данное преобразование позволяет непосредственно оценить такие показатели качества БФ, как: q сбалансированность; q нелинейность; q корреляционная иммунность. Кроме того, с помощью преобразования Уолша-Адамара можно получить оценки автокорреляционных свойств БФ и различных показателей распространения изменений. Очевидно, что БФ не могут удовлетворять всем показателям одновременно, поэтому возникает задача некоторого компромисса (оптимизации) в выборе БФ, удовлетворяющих тем или иным показателям. Под преобразованием Уолша-Адамара (ПУА) функции f(X), XÎGF(2)n, относительно вектора aÎGF(2) понимается линейное преобразование GF(2)n®Z, принимающее значение в области действительных чисел и имеющее следующий вид: (2) где знак “ ” – обозначает скалярное произведение двух векторов. Для сопряженной функции , осуществляющей отображение из GF(2)n в множество {-1, 1}, ПУА преобразуется к следующему виду: . (3) Обратное преобразование Уолша-Адамара (ОПУА) задается выражениями: , . (4) Если 2n значений таблицы истинности S(f) БФ f(X) и 2n значений действительной функции Ua(f ) записать в виде вектор-столбцов [S(f )] и [Ua(f )], то линейное преобразование Уолша-Адамара задается матрицей Адамара Hn в следующем виде: [Ua(f )] = Hn[S(f)]. (5) Аналогично . Матрица Hn формируется итеративно: , H0 = [1], (6) где Ä – означает кронекеровское произведение матриц. Кронекеровское произведение матрицы A размера m´n и матрицы B размера s´t – это матрица размера ms´nt задаваемая как , (7) где aij – элемент i-ой строки и j-го столбца матрицы A. Если записать матрицу Адамара с помощью ее строк hi , то каждая строка hi матрицы Hn является характеристической последовательностью линейной функции , где вектор aiÎGF(2)n, а его целочисленное представление равно i. В свою очередь каждая характеристическая последовательность линейной функции от n переменных является строкой матрицы Hn. Откуда следует, что строки матриц Hn и , охватывают последовательности всех аффинных функций над GF(2)n. Здесь - матрица, все элементы которой являются инверсией элементов матрицы Hn. Обратное ПУА описывается следующими соотношениями: [S(f)] = 2-nHn[Ua(f )], . Алгоритм преобразования Уолша-Адамара имеет сложность O(n2n) операций. ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|