SPS结构大规模S盒设计与分析

doi:10.11959/j.issn.1000-436x.2023033

摘要/Abstract

摘要：

基于循环移位与异或运算构造了有限域 ${(F_{2}^{m})}^{4}$ 上的一类最优线性变换 P，借鉴线性变换输入输出关系反证法的思想，提出将最优线性变换目标问题转化为若干个递进关系定理的证明方法，不仅解决了该类最优线性变换的证明，而且适用于任意线性变换的证明。通过小规模S盒与最优循环移位-异或型线性变换P，建立了2轮SPS结构的大规模S盒模型，设计了一系列密码学性质优良的轻量级大规模S盒，仅使用查表、循环移位、异或三类基本运算，提高了大规模S盒的线性度和差分均匀度。理论证明和实例分析表明，与已有大规模S盒构造方法相比，所提大规模S盒设计方案运算代价更加低廉，其差分、线性等密码学性质更加优良，适宜用于轻量级密码算法非线性置换设计。

关键词: SPS结构, 大规模S盒, 循环移位-异或型线性变换

Abstract:

A class of optimal linear transformation P over a finite field ${(F_{2}^{m})}^{4}$ was constructed based on cyclic shift and XOR operation.Using the idea of inverse proof of input-output relation of linear transformation for reference, a proof method was put forward that transformed the objective problem of optimal linear transformation into several theorems of progressive relation, which not only solved the proof of that kind of optimal linear transformation, but also was suitable for the proof of any linear transformation.By means of small-scale S-box and optimal cyclic shift-XOR linear transformation P, a large-scale S-box model with 2-round SPS structure was established, and a series of lightweight large-scale S-boxes with good cryptographic properties were designed.Only three kind of basic operations such as look-up table, cyclic shift and XOR were used in the proposed design scheme, which improved the linearity and difference uniformity of large-scale S-boxes.Theoretical proof and case analysis show that, compared with the existing large-scale S-box construction methods, the proposed large-scale S-box design scheme has lower computational cost and better cryptographic properties such as difference and linearity, which is suitable for the design of nonlinear permutation coding of lightweight cryptographic algorithms.

Key words: SPS structure, large-scale S-box, cyclic shift-XOR linear transformation

中图分类号:

TN918.1

张岚, 何良生, 郁滨. SPS结构大规模S盒设计与分析[J]. 通信学报, 2023, 44(2): 27-40.

Lan ZHANG, Liangsheng HE, Bin YU. Large-scale S-box design and analysis of SPS structure[J]. Journal on Communications, 2023, 44(2): 27-40.

图/表 10

图1

表1

表2

表3

表4

16 bit S盒S1、S2及S3密码学性质对比"

S盒	最大差分概率	差分均匀度	最大线性概率	线性度	ASIC硬件实现（标准门电路个数）/个	软件实现
S₁	$\frac{96}{65 536} \approx 2^{- 9.41}$	96	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200	368	一次查表
SPS:循环移位+异或	$\frac{96}{65 536} \approx 2^{- 9.41}$	96	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200	368	一次查表
Piccolo算法S₂	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096	432	一次查表
SPS:MDS	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096	432	一次查表
NBC算法S₃	$\frac{22}{65 536} = 2^{- 11.541}$	22	${(2 \times \frac{1 572}{65 536})}^{2} = 2^{- 1 0. 764}$	3 144	440	一次查表
Galois:16级NFSR	$\frac{22}{65 536} = 2^{- 11.541}$	22	${(2 \times \frac{1 572}{65 536})}^{2} = 2^{- 1 0. 764}$	3 144	440	一次查表

表4

表5

2轮SPS结构构造的大规模S盒密码学性质"

小规模4 bit S盒	最大差分概率	差分均匀度	最大线性概率	线性度
4,0,1,15,2,11,6,7,3,9,10,5,12,13,14,8	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
8,0,1,12,2,5,6,9,4,3,10,11,7,13,14,15	$\frac{136}{65 536} \approx 2^{- 8.91}$	136	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,0,1,12,15,5,6,7,4,3,10,11,9,13,14,2	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
2,0,1,8,3,13,6,7,4,9,10,5,12,11,14,15	$\frac{148}{65 536} \approx 2^{- 8.79}$	148	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
2,0,1,8,3,15,6,7,4,9,5,11,12,13,14,10	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 664}{65 536})}^{2} \approx 2^{- 8.59}$	3 328
2,0,1,8,3,11,6,7,4,9,10,15,12,13,14,5	$\frac{72}{65 536} \approx 2^{- 9.83}$	72	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
4,8,1,2,3,11,6,7,0,9,10,14,12,13,5,15	$\frac{164}{65 536} \approx 2^{- 8.64}$	164	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
8,0,1,9,2,5,13,7,4,6,10,11,12,3,14,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 6 00}{65 536})}^{2} \approx 2^{- 8.71}$	3 200
8,14,1,2,3,5,6,7,4,12,10,11,9,13,0,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,14,1,2,3,5,6,7,4,9,15,11,12,13,0,10	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,15,1,2,3,5,12,7,4,9,10,11,6,13,14,0	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,15,1,2,3,5,6,13,4,9,10,11,12,7,14,0	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{1 792}{65 536})}^{2} \approx 2^{- 8.38}$	3 584
12,0,1,9,3,5,4,7,6,2,10,11,8,13,14,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
12,11,1,2,3,5,4,7,6,9,10,0,8,13,14,15	$\frac{144}{65 536} \approx 2^{- 8.83}$	144	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
12,9,1,2,3,5,4,7,6,0,10,11,8,13,14,15	$\frac{132}{65 536} \approx 2^{- 8.95}$	132	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096
8,14,1,2,3,5,4,7,6,9,10,0,12,13,11,15	$\frac{128}{65 536} = 2^{- 9}$	128	${(2 \times \frac{2048}{65 536})}^{2} = 2^{- 8}$	4 096

表5

图2

表6

32 bit S盒密码学性质对比"

S盒	最大差分概率	差分均匀度	最大线性概率	线性度	ASIC硬件实现（标准门电路个数）/个
2轮SPS结构	$\frac{1 0^{4}}{2^{32}}$	10⁴	${(\frac{2^{24}}{2^{32}})}^{2}$	2²⁴	1 168
SPS:循环移位+异或	$\frac{1 0^{4}}{2^{32}}$	10⁴	${(\frac{2^{24}}{2^{32}})}^{2}$	2²⁴	1 168
SPRING算法S₃	$\frac{40}{2^{32}}$	40	${(\frac{119 \times 2^{11}}{2^{32}})}^{2}$	119×2¹¹	6 848
Galois:32 bit NFSR	$\frac{40}{2^{32}}$	40	${(\frac{119 \times 2^{11}}{2^{32}})}^{2}$	119×2¹¹	6 848

表6

图3

表7

64 bit S盒密码学性质对比"

S盒	最大差分概率	差分均匀度Diff(S)	最大线性概率	线性度Lin(S)	ASIC硬件实现（标准门电路个数）/个
2轮SPS结构	$\frac{72^{4}}{2^{64}}$	72 ⁴(＜2³²)	${(\frac{3 2 00^{4}}{2^{64}})}^{2}$	3 200(＜2^55.5)	3 456
SPS：循环移位+异或	$\frac{72^{4}}{2^{64}}$	72 ⁴(＜2³²)	${(\frac{3 2 00^{4}}{2^{64}})}^{2}$	3 200(＜2^55.5)	3 456
Alzette算法S盒	$\frac{2^{32}}{2^{64}}$	2 ³²	${(\frac{2^{55.5}}{2^{64}})}^{2}$	2 ^55.5	1 312
4轮ARX结构：64 bit	$\frac{2^{32}}{2^{64}}$	2 ³²	${(\frac{2^{55.5}}{2^{64}})}^{2}$	2 ^55.5	1 312

表7

参考文献［31］

［31］	WANG J B , ． The optimal permutation in cryptography based on cyclic-shift linear transform［C］// Proceedings of ChinaCrypt 2007． Chengdu:Southwest Jiaotong University Press, 2007: 306-307．
［32］	LEANDER G , POSCHMANN A ． On the classification of 4 bit S-boxes［M］． Berlin: Springer, 2007．
［1］	LI Y Q , WANG M S ． Constructing S-boxes for lightweight cryptography with Feistel structure［C］// International Workshop on Cryptographic Hardware ＆ Embedded Systems． Berlin:Springer, 2014: 127-146．
［2］	龚涛, 陈少真．基于扩展Feistel结构S盒的构造分析［J］．信息工程大学学报, 2017,18(3): 328-332．
	GONG T , CHEN S Z ． Analysis of S-boxes with expanded feistel structure［J］． Journal of Information Engineering University, 2017,18(3): 328-332．
［3］	JUNOD P , VAUDENAY S ． FOX:a new family of block ciphers［M］． Berlin: Springer, 2004．
［4］	CANTEAUT A , DUVAL S , LEURENT G ． Construction of lightweight S-boxes using Feistel and MISTY structures［C］// International Workshop on Cryptographic Hardware and Embedded Systems． Berlin:Springer, 2015: 373-393．
［5］	MATSUI M ． New block encryption algorithm MISTY［M］． Berlin: Springer, 1997．
［6］	董新锋, 张文政, 许春香． Feistel结构的8比特轻量化S盒［J］．西安电子科技大学学报, 2021,48(1): 69-75．
	DONG X F , ZHANG W Z , XU C X ． 8 bits lightweight S-box with the Feistel structure［J］． Journal of Xidian University, 2021,48(1): 69-75．
［7］	LIU Y , LIU XI L , ZHAO Y M ． Security cryptanalysis of NUX for the Internet of things［J］． Security and Communication Networks, 2019:doi．org/10．1155/2019/2062697．
［8］	SHIBUTANI K , ISOBE T , HIWATARI H ,et al． Piccolo:an ultra-lightweight blockcipher［C］// International Workshop on Cryptographic Hardware and Embedded Systems． Berlin:Springer, 2011: 342-357．
［9］	徐洪, 段明, 谭林 ,等． NBC 算法［J］．密码学报, 2019,6(6): 760-767．
	XU H , DUAN M , TAN L ,et al． On the NBC algorithm［J］． Journal of Cryptologic Research, 2019,6(6): 760-767．
［10］	田甜, 戚文峰, 叶晨东 ,等．基于 NFSR 的分组密码算法SPRING［J］．密码学报, 2019,6(6): 815-834．
	TIAN T , QI W F , YE C D ,et al． SPRING:a family of small hardware-oriented block ciphers based on NFSRs［J］． Journal of Cryptologic Research, 2019,6(6): 815-834．
［11］	National Institute of Standards and Technology. Lightweight crylptography［R］． 2020．
［12］	BEIERLE C , BIRYUKOV A , CARDOSO D S L ,et al． Lightweight AEAD and hashing using the sparkle permutation family［J］． IACR Transactions on Symmetric Cryptology, 2020(S1): 208-261．
［13］	BANIK S , CHAKRABORTI A , IWATA T ,et al． GIFT-COFB［J］． Cryptology ePrint Archive, 2020,738: 1-25．
［14］	CHRISTOF B , ALEX B ,et al． Alzette:a 64-bit ARX-box (feat.CRAX and TRAX)［C］// Proceedings of the Advances in Cryptology． Berlin:Springer, 2020: 419-448．
［15］	NIST． Advanced Encryption Standard(AES)［S］． 2001．
［16］	吴文玲, 张蕾, 郑雅菲 ,等．分组密码 uBlock［J］．密码学报, 2019,6(6): 690-703．
	WU W L , ZHANG L , ZHENG Y F ,et al． The block cipher uBlock［J］． Journal of Cryptologic Research, 2019,6(6): 690-703．
［17］	LIU M C , SIM S M ． Lightweight MDS generalized circulant matrices［C］// International Conference on Fast Software Encryption． Berlin:Springer, 2016: 101-120．
［18］	李瑞林, 熊海, 李超．基于循环移位和异或运算的对合线性变换研究［J］．国防科技大学学报, 2012,34(2): 46-50．
	LI R L , XIONG H , LI C ． Research on involutional linear transformations based on rotation and XOR［J］． Journal of National University of Defense Technology, 2012,34(2): 46-50．
［19］	DONG H C , SANG J L , JONG I L ,et al． New block cipher Donut using pairwise perfect decorrelation［C］// Proceedings of the First International Conference on Progress in Cryptology． Berlin:Springer, 2000: 262-270．
［20］	CANTEAUT A , DUVAL S , LEURENT G ,et al． Saturnin:a suite of lightweight symmetric algorithms for post-quantum security［J］． IACR Transactions on Symmetric Cryptology, 2020(S1): 160-207．
［21］	SAJADIEH M , DAKHILALIAN M , MALA H ,et al． Recursive diffusion layers for block ciphers and hash functions［C］// International Workshop on Fast Software Encryption． Berlin:Springer, 2012: 385-401．
［22］	WU S B , WANG M S , WU W L ． Recursive diffusion layers for (lightweight) block ciphers and hash functions［C］// International Conference on Selected Areas in Cryptography． Berlin:Springer, 2013: 355-371．
［23］	AUGOT D , FINIASZ M ． Direct construction of recursive MDS diffusion layers using shortened BCH codes［C］// International Workshop on Fast Software Encryption． Berlin:Springer, 2015: 3-17．
［24］	LI S , SUN S W , SHI D P ,et al． Lightweight iterative MDS matrices:how small can we go?［J］． IACR Transactions on Symmetric Cryptology, 2019(4): 147-170．
［25］	LI S , SUN S W , LI C Y ,et al． Constructing low-latency involutory MDS matrices with lightweight circuits［J］． IACR Transactions on Symmetric Cryptology, 2019(1): 84-117．
［26］	GUO Z , LIU R , WU W ,et al． Direct construction of lightweight rotational-XOR MDS diffusion layers［J］． IACR Cryptology ePrint Archive, 2016(1036): 1-16．
［27］	GUO Z Y , LIU R Z , GAO S ,et al． Direct construction of optimal rotational-XOR diffusion primitives［J］． IACR Transactions on Symmetric Cryptology, 2017(4): 169-187．
［28］	苏俊, 王鑫, 王涛 ,等．循环移位与异或构造扩散层的新证明方法［J］．密码学报, 2020,7(6): 763-773．
	SU J , WANG X , WANG T ,et al． New proof method for cyclic shift and XOR structured diffusion layer［J］． Journal of Cryptologic Research, 2020,7(6): 763-773．
［29］	HONG S , LEE S J , LIM J ,et al． Provable security against differential and linear cryptanalysis for the SPN structure［M］． Berlin: Springer, 2001．
［30］	BON W K , HWAN S J , JUNG H S ． Constructing and cryptanalysis of a 16 × 16 binary matrix as a diffusion layer［C］// International Workshop on Information Security Applications． Berlin:Springer, 2003: 489-503．
［31］	王金波．基于循环移位构造最优线性变换［C］// 中国密码学会 2007年会论文集．成都:西南交通大学出版社, 2007: 306-307．

序号	线性置换P₁的等价类{t₁,t₂,t₃,t₄,t₅}	线性置换P₂的等价类{t₁,t₂,t₃,t₄,t₅}
1	0,1,5,9,12	0,3,7,11,12
2	0,4,5,9,13	0,4,7,11,15
3	1,4,8,9,13	3,4,8,11,15
4	1,5,8,12,13	3,7,8,12,15

序号	线性置换P₃的等价类{t₁,t₂,t₃,t₄,t₅}	线性置换P₄的等价类{t₁,t₂,t₃,t₄,t₅}
1	0,2,10,18,24	0,6,14,22,24
2	0,8,10,18,26	0,8,14,22,30
3	2,8,16,18,26	6,8,16,22,30
4	2,10,16,24,26	6,14,16,24,30

序号	线性置换P₅的等价类{t₁,t₂,t₃,t₄,t₅}	线性置换P₆的等价类{t₁,t₂,t₃,t₄,t₅}
1	0,4,20,36,48	0,12,28,44,48
2	0,16,20,36,52	0,16,28,44,60
3	4,16,32,36,52	12,16,32,44,60
4	4,20,32,48,52	12,28,32,48,60

[1]	陈东昱, 陈华, 范丽敏, 付一方, 王舰. 基于深度学习的随机性检验策略研究[J]. 通信学报, 2023, 44(6): 23-33.
[2]	张艳硕, 刘宁, 袁煜淇, 杨亚涛. 基于ISRSAC数字签名算法的适配器签名方案[J]. 通信学报, 2023, 44(3): 178-185.
[3]	黄华伟. 基于矩阵作用问题的公钥密码体制抗量子攻击安全性分析[J]. 通信学报, 2023, 44(3): 220-226.
[4]	刘帅, 关杰, 胡斌, 马宿东. 基于MILP的轻量级密码算法ACE的差分分析[J]. 通信学报, 2023, 44(1): 39-48.
[5]	周照存, 冯登国. 流密码分析方法研究综述[J]. 通信学报, 2022, 43(11): 183-198.
[6]	石润华, 于辉, 柯唯阳, 徐小桐. 基于BB84态的量子匿名一票否决协议[J]. 通信学报, 2022, 43(8): 109-120.
[7]	李曼曼, 陈少真. 改进的减轮Kiasu-BC算法的中间相遇攻击[J]. 通信学报, 2022, 43(7): 41-48.
[8]	尹安琪, 郭渊博, 汪定, 曲彤洲, 陈琳. 可证明安全的抗量子两服务器口令认证密钥交换协议[J]. 通信学报, 2022, 43(3): 14-29.
[9]	蒋梓龙, 金晨辉. Saturnin算法的不可能差分分析[J]. 通信学报, 2022, 43(3): 53-62.
[10]	王念平, 殷勍. 类Piccolo结构的差分安全性评估[J]. 通信学报, 2022, 43(2): 55-64.
[11]	王念平, 郭祉成. 动态密码结构抵抗差分密码分析能力评估[J]. 通信学报, 2021, 42(8): 70-79.
[12]	王念平, 洪礼荣. 类MARS密码结构的线性特性及其优化设计[J]. 通信学报, 2021, 42(4): 169-176.
[13]	黄龙霞, 王良民, 张功萱. 面向区块链贸易系统的无管理者安全模型[J]. 通信学报, 2020, 41(12): 36-46.
[14]	杜蛟,刘春红,庞善起. 4t-1元旋转对称2-弹性函数的构造[J]. 通信学报, 2020, 41(11): 169-175.
[15]	张国双,陈晓,林东岱,刘凤梅. 基于Nonce重用的ACORN v3状态恢复攻击[J]. 通信学报, 2020, 41(8): 11-21.