基于多项式基的Camellia算法S盒硬件优化

李艳俊; 张伟国; 葛耀东; 王克

doi:10.11999/JEIT220499

基于多项式基的Camellia算法S盒硬件优化

doi: 10.11999/JEIT220499

李艳俊^{1, 2},
张伟国^2, ,,
葛耀东²,
王克²

1.
中国电子科技集团公司第十五研究所信息产业信息安全测评中心北京 100083
2.
北京电子科技学院北京 100070

基金项目: 广西密码学与信息安全重点实验室开放课题(GCIS201912)，北京高校“高精尖”学科建设项目(20210101Z0401)

详细信息

作者简介:
李艳俊：女，副教授，研究方向为分组密码的设计与分析

张伟国：男，硕士生，研究方向为S盒的设计与分析

葛耀东：男，硕士生，研究方向为分组密码量子安全性分析

王克：男，讲师，研究方向为格密码、后量子密码学和公钥密码学

通讯作者:
张伟国　18291965029@163.com

中图分类号: TN918.4
计量
- 文章访问数: 757
- HTML全文浏览量: 238
- PDF下载量: 81
- 被引次数: 0
出版历程
- 收稿日期: 2022-04-22
- 修回日期: 2022-05-23
- 网络出版日期: 2022-05-30
- 刊出日期: 2023-03-10

Hardware Optimization of S-box of Camellia Algorithm Based on Polynomial Basis

LI Yanjun^{1, 2},
ZHANG Weiguo^{2
, ,},
GE Yaodong²,
WANG Ke²

1.
Information Industry Information Security Evaluation Center, the 15th Research Institute of China Electronics Technology Group Corporation, Beijing 100083, China
2.
Beijing Institute of Electronic Science and Technology, Beijing 100070, China

Funds: The Open Project of Guangxi Key Labtorary of Cryptography and Information Security (GCIS201912), The Advanced Discipline Construction Project of Beijing Universities (20210101Z0401)

摘要

摘要: 该文提出一种基于不可约多项式的Camellia算法S盒的代数表达式，并给出了该表达式8种不同的同构形式。然后，结合Camellia算法S盒的特点，基于理论证明给出一种基于多项式基的S盒优化方案，此方法省去了表达式中的部分线性操作。相对于同一种限定门的方案，在中芯国际(SMIC)130 nm工艺库中，该文方案减少了9.12%的电路面积；在SMIC 65 nm工艺库中，该文方案减少了8.31%的电路面积。最后，根据Camellia算法S盒设计中的计算冗余，给出了2类完全等价的有限域的表述形式，此等价形式将对Camellia算法S盒的优化产生积极影响。
- 有限域 /
- 多项式基 /
- 正规基 /
- Camellia算法 /
- S盒
Abstract: An algebraic expression for the S-box of Camellia’s algorithm based on irreducible polynomials is proposed in this paper, and eight different isomorphic expressions are also given. Then combined with the characteristics of S-box, an optimization scheme based on polynomial basis is given by theoretical proof, in which some redundant linear operations are reduced. Compared with the same gate-limited scheme the circuit area is saved by 9.12% in the Semiconductor Manufacturing International Corporation (SMIC) 130 nm process library and by 8.31% in the SMIC 65 nm process library. Finally, according to the computational redundancy in the design of the S-box of Camellia algorithm, two completely equivalent representations on the finite field are given, which will have a positive impact on the optimization of the S-box of Camellia algorithm.
- Finite field /
- Polynomial basis /
- Normal basis /
- Camellia algorithm /
- S-box

HTML全文

图 1 ${\rm{ FL}}$和${{\rm{FL}}^{ - 1}}$

下载: 全尺寸图片幻灯片

图 2 Camellia算法流程图

下载: 全尺寸图片幻灯片

图 3 Camellia算法轮函数F

下载: 全尺寸图片幻灯片

图 4 Camellia算法S盒硬件优化流程

下载: 全尺寸图片幻灯片

表 1 正规基构造细节

不可约多项式	$ \alpha $	$\beta $
$p1(x) = {x^8} + {x^6} + {x^5} + {x^3} + 1$	108	2
	108	3
	18	4
	18	5
$p2(x) = {x^4} + x + 1$	109	16
	109	17
	19	104
	19	105

下载: 导出CSV

表 2 有限域构造参数

复合域	复合域	不可约多项式
${\rm GF}({2^{(n/2)}})$	${\rm GF}(2)[x]/{\rm{p}}2(x)$	${\rm{p}}2(x)$
${\rm GF}({({2^{(n/2)}})^2})$	${\rm GF}({2^{(n/2)} })[x]/{\rm{p}}3(x)$	${\rm{p}}3(x)={x}^{2}+Ax+B；A,B\in {\rm GF}({2}^{(n/2)})$

下载: 导出CSV

表 3 GF((2⁴)²)构造参数

复合域	复合域	不可约多项式
${\rm GF}({2^4})$	${\rm GF}(2)[x]/{\rm{p}}2(x)$	${\rm{p}}2(x) = {x^4} + x + 1$
${\rm GF}({({2^4})^2})$	${\rm GF}({2^{(n/2)} })[x]/{\rm{p}}3(x)$	${\rm{p}}3(x) = {x^2} + 0001x + 1001$

下载: 导出CSV

表 4 两种域的参数

不可约多项式	$i(\alpha=\beta^i)$	$\alpha $	${\beta }$	A	B
$ {\alpha ^4} + {\alpha ^3} = 1 $	17, 34, 68, 136	106, 6, 20, 121	104, 105	1	2, 14, 9, 4
		121, 106, 6, 20	16, 17
		20, 121, 106, 6	4, 5
		6, 20, 121, 106	2, 3
$ {\alpha ^4} + \alpha = 1 $	119, 187, 221, 238	109, 18, 108, 19	104, 105	1	13, 14, 11, 9
		18, 108, 19, 109	16, 17
		108, 19, 109, 18	4, 5
		19, 109, 18, 108	2, 3
$ {\alpha ^4} + {\alpha ^3} + {\alpha ^2} + \alpha = 1 $	51, 102, 153, 204	21, 120, 7, 107	104, 105	1	14, 5, 9, 3
		7, 21, 107, 120	16, 17
		107, 7, 120, 21	4, 5
		120, 107, 21, 7	2, 3

下载: 导出CSV

表 5 3种算法S盒代数安全性对比

算法	差分均匀度	分线性度	不动点个数	代数次数	代数项数
AES	4	112	0	7	(110,112,114,131,136,145,133,132)
SM4	4	112	1	7	(124,139,124,126,123,128,130,134)
Camellia	4	112	0	7	(127,132,126,135,129,133,129,126)

下载: 导出CSV

表 6 逻辑门参数(nm)

	NOT	AND	NAND	OR	XOR	XOR	MUX	NANDN
SMIC130	0.67	1.33	1.00	1.33	2.33	2.33	2.67	1.33
SMIC65	0.75	1.50	1.00	1.50	2.25	2.25	2.25	1.50

下载: 导出CSV

表 7 逻辑门参数

	算法	逻辑门数量								SMIC130 (nm)	SMIC65 (nm)
	算法	NOT	AND	NAND	OR	NOR	XOR	MUX	NANDN	SMIC130 (nm)	SMIC65 (nm)
Camellia	本文方案	9	53	0	6	0	78	0	0	266.24	270.75
	方案1^[16]	9	35	0	0	0	113	0	0	315.87	313.50
	方案2^[16]	9	58	0	0	0	94	0	0	302.19	304.50
	文献[17]	9	58	0	0	0	89	0	0	290.54	293.25
	方案1^[18]	1	0	27	0	5	63	4	2	193.00	186.50
	方案2^[18]	1	0	27	0	5	63	6	0	195.67	188.00
AES	文献[19]	4	34	0	0	0	91	0	0	259.93	258.75
SM4	文献[20]	14	34	0	0	0	85	0	0	252.65	252.75

下载: 导出CSV

参考文献(20)

[1]	BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. Cryptographic Hardware and Embedded Systems - CHES 2007, 9th International Workshop, Vienna, Austria, September 10–13, 2007, Proceedings, Berlin, Heidelberg, Germany, 2007.
[2]	WU Wenling and ZHANG Lei. LBlock: A lightweight block cipher[C]. The 9th International Conference on Applied Cryptography and Network Security, Berlin, Heidelberg, Germany, 2011.
[3]	CHEN Shiyao, FAN Yanhong, SUN Ling, et al. SAND: An AND-RX Feistel lightweight block cipher supporting S-box-based security evaluations[J]. Designs, Codes and Cryptography, 2021, 90(1): 155–198. doi: 10.1007/s10623-021-00970-9
[4]	FENG Jingya and LI Lang. SCENERY: A lightweight block cipher based on Feistel structure[J]. Frontiers of Computer Science, 2022, 16(3): 163813. doi: 10.1007/S11704-020-0115-9
[5]	GUO Ying, LI Lang, and LIU Botao. Shadow: A lightweight block cipher for IoT nodes[J]. IEEE Internet of Things Journal, 2021, 8(16): 13014–13023. doi: 10.1109/JIOT.2021.3064203
[6]	AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: A 128-bit block cipher suitable for multiple platforms-design and analysis[C]. 7th International Workshop on Selected Areas in Cryptography, Berlin Heidelberg, Germany, 2000.
[7]	SATOH A and MORIOKA S. Hardware-focused performance comparison for the standard block ciphers AES, camellia, and triple-DES[C]. 6th International Conference on Information Security, Berlin, Heidelberg, Germany, 2003: 252–266.
[8]	ZOU Jian, WEI Zihao, SUN Siwei, et al. Some efficient quantum circuit implementations of Camellia[J]. Quantum Information Processing, 2022, 21(4): 131. doi: 10.1007/S11128-022-03477-X
[9]	WEI Z, SUN S, HU L, et al. Scrutinizing the tower field implementation of the GF(2^8) inverter--with applications to AES, Camellia, and SM4[J]. Cryptology ePrint Archive, 2019.
[10]	CI C W, NAZIRI S Z M, ISMAIL R C, et al. Crypto-core design using camellia cipher[J]. Journal of Physics:Conference Series, 2021, 1755(1): 012019. doi: 10.1088/1742-6596/1755/1/012019
[11]	RASHIDI B. Compact and efficient structure of 8-bit S-box for lightweight cryptography[J]. Integration, 2021, 76: 172–182. doi: 10.1016/j.vlsi.2020.10.009
[12]	DAEMEN J and RIJMEN V. The Rijndael block cipher: AES proposal[C]. First Candidate Conference (AeS1), 1999: 343–348.
[13]	LIU Fen, JI Wen, HU Lei, et al. Analysis of the SMS4 block cipher[C]. Information Security and Privacy, 12th Australasian Conference, ACISP 2007, Townsville, Australia, July 2–4, 2007, Proceedings, Berlin, Heidelberg, Germany, 2007.
[14]	SATOH A, MORIOKA S, TAKANO K, et al. A compact Rijndael hardware architecture with S-box optimization[C]. 7th International Conference on the Theory and Application of Cryptology and Information Security, Berlin, Heidelberg, Germany, 2001: 239–254.
[15]	MAXIMOV A and EKDAHL P. New circuit minimization techniques for smaller and faster AES SBoxes[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019: 91–125. doi: 10.46586/tches.v2019.i4.91-125
[16]	MARTÍNEZ-HERRERA A F, MEX-PERERA J C, and NOLAZCO-FLORES J A. Some representations of the S-Box of Camellia in GF (((2²)²)²)[C]. 11th International Conference on Cryptology and Network Security, Berlin, Heidelberg, Germany, 2012: 296–309.
[17]	SATOH A and MORIOKA S. Unified hardware architecture for 128-bit block ciphers AES and Camellia[C]. 5th International Workshop on Cryptographic Hardware and Embedded Systems, Berlin, Heidelberg, Germany, 2003: 304–318.
[18]	魏子豪, 张英杰, 胡磊, 等. Camellia算法S盒的紧凑硬件实现[J]. 密码学报, 2021, 8(5): 844–855. doi: 10.13868/j.cnki.jcr.000481 WEI Zihao, ZHANG Yingjie, HU Lei, et al. A compact hardware implementation of S-Box for Camellia[J]. Journal of Cryptologic Research, 2021, 8(5): 844–855. doi: 10.13868/j.cnki.jcr.000481
[19]	BOYAR J, FIND M G, and PERALTA R. Small low-depth circuits for cryptographic applications[J]. Cryptography and Communications, 2019, 11(1): 109–127. doi: 10.1007/s12095-018-0296-3
[20]	刘建. 两类密码组件的实现优化方法研究[D]. [硕士论文], 战略支援部队信息工程大学, 2019. LIU Jian. Optimization on the implementation of two types of cryptographic components [D]. [Master dissertation], PLA Strategic Support Force Information Engineering University, 2019.