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

覃健诚 钟宇 程喆 黄成海 陆以勤 潘伟锵

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

覃健诚1钟宇2，3程喆4黄成海1陆以勤1，5†潘伟锵5

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

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

网络安全；
传感器密码；
梅森数；
加密运算电路

随着物联网（IoT）的兴起，大量传感器应用在工业、农业、道路、家居等各种领域和场所，不断产生海量有价值的数据。与此同时，物联网面临的安全问题也变得越来越重要［1］。那些在物联网上产生、传输的宝贵数据需要安全保护，而数据加密就是各传感器节点保护数据的重要方式。基于各种公钥密码算法的公钥基础设施（PKI）在互联网中已得到广泛的应用，能够解决网络节点之间身份认证、密钥管理、数据保密、防伪造、防篡改、防抵赖等一系列问题，因此把传统PKI引入物联网中是一种实用的思路，但仍有问题需要解决。

部分物联网通信有高速度、低延时的需求，而物联网中轻型传感器节点的计算资源、能源有限，并且公钥密码算法的运算量较大。因此，当出于安全性要求而采用较长的密钥时，传感器节点会面临速度、功耗上的挑战：

（1）现有提高公钥密码算法速度的加速算法往往比较复杂，不利于在轻型传感器中实施，在传感器硬件性能薄弱、能耗受限的情况下加速效果不佳。

（2）现有专用的加密运算集成电路硬件，虽然能整合到传感器中以提高性能，但算法相应的逻辑电路复杂度高，会显著提高硬件成本。

（3）国内集成电路芯片制造工艺水平受制于国外封锁，比28 nm工艺更先进的芯片产能有限。而传感器芯片在工艺上的差距体现在性能、功耗上，需要用快速算法、硬件设计等方式来弥补。

针对物联网的加密保护，国内外已有的研究工作从不同的方面给出解决方法，但也存在一些不足：

（1）最基本的加密方法就是把互联网的传统PKI算法直接应用于物联网，如通过DHM（Diffie-Hellman-Merkle）密钥交换算法［2］产生随机的会话密钥，用ElGamal数字签名算法［3］进行节点身份认证或者验证数据的真伪，或者用RSA（Rirest-Shamirh-Adleman）算法［4］同时做到会话密钥的交换和数字签名等。但这种方法仅在加密功能上达到基本要求，并未解决物联网节点在速度、功耗上的问题。

（2）把加密中最消耗算力的模幂运算外包给云计算平台［5］，从而节省物联网节点的计算资源。但这种方法只是把能耗转嫁给云平台，能够实现功能但无优化，而且外包会导致延时增加，不利于加密传输速度。

（3）对物联网节点采用基于特征的快速认证加密算法，如指纹认证［6］、属性基加密［7］等，但这样的轻量级加密强度明显低于传统PKI算法，影响安全性。

（4）利用区块链技术实现物联网的分布式加密认证，从而分散算力负荷，如轻量级区块链算法［8］、优化SM2国密算法［9］等。但从PKI的集中式认证转为区块链的分布式认证是个大转变，本身又引入了更多需要解决的问题，如分布式网络的性能瓶颈、物联网节点算力限制下的51%算力攻击、女巫攻击等。

文中聚焦于加密相关的算法优化本身，集中式、分布式计算不在讨论范围内。实际上文中提出的快速模幂算法在集中式的PKI和分布式的区块链计算中都有用武之地。

为了适应物联网加密传输中大量轻型传感器节点运算性能、能源有限的特点，解决前文所述传感器运行公钥密码算法面临的速度、功耗问题，文中提出了一种基于类梅森数的增强型快速密钥交换算法（CZ-Mod算法）。CZ-Mod算法是在原PKI加密算法的基础上，利用梅森数的数学特性，使复杂的mod（取模）运算变成简单的二进制移位相加运算，从而简化了mod运算，使相应的逻辑电路设计变得简单，以控制物联网传感器的硬件功耗和成本。

1.1　问题的物联网应用场景

物联网的信息安全是重要的需求，特别是无线传感器节点存在被窃听、被假冒的危险。借鉴互联网上的PKI，成熟的加密算法可以实现节点身份认证、数字签名、密钥交换、加密传输等安全功能。但如果把现有公钥加密算法直接用在物联网的传感器上，需要有足够的密码长度以防止暴力**，那么在节点能耗、算力上会面临挑战。

以一个无人机探测水底地貌的物联网应用场景为例，如图1所示。无人机母船运载多台无人机至目标水域，放飞无人机到周围探测水底地貌，收集数据并传回母船。无人机与母船之间的无线通信需要双向身份认证和加密传输，以防止无线窃听［10］。

图1　无人机探测水底地貌应用场景

物联网传感器节点受到算力、能耗的限制，直接沿用传统PKI算法的方式会存在问题。一方面，无人机探测数据的实时性要求较高，需要高速度、低延时的无线通信；
另一方面，无人机采用RSA之类公钥算法时的加密强度不宜低于512 b，否则有可能被强大的并行计算硬件资源暴力**。而无人机的载质量小，电能有限，所以运算性能较低。结果是加密强度越大，算法运行越慢。

算法优化的难点之一是不能只考虑速度的提高，还要考虑物联网传感器的功耗和成本问题，因此算法不可过于复杂。现有的加密算法如果要采用现场可编程门阵列（FPGA）、图形处理器（GPU）等硬件并行计算加速方式，往往只适用于重量级传感器，而对于轻型传感器则面临功耗大、成本高的挑战。

图2展示了一个适合于图1应用的典型物联网数据处理场景示意图，图中的网络有重型节点和轻型节点。轻型节点采集数据，汇总到重型节点，再通过压缩传输至云计算平台。这个过程中为了信息安全，数据通信需要加密，各种节点需要身份认证，因此PKI的现有加密算法可以借鉴和利用。

图2　典型物联网数据处理场景

物联网中的重型、轻型节点的区别主要体现在算力、能量供给和成本上。重型节点的算力和能耗没有受到太大限制，因此可以直接使用PKI算法。而轻型节点的算力和能量供给都很有限，如果直接使用PKI算法，当密钥长度达到512 b以上时加密速度会很慢，但轻型节点不适合采用FPGA、GPU并行加速，因为成本太高，功耗也大。

1.2　问题的前期研究基础

前期对上述物联网数据处理场景进行相关研究后，对无线传感器的计算问题提出了部分解决方法，主要涉及信源、信道、安全编码计算（即压缩、纠错、加密编码）以及可信计算，具体如下：

（1）对于数据压缩传输，已提出的海量数据压缩格式［11］和快速压缩算法［12-13］，可以节省无线通信带宽，减少发射功耗。

（2）对于数据加密传输，已提出的混沌压缩加密并行算法［14-15］，能做到压缩与加密合一，节省计算资源。

（3）对于纠错码，已提出的GPU加速的移动LDPC解码器［16］，可用于重型节点以提高无线抗干扰能力。

（4）对于无线节点分布式身份认证，已提出的嵌入式系统制成的无线认证中心［17-18］，用到了PKI的RSA等加密算法，但存在加密的速度问题。

在文献［18］的实验测试结果中，采用主频168 MHz的STM32嵌入式系统进行256 b的AES算法加密，耗时约0.6 ms，SHA-1散列计算耗时约0.2 ms，表明轻量级节点对数据进行加密传输、生成数字摘要的运算速度都足够快。而对于RSA加密计算，512 b和768 b加密的耗时分别约0.6 s和2.0 s，表明用RSA加密传递会话密钥和进行数字签名时，会有较大的延时，并且密钥越长延时越大，直至达到无法实用的程度。

文献［14］提出的混沌压缩加密算法，不论会话密钥有多长（甚至达到10 000 b），都不影响加密速度和计算资源。因此需要PKI算法进行密钥交换以获得会话密钥，例如采用RSA加密算法传送会话密钥。同样，密钥越长则RSA计算延时越大。而RSA只是物联网中速度较慢的加密算法之一，还有其他加密算法存在类似的问题。

1.3　要解决的问题

文中关注PKI中的一类加密算法的优化问题，这类算法的特点是基于Z整数集的数学难题进行加密，并且算法中包含mod运算，而mod运算是比加法和乘法更加复杂、消耗计算资源更多的操作。这类算法包括但不限于：①DHM密钥交换算法，基于离散对数难题，可用于生成会话密钥；
②Elgamal算法，基于离散对数难题，可用于会话密钥加密和数字签名；
③RSA算法，基于素因数分解难题，可用于会话密钥加密和数字签名；
④ECC算法，基于离散椭圆曲线难题，可用于会话密钥加密和数字签名。

文中要解决的问题集中于mod运算的优化上：如何使mod运算更快，需要的算力更少，从而有利于降低物联网节点的能耗，并简化运算逻辑电路设计。

由于mod运算过程也涉及加法、乘法运算，所以现有技术及相关研究涵盖了这些运算的优化。现有的优化方式可分为软件程序优化方式和硬件电路优化方式两大类，且两者可以互换，具体如下：

（1）软件程序优化方式。理论上有多种算法可以提高mod运算的速度，如文献［19］提到乘方的不同快速算法，文中仅以代表性的蒙哥马利算法为例，该算法是对模幂运算的优化，主要思路是减少除法运算，转化为快速的移位运算，从而减少耗时。不过该算法需要做预处理计算，功能较复杂，也增加了一定的延时。

类似地，现有的一些快速乘法的算法也显得过于复杂，如用快速傅里叶变换（FFT）把乘法变为加法的方式［20］。由于物联网节点参与运算的密钥低于10 000 b，这些快速乘法的优势发挥不出来，FFT及其逆变换的延时抵消了原本缩短的运算时间。

上述软件优化方式对于物联网传感器节点而言，其算法仍然过于复杂。在算力有限的轻量级节点中，复杂的算法会对延时有不利的影响，而且会使运算逻辑电路设计更复杂，对算法的硬件化加速造成困难。轻量级节点为了简化运算，保障硬件可靠运行，往往继续采用最基本的乘方快速算法。

（2）硬件电路优化方式。采用FPGA、GPU等硬件加速方式提高mod运算性能，如果单从缩短延时的角度而言是有效的，但现有研究一般不是专门针对物联网场景。一个代表性的例子是利用GPU并行计算加速RSA算法［21］。乔洋［22］基于OpenCL和GPU实现了RSA并行算法，但未考虑到物联网传感器的能耗、成本限制。因为某些需要长时间运行的轻量级无线传感器会供应不起FPGA或GPU的能耗，或者硬件成本过高。

近年有针对物联网节点的国密算法硬件加速SoC的研究［23］，其中国密算法SM2就是采用ECC算法加密。研究中采用的FPGA仅用于设计验证，最终则是要制成应用集成电路（ASIC）定制芯片，才能解决功耗和成本问题。

如前所述，mod运算的软件优化和硬件优化是可以互换的，如果找到一种软件的优化算法，那么也可以应用到硬件电路设计中，叠加两种优化效果。特别是复杂度低的软件优化算法，可以简化运算逻辑电路，使功耗、成本都降低。文中提出的CZ-Mod算法，就是一种简化了模幂运算的算法，并据此设计出相应的密钥交换方法和逻辑电路系统［24］。具体工作包括：提出了一种以类梅森数为模数的快速取模运算mod1，使复杂的mod运算变成简单的二进制移位相加运算；
提出了一种以近似类梅森数的正整数为模数的快速取模运算mod2，在简化mod运算的同时扩大模数的取值范围；
对mod1、mod2运算作逻辑电路设计，以简化mod运算的硬件电路；
将以上工作应用到物联网节点的密钥交换中，以优化模加、模乘和模幂运算，降低计算的复杂度，提高PKI密钥交换的速度。

梅森数是形如2-1的正整数，其中指数是素数。如果一个梅森数是素数，则称为梅森素数。文中取消梅森数中指数为素数的条件限制，提出了“类梅森数”的概念。若在PKI加密算法或者其他整数相关运算中，用类梅森数=2-1作为模数，那么在计算过程中的模加、模乘、模幂运算都不需要做除法，可以把慢速的mod运算转化为快速的二进制移位相加运算。

CZ-Mod算法由两种运算组成，分别定义为mod1和mod2运算，它们都是对传统mod运算在特定条件下的优化。其中mod1运算以类梅森数为模数，mod2运算以mod1为基础作出扩展，以近似类梅森数的正整数为模数。

2.1　以类梅森数为模数的mod1运算

定义1 类梅森数是形如2-1的正整数，其中指数是正整数。

定义2 mod1运算是模数为类梅森数的mod运算。

在整数集合内几种mod1运算等效于：

（1）模加，即=（+） mod1=（+） mod （2-1）；

（2）模乘，即=mod1=mod （2-1）；

（3）模幂，即=Amod1=Amod （2-1）。

定理1 类梅森数= 2-1，任意非负整数<22n，的二进制高位为，低位为，则

mod1= （+） mod（1）

证明= 2H +，

2mod= 2mod （2-1）=1，

2Hmod= （2mod）（mod） =，

mod1= （2H+） mod= （+） mod，

证毕。

根据定理1，只要重复运用式（1）不超过2次，就能使的高位= 0，此时就是mod的最终结果。

类梅森数去掉了梅森数指数为素数的约束条件，使mod运算的适用范围更广。式（1）使mod运算等价于移位相加运算，不需要做除法算法。在各种PKI加密算法中，完全可以做到每一步模加、模乘、模幂运算的中间结果数字位数都控制在2+2以内。

图3是mod1的模加、模乘运算流程图。而模幂运算是在模乘运算基础上由快速指数运算组合而成，可参考文献［19］。图中CLK_Reg等时钟信号是为了对应后面逻辑电路设计中的时序。若是用C/C++等软件编程实现图3的运算流程，则可以忽略这些时钟信号。

图3　mod1的模加、模乘运算流程图

2.2　以近似类梅森数为模数的mod2运算

定义3 近似类梅森数是形如2-S的正整数，其中是正整数，是一个比较小的正整数。

定义4 mod2运算是模数为近似类梅森数的mod运算。

在定义3中整数的“比较小”不作明确的定义，在实际算法应用中的大小限制以不会导致运算过程的进位溢出错误为准。

在整数集合内几种mod2运算等效于：

（1）模加，即=（+） mod2=（+） mod （2-S）；

（2）模乘，即=mod2=mod （2-S）；

（3）模幂，即=Amod2=Amod （2-S）。

定理2 近似类梅森数= 2-S，任意非负整数<22n，其中的二进制高位为，低位为，则

mod2= （+） mod（2）

证明= 2H +，

2mod= 2mod （2 - S） =，

2Hmod= （2mod）（mod） =，

mod2= （2H +） mod= （+） mod，

证毕。

式（2）使mod运算等价于移位相加运算，不需要做除法运算。这是对式（1）的拓展，可以使模数的可选择范围再扩大，不再局限于梅森数本身的形式。其中，系数只要一个整数寄存器即可容纳得下，那么就不属于长整数分段乘法，而是快速整数乘法运算，+与+的运算性能差距很小。

图4是mod2的模加、模乘运算流程图。而模幂运算同样以模乘运算为基础。

图4　mod2的模加、模乘运算流程图

CZ-Mod算法的核心是对mod运算的优化，文中对该算法的复杂度分析除了专门针对mod1、mod2运算与传统mod运算作对比分析外，还把mod运算放到模幂运算中进行分析。因为DHM、Elgamal和RSA等常见KPI加密算法的整体性能主要体现在模幂运算上，而不是单独看mod运算的局部性能。

进行对比分析的运算包括传统mod运算，CZ-Mod算法的mod1、mod2运算，以及蒙哥马利算法的模乘运算。

3.1　时间复杂度分析

512 b以上长整数的传统mod运算常用分段除法，算法类似于10进制竖式除法，只是10进制改为分段二进制。设模数的位数为，则分段数与是倍数关系。分段除法需要循环大约轮，每轮需要做复杂度为（）的分段快速乘法和减法，因此整个mod运算的时间复杂度为（2）。由于和的倍数关系，时间复杂度即为（2）。

蒙哥马利模乘运算通过设置约简基数，把除法运算变为移位运算，时间复杂度为（）。但需要进行一次性数据预处理，仍要用到传统mod运算，故时间复杂度为（2）。模乘中的分段乘法时间复杂度也为（2）。综合可知，蒙哥马利模乘运算的时间复杂度为（2）。

CZ-Mod算法的mod1、mod2运算把除法运算转化为移位相加运算，时间复杂度为（）。若是用于模乘，由于分段乘法时间复杂度是（2），掩盖了mod1、mod2取模运算的（），所以CZ-Mod算法的模乘运算时间复杂度也是（2），并且CZ-Mod算法不需要进行数据预处理。

上述几种算法的模幂运算均使用快速指数运算，若指数也是位，则进行轮循环的模乘运算，每轮1到2次模乘运算。因此几种算法的模幂运算时间复杂度均为（3）。

但蒙哥马利算法和CZ-Mod算法的瓶颈都在分段乘法的时间复杂度（2）。若为了看出区别，特意忽略分段乘法，只看模幂运算中的取模，则传统mod运算的时间复杂度仍为（3），而蒙哥马利算法、CZ-Mod算法的时间复杂度则降为（2）。

3.2　空间复杂度分析

设模数的位数为，则传统mod运算、蒙哥马利算法和CZ-Mod算法的空间复杂度均为（），只是存储空间（单位为b）倍数上有一些差异。

传统mod运算采用分段除法，要保存被除数（长度2）、除数（长度）和中间结果（长度2），共占用空间5。

蒙哥马利算法需要保存被除数（长度2）、除数（长度）、约简基数及其倒数（长度2）和中间结果（长度2），共占用空间7。

CZ-Mod算法需要保存被除数（长度2）和中间结果（长度），除数不用保存，值很小可忽略其位数，共占用空间3。

表1给出了3种算法的取模运算复杂度。

表1　3种算法的取模运算复杂度对比

Table 1　Comparison of modulus operation complexity among three algorithms

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

3.3　可用性与安全性分析

CZ-Mod算法的可用性从两个方面进行分析：一是CZ-Mod在物联网的嵌入式系统中的运行性能是否满足要求；
二是CZ-Mod对PKI的密钥生成运算有何影响，实际应用是否可行。除了这两方面，其他部分与普通PKI算法相同，暂未发现技术实现上有其他问题。

从图3、图4可以看到，CZ-Mod算法是简单的加法、乘法运算的组合，处理二进制高低位数据时可能还涉及移位运算，这都很容易实现。在后面的实验测试中，就是用C语言编写CZ-Mod算法程序在x86/64和ARM平台上运行的。如果ARM平台的树莓派仍不能代表物联网嵌入式系统终端，那么把C程序移植到STM32单片机上运行并不存在技术上的问题。至于性能，文献［18］已测试过传统mod运算的RSA算法在STM32单片机上的运算速度是可以实用的，而如果用CZ-Mod算法，则运算速度会更快。

CZ-Mod对PKI密钥生成运算的影响是：需要寻找近似类梅森素数来生成公钥/私钥对，这是耗费较多算力的过程。不过可以参考传统mod运算的RSA算法，生成公钥/私钥对同样需要寻找大素数，也要耗费大量算力，但RSA算法在PKI中是可以完全实用的。因为RSA算法的寻找大素数运算已经有足够快的Miller-Rabin概率算法可以筛选出数据，再经过AKS（Agrawal-Kayal-Saxena）算法确认，这两个算法同样适用于CZ-Mod算法的寻找近似类梅森素数。而且寻找大素数的运算并不需要在物联网终端进行密钥交换时进行，而是事先完成的，因而可以在算力充沛的云平台上实现，对物联网终端的密钥交换性能毫无影响，因此在实际应用中是可行的。

对于CZ-Mod的安全性，由于算法仅仅是改动了传统mod运算部分，因此只需要考虑这部分改动对整个PKI加密的安全性有没有影响。对比代表mod1运算的式（1）与代表mod2运算的式（2）可知，式（1）就是式（2）在=1时的特例，由此可以集中分析式（2）。

注意到定理2的近似类梅森数=2-S，当取值不受限制时，实际上就是任何数，此时的mod2与传统mod运算是等价运算，假如mod2运算的安全性有任何可**之处，这意味着传统mod运算也可以采用同样方法**，也就是传统PKI加密可**。但目前为止，在传统的电子计算机领域（即不考虑量子计算机上类似于Shor算法的理论上可**、而工程技术上尚未实用的情况），传统PKI加密仍是安全的。

因此，mod2运算与传统mod运算处于同一安全水平，对mod2运算的**将意味着对PKI的**。实际上，对定理2中的取值未作限制，仅提议“足够小”以获得实际运算性能。未发现的取值范围缩小或放大对PKI加密的安全性有影响，如常见PKI算法DHM、RSA和Elgamal的模数=2-S都是公开的，无须**求出，因此缩小或放大的取值范围并不能取得**上的优势。

3.4　运算逻辑电路设计

采用硬件电路加速是提升物联网节点性能的一种途径，其中重型节点可以用GPU、FPGA或ASIC，轻型节点通常要用ASIC才能控制能耗和成本。FPGA和ASIC可以采用同样的逻辑电路设计，但算法本身的复杂程度会影响电路的规模和设计复杂性。如果算法太复杂，会造成电路规模大、延时大、设计成本高，抵消硬件电路加速的效益。

表1中3种取模算法的硬件电路加速潜力如下：

（1）传统mod算法最复杂，分段除法需要设计多轮循环控制逻辑，循环造成延时很大，因此硬件加速效果差、功耗大、设计成本和制造成本都高。

（2）蒙哥马利算法把除法运算变成移位运算，所以硬件加速效果好，需要做数据预处理，其中仍需要分段除法运算。虽然一次性预处理的延时对整个模幂运算速度的影响不大，但是预处理功能的逻辑电路少不了，因此硬件规模大、设计成本和制造成本都高。

（3）CZ-Mod算法把除法运算变成移位相加运算，所以硬件加速效果好，而且CZ-Mod算法不需要做数据预处理，没有额外功能的逻辑电路，因此硬件规模小、功耗小、设计成本和制造成本相对较低。

图5、图6分别是mod1、mod2运算的逻辑电路简化设计图，其中Reg就是寄存器，ADD1是加法器1，MUL1是乘法器1，依此类推。图中的运算时序由各寄存器的时钟输入信号（如CLK_Reg）控制。图5仅支持1次进位溢出处理。图6的是+1位二进制数。

图5　mod1的模加、模乘运算逻辑电路图

图6　mod2的模加、模乘运算逻辑电路图

由于图5、图6是CZ-Mod运算的执行部件，还需要控制部件来控制执行的时序。控制部件可以用微程序控制器或组合逻辑电路控制器实现：控制部件以适当的顺序向各寄存器输出时钟信号（如CTL_Reg），触发相应的寄存器（如Reg）更新数据，只要时钟信号充分考虑各部件（如加法器ADD1）的延时即可。

表2是微程序控制器对图6的mod2运算逻辑电路的控制时序，而图5的mod1运算控制时序更简单。作为对比，普通mod运算多了除法运算，即使用上专门的阵列除法器，延时也明显高于只有加法器、乘法器的mod1/mod2运算。

表2　微程序控制器对mod2逻辑电路的控制时序

Table 2　Time sequence of microprogram control unit for mod2 logic circuit

微指令地址微指令（控制信号）下一微指令地址 1000CLK_RegA， CLK_RegB， CLK_RegS1001 1001CLK_RegX01002 1002！EN_ADD1，！EN_MUL1C（n，n+1，…，n+m）=0？ 1003 ：
1001 1003CLK_RegXffff

文中聚焦于类梅森数快速取模算法的理论研究，对硬件电路设计的工作仅限于理论上比较其是否简单易实现、延时是否低，实际的电路设计及电路实验并非文中研究工作的范围，可作为未来研究工作的内容。

为了模拟分析物联网重型节点和轻型节点的密钥交换性能，文中分别用x86/64和ARM两种平台运行DHM密钥交换算法，DHM算法中的mod运算部分采用传统mod算法和CZ-Mod算法进行性能对比测试。

根据DHM密钥交换算法流程，通信双方可以同时做一次模幂运算，把结果发送给对方，再同时把收到的数据做一次模幂运算，得到会话密钥。所以DHM算法的主要耗时就是两次模幂运算的时间。

虽然测试平台的CPU都是多核多线程的，但测试时的DHM采用串行计算，只使用了单线程。由于单次DHM密钥交换的耗时是ms级，所以采用多次循环DHM运算，采用总时长除以循环次数的方式计算单次密钥交换的平均耗时。循环次数以保证总时长超过10 s为最低标准，以限制系统计时的误差。

DHM算法的测试程序用C语言编写，GCC编译执行。测试了密钥长度从512 b至9 941 b的平均耗时。混沌压缩加密算法“CZ算法”可以支持10 000 b的会话密钥［13］。

对于以纯软件方式运行密钥交换算法的物联网节点而言，文中实验以x86/64平台的移动电脑代表物联网重型节点，以ARM平台的树莓派代表物联网轻型节点，与实际的物联网节点硬件性能相当，因此测试结果具有充分的参考价值。算法的C语言程序若要移植到常见嵌入式系统STM32单片机中也不存在技术问题，并且STM32的加密性能已在文献［18］中测试验证过。CZ-Mod算法仅对运算时间有加速效果，对物联网传输时间无影响。因此，文中实验可以反映出算法在物联网中的加速效果（文中工作作为理论研究的算法成果总结，并未包含下一研究阶段的实际物联网应用测试工作）。

在测试中，CZ-Mod算法预先根据密钥长度选择mod1或mod2运算：由于一些特定长度的梅森数是素数，这些长度的密钥交换就采用梅森素数作为模数，选用mod1运算；
否则，寻找与密钥长度相同，并且是素数的近似类梅森数作为模数，选用mod2运算。

4.1　x86/64平台测试结果分析

x86/64测试平台是一个移动电脑，硬件配置为：CPU是Intel Core i5-8250U@1.6 GHz，内存为8 GB，硬盘为256 GB SSD。用这个平台模拟分析物联网重型移动节点的性能。

表3是x86/64平台采用了不同mod运算的DHM密钥交换测试结果对比，对应的耗时曲线如图7（a）所示。从算法的时间复杂度分析和表1可知，虽然传统mod和CZ-Mod的取模运算时间复杂度不同，但模幂运算时间复杂度都是（3）。图7（a）显示的不是三次曲线，因为、轴都用了对数坐标系，而logn3=3logn，所以展现的是近似线性图像，三次曲线的指数变成了斜率系数。

表3　x86/64平台上DHM密钥交换测试结果对比

Table 3　Test results comparison of DHM key exchange on x86/64 platform

密钥位数计时循环次数单次DHM密钥交换时长/s耗时倍数 传统modmod1mod2 51240 0000.001 7 0.000 53.67 52120 0000.001 90.000 5 3.70 60720 0000.002 50.000 8 3.33 1 0245 0000.010 6 0.003 23.31 1 2792 0000.021 50.006 0 3.58 2 0488000.088 8 0.022 53.94 2 2034000.110 00.027 5 4.00 2 2814000.115 00.040 0 2.88 3 2171600.294 00.106 0 2.76 4 0961000.590 0 0.230 02.57 4 253800.738 00.200 0 3.69 4 423500.840 00.240 0 3.50 8 192105.000 0 1.300 03.85 9 68988.130 02.380 0 3.42 9 94189.000 02.380 0 3.79

图7　DHM密钥交换耗时对比

从表3可以看出，DHM采用传统mod运算还是CZ-Mod运算，耗时相差最低2.57倍，最高4.00倍，这个速度差距比较明显。从图7（a）可以看出，采用mod1和mod2运算的曲线几乎重合，意味着两者的速度差异很小，即式（1）和式（2）等号右边的运算所消耗资源都差不多。

4.2　ARM平台测试结果分析

ARM测试平台是一个树莓派2B型，硬件配置为：CPU是ARM Cortex-A7@900 MHz，内存为1 GB，硬盘为32 GB SD卡。用这个平台模拟分析物联网轻型移动节点的性能。

表4是ARM平台采用了不同mod运算的DHM密钥交换测试结果对比，对应的耗时曲线如图7（b）所示。可以看到，ARM平台的测试结果与x86/64平台的测试结果很相似。从表4可以看出，DHM采用传统mod运算还是CZ-Mod运算，耗时相差最低2.76倍，最高4.06倍。除了运算速度差异外，由于轻型节点相比重型节点更容易受到能耗的限制，这个耗时数据也可以作为能耗的参考，因为DHM运算耗时的过程就是消耗能量的过程。

表4　ARM平台上DHM密钥交换测试结果对比

Table 4　Test results comparison of DHM key exchange on ARM platform

密钥位数计时循环次数单次DHM密钥交换时长/s耗时倍数 传统modmod1mod2 5122 0000.027 0 0.007 03.86 5212 0000.032 50.008 0 4.06 6071 0000.042 00.012 0 3.50 1 0242500.172 0 0.048 03.58 1 2792000.355 00.095 0 3.74 2 048401.300 0 0.400 03.25 2 203201.550 00.500 0 3.10 2 281201.850 00.600 0 3.08 3 21784.750 01.630 0 2.92 4 09649.750 0 3.250 03.00 4 253410.800 03.750 0 2.87 4 423412.300 04.250 0 2.88 8 192273.500 0 26.000 02.83 9 6892123.000 044.000 0 2.78 9 9412131.000 047.500 0 2.76

物联网应用越来越广泛，大量传感器在各行各业发挥着重要的作用，而物联网节点也有着安全认证、加密通信的巨大需求。传统互联网的PKI加密算法要运用到物联网中，会遇到高速度、低延时的通信需求与节点低功耗、低算力的限制之间的矛盾。尤其是无线传感器网络中的轻量级节点，还会受能量供应、硬件成本、集成电路制造工艺水平等的限制，如何为运算量大的公钥密码算法提高运算速度，成为物联网场景下亟须解决的问题。

文中借鉴梅森数的数学特性，提出了一种基于类梅森数的增强型快速密钥交换算法CZ-Mod，该算法能使关键的mod运算的时间复杂度降至（）。CZ-Mod算法包含mod1和mod2两种可选运算，两者都能把mod运算中最耗时的除法运算简化为移位相加运算，同时简化其运算逻辑电路的设计。

CZ-Mod算法可用于DHM、Elgamal、RSA、ECC和其他需要用到模加、模乘、模幂等涉及mod运算的算法。文中用DHM密钥交换算法在x86/64和ARM平台上进行了对比测试实验。结果表明，采用CZ-Mod算法的DHM密钥交换速度可达到常规算法的2.5～4倍。由于加密过程中运算单元在全速运行，这意味着物联网节点在算力上的能耗，常规算法可能达到CZ-Mod算法能耗的2.5～4倍，差距比较明显。

未来可以关注CZ-Mod算法中mod2运算的模数选取方法，并推广到更多算法上。由于类似DHM、Elgamal等算法的模数是素数，要想找近似类梅森数的大素数不存在问题，目前已经有快速找素数的算法。而RSA算法的模数是两数之积，要找到这样符合条件的模数还比较慢。虽然分配密钥、寻找模数的工作可以放在云计算平台上完成，但寻找两数乘积的近似类梅森数的快速算法，能够大大提高密钥生成的速度，减少算力消耗，值得进一步研究。

［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.

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

12，3411，55

（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）

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(). 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.

network security；
sensor key；
Mersenne number；
encrypting operation circuit

Supported by the Key-Area R&D Program of Guangdong Province （2020B0101120002，2019B010137001）

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

2022⁃06⁃06

广东省重点领域研发计划项目（2020B0101120002，2019B010137001）；
广东省科技厅海外名师项目（科技类）（粤财科教［2021］157号）

覃健诚（1976-），男，博士，高级工程师，主要从事加密算法、物联网、SDN、网络安全研究。E-mail：jcqin@scut.edu.cn

陆以勤（1968-），男，教授，博士生导师，主要从事SDN、网络功能虚拟化、网络安全研究。E-mail：eeyqlu@scut.edu.cn

TP393

1000-565X（2023）05-0024-12

猜你喜欢加密算法模数复杂度基于单片机和模数化设计的低压侧电压监视与保护装置能源工程(2021年2期)2021-07-21模数化设计方法在景观铺装设计中的应用绿色科技(2020年11期)2020-08-01一种低复杂度的惯性/GNSS矢量深组合方法中国惯性技术学报(2019年6期)2019-03-04基于LID模式的城区排涝模数探析水利规划与设计(2017年6期)2017-07-18求图上广探树的时间复杂度中央民族大学学报（自然科学版）(2017年2期)2017-06-11一种新型的RSA密码体制模数分解算法信息安全研究(2016年3期)2016-12-01某雷达导51 头中心控制软件圈复杂度分析与改进火控雷达技术(2016年3期)2016-02-06基于小波变换和混沌映射的图像加密算法火控雷达技术(2016年1期)2016-02-06出口技术复杂度研究回顾与评述浙江理工大学学报(自然科学版)(2015年10期)2015-03-01Hill加密算法的改进四川师范大学学报（自然科学版）(2015年1期)2015-02-28

推荐访问:密钥 联网 算法