伪阿达玛变换

伪阿达马变换是一个可逆的变换，对于一个二元字串提供混淆与扩散，见阿达马变换。

这个二元字串长度需是偶数，可以拆成两个长度相等的二元字串a 和b，各有n位。计算转换 a' and b'，我们使用下面的式子:

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

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

而要回复 a 与 b 只需:

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

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

一般化

上面的式子可以透过矩阵来表示，考虑 a 和 b 是一个向量的两个元素，那么上面的变换就是单纯把自己乘上一个矩阵:

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

而透过求得矩阵的反矩阵就可以得到这个变换的反函式。

这个矩阵能被推广到更高的维度，允许任何长度是2的次方的向量被转换，透过以下的递回定律:

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

举例而言:

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

密码学性质

• 伪阿达马变换有两个非常好的密码学性质，首先，由于两个元素的时候，这个变换是可逆的，因此更高维度也能由此重建。在密码学中，可逆的加密是必要的，单纯阿达马变换(a' = a+b, b' = a-b)并没有这个性质，当我们使用模的时候，但伪阿达马变换有。
• 另外，对于任何转换，可以知道所有的输出数值都和所有的输入数值有关，这在混淆与扩散是一个相当有用的性质。

相关条目

• SAFER
• Twofish
• 沃尔什转换
• 阿达马变换

参考资料

• 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]

外部链接

• Fast Pseudo-Hadamard Transforms （页面存档备份，存于互联网档案馆）