S-Box Construction and Optimization Method Based on Composite Chaotic System

doi:10.3778/j.issn.1673-9418.2406085

Abstract

Abstract: The S-box is the only nonlinear component of block cipher, and its merit determines the security strength of the cryptographic algorithm. In order to efficiently construct S-boxes with excellent and stable cryptographic properties, an 8-bit S-box construction and optimization method based on composite chaotic system is proposed. Firstly, an extended tent mapping is given by extending the value domain of the tent chaotic mapping, and a composite chaotic system with excellent chaotic properties is constructed by combining the extended tent mapping with the extended logistic mapping. Subsequently, after 50 iterations to eliminate the transient effects of chaotic systems, the composite chaotic system is used to generate random sequences to construct initial 8-bit S-boxes. Furthermore, for the initial S-boxes with poor cryptographic properties, an optimization objective constraint function is designed to trade-off the relationship between the differential uniformity and linearity of the S-boxes, and the iterative optimization methods, searching for the data that make the differential distribution and linear distribution of the S-boxes more uniform according to the differential and linear distributions of the S-boxes, are carried out to lower the differential uniformity and linearity of the S-boxes as much as possible, and improve the ability of S-box to resist differential analysis and linear analysis. The experimental results show that the method can optimize all the initial S-boxes with poor cryptographic properties, the differential uniformity reaches 8, and the nonlinearity reaches 102. And the proposed method has a fast optimization speed, requiring at least 33 iterations to complete the optimization.

Key words: S-box, chaos map, differential uniformity, nonlinearity, linearity

摘要： S盒是分组密码算法的唯一非线性部件，其优劣决定了密码算法的安全强度。为高效构造密码学性质优良且稳定的S盒，提出一种基于复合混沌系统的8比特S盒构造及优化方法。通过扩展tent混沌映射的值域给出扩展的tent映射，并与扩展的logistic映射结合构造了一个具有优秀混沌特性的复合混沌系统；在迭代50次消除混沌系统暂态效应后，利用复合混沌系统产生随机序列构造初始8比特S盒；进一步地，针对密码学性质较差的初始S盒，设计一个用于权衡S盒差分均匀度和线性度的优化目标约束函数，分别根据S盒的差分分布和线性分布情况，搜索使得S盒差分分布和线性分布更均匀的数据进行迭代优化，尽可能地降低S盒的差分均匀度和线性度，提高S盒抵抗差分分析和线性分析的能力。实验测试结果表明，该方法能够对所有密码学性质较差的初始S盒进行性质优化提升，优化后的差分均匀度可以达到8，非线性度达到102；该方法的优化速度快，最少仅需要33次迭代就可以完成优化。

关键词: S盒, 混沌映射, 差分均匀度, 非线性度, 线性度

WU Xiaonian, WU Ting, HUANG Zhaowen, ZHANG Runlian. S-Box Construction and Optimization Method Based on Composite Chaotic System[J]. Journal of Frontiers of Computer Science and Technology, 2025, 19(4): 1095-1104.

武小年, 吴庭, 黄昭文, 张润莲. 基于复合混沌系统的S盒构造与优化方法[J]. 计算机科学与探索, 2025, 19(4): 1095-1104.

References

[1] SHANNON C E. A mathematical theory of communication[J]. Bell System Technical Journal, 1948, 27(3): 379-423.
[2] RIJMEN V, DAEMEN J. Advanced encryption standard[J]. Proceedings of Federal Information Processing Standards Publications, 2001: 19-22.
[3] Office of State Commercial Cipher Administration. Block cipher for WLAN products-SMS4[Z]. 2001.
[4] AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: a 128-bit block cipher suitable for multiple platforms: design and analysis[C]//Proceedings of the 7th Annual International Workshop on Selected Areas in Cryptography. Berlin, Heidelberg: Springer, 2001: 39-56.
[5] LIM C H, LIM C H. A revised version of CRYPTON: CRYPTON V1.0[C]//Proceedings of the 6th International Workshop on Fast Software Encryption. New York: ACM, 1999: 31-45.
[6] BEIERLE C, JEAN J, K?LBL S, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C]//Advances in Cryptology-CRYPTO 2016. Berlin, Heidelberg: Springe, 2016: 123-153.
[7] 武小年, 豆道饶, 韦永壮, 等. 基于Feistel-NFSR结构的16比特S盒设计方法[J]. 密码学报, 2023, 10(1): 146-154.
WU X N, DOU D R, WEI Y Z, et al. A 16-bit S-box design method based on feistel-NFSR structure[J]. Journal of Cryptologic Research, 2023, 10(1): 146-154.
[8] 武小年, 舒瑞, 豆道饶, 等. 基于L-M-NFSR结构的16比特S盒设计方法[J]. 计算机科学与探索, 2023, 17(10): 2511-2518.
WU X N, SHU R, DOU D R, et al. 16-bit S-box design method based on L-M-NFSR structure[J]. Journal of Frontiers of Computer Science and Technology, 2023, 17(10): 2511-2518.
[9] MILLAN W, CLARK A, DAWSON E. Boolean function design using hill climbing methods[C]//Proceedings of the 4th Australasian Conference on Information Security and Privacy. Berlin, Heidelberg: Springer, 1999: 1-11.
[10] NOUGHABI M N A, SADEGHIYAN B. Design of S-boxes based on neural networks[C]//Proceedings of the 2010 International Conference on Electronics and Information Engineering. Piscataway: IEEE, 2010: 172-178.
[11] KAPU?CI?SKI T, NOWICKI R K, NAPOLI C. Comparison of effectiveness of multi-objective genetic algorithms in optimization of invertible S-boxes[C]//Proceedings of the 16th International Conference on Artificial Intelligence and Soft Computing. Cham: Springer, 2017: 466-476.
[12] GHOSHAL A, SADHUKHAN R, PATRANABIS S, et al. Lightweight and side-channel secure 4×4 S-boxes from cellular automata rules[J]. IACR Transactions on Symmetric Cryptology, 2018: 311-334.
[13] 张润莲, 孙亚平, 韦永壮, 等. 密码S盒的一种新自动搜索方法[J]. 计算机研究与发展, 2020, 57(7): 1415-1423.
ZHANG R L, SUN Y P, WEI Y Z, et al. A new automatic search method for cryptographic S-box[J]. Journal of Computer Research and Development, 2020, 57(7): 1415-1423.
[14] WANG Y, ZHANG Z Q, ZHANG L Y, et al. A genetic algorithm for constructing bijective substitution boxes with high nonlinearity[J]. Information Sciences, 2020, 523: 152-166.
[15] ALHADAWI H S, MAJID M A, LAMBI? D, et al. A novel method of S-box design based on discrete chaotic maps and cuckoo search algorithm[J]. Multimedia Tools and Applications, 2021, 80(5): 7333-7350.
[16] LONG M, WANG L L. S-box design based on discrete chaotic map and improved artificial bee colony algorithm[J]. IEEE Access, 2021, 9: 86144-86154.
[17] ZHANG R L, SHU R, WEI Y Z, et al. A novel S-box generation methodology based on the optimized GAN model[J]. Computers, Materials & Continua, 2023, 76(2): 1911-1927.
[18] JAKIMOSKI G, KOCAREV L. Chaos and cryptography: block encryption ciphers based on chaotic maps[J]. IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 2001, 48(2): 163-169.
[19] CASSAL-QUIROGA B B, CAMPOS-CANTóN E. Generation of dynamical S-boxes for block ciphers via extended logistic map[J]. Mathematical Problems in Engineering, 2020: 2702653.
[20] LAMBI? D. A new discrete-space chaotic map based on the multiplication of integer numbers and its application in S-box design[J]. Nonlinear Dynamics, 2020, 100(1): 699-711.
[21] LIU G J, YANG W W, LIU W W, et al. Designing S-boxes based on 3-D four-wing autonomous chaotic system[J]. Nonlinear Dynamics, 2015, 82(4): 1867-1877.
[22] ?AVU?O?LU ü, ZENGIN A, PEHLIVAN I, et al. A novel approach for strong S-box generation algorithm design based on chaotic scaled Zhongtang system[J]. Nonlinear Dynamics, 2017, 87(2): 1081-1094.
[23] TIAN Y, LU Z M. Chaotic S-box: six-dimensional fractional Lorenz-Duffing chaotic system and O-shaped path scrambling[J]. Nonlinear Dynamics, 2018, 94(3): 2115-2126.
[24] CHEN G. A novel heuristic method for obtaining S-boxes[J]. Chaos, Solitons & Fractals, 2008, 36(4): 1028-1036.
[25] FARAH T, RHOUMA R, BELGHITH S. A novel method for designing S-box based on chaotic map and teaching-learning-based optimization[J]. Nonlinear Dynamics, 2017, 88(2): 1059-1074.
[26] MANZOOR A, ZAHID A H, HASSAN M T. A new dynamic substitution box for data security using an innovative chaotic map[J]. IEEE Access, 2022, 10: 74164-74174.
[27] ARTU?ER F, ?ZKAYNAK F. SBOX-CGA: substitution box generator based on chaos and genetic algorithm[J]. Neural Computing and Applications, 2022, 34(22): 20203-20211.
[28] 周宇, 胡予濮, 董新锋. 布尔函数的设计与分析[M]. 北京: 国防工业出版社, 2015: 15-16.
ZHOU Y, HU Y P, DONG X F. Design and analysis of Boolean functions[M]. Beijing: National Defense Industry Press, 2015: 15-16.
[29] ADAMS C, TAVARES S. The structured design of cryptographically good S-boxes[J]. Journal of Cryptology, 1990, 3(1): 27-41.
[30] CHABAUD F, VAUDENAY S. Links between differential and linear cryptanalysis[C]//Proceedings of the Workshop on the Theory and Application of of Cryptographic Techniques. Berlin, Heidelberg: Springer, 1995: 356-365.
[31] BIHAM E, SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3-72.
[32] BOURA C, CANTEAUT A. On the boomerang uniformity of cryptographic sboxes[J]. IACR Transactions on Symmetric Cryptology, 2018: 290-310.
[33] PROUFF E. DPA attacks and S-boxes[C]//Proceedings of the 12th International Workshop on Fast Software Encryption. Berlin, Heidelberg: Springer, 2005: 424-441.
[34] WEBSTER A F, TAVARES S E. On the design of S-boxes[C]//Advances in Cryptology-CRYPTO 1985. Berlin, Heidelberg: Springer, 1985: 523-534.
[35] DETOMBE J, TAVARES S E, DETOMBE J, et al. Constructing large cryptographically strong S-boxes[C]//Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques: Advances in Cryptology. New York: ACM, 1992: 165-181.