基于类梅森数的物联网密钥交换快速取模算法

doi:10.12141/j.issn.1000-565X.220355

华南理工大学学报(自然科学版) ›› 2023, Vol. 51 ›› Issue (5): 24-35.doi: 10.12141/j.issn.1000-565X.220355

所属专题： 2023年计算机科学与技术

基于类梅森数的物联网密钥交换快速取模算法

覃健诚¹ 钟宇²^,³ 程喆⁴ 黄成海¹ 陆以勤¹^,⁵ 潘伟锵⁵

^1.华南理工大学电子与信息学院, 广东广州 510640
^2.中国电信广东肇庆分公司, 广东肇庆 526000
^3.华南理工大学软件学院, 广东广州 510006
^4.华南理工大学计算机科学与工程学院, 广东广州 510006
^5.华南理工大学信息网络工程研究中心, 广东广州 510640

收稿日期:2022-06-06 出版日期:2023-05-25 发布日期:2023-01-16
通信作者: 陆以勤（1968-），男，教授，博士生导师，主要从事SDN、网络功能虚拟化、网络安全研究。 E-mail:eeyqlu@scut.edu.cn
作者简介:覃健诚（1976-），男，博士，高级工程师，主要从事加密算法、物联网、SDN、网络安全研究。E-mail:jcqin@scut.edu.cn
基金资助:
广东省重点领域研发计划项目(2020B0101120002);广东省科技厅海外名师项目（科技类）(粤财科教［2021］157号)

Fast Modulus Algorithm for Internet of Things Key Exchange Based on Mersenne-like Numbers

QIN Jiancheng¹ ZHONG Yu²^,³ CHENG Zhe⁴ HUANG Chenghai¹LU Yiqin¹^,⁵ PAN Weiqiang⁵

^1.School of Electronic and Information Engineering，South China University of Technology，Guangzhou 510640，Guangdong，China
^2.Zhaoqing Branch of China Telecom，Zhaoqing 526000，Guangdong，China
^3.School of Software Engineering，South China University of Technology，Guangzhou 510006，Guangdong，China
^4.School of Computer Science and Engineering，South China University of Technology，Guangzhou 510006，Guangdong，China
^5.Information and Network Engineering and Research Center，South China University of Technology，Guangzhou 510640，Guangdong，China

Received:2022-06-06 Online:2023-05-25 Published:2023-01-16
Contact: 陆以勤（1968-），男，教授，博士生导师，主要从事SDN、网络功能虚拟化、网络安全研究。 E-mail:eeyqlu@scut.edu.cn
About author:覃健诚（1976-），男，博士，高级工程师，主要从事加密算法、物联网、SDN、网络安全研究。E-mail:jcqin@scut.edu.cn
Supported by:
the Key-Area R&D Program of Guangdong Province(2020B0101120002)

摘要/Abstract

摘要：

为适应物联网加密传输中大量轻型传感器节点运算性能和能源有限的特点，解决传感器运行RSA（Rivest-Shamir-Adleman）、DHM（Diffie-Hellman-Merkle）、Elgamal等公钥基础设施（PKI）加密算法所面临的运算速度、功耗等瓶颈问题，并简化相应的硬件加密电路逻辑设计，文中提出了一种基于类梅森数的密钥交换快速取模算法（CZ-Mod算法）。CZ-Mod算法利用梅森数的数学特性，使关键的mod（取模）运算的时间复杂度降至O（n）。首先，提出了一种以类梅森数为模数的快速取模运算mod1，使复杂的mod运算变成简单的二进制移位相加运算；其次，提出了一种以任意近似类梅森数的正整数为模数的快速取模运算mod2，在简化mod运算的同时扩大模数的取值范围；然后，对mod1、mod2运算作逻辑电路设计，以简化mod运算的硬件电路；最后，将以上工作应用到物联网节点的密钥交换中，以降低计算的复杂度，提高PKI加密算法的速度。实验测试结果表明：采用CZ-Mod算法的DHM密钥交换速度可达到常规算法的2.5~4倍；CZ-Mod算法精简，适合做物联网传感器的硬件电路设计。

关键词: 网络安全, 传感器密码, 梅森数, 加密运算电路

Abstract:

In order to adapt to the limited computing performance and energy of numerous lightweight sensor nodes in the encrypted transmission of IoT (Internet of Things), this paper proposed a fast modulus algorithm (CZ-Mod algorithm) based on Mersenne-like numbers to slove the bottleneck problems of computing speed, power consumption and so on during the sensors run PKI (Public Key Infrastructure) encryption algorithms such as RSA (Rivest-Shamir-Adleman), DHM (Diffie-Hellman-Merkle), Elgamal, etc., and to simplify the corresponding hardware encrypting circuit logic design. CZ-Mod algorithm uses the mathematic characteristics of Mersenne numbers, and lowers the time complexity of its essential operation mod (modulo) into O(n). Firstly, a fast modulus algorithm mod1 using Mersenne-like numbers as modulus was presented, changing complex mod operation into simple binary shift/add operation; secondly, a fast modulus algorithm mod2 using any positive integers near Mersenne-like numbers as modulus was presented, expanding the modulus value range while simplifying mod operation; and then logic circuits of mod1 and mod2 operations were designed, simplifying mod operation hardware circuit. Finally, the above work was applied to the key exchange of IoT nodes, so as to lower the computing complexity and improve the speed of PKI encryption algorithms. The experiment test results indicate that the speed of DHM key exchange with CZ-Mod algorithm can reach 2.5 to 4 times of that of the conventional algorithm; CZ-Mod algorithm is concise and fits the hardware circuit design for the IoT sensors.

Key words: network security, sensor key, Mersenne number, encrypting operation circuit

中图分类号:

TP393

覃健诚, 钟宇, 程喆, 等. 基于类梅森数的物联网密钥交换快速取模算法[J]. 华南理工大学学报(自然科学版), 2023, 51(5): 24-35.

QIN Jiancheng, ZHONG Yu, CHENG Zhe, et al. Fast Modulus Algorithm for Internet of Things Key Exchange Based on Mersenne-like Numbers[J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(5): 24-35.

图/表 11

图1

图2

图3

图4

表1

图5

图6

表2

表3

图7

表4

参考文献 24

1	HADDADPAJOUH H， DEHGHANTANHA A， PARIZI R M，et al ．A survey on internet of things security：requirements，challenges，and solutions ［J］．Internet of Things，2021，14：100129/1-19.
2	DIFFIE W， HELLMAN M ．New directions in cryptography［J］．IEEE Transactions on Information Theory，1976，22（6）：644-654.
3	GAMAL T E ．A public key cryptosystem and a signature scheme based on discrete logarithms［J］．IEEE Transactions on Information Theory，1985，31：469-472.
4	RIVEST R L， SHAMIR A， ADLEMAN L ．A method for obtaining digital signatures and public-key cryptosystems［J］．Communications of the ACM，1978，21（2）：120-126.
5	HU Q L， DUAN M X， YANG Z B，et al ．Efficient parallel secure outsourcing of modular exponentiation to cloud for IoT applications［J］．IEEE Internet of Things Journal，2020，8（16）：12782-12791.
6	AL-NAJI F H， ZAGROUBA R ．A survey on continuous authentication methods in internet-of-things environment［J］．Computer Communications，2020，163：109-133.
7	张帆．基于区块链与属性基加密的物联网访问控制研究［D］．南京：南京邮电大学，2020.
8	WU Y， SONG L， LIU L ．The new method of sensor data privacy protection for IoT［J］．Shock and Vibration，2021：3920579/1-11．DOI：10.1155/2021/3920579 .
9	杨宏志，袁凌云，王舒．基于SM2国密算法优化的区块链设计［J］．计算机工程与设计，2021，42（3）：622-627.
	YANG Hong-zhi， YUAN Ling-yun， WANG Shu ．Optimized blockchain design based on SM2 algorithm ［J］．Computer Engineering and Design，2021，42（3）：622-627.
10	吴皓威，黄风娇，闫莲，等．面向可疑中继通信网络的合法窃听方案［J］．华南理工大学学报（自然科学版），2022，50（10）：70-79.
	WU Haowei， HUANG Fengjiao， YAN Lian，et al ．Legitimate eavesdropping scheme for suspicious relay communication networks［J］．Journal of South China University of Technology（Natural Science Edition），2022，50（10）：70-79.
11	QIN J C， BAI Z Y ．Design of new format for mass data compression［J］．Journal of China Universes of Posts and Telecommunications，2011，18（1）：121-128.
12	QIN J C， LU Y Q， ZHONG Y ．Fast algorithm of truncated Burrows-Wheeler transform coding for data compression of sensors［J］．Journal of Sensors，2018：6908760/1-17．DOI：10.1155/2018/6908760 .
13	QIN J C， LU Y Q， ZHONG Y ．Block-split array coding algorithm for long-stream data compression［J］．Journal of Sensors，2020：5726527/1-21．DOI：10.1155/2020/5726527 .
14	QIN J C， LU Y Q， ZHONG Y ．Parallel algorithm for wireless data compression and encryption［J］．Journal of Sensors，2017：4209397/1-11．DOI：10.1155/2017/4209397 .
15	覃健诚，陆以勤．利用数据压缩编码的混沌同步加密解密方法及其装置：201210386406.9［P］．2012-10-13.
16	LU Y Q， SU W Y， QIN J C ．LDPC decoding on GPU for mobile device［J］．Mobile Information Systems，2016：7048482/1-6．DOI：10.1155/2016/7048482 .
17	LU Y Q， WU D W， QIN J C ．Wireless authentication center based on embedded Wi-Fi technology［J］．WIT Transaction on Information and Communication Technologies，2014，59：387-394.
18	LU Y Q， ZHAI J， ZHU R H，et al ．Study of wireless authentication center with mixed encryption in WSN［J］．Journal of Sensors，2016：9297562/1-7．DOI：10.1155/2016/9297562 .
19	GORDON D M ．A survey of fast exponentiation mehods［J］．Journal of Algorithms，1998，27（1）：129-146.
20	KNUTH D E ．计算机程序设计艺术（卷2）［M］．北京：人民邮电出版社，2016.
21	MOSS A， PAGE D， SMART N ．Toward acceleration of RSA using 3D graphics hardware［C］∥ Proceedings of the 11th IMA International Conference on Cryptography and Coding．Cirencester：Springer，2007：364-383.
22	乔洋．基于GPU的RSA算法并行研究与设计及OpenCL实现［D］．广州：华南理工大学，2013.
23	张盛仕．基于国密算法加密技术的SoC设计与优化［D］．广州：广东工业大学，2019.
24	覃健诚，钟宇，陆以勤，等．基于梅森数的密钥交换或公钥密码加密优化方法及系统：202111668723.5 ［P］．2022-04-29.

编辑推荐 0

Metrics

阅读次数

全文

HTML			PDF

最新录用	在线预览	正式出版	最新录用	在线预览	正式出版
0	0	15	1	0	60

来源	本网站	其他网站

次数	30	46
比例	39%	61%

摘要

160

最新录用	在线预览	正式出版

11	0	149

来源	本网站	其他网站

次数	42	118
比例	26%	74%

算法	时间复杂度				数据预处理	占用空间/b
算法	取模	模乘	模幂	模幂（忽略分段乘法）	数据预处理	占用空间/b
传统mod	O（n²）	O（n²）	O（n³）	O（n³）	无	5n
蒙哥马利	O（n）	O（n²）	O（n³）	O（n²）	有	7n
CZ-Mod	O（n）	O（n²）	O（n³）	O（n²）	无	3n

微指令地址	微指令（控制信号）	下一微指令地址
1000	CLK_RegA， CLK_RegB， CLK_RegS	1001
1001	CLK_RegX0	1002
1002	！EN_ADD1，！EN_MUL1	C（n，n+1，…，n+m）=0？ 1003 ： 1001
1003	CLK_RegX	ffff

密钥位数	计时循环次数	单次DHM密钥交换时长/s			耗时倍数
密钥位数	计时循环次数	传统mod	mod1	mod2	耗时倍数
512	40 000	0.001 7		0.000 5	3.67
521	20 000	0.001 9	0.000 5		3.70
607	20 000	0.002 5	0.000 8		3.33
1 024	5 000	0.010 6		0.003 2	3.31
1 279	2 000	0.021 5	0.006 0		3.58
2 048	800	0.088 8		0.022 5	3.94
2 203	400	0.110 0	0.027 5		4.00
2 281	400	0.115 0	0.040 0		2.88
3 217	160	0.294 0	0.106 0		2.76
4 096	100	0.590 0		0.230 0	2.57
4 253	80	0.738 0	0.200 0		3.69
4 423	50	0.840 0	0.240 0		3.50
8 192	10	5.000 0		1.300 0	3.85
9 689	8	8.130 0	2.380 0		3.42
9 941	8	9.000 0	2.380 0		3.79

密钥位数	计时循环次数	单次DHM密钥交换时长/s			耗时倍数
密钥位数	计时循环次数	传统mod	mod1	mod2	耗时倍数
512	2 000	0.027 0		0.007 0	3.86
521	2 000	0.032 5	0.008 0		4.06
607	1 000	0.042 0	0.012 0		3.50
1 024	250	0.172 0		0.048 0	3.58
1 279	200	0.355 0	0.095 0		3.74
2 048	40	1.300 0		0.400 0	3.25
2 203	20	1.550 0	0.500 0		3.10
2 281	20	1.850 0	0.600 0		3.08
3 217	8	4.750 0	1.630 0		2.92
4 096	4	9.750 0		3.250 0	3.00
4 253	4	10.800 0	3.750 0		2.87
4 423	4	12.300 0	4.250 0		2.88
8 192	2	73.500 0		26.000 0	2.83
9 689	2	123.000 0	44.000 0		2.78
9 941	2	131.000 0	47.500 0		2.76

[1]	陆以勤, 毛中书, 程喆, 等. SDN 拓扑攻击及其防御[J]. 华南理工大学学报（自然科学版）, 2020, 48(11): 114-122.
[2]	文志诚陈志刚唐军. 基于时间序列分析的网络安全态势预测[J]. 华南理工大学学报（自然科学版）, 2016, 44(5): 137-143,150.
[3]	徐红云许隽龚羽菁徐梦真. 基于空间混淆位置隐私保护的位置隐私区域生成算法[J]. 华南理工大学学报（自然科学版）, 2014, 42(1): 93-103.
[4]	刘小跃杨凯马建峰 . 基于D-S 证据理论的双层卫星网络可信路由[J]. 华南理工大学学报（自然科学版）, 2011, 39(5): 78-83.
[5]	陈君华胡昌振石峰危胜军. 一种随机-无标度混合的P2P蠕虫传播模型[J]. 华南理工大学学报（自然科学版）, 2010, 38(5): 80-85.

基于类梅森数的物联网密钥交换快速取模算法

Fast Modulus Algorithm for Internet of Things Key Exchange Based on Mersenne-like Numbers

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 11

参考文献 24

相关文章 5

编辑推荐 0

Metrics

本文评价