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

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

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

Пусть на вход преобразования подаётся строка бит ${\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 года.