改进的KLEIN算法及其量子分析

doi:10.11772/j.issn.1001-9081.2023091333

《计算机应用》唯一官方网站 ›› 2024, Vol. 44 ›› Issue (9): 2810-2817.DOI: 10.11772/j.issn.1001-9081.2023091333

改进的KLEIN算法及其量子分析

李艳俊¹^,², 葛耀东², 王琦²(), 张伟国², 刘琛¹

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

收稿日期:2023-09-27 修回日期:2023-11-16 接受日期:2023-11-20 发布日期:2023-12-01 出版日期:2024-09-10
通讯作者: 王琦
作者简介:李艳俊（1979—），女，山西阳城人，副教授，博士，主要研究方向：密码分析与测评
葛耀东（1997—），男，河北邯郸人，硕士研究生，主要研究方向：基于量子模型的分组密码
张伟国（1998—），男，陕西渭南人，硕士研究生，主要研究方向：有限域、S盒
刘琛（1990—），男，河北昌黎人，硕士研究生，主要研究方向：密码测评。
基金资助:
北京市自然科学基金资助项目(4234084);河南省网络密码技术重点实验室研究课题(LNCT2021-A09)

Improved KLEIN algorithm and its quantum analysis

Yanjun LI¹^,², Yaodong GE², Qi WANG²(), Weiguo ZHANG², Chen LIU¹

^1.Information Industry Information Security Evaluation Center，The 15th Research Institute of China Electronics Technology Group Corporation，Beijing 100083，China
^2.Department of Cryptographic Science and Technology，Beijing Electronic Science and Technology Institute，Beijing 100070，China

Received:2023-09-27 Revised:2023-11-16 Accepted:2023-11-20 Online:2023-12-01 Published:2024-09-10
Contact: Qi WANG
About author:LI Yanjun， born in 1979， Ph. D.， associate professor. Her research interests include cryptographic analysis and evaluation.
GE Yaodong， born in 1997， M. S. candidate. His research interests include block ciphers based on quantum model.
ZHANG Weiguo， born in 1998， M. S. candidate. His research interests include finite fields， S-box.
LIU Chen， born in 1990， M. S. candidate. His research interests include cryptographic evaluation.
Supported by:
Beijing Natural Science Foundation(4234084);Research Project of Henan Key Laboratory of Network Cryptography Technology(LNCT2021-A09)

摘要/Abstract

摘要：

KLEIN自提出之后经历了截断差分分析、积分分析等攻击，加密结构具有实际安全性，但是由于密钥扩展算法的脆弱性导致了全轮密钥恢复攻击。首先，修改密钥扩展算法，提出一种改进后的算法N-KLEIN；其次，采用in-place方法对S盒进行高效量子电路实现，减小了电路的宽度和深度，提高了量子电路的实现效率；再次，使用LUP分解技术实现混淆操作的量子化；继次，对N-KLEIN进行量子电路设计，提出全轮N-KLEIN的高效量子电路。最后，评估N-KLEIN算法量子实现的资源占用，并与PRESENT、HIGHT等现有的轻量级分组密码的量子实现占用资源进行对比；同时，基于Grover算法对密钥搜索攻击所需要的代价进行深入研究，给出Clifford+T模型下N-KLEIN-｛64，80，96｝使用Grover算法搜索密钥需要的代价，并评估了N-KLEIN的量子安全性。对比结果表明，N-KLEIN算法量子实现的成本明显较低。

关键词: 轻量级分组密码, KLEIN, 量子电路, S盒, Grover算法

Abstract:

KLEIN has experienced attacks such as truncated difference cryptanalysis and integral cryptanalysis since it was proposed. Its encryption structure has actual security， but the vulnerability of the key expansion algorithm leads to full-round key recovery attacks. Firstly， the key expansion algorithm was modified and an improved algorithm N-KLEIN was proposed. Secondly， an efficient quantum circuit was implemented on the S-box using the in-place method， which reduced the width and depth of the circuit and improved the implementation efficiency of the quantum circuit. Thirdly， the quantization of obfuscation operations was achieved using LUP decomposition technology. Then， an efficient quantum circuit was designed for N-KLEIN， and an efficient quantum circuit for all round N-KLEIN was proposed. Finally， the resource occupation for the quantum implementation of full-round N-KLEIN was evaluated and compared with the resources occupied by existing quantum implementations of lightweight block ciphers such as PRESENT and HIGHT. At the same time， an in-depth study was conducted on the cost of key search attacks based on Grover algorithm， and the cost of N-KLEIN-｛64，80，96｝ using Grover algorithm to search for keys under the Clifford+T model was given， and then the quantum security of N-KLEIN was evaluated. Comparative results indicate that the quantum implementation cost of N-KLEIN algorithm is significantly lower.

Key words: lightweight block cipher, KLEIN, quantum circuit, S-box, Grover algorithm

中图分类号:

TP309.7

李艳俊, 葛耀东, 王琦, 张伟国, 刘琛. 改进的KLEIN算法及其量子分析[J]. 计算机应用, 2024, 44(9): 2810-2817.

Yanjun LI, Yaodong GE, Qi WANG, Weiguo ZHANG, Chen LIU. Improved KLEIN algorithm and its quantum analysis[J]. Journal of Computer Applications, 2024, 44(9): 2810-2817.

图/表 13

表1 N-KLEIN密钥长度与加密轮数表

Tab. 1 Key lengths and encryption rounds of N-KLEIN

算法	分组长度/b	密钥长度/b	加密轮数
N-KLEIN-64	64	64	12
N-KLEIN-80	64	80	16
N-KLEIN-96	64	96	20

图1 N-KLEIN算法的加密流程

Fig. 1 Encryption process in N-KLEIN algorithm

图2 N-KLEIN的一轮加密过程

Fig. 2 One round encryption process of N-KLEIN

表2 N-KLEIN的S盒真值表

Tab. 2 N-KLEIN’s S-box truth table

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

图3 S盒的ANF评估

Fig. 3 ANF evaluation of S-box

图4 使用in-place方法实现的S盒量子电路

Fig. 4 S-box quantum circuit implemented by in-place method

表3 S盒量子资源消耗

Tab. 3 Quantum resource consumption of S-box

方法	量子位（qubit）	CNOT门数	Toffoli门数	X门数
ANF	15	15	12	3
in-place	4	3	7	2

表4 密钥扩展结构的量子资源消耗

Tab. 4 Quantum resource consumption of key expansion structure

算法	量子位（qubit）	CNOT门数	Toffoli门数	X门数	电路深度
N-KLEIN-64	64	58	84	24	121
N-KLEIN-80	80	81	112	32	165
N-KLEIN-96	96	122	140	40	209

表5 改进后密钥扩展与原密钥扩展的比较

Tab. 5 Comparison between improved key expansion and original key expansion

算法	安全性	CNOT门数	Toffoli门数	X门数	电路深度
KLEIN-64	×	1 496	2 464	704	121
KLEIN-80	×	2 160	3 360	960	165
KLEIN-96	×	2 888	4 256	1 216	209
N-KLEIN-64	√	58	84	24	121
N-KLEIN-80	√	81	112	32	165
N-KLEIN-96	√	122	140	40	209

表6 N-KLEIN算法量子资源消耗

Tab. 6 Quantum resource consumption of N-KLEIN algorithm

算法	量子位（qubit）	CNOT门数	Toffoli门数	X门数
N-KLEIN-64	128	8 050	1 428	408
N-KLEIN-80	160	10 737	1 904	544
N-KLEIN-96	192	13 442	2 380	680

表7 不同算法的量子资源消耗比较

Tab. 7 Comparison of quantum resource consumption among different algorithms

算法	CNOT门数	X门数	Toffoli门数	T深度	量子位（qubit）	电路深度
KLEIN-64	8 264	1 088	3 808	216	128	612
N-KLEIN-64	8 050	408	1 428	81	128	288
PRESENT-64^［28］	4 838	1 164	2 232	N/A	192	311
PIPO-64^［29］	2 248	1 477	1 248	N/A	192	248
HIGHT-64^［9］	22 614	4 496	5 824	N/A	228	2 479
CHAM-64^［9］	12 285	240	2 400	N/A	196	N/A
LBlock-80^［30］	16 747	877	2 040	N/A	144	1 740

图5 N-KLEIN-64算法中Uf算子的量子实现

Fig. 5 Quantum implementation of operator Uf in N-KLEIN-64 algorithm

表8 3种密钥长度下N-KLEIN使用Grover算法的量子资源

Tab. 8 Quantum resources of N-KLEIN using Grover algorithm under three key lengths

算法	总门数	总深度	总消耗	安全级别
N-KLEIN-64	$1.01 × 247$	$1.04 × 243$	$1.05 × 290$	未达到级别1
N-KLEIN-80	$1.47 × 247$	$1.36 × 243$	$1.01 × 291$	未达到级别1
N-KLEIN-96	$1.67 × 247$	$1.68 × 243$	$1.40 × 291$	未达到级别1

表8 3种密钥长度下N-KLEIN使用Grover算法的量子资源

Tab. 8 Quantum resources of N-KLEIN using Grover algorithm under three key lengths

算法	总门数	总深度	总消耗	安全级别
N-KLEIN-64	$1.01 × 247$	$1.04 × 243$	$1.05 × 290$	未达到级别1
N-KLEIN-80	$1.47 × 247$	$1.36 × 243$	$1.01 × 291$	未达到级别1
N-KLEIN-96	$1.67 × 247$	$1.68 × 243$	$1.40 × 291$	未达到级别1

参考文献 36

1	HANKERSON D， MENEZES A， VANSTONE S. Elliptic curve arithmetic ［M］// Guide to Elliptic Curve Cryptography. New York： Springer， 2004： 75-152.
2	SHOR P W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer ［J］. SIAM Review， 1999， 41（2）： 303-332.
3	KUWAKADO H， MORII M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation ［C］// Proceedings of the 2010 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2010： 2682-2685.
4	KUWAKADO H， MORII M. Security on the quantum-type Even-Mansour cipher ［C］// Proceedings of the 2012 International Symposium on Information Theory and its Applications. Piscataway： IEEE， 2012： 312-316.
5	KAPLAN M， LEURENT G， LEVERRIER A， et al. Breaking symmetric cryptosystems using quantum period finding ［C］// Advances in Cryptology — EUROCRYPT 2016. Cham： Springer， 2016： 207-237.
6	梁敏，罗宜元，刘凤梅.抗量子计算对称密码研究进展概述［J］.密码学报， 2021， 8（6）： 925-947.
	LIANG M， LUO Y Y， LIU F M. A survey on quantum-secure symmetric cryptography ［J］. Journal of Cryptologic Research， 2021， 8（6）： 925-947.
7	KIM P， HAN D， JEONG K C. Time-space complexity of quantum search algorithms in symmetric cryptanalysis： applying to AES and SHA-2 ［J］. Quantum Information Processing， 2018， 17（12）： 339.
8	JAQUES S， NAEHRIG M， ROETTELER M， et al. Implementing Grover oracles for quantum key search on AES and LowMC ［C］// Advances in Cryptology — EUROCRYPT 2020. Cham： Springer， 2020： 280-310.
9	JANG K B， CHOI S J， KWON H D， et al. Grover on Korean block ciphers ［J］. Applied Sciences， 2020， 10（18）： 6407.
10	SCHLIEPER L. In-place implementation of Quantum-Gimli ［EB/OL］. ［2022-06-14］. .
11	JANG K B， CHOI S J， KWON H D， et al. Grover on SPECK： quantum resource estimates ［J］. Cryptology ePrint Archive， 2020， 2020： 640.
12	ANAND R， MAITRA A， MUKHOPADHYAY S. Grover on SIMON ［J］. Quantum Information Processing， 2020， 19（9）： 340.
13	JANG K， BAKSI A， BREIER J， et al. Quantum implementation and analysis of DEFAULT ［J］. Cryptology ePrint Archive， 2022， 2022： 647.
14	SONG G， JANG K， KIM H， et al. SPEEDY quantum circuit for Grover’s algorithm ［J］. Applied Sciences， 2022， 12（14）： 6870.
15	JEAN J， PEYRIN T， SIM S M， et al. Optimizing implementations of lightweight building blocks ［J］. IACR Transactions on Symmetric Cryptology， 2017， 2017（4）： 130-168.
16	BAKSI A， JANG K， SONG G， et al. Quantum implementation and resource estimates for rectangle and knot ［J］. Quantum Information Processing， 2021， 20（12）： 395.
17	XIANG Z， ZENG X， LIN D， et al. Optimizing implementations of linear layers ［J］. IACR Transactions on Symmetric Cryptology， 2020， 2020（2）： 120-145.
18	HUANG Z， SUN S. Synthesizing quantum circuits of AES with lower t-depth and less qubits ［C］// Advances in Cryptology —ASIACRYPT 2022. Cham： Springer， 2023： 614-644.
19	GRASSL M， LANGENBERG B， ROETTELER M， et al. Applying Grover’s algorithm to AES： quantum resource estimates［C］// Proceedings of the 7th International Workshop on Post-Quantum Cryptography. Cham： Springer， 2016： 29-43.
20	GONG Z， NIKOVA S， LAW Y W. KLEIN： a new family of lightweight block ciphers ［C］// Proceedings of the 7th International Workshop on RFID Security and Privacy. Cham： Springer， 2011： 1-18.
21	LALLEMAND V， NAYA-PLASENCIA M. Cryptanalysis of KLEIN［C］// Proceedings of the 21st International Workshop on Fast Software Encryption. Cham： Springer， 2014： 451-470.
22	BOGDANOV A， KNUDSEN L R， LEANDER G， et al. PRESENT： an ultra-lightweight block cipher ［C］// Proceedings of the 9th International Workshop on Cryptographic Hardware and Embedded Systems. Cham： Springer， 2007： 450-466.
23	YU X， WU W， LI Y， et al. Cryptanalysis of reduced-round KLEIN block cipher ［C］// Proceedings of the 7th International Conference on Information Security and Cryptology. Cham： Springer， 2012： 237-250.
24	J-P AUMASSON， NAYA-PLASENCIA M， SAARINEN M-J O. Practical attack on 8 rounds of the lightweight block cipher KLEIN［C］// Proceedings of the 12th International Conference on Cryptology in India. Cham： Springer， 2011： 134-145.
25	CUCCARO S A， DRAPER T G， KUTIN S A， et al. A new quantum ripple-carry addition circuit ［EB/OL］. ［2023-07-23］. .
26	DRAPER T G， KUTIN S A， RAINS E M， et al. A logarithmic-depth quantum carry-lookahead adder ［EB/OL］. ［2023-04-14］. .
27	TAKAHASHI Y， TANI S， KUNIHIRO N. Quantum addition circuits and unbounded fan-out ［EB/OL］. ［2023-08-13］. .
28	JANG K， SONG G， KIM H， et al. Efficient implementation of PRESENT and GIFT on quantum computers ［J］. Applied Sciences， 2021， 11（11）： 4776.
29	JANG K， SONG G， KWON H， et al. Grover on PIPO ［J］. Electronics， 2021， 10（10）： 1194.
30	JING X Y， LI Y J， ZHAO G Y， et al. Quantum circuit implementation and resource analysis of LBlock and LiCi ［J］. Quantum Information Processing， 2023， 22： 347.
31	LANGENBERG B， PHAM H， STEINWANDT R. Reducing the cost of implementing the advanced encryption standard as a quantum circuit ［J］. IEEE Transactions on Quantum Engineering， 2020， 1： 1-12.
32	AMY M， DI MATTEO O， GHEORGHIU V， et al. Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3［C］// Proceedings of the 23rd International Conference on Selected Areas in Cryptography. Cham： Springer， 2017： 317-337.
33	WIEBE N， ROETTELER M. Quantum arithmetic and numerical analysis using Repeat-Until-Success circuits ［EB/OL］. ［2022-10-02］. .
34	BOYER M， BRASSARD G， HØYER P， et al. Tight bounds on quantum searching ［J］. Fortschritte der Physik： Progress of Physics， 1998， 46（4/5）： 493-505.
35	Submission requirements and evaluation criteria for the post-quantum cryptography standardization process： NIST Interagency/Internal Report （NISTIR） — 8105 ［S/OL］. ［S.l.］： National Institute of Standards and Technology， 2016 ［2023-09-01］. .
36	JANG K， BAKSI A， KIM H， et al. Quantum analysis of AES ［J］. Cryptology ePrint Archive， 2022， 2022： 683.

[1]	张润莲, 张密, 武小年, 舒瑞. 基于GPU的大状态密码S盒差分性质评估方法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2785-2790.
[2]	翟飞宇, 马汉达. 基于DenseNet的经典-量子混合分类模型[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1905-1910.
[3]	李艳俊, 景小宇, 谢惠琴, 项勇. 量子计算模型下PFP算法的安全性分析[J]. 《计算机应用》唯一官方网站, 2024, 44(4): 1166-1171.
[4]	项勇, 李艳俊, 黄丁韫, 陈愚, 谢惠琴. 全轮Shadow算法的差分和线性特征分析[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3839-3843.
[5]	石一鹏, 刘杰, 祖锦源, 张涛, 张国群. 基于混合整数线性规划模型的SPONGENT S盒紧凑约束分析[J]. 《计算机应用》唯一官方网站, 2023, 43(5): 1504-1510.
[6]	蒲金伟, 高倾健, 郑欣, 徐迎晖. SM4抗差分功耗分析轻量级门限实现[J]. 《计算机应用》唯一官方网站, 2023, 43(11): 3490-3496.
[7]	霍珊珊, 李艳俊, 刘健, 李寅霜. 密码组件安全指标测试工具设计与实现[J]. 《计算机应用》唯一官方网站, 2023, 43(10): 3156-3161.
[8]	蔡婧雯, 韦永壮, 刘争红. 基于GPU的密码S盒代数性质评估方法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2750-2756.
[9]	赵耿, 张森民, 马英杰, 高世蕊. 基于抗退化混沌系统的动态S盒设计与分析[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3069-3073.
[10]	刘宗甫, 袁征, 赵晨曦, 朱亮. 对PICO算法基于可分性的积分攻击[J]. 计算机应用, 2020, 40(10): 2967-2972.
[11]	赵颖, 叶涛, 韦永壮. 几类高强度密码S盒的安全性新分析[J]. 计算机应用, 2017, 37(9): 2572-2575.
[12]	马云飞, 王韬, 陈浩, 黄长阳. 轻量级分组密码SIMON代数故障攻击[J]. 计算机应用, 2017, 37(7): 1953-1959.
[13]	胡志华, 颜硕, 熊宽江. 不可能差分性质更优的动态S盒构造方法[J]. 计算机应用, 2016, 36(5): 1257-1261.
[14]	覃冠杰, 马建设, 程雪岷. 基于组合式爬山算法提高S盒非线性度的方法[J]. 计算机应用, 2015, 35(8): 2195-2198.
[15]	李灵琛, 韦永壮, 朱嘉良. 11轮3D分组密码算法的中间相遇攻击[J]. 计算机应用, 2015, 35(3): 700-703.

改进的KLEIN算法及其量子分析

Improved KLEIN algorithm and its quantum analysis

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 36

相关文章 15

编辑推荐

Metrics

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05

x	S（x）	x	S（x）	x	S（x）	x	S（x）
00	07	04	01	08	0C	0C	08
01	04	05	0F	09	03	0D	0E
02	0A	06	0B	0A	02	0E	0D
03	09	07	00	0B	06	0F	05