一种基于双勾函数的数据加密算法研究

李宏伟，潘志远，黄继杰

(1.国家电网有限公司技术学院分公司，山东 济南 250002；2.北京科东电力控制系统有限责任公司，北京 100192)

0 引 言

根据香农定理，每传送一次密文就更换密钥是绝对安全的，量子保密通信可实现这一要求[1],但量子信号的减衰除受线路运行环境的影响，还受设备精度和组网模式的影响，使得经典的对称和非对称加密方法还在继续研究和应用。文献[2-4]在研究网络安全时采用了基于主体身份鉴别和认证、数据加密传输、传输链路节点身份鉴别和认证等技术；文献[5-7]在研究区块链时采用了非对称加密算法RSA、对称加密AES算法和单向加密算法SHA256；文献[8-9]在研究电力变电站远动通信时采用了非对称加密和对称加密混用的算法；文献[10-14]对非对称加密中的椭圆曲线加密算法进行了研究和应用。

但随着量子计算技术的发展及其超乎想象的计算能力，使得经典的对称和非对称加密方法中的密钥和密码将有可能被轻易破解，促进了后量子密码时代的到来。其中格密码学的研究成为一大热点[15-16]，且成为了美国国家标准与技术研究院(national institute of standards and technology，NIST)后量子密码时代的优选技术。

该文从非线性的双勾函数特性出发，依次研究其在对称加密、非对称加密及格加密中的算法实现及在电力云培训仿真中的应用。

1 双勾函数的特性

双勾函数形如：

(1)

双勾函数的图像是分别以y轴和y=ax为渐近线的两支曲线，且图像上任意一点到两条渐近线的距离之积恰为渐近线夹角(0°～180°)的正弦值与|b|的乘积。

变化趋势：在y轴左边先增后减，在y轴右边先减后增。双勾函数的两条渐近线分别为y轴和y=ax。

双勾函数的图形是在笛卡尔坐标系中第一和第四象限的曲线，现在基于椭圆曲线加密算法(ECC算法)被广泛应用于互联网领域，如区块链的加密中。ECC算法的数学原理是椭圆曲线和离散对数，使得ECC算法要比RSA算法复杂很多，这种复杂的计算虽带来了性能提升的好处，但是也同时潜藏了一些问题。首先是一套ECC算法标准所对应的这条曲线，可能暗藏数学机关并可以通过后门来破解，比如目前使用面很广的一套标准是美国国家安全局发布的，这套标准就被怀疑是有后门。

另外一个问题就是基于ECC的专利太多，而且这些专利很多都被一个公司所持有，这个公司就是黑莓，这就使得开发一套新的ECC方案有可能被认为触犯了某个专利。故虽然ECC目前发展良好，但是也面临着各种挑战，这就为基于双勾函数曲线加密的应用提供了机会。

2 基于双勾函数的加密算法

2.1 基于双勾函数的对称加密

图1 双勾函数做垂线和平行线

以由双勾函数曲线上的点(X0,Y0)为一个开始的(原文，密文)对，从点(X0,Y0)做渐近线的法线，交双勾函数曲线上的点 (X1,Y1)，再由点(X1,Y1)做平行线，交于勾函数曲线上的点(X2,Y2)，由下列方程：

(2)

(3)

再由点(X1,Y1)做平行线，交于双勾函数曲线上的点(X2,Y2)：

(4)

再从点(X2,Y2)开始按上述方法做渐近线的法线，并与交点处做X轴的平行线，交于双勾曲线上，这个过程称为第二次操作。依此可进行第三次、第四次，直至第N次，此时N为偶数。可以看出第N次交于双勾曲线上的点由三个参数决定：重复次数N，双勾函数参量a和b(这两个参量也可以换成渐近线与X轴的夹角β，用弧度表示；和最低点(X0,Y0)的X0值，即三元组(β，X0，N)。

图2 双勾函数的解密过程

以图中点(X0,Y0)为例，先做平行线交于点(X0,Y0)，此为第一次操作，再按上面的步骤，从点(X0,Y0)作法线，交于点(X1,Y1)，此为第二次操作，再由点(X1,Y1)做平行线，交于双勾函数曲线上的点(X2,Y2)，这个过程称为第三次操作。依此可进行第四次、第五次，直至第N次，此时N为奇数。

2.2 基于双勾函数的非对称加密

上述由法线和平行线操作次数构成的集是一个阿贝尔群(P，+)，因为：

封闭性：s和t是整数操作次数，属于P，那么s+t也是整数操作次数，也属于P。

结合性：(s+t)+c=s+(t+c)，为双勾曲线上同一点。

单位元：0即为单位元(在基点G没操作)，因为对于所有操作次数s，s+0=0+s=s，为双勾曲线上同一点。

逆元：s的逆元为-s(由操作s次后的双勾曲线上的点，反向操作，即当s为奇数时，做渐近线的法线；s为偶数时，作平行线，交于双勾函数曲线上的另一点)，因为s+(-s)=0,即单位元(回到基点G)。

所以由法线和平行线操作次数构成的集P是阿贝尔群(P,+)。

双勾函数曲线上求解的问题描述为：已知(1)双勾函数曲线E；(2)双勾函数曲线E上一点G(基点)；(3)双勾函数曲线E上的一点xG(x为由G作法线和平行线的总次数)。据此求解x，这个问题的难度保证了基于双勾函数曲线加码的安全性。

基于双勾函数数字签名法的加密算法(DHC)具体如下：

基于双勾函数的数据加密算法属于非对称密钥加密系统体系，又称公钥密钥加密体系。它需要使用不同的密钥来分别完成加密和解密操作，一个公开发布，即公开密钥，另一个由用户自己秘密保存，即私用密钥。信息发送者用公开密钥去加密，而信息接收者则用私用密钥去解密。

针对上面确定的双勾函数加密三元组(β，X0，Xg)，都采用上面基于素数的公共密钥机制来生成。这三个数中都是带小数的实数，为确保法线能尽可能不平行于Y轴，β取值应在30至60之内为宜。同时，为了使第一次操作就是做法线，Xg应取最低点X0的右边值，即Xg大于X0。

在双勾函数曲线加密中，给定双勾函数曲线E，基点G和点kG(该点为从G点开始，做了k次上述操作后与双勾函数曲线E的交点)，称(β，X0，kG)为公钥，(β，X0，G)值为私钥，更简单地k就是真正的私钥。

计算公钥和私钥利用了上述“运算”中两种操作：奇数为做渐近线的法线，记录交点的y值；偶数为做平行于X的平行线，记录交点的x值的负数，即记录双勾函数曲线下半部对称的点的x值。

采用DHC算法对数据进行加密和解密，首先要确定分组的大小。由于DHC算法计算出的取值(奇数为做渐近线的法线，取交点的y值；偶数为做平行于X的平行线，取交点的x值的负数，即记录双勾函数曲线下半部对称的点的x值)是用4字节表示的浮点数表示，而从缓冲区明文M中取出的数是整数(次数)，为保证加密后的报文长度不变，每次从M中取4字节的整数i出来，从双勾函数曲线的点kG处做i次运算，从而得到4字节明文对应的密文。

使用DHC算法解密时，从双勾函数曲线的点G处循环做运算(奇数为做渐近线的法线，取交点的y值；偶数为做平行于X的平行线，取交点的x值的负数，即记录双勾函数曲线下半部对称的点的x值)，直至与4字节密文所对应的浮点数差小于0.000 01为止(按照IEEE754的标准，单精度浮点数有效位最多小数点后7位)，并将这次的循环次数n减去私钥k所得的整数，其4字节所对应的二进制就是明文中对应的4字节信息。

上述加解密保证了明文和密文等长，但以4字节作为整数的过程计算量大。为此取明文中的2字节作为整数(操作次数)，每次从M中取2字节的整数i出来，从双勾函数曲线的点kG处做i次运算，从而得到2字节明文对应的4字节密文，因而密文长度是明文的2倍。为了更快的应用场合，也可以每次从M中取1字节的整数i出来，从双勾函数曲线的点kG处做i次运算，从而得到1字节明文对应的4字节密文，因而密文长度是明文的4倍。

使用DHC算法进行数字签名时，设私钥、公钥分别为k、K，即K=kG，其中G为位于双勾函数(y=ax+b/x,ab>0)曲线上的基点。设定哈希值用h表示，私钥用k表示，随机数用r表示，根据如下原理：

hG/s+xK/s=hG/s+x(kG)/s=(h+xk)G/s=r(h+xk)G/(h+kx)=rG。

(1)私钥签名的过程。

(a)选择随机数r，计算点rG。

(b)根据随机数r，消息M的哈希值h，私钥k，计算s=(h+kx)/r。

(c)将消息M和签名{rG,s}发给接收方。

此处的消息M为采用DHC算法对数据进行加密后的信息。

上述计算中，x表示双勾函数曲线的基点G的X轴值，kx是指在双勾曲线上从基点做了k次上文所提的操作(垂直线和平行线)的次数。

(2)公钥验证签名的过程。

(a)接收方收到消息M以及签名{rG,s}。

(b)根据消息M采用与发送方相同的哈希算法求解哈希值h。

(c)使用发送方公钥K计算：hG/s+xK/s，将计算结果与rG比较，如相等即验签成功。

上述计算中，xK指在双勾曲线上从点K做了x次上文所提的操作(垂直线和平行线)的次数。

2.3 基于双勾函数的格加密研究

利用量子干涉效应使得“量子并行计算”的若干个计算结果中，一部分的计算结果被量子干涉所强化，而另外一部分被量子干涉所抵消。这将导致观测到特定结果的概率增加，从而使得量子计算机以更高的概率输出想要得到的计算结果。基于此量子干涉效应，Peter Shor于1994年提出了Shor算法。Shor算法可以用量子计算机以多项式时间求解周期函数的周期，而RSA、椭圆曲线等密码体制所基于的困难问题：大整数分解和离散对数求解，都可以转化为周期函数求解周期的问题，因而可以通过Shor算法求解。这使得现有的公钥密码体制很容易被量子计算机所击破。

2019年《Nature》上发表了Google最新一代量子处理器Sycamore，它包含53个量子比特，对量子处理器的输出进行重复性采样，并与经典计算机模拟的结果进行比较。Sycamore完成同样的任务只需要200 秒，而Google估计使用目前世界上最强大的超级计算机Summit需要1万年,以此证明该量子处理器实现了量子优越性(quantum supremacy)。IBM提出使用二级存储可以模拟54-bit量子计算机，并且通过优化将经典计算机执行任务的时间从1万年降低到2.55天。针对量子计算机的这种威胁，密码学家们提出了“后量子密码”这一概念。从广义的角度上说，后量子密码学研究量子计算机出现后将对密码学产生的影响；从狭义的角度上说，后量子密码主要关注于设计可抵抗量子计算威胁的密码算法，尤其是公钥加密和数字签名算法。

格密码就是这样一类备受关注的抗量子计算攻击的公钥密码体制。2020年7月22日，美国国家标准局NIST公布了其举办的后量子密码标准竞赛的第三轮入选算法，这意味着从2016年开始的美国后量子密码标准制定工作进入了最后的冲刺阶段，在7个正式入选第三轮的算法中，有5个都属于格密码的范畴。而与此同时，在中国密码学会举办的后量子密码算法竞赛中，格密码也在其中占据了相当大的比例。

格(lattice)是一种数学结构，定义为一组线性无关的非0向量(称作格基)的整系数线性组合。具体来说，给定一组格基，x1,x2,…,xn对任意的整数c1,c2,…,cn，c1x1,c2x2,…,cnxn都是属于这个格的向量，其中n称为格的维数。基于格的密码学近年来发展迅速，利用格上困难问题作为极微本原来构造的密码学方案层出不穷[17-20]。

(5)

显然c1y1,c2y2,…,cnyn也是双勾函数且是非线性的，故构成了格；同时c1y1+c2y2+…+cnyn也是双勾函数考虑。双勾函数在正一象限的曲线，由这个格构成了一个双勾曲线空间(正半部曲线)，包含了无穷多条这样的曲线，其中每条曲线由a和b两参数决定。

在用格进行加密时，需要求解数学难题来加大破解的计算量。取明文中三字节(并增加1)构成一个正整数ak，现取一未知的整数bk，构成双勾曲线空间中的一条双勾曲线yk。

选取c1k,c2k,…,cnk，使得c1ka1+c2ka2+…+cnkan=ak且c1kb1+c2kb2+…+cnkbn=bk，即由y1,y2,…,yn构成yk。当允许c1,c2,…,cn为正有理数时，计算满足上式中c1k,c2k,…,cnk的和为最小可以看成是一数学难题，存在进行加密的条件了。

另外，在这个双勾曲线空间中，求该曲线与任意两条曲线的交点。比如上式中y1和y2两条曲线的交点(Xc,Yc),其中：

(6)

在用格进行加密时所构成的双勾曲线yk，其与上面n条曲线的交点为(Xk1,Xk2,…,Xkn)，现在就是找出整数bk使(Xk1,Xk2,…,Xkn)存在，因为为负值开根号不成立(也即没交点，此时取值为0，表示没交点)。对于每个整数ak找出满足这条件的最小bk，其计算量随n的增大而加大，也可以看成是一数学难题，故而存在进行加密的条件了。

3 仿真实验或案例分析

在联想工作站(四颗Inter i5-6500 Cpu，48G内存)上进行仿真实验，同时在加解密的速度上与椭圆曲线加密算法(ECC)进行对比。在实现ECC时调用了LibTommath库(源码网址：https://blog.csdn.net/cg129054036/article/details/83862918)。

在用双勾函数加、解密(算法流程如图3、4所示)时，先根据选定的参数a、b和基点的x，依次做渐近线的法线和交点的x轴平行线，从而初始生成加密码值表。考虑到码值表的大小与取原文的字节数相关，这里取原文1个字节数来对应码值表前256个浮点数。这两算法的加密速度对比见表1。

表1 与椭圆曲线加密算法的速度对比

图3 基于双勾函数的加密流程

图4 基于双勾函数的解密流程

在应用案例上，将基于双勾函数数字签名法的加密算法(DHC)应用到了电力云培训仿真中,确保了云培训考核的安全性。具体实施过程如下：

(1)教员根据每个学员的邮箱信息在密码中心为其申请证书，如图5所示，为学员Bob的邮箱“bob@b.com”申请证书。

图5 双勾函数的非对称加密应用

(2)教员收到密码中心下发的学员Bob的私钥。

(3)学员Bob从密码中心获得他的公钥。

(4)学员Bob对获得的公钥进行验证以确定是他的公钥。

(5)学员Bob采用获得的公钥加密其考试答案，并利用自已的私钥进行数字签名，一并发给教员。

(6)教员采用学员的公钥对数字签名进行验证，验证通过后，采用学员Bob的私钥解密报文，获得学员Bob的考试答案。

4 结束语

双勾曲线函数仅由两个参数决定其曲线形状，可以在其曲线上添加某种操作来进行对称和非对称的加密。该文通过对其渐近线添加垂直线操作以及线上点的X轴平行线操作，将明文数值对应为交替所做的垂直线和平行线的次数，用最后一次交点的X或Y值作为对应的密文。这种对称加密算法比椭圆曲线加密算法快了两个数量级，在此基础上可设计相应的非对称加密算法(DHC)来满足快速加密场合的需求。同时可选择任意条双勾曲线函数作为格基，来构成非线性的格空间，从而具有了进行格加密的可能。