Псевдопреобразование Адамара

Псевдопреобразова́ние Адама́ра (англ. Pseudo-Hadamard Transform, PHT) — обратимое преобразование битовых строк, используемое в криптографии для обеспечения диффузии при шифровании. Количество бит на входе преобразования должно быть чётным, чтобы было возможным разделение строки на две части равной длины. Создателем преобразования является французский математик Жак Адамар.

Действие преобразования

Пусть на вход преобразования подаётся строка бит $a$ длины $2n$. Представим её в виде двух строк длины $n$: $a=(a_1,a_2)$. Тогда в результате действия псевдопреобразования Адамара получим строку $b=(b_1,b_2)$, значения подстрок которой вычисляются по следующим формулам:

$b_1 = (2a_1+a_2) \mbox{ mod } 2^n$

$b_2 = (a_1+a_2) \mbox{ mod } 2^n$

Соответственно, из этих формул легко получается обратное псевдопреобразование Адамара:

$a_1 = (b_1-b_2) \mbox{ mod } 2^n$

$a_2 = (-b_1+2b_2) \mbox{ mod } 2^n$

Матричное представление

Псевдопреобразование Адамара может быть представлено в матричной форме. Если записать $a$ и $b$ в векторной форме $a=\begin{bmatrix} a_1 \\ a_2 \end{bmatrix}$, $b=\begin{bmatrix} b_1 \\ b_2 \end{bmatrix}$, то преобразование будет равносильно умножению на матрицу $H_1 = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}$:

$\begin{bmatrix} b_1 \\ b_2 \end{bmatrix}=\begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}*\begin{bmatrix} a_1 \\ a_2 \end{bmatrix}$

Конечно, не стоит забывать, что все операции при умножении на матрицу производятся по модулю $2^n$.

Обратное преобразование равносильно умножению на матрицу, обратную к $H_1$: $H_1^{-1} = \begin{bmatrix} 1 & -1 \\ -1 & 2 \end{bmatrix}$.

Можно также представить матрицу преобразования в виде матрицы большей размерности, являющейся степенью двойки. Так, например, если мы работаем с 8-битовой строкой, мы можем представить её в виде 4-х подстрок длиной по 2 бита: $a(a_1,a_2,a_3,a_4)$, и аналогично поступить с выходной строкой $b$. Матрица для такого преобразования получается из рекурсивного правила:

$H_k = \begin{bmatrix} 2 \times H_{k-1} & H_{k-1} \\ H_{k-1} & H_{k-1} \end{bmatrix}$

В нашем примере $k=2$, и матрица преобразования имеет вид:

$H_2 = \begin{bmatrix} 4 & 2 & 2 & 1 \\ 2 & 2 & 1 & 1 \\ 2 & 1 & 2 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}$

Применение

Псевдопреобразование Адамара применяется в некоторых алгоритмах шифрования для обеспечения лучшей криптографической диффузии. Примерами таких алгоритмов являются Twofish и SAFER. При этом 2-х точечное преобразование (на входе строка длиной 2 байта) применяется во всех разновидностях SAFER, кроме последней версии SAFER++ (2000 год), в которой применяется 4-х точечное преобразование (на входе строка длиной 4 байта).

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

Ссылки

• Сравнительный анализ симметричных шифров  (рус.). — Описание шифров, в том числе использующих псевдопреобразование Адамара. Архивировано из первоисточника 10 апреля 2012.

• Англо-русский криптологический словарь  (рус.). Архивировано из первоисточника 10 апреля 2012.