偽阿達瑪變換

偽阿達馬變換是一個可逆的變換，對於一個二元字串提供混淆與擴散，見阿達馬變換。

這個二元字串長度需是偶數，可以拆成兩個長度相等的二元字串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 （页面存档备份，存于互联网档案馆）