Pseudo Hadamard transformation

Pseudo -Hadamard Transform ( PHT ) är en reversibel transformation av bitsträngar som används i kryptografi för att ge diffusion i kryptering . Antalet bitar i ingången av konverteringen måste vara jämnt, så att det är möjligt att dela strängen i två lika långa delar. Skaparen av förvandlingen är den franske matematikern Jacques Hadamard .

Transformeringsåtgärd

Låt inmatningen av transformationen vara en sträng av bitar av längd . Låt oss representera det som två längdsträngar : . Sedan, som ett resultat av handlingen från Hadamard-pseudotransformationen, får vi en sträng vars delsträngvärden beräknas med följande formler: $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}

Följaktligen, från dessa formler, erhålls den omvända Hadamard-pseudotransformen lätt:

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

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

Matrisrepresentation

Hadamard-pseudotransformen kan representeras i matrisform . Om vi skriver och i vektorform , , kommer transformationen att vara likvärdig med att multiplicera med en matris : $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}}$

Naturligtvis, glöm inte att alla operationer när du multiplicerar med en matris utförs modulo . $2^{n}$

Den omvända transformationen är ekvivalent med att multiplicera med matrisen invers till : . $H_1$ $H_{1}^{{-1}}={\begin{bmatrix}1&-1\\-1&2\end{bmatrix}}$

Du kan också representera transformationsmatrisen som en större matris som är en potens av två. Så, till exempel, om vi arbetar med en 8-bitars sträng, kan vi representera den som 4 delsträngar med 2 bitar vardera: , och göra samma sak med utgångssträngen . Matrisen för en sådan transformation erhålls från den rekursiva regeln: $a(a_{1},a_{2},a_{3},a_{4})$ $b$

H_{k}={\begin{bmatrix}2\ gånger H_{{k-1}}&H_{{k-1}}\\H_{{k-1}}&H_{{k-1}}\end {bmatrix}}

I vårt exempel ser , och transformationsmatrisen ut så här: $k=2$

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

Applikation

Pseudo Hadamard-transformen används i vissa krypteringsalgoritmer för att ge bättre kryptografisk spridning. Twofish och SAFER är exempel på sådana algoritmer . Samtidigt används en 2-punktskonvertering (vid ingången en sträng på 2 byte lång) i alla varianter av SAFER, förutom den senaste versionen av SAFER ++ ( 2000 ), som använder en 4-punktskonvertering (vid ingången, en sträng på 4 byte lång).

I ovanstående krypteringsalgoritmer utförs de flesta operationerna, inklusive Hadamard-pseudotransformen, på bytes . Följaktligen, i formlerna som beskriver transformationen, tas den lika med 8 $n$

Länkar

Jämförande analys av symmetriska chiffer (länk ej tillgänglig) . — Beskrivning av chiffer, inklusive de som använder Hadamard-pseudotransform. Hämtad 9 november 2009. Arkiverad från originalet 16 juni 2012. (ryska)

Engelsk-rysk kryptologisk ordbok (otillgänglig länk) . Hämtad 9 november 2009. Arkiverad från originalet 25 februari 2011. (ryska)