Псевдопреобразова́ние Адама́ра ( англ. 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 года.