Citizendium - a community developing a quality comprehensive compendium of knowledge, online and free. Click here to join and contribute—free
CZ thanks AUGUST 2014 donors; special to Darren Duncan. SEPTEMBER 2014 donations open; need minimum total $100. Let's exceed that. Donate here. Treasurer's Financial Report -- Thanks to August content contributors. --




Pseudo-Hadamard transform

From Citizendium, the Citizens' Compendium

Jump to: navigation, search
This article is developing and not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
 
This editable Main Article is under development and not meant to be cited; by editing it you can help to improve it towards a future approved, citable version. These unapproved articles are subject to a disclaimer.

The pseudo-Hadamard transform, or PHT, is a technique used in cryptography, primarily block cipher design. It was introduced in the SAFER ciphers and has been used in others such as Twofish. Its main function is to provide cryptographic diffusion.

A two-element transform can be applied to any bit string of even length. Split it into two bit strings a and b of equal lengths, each of n bits. Then, with all arithmetic mod 2n, compute:

 a' = a + b
 b' = a + 2b

To reverse this, clearly:

 b = b' - a'
 a = 2a' - b'

Generally, the transform is done in place, so it becomes conceptually:

 x = a + b
 y = a + 2b
 a = x
 b = y

The actual implementation often dispenses with the intermediate variables giving:

 a += b
 b += a

This can be applied recursively to get a transform for any number of blocks that is a power of two. For example, if pht(a,b) does an in-place PHT of two blocks, then the in-place PHT for an array of four blocks is:

  pht(0,1)
  pht(2,3)
  pht(0,3)
  pht(2,4)

For an 8-element transform, apply the 4-element one to the two halves then mix the halves with eight two-element transforms: pht(0,8), .... pht(7,15). This can be extended to 16, 32 ... 2n elements.

Matrix version

The transform can also be expressed as a matrix multiplication of a data vector by the appropriate member of a recursively-defined set of matrices.

The first matrix is:

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

and the recursion rule is:

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

To reverse the transform, multiply by the inverse of the matrix.

Cryptographic properties

This has two very desirable properties for cryptographic use.

First, since the two-element transform is reversible, so are all the higher-level transforms constructed from it. For cryptography, a reversible transform is required so that decryption can be the inverse of encryption. The Walsh-Hadamard transform (same recursive structure but using a' = a+b, b' = a-b) does not have that property when modular arithmetic is involved, but the PHT variant does.

Second, for any level of the transform, it is clear that every output block depends on all input blocks. This is a very useful property in terms of cryptographic diffusion

Views
Personal tools