Login
Login

pseudo-Hadamard transform

The pseudo-Hadamard transform is a reversible transformation of a bit string that provides cryptographic diffusion. See Hadamard transform.

The bit string must be of even length so that it can be split into two bit strings a and b of equal lengths, each of n bits. To compute the transform for Twofish algorithm, a' and b', from these we use the equations:

:a' = a + b \, \pmod{2^n}

:b' = a + 2b\, \pmod{2^n}

To reverse this, clearly:

:b = b' - a' \, \pmod{2^n}

:a = 2a' - b' \, \pmod{2^n}

On the other hand, the transformation for SAFER+ encryption is as follows:

:a' = 2a + b \, \pmod{2^n}

:b' = a + b\, \pmod{2^n}

Generalization

The above equations can be expressed in matrix algebra, by considering a and b as two elements of a vector, and the transform itself as multiplication by a matrix of the form:

:H_1 = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}

The inverse can then be derived by inverting the matrix.

However, the matrix can be generalised to higher dimensions, allowing vectors of any power-of-two size to be transformed, using the following recursive rule:

:H_n = \begin{bmatrix} 2 \times H_{n-1} & H_{n-1} \\ H_{n-1} & H_{n-1} \end{bmatrix}

For example:

:H_2 = \begin{bmatrix} 4 & 2 & 2 & 1 \\ 2 & 2 & 1 & 1 \\ 2 & 1 & 2 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}

See also

This is the Kronecker product of an Arnold Cat Map matrix with a Hadamard matrix.

References

  • James Massey, "On the Optimality of SAFER+ Diffusion", 2nd AES Conference, 1999. [http://csrc.nist.gov/archive/aes/round1/conf2/papers/massey.pdf]
  • Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, "Twofish: A 128-Bit Block Cipher", 1998. [http://www.schneier.com/paper-twofish-paper.html]
  • Helger Lipmaa. On Differential Properties of Pseudo-Hadamard Transform and Related Mappings. INDOCRYPT 2002, LNCS 2551, pp 48-61, 2002.[https://web.archive.org/web/20090218060451/http://research.cyber.ee/~lipmaa/papers/lip02c/]

{{crypto-stub}}

External links

  • [http://eprint.iacr.org/2004/010.pdf Fast Pseudo-Hadamard Transforms]

Category:Theory of cryptography

Category:Transforms