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

Интернет магазин китайских планшетных компьютеров

Компьютеры - Псевдопреобразование Адамара

23 января 2011

Оглавление:
1. Псевдопреобразование Адамара
2. Применение

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

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

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

b₁ = mod 2

b₂ = mod 2

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

a₁ = mod 2

a₂ = mod 2

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

Псевдопреобразование Адамара может быть представлено в матричной форме. Если записать 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.

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

Можно также представить матрицу преобразования в виде матрицы большей размерности, являющейся степенью двойки. Так, например, если мы работаем с 8-битовой строкой, мы можем представить её в виде 4-х подстрок длиной по 2 бита: a, и аналогично поступить с выходной строкой 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}$

<<< Протокол конфиденциального вычисления

Компьютерное аппаратное обеспечение
Вычислительные комплексы
Компьютерные данные
Компьютерные журналы
Классы компьютеров
Компьютеры

Программное обеспечение
Производители компьютеров
Профессии в ИТ
Системное администрирование
Компьютерный сленг
Списки компьютерных терминов

Человеко-компьютерное взаимодействие