基于Walsh-Hadamard编码思想的DES-S盒密钥求取

夏晓伟,张浩,蒋玉明

（1.四川大学计算机学院，成都 610065；2.中国工程物理研究院计算机应用研究所，绵阳 621000）

基于Walsh-Hadamard编码思想的DES-S盒密钥求取

夏晓伟1,张浩2,蒋玉明1

（1.四川大学计算机学院，成都 610065；2.中国工程物理研究院计算机应用研究所，绵阳 621000）

S盒是许多分组密码算法中唯一的非线性结构，对S盒性质的研究在许多分组密码分析中都是重中之重。Walsh谱是研究布尔函数性质的重要数学工具，布尔函数的许多密码学特征和性质都可以由Walsh谱反映出来。Hadamard编码是一种线性纠错码，并能通过快速Hadamard变换（FHT）实现快速译码。基于Hadamard编码思想，利用Walsh谱定义及性质，提出求取S盒加密密钥的Hadamard编码方法。并以DES的S盒为例，对该方法进行阐述。

DES-S盒；布尔函数；Walsh 谱；Hadamard 矩阵；Hadamard 编码

0 引言

S盒是许多分组密码算法唯一的非线性结构,它的密码学性质对分组密码的安全性至关重要。在常用的分组密码分析中，通常以研究S盒为突破口。例如：在差分密码分析中[1]，研究S盒的差分特性；在线性密码分析中[2]，寻找S盒的最佳线性近似表达式；在非线性密码分析中[3]，寻找S盒的非线性近似表达式等。

对分组密码S盒分析的主要目的是为了求取S盒的加密密钥K。本文基于Hadamard编码思想[4-6]，利用Walsh谱定义及性质[7-8]，将S盒函数的输入输出转化成K的一个Hadamard编码，再对其进行译码，进而求取K。本文最后以DES[9]的S盒为例，对该方法的原理进行了说明。

1 Hadamard编码

1.1 Hadamard矩阵[10-11]

定义1一个n阶的Hadamard矩阵Hn是一个由1和-1构成的，并且满足的正交方阵，其中In是 n×n单位矩阵。

定理1若n阶的Hadamard矩阵Hn存在，则n是1、2或者4的倍数。

定理2设Hn为n阶的Hadamard矩阵，则：

为2n阶的Hadamard矩阵。

特别的H1=[1]，可按如下方式递归定义H2n：

其中⊗表示直积。这样的矩阵也被称作Walsh-Hadamard矩阵。

1.2 Hadamard编码

Hadamard编码是一种纠错码，可在不可靠信道中进行错误检测和校正。对于一个长度为k的二进制信息x∈{0，1}k，Hadamard编码的编码函数Had将x映射为Had（x）：

1.3 基于Hadamard矩阵的译码算法

然后进行FHT计算。

基于Hadamard矩阵的译码过程如下：

（1）对接收到的n比特码字c=（c0，c1，…，cn-1），计算v=（（-1）c0，（-1）c1，（-1）cn-1）T；

（2）计算s=Hnv；

（3）找出s中绝对值最大的数，记下序号，该序号的二进制表示即为原始信息。

2 Walsh谱

Walsh谱是研究布尔函数性质的重要数学工具，布尔函数的许多密码学特征和性质都可以由Walsh谱反映出来。如：可利用Walsh谱分析S盒的差分均匀性、线性性、非线性度、代数次数等密码性质。下面给出Walsh谱的定义。

定义2 n元布尔函数f（x）的Walsh循环谱为：

简称为Walsh谱。

对于Walsh谱，可以利用Walsh-Hadamard矩阵计算。

3 密钥K还原原理

对Walsh变换做如下推导：

在实际计算过程中，由于k未知，我们通过统计输入x及其对应的输出y，计算Walsh谱S（f）（w；k）。利用f的定义，可以直接计算S（f）（w；0）。通过对比S（f）（w；k）与S（f）（w；0）的符号，求出 hk=（（-1）0·k，（-1）1·k，…（-1）N·k）T，再用译码算法，求取k。

在计算时，遇到x中有部分比特未知的情况怎么办？解决办法如下。

假设x由（x′，x′′）两部分组成，其中x′为m比特，x′已知；x′′为n-m比特，x′′未知。相对应的，k也有（k′，k′′）组成，w有（w′，w′′）组成。设w′′=0，考虑下面的Walsh变换：

4 DES的S盒分析

4.1 S 盒密钥K 求取

DES中有8个6进4出的S盒，共计32比特输出。将这32比特输出分别看作独立的非线性函数，每个函数有6比特输入，1比特输出。本文用第1个S盒的第1个输出作为示例，设该S盒对应的布尔函数为f（x），取k=（101110）为加密密钥做讨论。

首先计算k取（000000）和（101110）时S盒的真值表，结果如下表：

表1 输出真值表

表2 在不同k下的Walsh谱

从结果s中看到，在第46（从0计数）位置处取得最大绝对值50，而46的二进制为（101110），即我们要求取的密钥k。

4.2 部分k′的求取

用6bit掩码MASK来表示x′的所取的位置，并计算S（f）（w；0）、S（f）（w；k）及s′，如下：

表3 求取过程及结果表

表4 MASK为0x3e时部分密钥k′求取结果表

MASK：0x3e，掩码为16进制的3e，即（111110），表示x′取1、2、3、4、5比特位；

MASKCNT:5，表示掩码有效位数为5；

MASKKEY:23，因为k=（101110），按掩码位取k值得对应的k′=（10111），即十进制的23。

从s′中可以看出，最大值25正好在第23位，即我们所求取的部分密钥k′的十进制表示为23，与从掩码位取得的k′值相等，求取结果正确。

下面列了取其他掩码时的结果（部分结果）：

表5 部分密钥k′求取结果表

上述结果中，加粗的值所在位置序号即为所求k′的十进制值表示，它与按掩码位取得的k的部分密钥对应。

5 结语

本文从Walsh变换出发，利用S盒对应的布尔函数在加密密钥K取不同值时Walsh谱的对应关系，将密钥K映射成它的Walsh-Hadamard编码，再利用译码算法，将密钥K还原出来。

由于Hadamard编码纠错能力比较强，在统计输入x及其对应的输出y的过程中，即使存在少量误差，也不影响我们正确还原加密密钥K。

[1]Eli Biham，Adi Shamir.Differential Cryptanalysis of DES-Like Cryptosystems[M].New York:Springer-Verlag，1993，4（1）:3-72.

[2]Mitsuru Matsui.Linear Cryptanalysis Method for DES Cipher[A].Advances in Cryptology:Euroerypt′93[C].Springer-Verlag，1993，765: 386-397.

[3]Lars R.Knudsen，M.J.B.Robshaw.Non-Linear Approximations in Linear Cryptanalysis[C].International Conference on Theory& Application of Crytographic Techniques，1996，1070（1）:224-236.

[4]Tom Richardson，Rudiger Urbanke.Modern Coding Theory[M].Cambridge University Press，2008.

[5]F.J.MacWilliams，N.J.A.Sloane.The Theory of Error-Correcting Codes[M].New York:North-Holland，1977.

[6]W.K.Leung，Guosen Yue，Li Ping，et al.Concatenated Zigzag Hadamard Codes[J].IEEE Transactions on Information Theory，2006，Apr，52（4）:1711-1723.

[7]温巧燕，钮心忻，杨义先.现代密码学中的布尔函数[M].北京，科学出版社，2000.

[8]冯登国.频谱理论及其在密码学中的应用[M].北京，科学出版社，2000.

[9]NBS.Federal Information Processing Standard Publication 46:Data Encryption Standard（DES）[S].National Bureau of Standards，Gainthersburg，MD，1977.

[10]K.J.Horadam.Hadamard Matrices and Their Applications[M].Princeton，N J:Princeton University Press，2007.

[11]R.Craigen.Hadamard Matrices and Designs[M].Cambridge:Cambridge University Press，2004:113-132.

[12]Li Ping，W.K.Leung，K.Y.Wu.Low-Rate Turbo-Hadamard Codes[J].IEEE Transactions on Information Theory，2003，Des.49（12）: 3213-3224.

[13]杨义先，林须端.编码密码学[M].北京：人民邮电出版社，1992-12.337-338.

DES-S Box Key Recovery Based on Walsh-Hadamard Coding Theory

XIA Xiao-wei1，ZHANG Hao2，JIANG Yu-ming1

（1.College of Computer Science，Sichuan University，Chengdu 610065;
2.Institute of Computer Application，China Academy of Engineering Physics，Mianyang 621000）

Since S-box is the only nonlinear part in most block ciphers，it′s crucial to study their properties for cryptanalysis of an block cipher. Walsh spectrum is an important mathematical tool to study the properties of Boolean functions.Many cryptographic features and properties of Boolean functions can be reflected by Walsh spectrum.The Hadamard code is a linear error-correcting code,and can be quickly decoded by fast Hadamard transform (FHT).Based on Walsh spectrum and Hadamard coding theory,develops a new approach to recover the encryption key of a S-box.The method is expounded by taking DES S-box as an example.

DES-Sbox;Boolean Functions;Walsh Spectrum;Hadamard Matrix;Hadamard Codes

1007-1423（2017）09-0003-04

10.3969/j.issn.1007-1423.2017.09.001

夏晓伟（1987-），男，四川绵竹人，硕士研究生，研究方向为网络与信息安全

2017-01-17

2017-03-10

张浩（1981-），男，河北保定人，博士，研究方向为数学、计算机应用

蒋玉明（1964-），男，四川南充人，博士，教授，硕士生导师，研究方向为计算机网络与信息系统