夏曉偉,張浩,蔣玉明

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2.中國工程物理研究院計(jì)算機(jī)應(yīng)用研究所，綿陽 621000）

基于Walsh-Hadamard編碼思想的DES-S盒密鑰求取

夏曉偉1,張浩2,蔣玉明1

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2.中國工程物理研究院計(jì)算機(jī)應(yīng)用研究所，綿陽 621000）

S盒是許多分組密碼算法中唯一的非線性結(jié)構(gòu)，對(duì)S盒性質(zhì)的研究在許多分組密碼分析中都是重中之重。Walsh譜是研究布爾函數(shù)性質(zhì)的重要數(shù)學(xué)工具，布爾函數(shù)的許多密碼學(xué)特征和性質(zhì)都可以由Walsh譜反映出來。Hadamard編碼是一種線性糾錯(cuò)碼，并能通過快速Hadamard變換（FHT）實(shí)現(xiàn)快速譯碼。基于Hadamard編碼思想，利用Walsh譜定義及性質(zhì)，提出求取S盒加密密鑰的Hadamard編碼方法。并以DES的S盒為例，對(duì)該方法進(jìn)行闡述。

DES-S盒；布爾函數(shù)；Walsh 譜；Hadamard 矩陣；Hadamard 編碼

0 引言

S盒是許多分組密碼算法唯一的非線性結(jié)構(gòu),它的密碼學(xué)性質(zhì)對(duì)分組密碼的安全性至關(guān)重要。在常用的分組密碼分析中，通常以研究S盒為突破口。例如：在差分密碼分析中[1]，研究S盒的差分特性；在線性密碼分析中[2]，尋找S盒的最佳線性近似表達(dá)式；在非線性密碼分析中[3]，尋找S盒的非線性近似表達(dá)式等。

對(duì)分組密碼S盒分析的主要目的是為了求取S盒的加密密鑰K。本文基于Hadamard編碼思想[4-6]，利用Walsh譜定義及性質(zhì)[7-8]，將S盒函數(shù)的輸入輸出轉(zhuǎn)化成K的一個(gè)Hadamard編碼，再對(duì)其進(jìn)行譯碼，進(jìn)而求取K。本文最后以DES[9]的S盒為例，對(duì)該方法的原理進(jìn)行了說明。

1 Hadamard編碼

1.1 Hadamard矩陣[10-11]

定義1一個(gè)n階的Hadamard矩陣Hn是一個(gè)由1和-1構(gòu)成的，并且滿足的正交方陣，其中In是 n×n單位矩陣。

定理1若n階的Hadamard矩陣Hn存在，則n是1、2或者4的倍數(shù)。

定理2設(shè)Hn為n階的Hadamard矩陣，則：

為2n階的Hadamard矩陣。

特別的H1=[1]，可按如下方式遞歸定義H2n：

其中?表示直積。這樣的矩陣也被稱作Walsh-Hadamard矩陣。

1.2 Hadamard編碼

Hadamard編碼是一種糾錯(cuò)碼，可在不可靠信道中進(jìn)行錯(cuò)誤檢測(cè)和校正。對(duì)于一個(gè)長度為k的二進(jìn)制信息x∈{0，1}k，Hadamard編碼的編碼函數(shù)Had將x映射為Had（x）：

1.3 基于Hadamard矩陣的譯碼算法

然后進(jìn)行FHT計(jì)算。

基于Hadamard矩陣的譯碼過程如下：

（1）對(duì)接收到的n比特碼字c=（c0，c1，…，cn-1），計(jì)算v=（（-1）c0，（-1）c1，（-1）cn-1）T；

（2）計(jì)算s=Hnv；

（3）找出s中絕對(duì)值最大的數(shù)，記下序號(hào)，該序號(hào)的二進(jìn)制表示即為原始信息。

2 Walsh譜

Walsh譜是研究布爾函數(shù)性質(zhì)的重要數(shù)學(xué)工具，布爾函數(shù)的許多密碼學(xué)特征和性質(zhì)都可以由Walsh譜反映出來。如：可利用Walsh譜分析S盒的差分均勻性、線性性、非線性度、代數(shù)次數(shù)等密碼性質(zhì)。下面給出Walsh譜的定義。

定義2 n元布爾函數(shù)f（x）的Walsh循環(huán)譜為：

簡(jiǎn)稱為Walsh譜。

對(duì)于Walsh譜，可以利用Walsh-Hadamard矩陣計(jì)算。

3 密鑰K還原原理

對(duì)Walsh變換做如下推導(dǎo)：

在實(shí)際計(jì)算過程中，由于k未知，我們通過統(tǒng)計(jì)輸入x及其對(duì)應(yīng)的輸出y，計(jì)算Walsh譜S（f）（w；k）。利用f的定義，可以直接計(jì)算S（f）（w；0）。通過對(duì)比S（f）（w；k）與S（f）（w；0）的符號(hào)，求出 hk=（（-1）0·k，（-1）1·k，…（-1）N·k）T，再用譯碼算法，求取k。

在計(jì)算時(shí)，遇到x中有部分比特未知的情況怎么辦？解決辦法如下。

假設(shè)x由（x′，x′′）兩部分組成，其中x′為m比特，x′已知；x′′為n-m比特，x′′未知。相對(duì)應(yīng)的，k也有（k′，k′′）組成，w有（w′，w′′）組成。設(shè)w′′=0，考慮下面的Walsh變換：

4 DES的S盒分析

4.1 S 盒密鑰K 求取

DES中有8個(gè)6進(jìn)4出的S盒，共計(jì)32比特輸出。將這32比特輸出分別看作獨(dú)立的非線性函數(shù)，每個(gè)函數(shù)有6比特輸入，1比特輸出。本文用第1個(gè)S盒的第1個(gè)輸出作為示例，設(shè)該S盒對(duì)應(yīng)的布爾函數(shù)為f（x），取k=（101110）為加密密鑰做討論。

首先計(jì)算k?。?00000）和（101110）時(shí)S盒的真值表，結(jié)果如下表：

表1 輸出真值表

表2 在不同k下的Walsh譜

從結(jié)果s中看到，在第46（從0計(jì)數(shù)）位置處取得最大絕對(duì)值50，而46的二進(jìn)制為（101110），即我們要求取的密鑰k。

4.2 部分k′的求取

用6bit掩碼MASK來表示x′的所取的位置，并計(jì)算S（f）（w；0）、S（f）（w；k）及s′，如下：

表3 求取過程及結(jié)果表

表4 MASK為0x3e時(shí)部分密鑰k′求取結(jié)果表

MASK：0x3e，掩碼為16進(jìn)制的3e，即（111110），表示x′取1、2、3、4、5比特位；

MASKCNT:5，表示掩碼有效位數(shù)為5；

MASKKEY:23，因?yàn)閗=（101110），按掩碼位取k值得對(duì)應(yīng)的k′=（10111），即十進(jìn)制的23。

從s′中可以看出，最大值25正好在第23位，即我們所求取的部分密鑰k′的十進(jìn)制表示為23，與從掩碼位取得的k′值相等，求取結(jié)果正確。

下面列了取其他掩碼時(shí)的結(jié)果（部分結(jié)果）：

表5 部分密鑰k′求取結(jié)果表

上述結(jié)果中，加粗的值所在位置序號(hào)即為所求k′的十進(jìn)制值表示，它與按掩碼位取得的k的部分密鑰對(duì)應(yīng)。

5 結(jié)語

本文從Walsh變換出發(fā)，利用S盒對(duì)應(yīng)的布爾函數(shù)在加密密鑰K取不同值時(shí)Walsh譜的對(duì)應(yīng)關(guān)系，將密鑰K映射成它的Walsh-Hadamard編碼，再利用譯碼算法，將密鑰K還原出來。

由于Hadamard編碼糾錯(cuò)能力比較強(qiáng)，在統(tǒng)計(jì)輸入x及其對(duì)應(yīng)的輸出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]溫巧燕，鈕心忻，楊義先.現(xiàn)代密碼學(xué)中的布爾函數(shù)[M].北京，科學(xué)出版社，2000.

[8]馮登國.頻譜理論及其在密碼學(xué)中的應(yīng)用[M].北京，科學(xué)出版社，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]楊義先，林須端.編碼密碼學(xué)[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-），男，四川綿竹人，碩士研究生，研究方向?yàn)榫W(wǎng)絡(luò)與信息安全

2017-01-17

2017-03-10

張浩（1981-），男，河北保定人，博士，研究方向?yàn)閿?shù)學(xué)、計(jì)算機(jī)應(yīng)用

蔣玉明（1964-），男，四川南充人，博士，教授，碩士生導(dǎo)師，研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)與信息系統(tǒng)