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^{\prime }=a+b(\mathrm{mod}{2}^n)$

$b^{\prime }=a+2b(\mathrm{mod}{2}^n)$

To reverse this, clearly:

$b=b^{\prime }-a^{\prime }(\mathrm{mod}{2}^n)$

$a=2a^{\prime }-b^{\prime }(\mathrm{mod}{2}^n)$

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

$a^{\prime }=2a+b(\mathrm{mod}{2}^n)$

$b^{\prime }=a+b(\mathrm{mod}{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=\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right]$

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=\left[\begin{array}{cc}2\times H_{n-1}& H_{n-1}\\ H_{n-1}& H_{n-1}\end{array}\right]$

For example:

$H_2=\left[\begin{array}{cccc}4& 2& 2& 1\\ 2& 2& 1& 1\\ 2& 1& 2& 1\\ 1& 1& 1& 1\end{array}\right]$

See also

• SAFER
• Twofish

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. [1]
• Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall, "Twofish: A 128-Bit Block Cipher", 1998. [2]
• Helger Lipmaa. On Differential Properties of Pseudo-Hadamard Transform and Related Mappings. INDOCRYPT 2002, LNCS 2551, pp 48-61, 2002.[3]

External links

• Fast Pseudo-Hadamard Transforms