Pseudo transformată Hadamard

Pseudo -Hadamard Transform ( PHT ) este o transformare reversibilă a șirurilor de biți utilizate în criptografie pentru a oferi difuzie în criptare . Numărul de biți din intrarea conversiei trebuie să fie par, astfel încât să fie posibilă împărțirea șirului în două părți de lungime egală. Creatorul transformării este matematicianul francez Jacques Hadamard .

Acțiune de transformare

Fie intrarea transformării un șir de biți de lungime . Să-l reprezentăm ca două șiruri de lungime : . Apoi, ca urmare a acțiunii pseudo-transformării Hadamard, obținem un șir ale cărui valori ale subșirului sunt calculate prin următoarele formule: $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}

În consecință, din aceste formule, se obține ușor pseudo-transforma inversă Hadamard:

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

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

Reprezentare matrice

Pseudo-transformarea Hadamard poate fi reprezentată sub formă de matrice . Dacă scriem și sub formă vectorială , , atunci transformarea va fi echivalentă cu înmulțirea cu o matrice : $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}}$

Desigur, nu uitați că toate operațiile la înmulțirea cu o matrice sunt efectuate modulo . $2^{n}$

Transformarea inversă este echivalentă cu înmulțirea cu matricea inversă la : . $H_1$ $H_{1}^{{-1}}={\begin{bmatrix}1&-1\\-1&2\end{bmatrix}}$

De asemenea, puteți reprezenta matricea de transformare ca o matrice mai mare care este o putere a doi. Deci, de exemplu, dacă lucrăm cu un șir de 8 biți, îl putem reprezenta ca 4 subșiruri de câte 2 biți fiecare: , și facem același lucru cu șirul de ieșire . Matricea pentru o astfel de transformare se obține din regula recursivă: $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}}

În exemplul nostru , , și matricea de transformare arată astfel: $k=2$

H_{2}={\begin{bmatrix}4&2&2&1\\2&2&1&1\\2&1&2&1\\1&1&1&1\end{bmatrix}}

Aplicație

Transformarea pseudo Hadamard este utilizată în unii algoritmi de criptare pentru a oferi o difuzie criptografică mai bună. Twofish și SAFER sunt exemple de astfel de algoritmi . În același timp, o conversie în 2 puncte (la intrare, un șir de 2 octeți) este utilizată în toate variantele de SAFER, cu excepția celei mai recente versiuni a SAFER ++ ( 2000 ), care utilizează o conversie în 4 puncte. (la intrare, un șir de 4 octeți).

În algoritmii de criptare de mai sus, majoritatea operațiunilor, inclusiv pseudo-transformarea Hadamard, sunt efectuate pe octeți . În consecință, în formulele care descriu transformarea, aceasta este luată egală cu 8 $n$

Link -uri

Analiza comparativă a cifrurilor simetrice (link indisponibil) . — Descrierea cifrurilor, inclusiv a celor care utilizează pseudo-transforma Hadamard. Consultat la 9 noiembrie 2009. Arhivat din original la 16 iunie 2012. (Rusă)

Dicționar criptologic englez-rus (link inaccesibil) . Consultat la 9 noiembrie 2009. Arhivat din original pe 25 februarie 2011. (Rusă)