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

Пусть на вход преобразования подаётся строка бит ${\displaystyle a}$ длины ${\displaystyle 2n}$. Представим её в виде двух строк длины ${\displaystyle n}$: ${\displaystyle a=(a_{1},a_{2})}$. Тогда в результате действия псевдопреобразования Адамара получим строку ${\displaystyle b=(b_{1},b_{2})}$, значения подстрок которой вычисляются по следующим формулам:

${\displaystyle b_{1}=(2a_{1}+a_{2}){\mbox{ mod }}2^{n}}$

${\displaystyle b_{2}=(a_{1}+a_{2}){\mbox{ mod }}2^{n}}$

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

${\displaystyle a_{1}=(b_{1}-b_{2}){\mbox{ mod }}2^{n}}$

${\displaystyle a_{2}=(-b_{1}+2b_{2}){\mbox{ mod }}2^{n}}$

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

${\displaystyle {\begin{bmatrix}b_{1}\\b_{2}\end{bmatrix}}={\begin{bmatrix}2&1\\1&1\end{bmatrix}}*{\begin{bmatrix}a_{1}\\a_{2}\end{bmatrix}}}$

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

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

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

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

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

${\displaystyle 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 байта).

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

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

• Англо-русский криптологический словарь (рус.) (недоступная ссылка). Дата обращения: 9 ноября 2009. Архивировано 25 февраля 2011 года.