一种基于矩阵路径环的后量子加密解密方法和系统

1.本发明属于保密通信技术领域，更具体地，涉及一种基于矩阵路径环的后量子加密解密方法和系统。

背景技术：

2.随着互联网技术的蓬勃发展，通讯安全的重要性也与日俱增。在众多场合下，通讯双方都希望在利用公共信道的情况下进行保密通讯。例如，当用户向网上银行提交账号和密码时，用户希望这些信息在传递过程中是保密的，即任何第三方都无法窃听。当前正在被广泛使用的加密方法是公钥加密方法，此类方法的安全性是基于某些数学问题的算法复杂度。然而，随着科技的发展，特别是量子计算机的发展，公钥加密方法的安全性已经受到了威胁。因此，亟需开发更加安全可靠的抗量子计算的加密方法。
3.然而目前基于数论难题的公钥方案，如整数分解的，基于离散对数的elgamal，基于椭圆曲线的ecc等，实现效率较低。当前移动通信、无线传感网络、低廉智能卡、无线射频rfid 等新技术领域发展非常迅速。但这些特殊应用领域并不适用于直接使用基于rsa、elgamal、ecc 的公钥加密方案，因为这些传统公钥密码方案计算效率低，加解密时速度慢。所以，构造安全快速的公钥密码方案具有重要的现实意义。

技术实现要素：

4.针对现有技术的以上缺陷或改进需求，本发明提供了一种基于矩阵路径环的后量子加密解密方法和系统，其目的在于提高加解密的效率和安全性。
5.为实现上述目的，按照本发明的一个方面，提供了一种基于矩阵路径环的后量子加密解密方法，包括：s1.密钥生成：01.随机生成加权矩阵w；所述加权矩阵为非对称矩阵，其对角线上的元素为0，非对角线上的元素由随机数产生；所述非对称矩阵表示两个节点之间来回的路径不相等；02.随机生成n个随机数，由这n个随机数构成的回路生成第一回路矩阵环h；同理，生成第二回路矩阵环g；03.生成随机数k，输出私钥（k,g）；04.计算，，；
ꢀꢀ
表示第二回路矩阵环g的加权和；表示从g中任选的一条支路中节点，的加权值或距离，表示中的最大整数倍的倍数，是指除的余数，；05.输出公钥（g1，g2，g3）；s2.发送方生成随机数r，并利用公钥对消息明文m进行加密，生成密文：s2.发送方生成随机数r，并利用公钥对消息明文m进行加密，生成密文：s2.发送方生成随机数r，并利用公钥对消息明文m进行加密，生成密文：
s3.发送密文给接收方；s4.接收方解密密文，得到发送方产生的随机数r和m；。
6.进一步地，第一回路矩阵环h的生成方式为：随机生成n个大小不等的随机数，由这n个数构成回路，第一回路矩阵环h中n个元素为1：，其余元素都为0；
ꢀꢀ
，。
7.进一步地，第二回路矩阵环g的生成方式为：随机产生n个大小不等的随机数，由这n个数构成回路，第二回路矩阵环g中n个元素为1：，其余元素都为0；，。
8.按照本发明的另一方面提供了一种基于矩阵路径环的后量子加密解密系统，包括：密钥生成中心，用于执行以下处理：01.随机生成加权矩阵w；所述加权矩阵为非对称矩阵，其对角线上的元素为0，非对角线上的元素由随机数产生；所述非对称矩阵表示两个节点之间来回的路径不相等；02.随机生成n个随机数，由这n个随机数构成的回路生成第一回路矩阵环h；同理，生成第二回路矩阵环g；03.生成随机数k，输出私钥（k,g）；04.计算，，；表示第二回路矩阵环g的加权和；表示从g中任选的一条支路中节点，的加权值或距离，表示中的最大整数倍的倍数，是指除的余数，；05.输出公钥（g1，g2，g3）；发送方，用于生成随机数r，并利用公钥对消息明文m进行加密，生成密文，并将密文发送至接收方：文发送至接收方：文发送至接收方：接收方，用于解密密文，得到发送方产生的随机数r和m；。
9.进一步地，第一回路矩阵环h的生成方式为：随机生成n个大小不等的随机数，由这n个数构成回路，第一回路矩阵环h中n个元素为1：，其余元素都为0；，。
10.进一步地，第二回路矩阵环g的生成方式为：随机产生n个大小不等的随机数，由这n个数构成回路，第二回路矩阵环g中n个元素为1：，其余元素都为0；
，。
11.本发明还提供了一种电子设备，包括：处理器；存储器，其存储有计算机可执行程序，所述程序在被所述处理器执行时，使得所述处理器执行如上所述的基于矩阵路径环的后量子加密解密方法。
12.本发明还提供了一种计算机可读存储介质，其上存储有计算机程序，所述程序被处理器执行时实现如上所述的基于矩阵路径环的后量子加密解密方法。
13.总体而言，通过本发明所构思的以上技术方案与现有技术相比，能够取得下列有益效果。
14.本发明方法的安全性建立在np算法难解性的基础上：采用随机的方法生成两个回路矩阵，一个回路矩阵作为公开密钥，另一个回路矩阵作为秘密密钥，从加权矩阵中任意选择一个回路环矩阵，以及反过来在加权矩阵中到这个回路矩阵都是np完全问题，所以要破解私钥的回路矩阵环也是np完全问题，这就保证了私钥无法在多项式计算范围破解私钥的回路矩阵环，保障了加密解密的安全性；本发明在生成公钥、私钥和加密解密过程中，除传送数据，加密和解密过程中用到乘法运算，其它的运算都采用加法完成，计算简单，计算量小。
附图说明
15.图1是非对称加权矩阵。
16.图2是对称加权矩阵。
17.图3是本发明方法的流程图。
具体实施方式
18.为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。此外，下面所描述的本发明各个实施方式中所涉及到的技术特征只要彼此之间未构成冲突就可以相互组合。
19.旅行商问题，即tsp问题（traveling salesman problem）又译为旅行推销员问题、货郎担问题，是数学领域中著名难题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。迄今为止，这类问题中没有一个到有效算法。倾向于接受np完全问题（np-complete或npc）和np难题（np-hard或nph）不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。
20.本发明的重点是采用加权矩阵和回路矩阵环
ꢀꢀ
，将加解密问题转换为将tsp问题去描述，然后利用加权矩阵和回路矩阵环的hadamard乘积矩阵c非常方便的求出回路路径的加权和，本发明采用的加权矩阵可以是对称的或非对称的；事实上，从加权矩阵中任意选择一个回路环矩阵，要反过来在加权矩阵中到这个回路矩阵都是np完全问题，所以要破解私钥的回路矩阵环也np完全问题，这就保证了私钥是没有办法在多项式计算范围破解私钥的回路矩阵环。本发明采用了类似ecc的加密方式，使用简单的运算就能完成加密
和解密，但由私钥回路矩阵环产生的参数（回路矩阵环 g的加权和）和任选一个支路的加权数取模运算，这种计算方法简单有效，只用简单的组合运算就完成。
21.在介绍本发明方法具体步骤之前，先介绍方法中需要用到的如下概念：定义1：加权矩阵，有，正整数集合，加权矩阵描述为：描述为：对角线上的元素为0，非对角线上的元素由随机数产生，非0元素的数量为，这个矩阵可以是非对称的，如图1，也可以是对称的，如图2，非对称矩阵表示从节点i到节点j来回的路径是不等的，如果为对称的表示节点i到节点j来回的路径相等的。举例如下：定义2：回路环矩阵为,既在图中存在一个回路，该回路经过图中所有节点，且最后回到起始点，不妨设回路为：经过图中所有节点，且最后回到起始点，不妨设回路为：
ꢀꢀ
表示从节点到节点支路，在矩阵中就表示第行，第列的位置上为1。则回路环矩阵h为：矩阵h的元素除：，n个元素为1外，其余的都为0元素。
22.例如，对于顶点数为３的图，，回路为：1
→
3,3
→
2,2
→
1；对于顶点数为４的图，，回路为：1
→
2,2
→
3,3
→
4,4
→
1；以上都是回路环矩阵。
23.定义3：加权矩阵w 和回路环矩阵h对应的hadamard积的乘积矩阵c定义为：为：定义4：矩阵所有元素的和sum(c)为：其中：也可以称为回路环矩阵h的加权和；定义5：hadamard乘积矩阵c中不为零的向量，构成一个加权列向量p：定义6：全局最优回路环矩阵定义为：对于任意一个最优的回路环矩阵；如果对
于任意的一个回路环矩阵，有则称回路环矩阵全局最优回路环矩阵。全局最优回路环矩阵是一个属于np-hard类问题。
24.基于上述定义，并参考图3，本发明方法包括如下步骤：s1.公钥和私钥的生成(1)随机生成加权矩阵随机生成加权矩阵,,(2)随机生成公钥矩阵环随机产生n个大小不等的随机数，由这n个整数构成一个回路为：由回路构成的回路矩阵环的元素除n个元素为1外，其余的都为0元素。由这个产生的随机矩阵环h为公钥矩阵环；(3)根据回路环矩阵为构造加权列向量p，列向量p中的元素为加权矩阵和回路环矩阵的hadamard乘积矩阵中的非零项，的hadamard乘积矩阵中的非零项，表示从节点，的加权值或距离；(4)随机生成私钥矩阵环随机产生n个大小不等的随机数，由这n个整数构成一个回路为：由回路构成的回路矩阵环g的元素除n个元素为1外，其余的都为0元素。由这个产生的随机矩阵g为私钥矩阵环；(5)根据回路环矩阵g构造加权列向量q，列向量q中的元素为加权矩阵和回路环矩阵g的hadamard乘积矩阵中的非零项，(6)生成公钥计算下述几个基本参数，首先随机产生私钥k，并通过加权矩阵w和私钥矩阵环g计算，和。其中：
其中：也可以称为回路矩阵环 g的加权和；上式中的指取模运算符；是指除的余数，且满足；所以：上式中表示中的最大整数倍的倍数；所以：所以：所以：s2.发送方加密明文，生成密文随机产生一个数r，将发送的明文m按如下公式秘密：随机产生一个数r，将发送的明文m按如下公式秘密：随机产生一个数r，将发送的明文m按如下公式秘密：s3.接收方解密密文接收方将接收的数据按如下公式解密数据，解密发送方产生的随机数r和m，按如下公式解密明文m：因为：下面以一个加密和解密的实例，说明本发明方法的实施过程：1）随机生成加权矩阵，2）随机生成公钥矩阵环
3)hadamard乘积矩阵3)hadamard乘积矩阵4)将中不为零的n个加权数取出，构成一个环矩阵因此得构成一个环向量，，为5）随机生成私钥矩阵环g6）随机生成私钥 k=49833，并选择环中的一条支路
ꢀꢀ
7）明文加密 12345，首先产生一个随机数r=5；12345，首先产生一个随机数r=5；12345，首先产生一个随机数r=5；8）加密文件的解密；解密明文m：要破解私钥的回路矩阵环，是一个旅行商类问题的np难题，从加权矩阵中选取回路矩阵环的数量是，如果采用对称加权矩阵，则回路矩阵环的数量是，则目前还没有一个多项式算法能够破解，所以本发明方法的安全性有保障。
25.本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。

技术特征：

1.一种基于矩阵路径环的后量子加密解密方法，其特征在于，包括：s1.密钥生成：01.随机生成加权矩阵w；所述加权矩阵为非对称矩阵，其对角线上的元素为0，非对角线上的元素由随机数产生；所述非对称矩阵表示两个节点之间来回的路径不相等；02.随机生成n个随机数，由这n个随机数构成的回路生成第一回路矩阵环h；同理，生成第二回路矩阵环g；03.生成随机数k，输出私钥（k,g）；04.计算，，；表示第二回路矩阵环g的加权和；表示从g中任选的一条支路中节点，的加权值或距离，表示中的最大整数倍的倍数，是指除的余数，；05.输出公钥（g1，g2，g3）；s2.发送方生成随机数r，并利用公钥对消息明文m进行加密，生成密文：s2.发送方生成随机数r，并利用公钥对消息明文m进行加密，生成密文：s2.发送方生成随机数r，并利用公钥对消息明文m进行加密，生成密文：s3.发送密文给接收方；s4.接收方解密密文，得到发送方产生的随机数r和m；。2.根据权利要求1所述的一种基于矩阵路径环的后量子加密解密方法，其特征在于，第一回路矩阵环h的生成方式为：随机生成n个大小不等的随机数，由这n个数构成回路，第一回路矩阵环h中n个元素为1：，其余元素都为0；，。3.根据权利要求1所述的一种基于矩阵路径环的后量子加密解密方法，其特征在于，第二回路矩阵环g的生成方式为：随机产生n个大小不等的随机数，由这n个数构成回路，第二回路矩阵环g中n个元素为1：，其余元素都为0；，。4.一种基于矩阵路径环的后量子加密解密系统，其特征在于，包括：密钥生成中心，用于执行以下处理：01.随机生成加权矩阵w；所述加权矩阵为非对称矩阵，其对角线上的元素为0，非对角线上的元素由随机数产生；所述非对称矩阵表示两个节点之间来回的路径不相等；
02.随机生成n个随机数，由这n个随机数构成的回路生成第一回路矩阵环h；同理，生成第二回路矩阵环g；03.生成随机数k，输出私钥（k,g）；04.计算，，；表示第二回路矩阵环g的加权和；表示从g中任选的一条支路中节点，的加权值或距离，表示中的最大整数倍的倍数，是指除的余数，；05.输出公钥（g1，g2，g3）；发送方，用于生成随机数r，并利用公钥对消息明文m进行加密，生成密文，并将密文发送至接收方：送至接收方：送至接收方：接收方，用于解密密文，得到发送方产生的随机数r和m；。5.根据权利要求4所述的一种基于矩阵路径环的后量子加密解密系统，其特征在于，第一回路矩阵环h的生成方式为：随机生成n个大小不等的随机数，由这n个数构成回路，第一回路矩阵环h中n个元素为1：，其余元素都为0；，。6.根据权利要求4所述的一种基于矩阵路径环的后量子加密解密系统，其特征在于，第二回路矩阵环g的生成方式为：随机产生n个大小不等的随机数，由这n个数构成回路，第二回路矩阵环g中n个元素为1：，其余元素都为0；，。7.一种电子设备，其特征在于，包括：处理器；存储器，其存储有计算机可执行程序，所述程序在被所述处理器执行时，使得所述处理器执行如权利要求1-3中任一项所述的基于矩阵路径环的后量子加密解密方法。8.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述程序被处理器执行时实现如权利要求1-3中任一项所述的基于矩阵路径环的后量子加密解密方法。

技术总结

本发明公开了一种基于矩阵路径环的后量子加密解密方法和系统，属于保密通信技术领域。本发明的安全性基于NP难题的复杂性，采用随机的方法生成两个回路矩阵，一个回路矩阵作为公开密钥，另一个回路矩阵作为秘密密钥，从加权矩阵中任意选择一个回路环矩阵，以及反过来在加权矩阵中到这个回路矩阵都是NP完全问题，所以要破解私钥的回路矩阵环也是NP完全问题，这就保证了私钥无法在多项式计算范围破解私钥的回路矩阵环，保障了加密解密的安全性；本发明在生成公钥、私钥和加密解密过程中，除传送数据，加密和解密过程中用到乘法运算，其它的运算都采用加法完成，计算简单，计算量小。小。小。