基于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-），男，四川南充人，博士，教授，碩士生導師，研究方向為計算機網絡與信息系統