基于密码结构的扩散层构造

doi:10.11959/j.issn.2096-109x.2017.00170

摘要/Abstract

摘要：

以分组密码扩散层为研究对象，根据轻量级分组密码的特点，基于2种密码结构构造轻量级扩散层，分别是基于Feistel结构构造面向软件实现的扩散层和基于LFSR构造面向硬件实现的扩散层。利用三轮Feistel结构，轮函数采用基于循环移位和异或的线性变换，构造出作用在8个4 bit和8 bit S盒上分支数为7的轻量级对合扩散层。基于LFSR构造出作用在4个4 bit和8 bit S盒上的次最优扩散层和作用在8个4 bit和8 bit S盒上分支数为7的扩散层。另外，利用LFSR构造出了6、7、8维MDBL矩阵以及16、18、32维分支数分别为7、7、12的大维数二进制矩阵。研究结果在分组密码的设计方面具有较高的应用价值。

关键词: 分组密码, 扩散层, Feistel结构, 反馈移位寄存器, MDBL矩阵

Abstract:

Taked diffusion layers of block cipher algorithms as the research object,lightweight diffusion layers were constructed by two cipher structures based on the characteristics of diffusion layers of lightweight block cipher algorithms,which were the construction of software-oriented diffusion layers based on Feistel structure and the construction of hardware-oriented diffusion layers based on LFSR.Lightweight involution diffusion layers with branch numbers 7 over eight 4-bit and 8-bit S-boxes were constructed by 3-round Feistel structure and the round functions adopt linear transformations with rotation and XORs.Some suboptimal diffusion layers over four 4 bit and 8 bit S-boxes and diffusion layers with branch numbers 7 over eight 4 bit and 8 bit S boxes based on LFSR were constructed.In addition,6,7,8 dimension MDBL matrices and many 16,18,32 dimension binary matrices with big dimension and branch numbers 7,7,12 based on LFSR were constructed.The experimental results have high practical significance in realm of the design of block cipher algorithms.

Key words: block cipher, diffusion layer, Feistel structure, linear feedback shift register, MDBL matrix

中图分类号:

TP393

李鹏飞. 基于密码结构的扩散层构造[J]. 网络与信息安全学报, 2017, 3(6): 65-76.

Peng-fei LI. Construction of diffusion layers based on cipher structures[J]. Chinese Journal of Network and Information Security, 2017, 3(6): 65-76.

图/表 17

表1

一些采用MDBL矩阵作为扩散层的密码算法"

密码算法	矩阵维数	扩散层作用在 $F_{2}^{m}$ 上	对合性	分支数	汉明重量
ARIA	16	$F_{2}^{8}$	是	8	112
Camellia	8	$F_{2}^{8}$	否	5	44
E2	8	$F_{2}^{8}$	否	5	44
MIBS	8	$F_{2}^{4}$	否	5	44
Midori	4	$F_{2}^{4}$ 或 $F_{2}^{8}$	是	4	12
FIDES	4	$F_{2}^{5}$ 或 $F_{2}^{6}$	是	4	12
Minalpher	4	$F_{2}^{4}$	是	4	12

表1

图1

图2

图3

图4

图5

表2

表3

表4

表5

表6

表7

表8

n维LFSR矩阵最大分支数 β max lfsr 和MDBL矩阵的分支数βmdbl"

n	$β_{\max}^{l f s r}$	β^mdbl	n	$β_{\max}^{l f s r}$	β^mdbl
4	3	4	5	3	4
6	4	4	7	4	4
8	5	5	9	5	6
10	5	6	12	7	8
14	6	8	16	7	8
18	7	8	32	12	12*

表8

表9

当n=6,7,8时，利用LFSR构造出的MDBL矩阵"

矩阵维数n	状态转移矩阵 $S_{i}^{n}$
6	$S_{46}^{6}$ 6、 $S_{53}^{6}$ 、 $S_{55}^{6}$ 、 $S_{61}^{6}$
7	$S_{69}^{7}$ 、 $S_{70}^{7}$ 、 $S_{77}^{7}$ 、 $S_{83}^{7}$ 、 $S_{88}^{7}$ 、 $S_{91}^{7}$ 、 $S_{91}^{7}$ 、 $S_{101}^{7}$ 、 $S_{103}^{7}$ 、 $S_{104}^{7}$ 、 $S_{105}^{7}$ 、 $S_{108}^{7}$ 、 $S_{111}^{7}$ 、 $S_{114}^{7}$ 、 $S_{118}^{7}$ 、 $S_{121}^{7}$ 、 $S_{125}^{7}$
8	$S_{156}^{8}$ 、 $S_{235}^{8}$

表9

表10

表11

表12

参考文献 68

[1]	SCHNEIER B , SCHNEIER B . Data encryption standard (DES)[C]// Advances in Cryptology—EUROCRYPT’85. 1985: 3-5.
[2]	DAEMEN J , RIJMEN V . The design of Rijndael:AES,the advanced encryption standard[M]. Berlin: SpringerPress, 2002.
[3]	无线局域网产品中使用的 SMS4 算法[EB/OL]. .
	SMS4 algorithm used in wireless LAN products[EB/OL]. .
[4]	HONG D , SUNG J , HONG S ,et al. HIGHT:a new block cipher suitable for low-resource device[C]// Cryptographic Hardware and Embedded Systems. 2006: 46-59.
[5]	BOGDANOV A , KNUDSEN L R , LEANDER G ,et al. PRESENT:an ultra-lightweight block cipher[C]// Cryptographic Hardware and Embedded Systems . 2007: 450-466.
[6]	SHIRAI T , SHIBUTANI K , AKISHITA T ,et al. The 128 bit blockcipher CLEFIA[C]// The 14th International Conference on Fast Software Encryption. 2007: 181-195.
[7]	GUO J , PEYRIN T , POSCHMANN A ,et al. The LED block cipher[C]// Cryptographic Hardware and Embedded Systems. 2011: 326-341.
[8]	WU W , ZHANG L . LBlock:a lightweight block cipher[C]// Applied Cryptography and Network Security. 2011: 327-344.
[9]	BORGHOFF J , CANTEAUT A , GüNEYSU T ,et al. PRINCE—a low-latency block cipher for pervasive computing applications[C]// The International Conference on the Theory and Application of Cryptology and Information Security. 2012: 208-225.
[10]	RAY B , DOUGLAS S , JASON S . The simon and speck families of lightweight block ciphers[R]. 2013.
[11]	GéRARD B , GROSSO V , NAYA-PLASENCIA M ,et al. Block ciphers that are easier to mask:How far can we go?[C]// International Workshop on Cryptographic Hardware and Embedded Systems. 2013: 383-399.
[12]	YANG G , ZHU B , SUDER V ,et al. The simeck family of lightweight block ciphers[C]// The International Workshop on Cryptographic Hardware and Embedded Systems. 2015: 307-329.
[13]	GUO J , PEYRIN T , POSCHMANN A . The photon family of lightweight Hash functions[C]// Advances in Cryptology Conference. 2011: 222-239.
[14]	ANDREEVA E , BILGIN B , BOGDANOV A ,et al. Submission to the CAESAR competition[EB/OL]. .
[15]	RIJMEN V , DAEMEN J . The cipher shark[C]// Fast Software Encryption. 1996: 99-112.
[16]	SCHNEIER B , KELSEY J , WHITING D ,et al. Twofish:a 128 bit block cipher[C]// The 1st AES Candidate Conference on National Institute for Standards and Technology. 1998.
[17]	SCHNEIER B , KELSEY J , WHITING D ,et al. The twofish encryption algorithm[M]. New York:John Wiley ＆Sons. 1999.
[18]	DAEMEN J , KNUDSEN L R , RIJMEN V . The block cipher square[C]// The 4th Fast Software Encryption Workshop. 1997: 149-165.
[19]	BARRETO P , RIJMEN V . The anubis block cipher[EB/OL]. .
[20]	BARRETO P , RIJMEN V . The khazad legacy-level block cipher[C]// Primitive Submitted to NESSIE. 2000.
[21]	JUNOD P , VAUDENAY S . FOX:a new family of block ciphers[C]// Selected Areas in Cryptography. 2004: 114-119.
[22]	DAI W , FURUYA S , YOSHIDA H ,et al. A new keystream generator MUGI[M]// Fast Software Encryption. Berlin: SpringerPress, 2002: 37-45.
[23]	FILHO G D , BARRETO P , RIJMEN V . The maelstrom-0 Hash function[C]// The 6th Brazilian Symposium on Information and Computer Systems Security. 2006.
[24]	GAURAVARAM P , KNUDSEN L R , MATUSIEWICZ K ,et al. Gr?stl a SHA-3 candidate[EB/OL]. .
[25]	BARRETO P S L M , RIJMEN V . The Whirlpool hashing function[EB/OL]. .
[26]	MORADI A , POSCHMANN A , LING S ,et al. Pushing the limits:a very compact and a threshold implementation of AES[C]// Advances in Cryptology – EUROCRYPT . 2011.
[27]	崔霆, 金晨辉 . 对合 Cauchy-Hadamard 型 MDS 矩阵的构造[J]. 电子与信息学报, 2010,32(2): 500-503.
	CUI T , JIN C H . Construction of involution cauchy-hadamard type MDS matrices[J]. Journal of Electronics ＆Information Technology, 2010,32(2): 500-503.
[28]	SAJADIEH M , DAKHILALIAN M , MALA H ,et al. On construction of involutory MDS matrices from Vandermonde Matrices in GF[J]. Designs,Codes and Cryptography, 2012,64(3): 287-308.
[29]	SAJADIEH M , DAKHILALIAN M , MALA H ,et al. Recursive diffusion layers for block ciphers and Hash functions[C]// The International Conference on Fast Software Encryption. 2012: 385-401.
[30]	WU S , WANG M , WU W . Recursive diffusion layers for (lightweight) block ciphers and Hash functions[C]// Selected Areas in Cryptography. 2012: 355-371.
[31]	AUGOT D , FINIASZ M . Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and Hash functions[C]// IEEE International Symposium on Information Theory Proceedings. 2013: 1551-1555.
[32]	BERGER T P , . Construction of recursive MDS diffusion layers from Gabidulin codes[C]// INDOCRYPT. 2013: 274-285.
[33]	AUGOT D , FINIASZ M . Direct construction of recursive MDS diffusion layers using shortened BCH codes[C]// Fast Software Encryption. 2014: 3-17.
[34]	KHOO K , PEYRIN T , POSCHMANN A Y ,et al. FOAM:searching for hardware-optimal SPN structures and components with a fair comparison[C]// Cryptographic Hardware and Embedded System. 2014: 433-450.
[35]	SIM S M , KHOO K , OGGIER F ,et al. Lightweight MDS involution matrices[C]// Fast Software Encryption. 2015: 471-493.
[36]	NAKAHARA J , ABRAHO L . A new involutory MDS matrix for the AES[J]. International Journal of Network Security, 2009,9(2): 109-116.
[37]	GUPTA K C , RAY I G . On constructions of circulant MDS matrices for lightweight cryptography[C]// Information Security Practice and Experience. 2014: 564-576.
[38]	LIU M , SIM S M . Lightweight MDS generalized circulant matrices[C]// Fast Software Encryption. 2016.
[39]	LI Y , WANG M . On the construction of lightweight circulant involutory MDS matrices[C]// Fast Software Encryption. 2016.
[40]	KWON D , KIM J , PARK S ,et al. New block cipher:ARIA[C]// ICISC. 2003: 432-445.
[41]	AOKI K , ICHIKAWA T , KANDA M ,et al. Camellia:a 128 bit block cipher suitable for multiple platforms design and analysis[C]// Selected Areas in Cryptography. 2000: 39-56.
[42]	KANDA M , MORIAI S , AOKI K ,et al. E2—a new 128 bit block cipher[J]. Ieice Transactions on Fundamentals of Electronics Communications ＆Computer Sciences, 2000,83(1): 48-59.
[43]	IZADI M , SADEGHIYAN B , SADEGHIAN S S ,et al. MIBS:a new lightweight block cipher[C]// The International Conference on Cryptology and Network Security. 2009: 334-348.
[44]	BANIK S , BOGDANOV A , ISOBE T ,et al. Midori:a block cipher for low energy[C]// The International Conference on the Theory and Application of Cryptology and Information Security. 2014: 411-436.
[45]	BILGIN B , BOGDANOV A , KNE?EVI? M ,et al. Fides:lightweight authenticated cipher with side-channel resistance for constrained hardware[C]// The International Workshop on Cryptographic Hardware and Embedded Systems. 2013: 142-158.
[46]	SASAKI Y , TODO Y , AOKI K ,et al. Minalpher v1[C]// Submission to the CAESAR Competition. 2014.
[47]	KWON D , SUNG S H , SONG J H ,et al. Design of block ciphers and coding theory[J]. Trends in Mathematics, 2005,8(1): 13-20.
[48]	KOO B W , JANG H S , SONG J H . Constructing and cryptanalysis of a 16×16 binary matrix as a diffusion layer[C]// The International Workshop on Information Security Applications. 2003: 489-503.
[49]	KOO B W , JANG H S , SONG J H . On constructing of a 32×32 binary matrix as a diffusion layer for a 256-bit block cipher[C]// Information Security and Cryptology (ICISC). 2006: 51-64.
[50]	KANG J S , HONG S , LEE S ,et al. Practical and provable security against differential and linear cryptanalysis for substitution permutation networks[J]. ETRI Journal, 2001,23(4): 158-167.
[51]	KANDA M , TAKASHIMA Y , MATSUMOTO T ,et al. A strategy for constructing fast round functions with practical security against differential and linear cryptanalysis[C]// Selected Areas in Cryptography. 1998: 264-279.
[52]	GAO Y , GUO G . Unified approach to construct 8×8 binary matrices with branch number 5[C]// The 1st Acis International Symposium on Cryptography,and Network Security,Data Mining and Knowledge Discovery,E-Commerce and ITS Applications,and Embedded Systems. 2010: 413-416.
[53]	ASLAN B , SAKALLI M . Algebraic construction of cryptographically good binary linear transformations[J]. Security and Communication Networks, 2014,7(1): 53-63.
[54]	SAKALL M T , ASLAN B . On the algebraic construction of cryptographically good 32×32 binary linear transformations[J]. Journal of Computational ＆Applied Mathematics, 2014,259: 485-494.
[55]	SAKALL S M T , ASLAN B . Algebraic construction of 16×16 binary matrices of branch number 7 with one fixed point[EB/OL]. .
[56]	DEHNAVI S M , RISHAKANI A M , SHAMSABAD M R M . Bitwise linear mappings with good cryptographic properties and efficient implementation[J]. Antiquity, 2015,75.
[57]	LIM C H . CRYPTON:a new 128-bit block cipher[J]. Nist Aes Proposal, 1998.
[58]	ETSI/SAGE TS 35.222-2011,Specification of the 3GPP Confidentiality and Integrity Algorithms 128-EEA3 ＆128-EIA3;Document 2:ZUC Specification[S].
[59]	STERN J , VAUDENAY S . CS-Cipher[J]. Lecture Notes in Computer Science, 1998,1372: 189-205.
[60]	MATSUI M , . New block encryption algorithm MISTY[C]// The International Workshop on Fast Software Encryption. 1997: 54-68.
[61]	LI Y , WANG M . Constructing s-boxes for lightweight cryptography with feistel structure[C]// Cryptographic Hardware and Embedded Systems. 2014: 127-146.
[62]	CANTEAUT A , DUVAL S , LEURENT G . Construction of lightweight s-boxes using feistel and misty structures[C]// The International Conference on Selected Areas in Cryptography. 2015: 373-393.
[63]	GUO Z , WU W , GAO S . Constructing lightweight optimal diffusion primitives with feistel structure[C]// The International Conference on Selected Areas in Cryptography. 2015: 352-372.
[64]	张雪锋, 范九伦 . 基于线性反馈移位寄存器和混沌系统的伪随机序列生成方法[J]. 物理学报, 2010,59(4): 2289-2297.
	ZHANG X F , FAN J L . Pseudo-random sequence generating method based on LFSR and chaotic system[J]. Acta Physica Sinica, 2010,59(4): 2289-2297.
[65]	STALLINGS W . Cryptography and network security:principles and practice,fifth edition[M]. Pearson Education, 2011.
[66]	TODO Y , AOKI K . Wide trail design strategy for binary mixcolumns[M]. Applied Cryptography and Network Security. 2016.
[67]	公丽丽 . 分组密码的软件实现评估方法研究及RECTANGLE在X86平台的软件实现测评[D]. 北京:中国科学院大学, 2015.
	GONG L L . A study of software implementation of block cipher and software implementation of RECTANGLE on X86 platforms[D]. Beijing:The University of Chinese Academy of Sciences, 2015.
[68]	NAKAHARA J , ABRAH?O E . A new involutory MDS matrix for the AES[J]. International Journal of Network Security, 2009,9(2): 109-116.

S₁	S₂
{0,4,9}	{0,3,7}
{0,4,9}	{0,10,15}
{1,5,9}	{0,7,11}
{1,5,9}	{1,2,14}
{2,6,13}	{1,8,11}
{2,6,13}	{2,9,15}
{5,9,13}	{0,1,4}
{5,9,13}	{0,2,14}
{6,10,14}	{0,1,5}
{6,10,14}	{0,3,7}

S₁
{6,14,22}
{6,14,22}
{6,14,22}
{6,14,23}
{6,14,23}
{6,21,29}
{6,21,29}
{6,21,29}
{6,22,30}
{6,22,30}
{6,22,30}

LFSR维数	LFSR状态转移矩阵的最后一列值i
16	32966、32970、32978、32990、32994、33003、33011、33032、33033
16	33037、33039、33040、33041、33042、33046、33047、33051、33052
16	33061、33072、33073、33075、33079、33080、33082、33093、33097
16	33098、33106、33114、33131、33139、33145、33161、33165、33167

LFSR维数	LFSR状态转移矩阵的最后一列值i
32	2147520533、2147520538、2147520547、2147520551、2147520562
32	2147520565、2147520571、2147520574、2147520578、2147520587
32	2147520590、2147520593、2147520598、2147520599、2147520619
32	2147520630、2147520631、2147520634、2147520642、2147520650

LFSR维数	LFSR状态转移矩阵的最后一列值i
32	2148618279、2149459469、2149669179、2149717069、2150038164
32	2150165475、2150195621、2150962835、2151045265、2151128281
32	2151446953、2151536558、2151650836、2151803149、2151849147
32	2151871370、2151936204、2152034193、2152036577、2152054356