一种基于NTRU的密钥生成、封装和解封装方法

摘要: 本发明涉及信息安全,尤其涉及一种基于ntru的密钥生成、封装和解封装方法。背景技术:1、密钥封装机制(kem)及公钥加密广泛应用于确保信息传输的隐秘性和建立安全...
一种基于NTRU的密钥生成、封装和解封装方法

本发明涉及信息安全,尤其涉及一种基于ntru的密钥生成、封装和解封装方法。

背景技术:

1、密钥封装机制(kem)及公钥加密广泛应用于确保信息传输的隐秘性和建立安全通信信道。在互联网通信、虚拟专用网络、即时通讯等场景中,kem能够安全地在通信双方之间共享对称密钥并保证数据免受窃听。随着量子计算的进步,传统公钥加密与密钥交换方案(如rsa和diffie-hellman)面临安全威胁,因此抗量子安全的kem方案,如基于格的kem方案被提出,用于防止量子计算对现代密码系统的破解。

2、霍夫斯坦(hoffstein)、派弗(pipher)和西尔弗曼(silverman)在1996年首次提出了基于多项式环的ntru公钥加密方案框架。随后在2003年,豪格雷夫-格雷厄姆(howgrave-graham)等人利用填充模式提出了naep机制,有效增强了ntru抵抗适应性选择密文攻击(cca)的安全性。斯泰莱(stehlé)和斯坦菲尔德(steinfeld)在2011年提出改进的ss-ntru变体,首次从理论上证明了其安全性可归约至理想格上的困难问题。近年来,为了降低解密失败的概率同时提升性能,研究者们陆续设计了ntru-hrss、ntru prime等方案。2023年入选后量子密码竞赛首轮、2025年进入最终算法名单并现为标准候选技术的ntru+,通过改进多项式环代数结构与封装机制,在确保高安全性的前提下显著降低了通信开销。2025年,刘易简等人则提出了一种基于双重编码(double encoding)技术的ntru方案dawn,实现了更紧凑、更快速的kem机制。综合来看,基于ntru的密钥封装机制在安全性与效率之间的平衡仍存在优化空间,值得继续探索。

3、在现有的基于ntru的密钥封装机制中,以ntru+为例,所涉及的第一多项式环为,第二多项式环为,设置的私钥的形式为,解密过程中,先在第一多项式环中计算出多项式,将计算出来的值转换到第二多项式环中即可恢复消息,多项式环的转换不会导致解密失败的前提是系数的无穷范数不会超过,在这类方案中,为降低解密失败概率,通常采取的手段为增大模数参数的取值,然而此举会导致公钥、私钥及密文尺寸急剧膨胀,不利于资源受限场景下的部署。

4、因此,如何保证解密失败率的条件下降低公钥、私钥及密文的尺寸是目前亟待解决的技术问题。

技术实现思路

1、鉴于上述问题,本发明提供了一种克服上述问题或者至少部分地解决上述问题的基于ntru的密钥生成、封装及解封装的方法。

2、第一方面,本发明提供了一种基于ntru的密钥生成方法,包括:

3、提供第一多项式环、第二多项式环、第一多项式以及第二多项式,其中,所述第二多项式环为,表示模整数环,为模数,表示以中的元素为系数、以为不定元的多项式环,表示多项式的不定元,表示由多项式生成的理想,符号/表示对理想取商,

表示以为模多项式构造得到的商多项式环,第一多项式和第二多项式均在第一多项式环中可逆,第一多项式在第二多项式环中可逆,第一多项式和第二多项式均为三元系数多项式,第一多项式的系数服从取值为1、-1的概率均为,取值为0的概率为,第二多项式的系数服从取值为1、-1的概率均为,取值为0的概率为,其中,均为整数;

4、计算第一多项式在第一多项式环中的第一逆多项式;

5、基于第二多项式、第一逆多项式以及第一多项式环,按照如下公式,得到乘积多项式:

6、

7、其中,为乘积多项式,为第一逆多项式,为第二多项式,表示对多项式进行模约化处理,所述模约化处理包括:将多项式的运算结果的各项系数按照模进行约化,得到第一约化多项式,并将第一约化多项式按照模多项式进行约化,得到第二约化多项式,所述第二约化多项式为各项系数属于且次数小于的第一余式多项式,所述第一余式多项式即为乘积多项式,表示模整数环,为模数;

8、计算第一多项式在第二多项式环中的第二逆多项式;

9、将所述乘积多项式作为公钥,将所述第一多项式和所述第二逆多项式作为私钥,并公布所述公钥。

10、优选的,在提供第一多项式环、第二多项式环、第一多项式以及第二多项式之后,还包括:

11、确定的值;

12、基于的值,确定的值,其中,为3,和互素,的取值使得第一多项式环能够执行ntt变换,以加速第一多项式环中元素间的乘法运算,所述第一多项式环为,其中,表示模整数环,为模数,表示以中的元素为系数、以为不定元的多项式环,表示多项式的不定元,表示由多项式生成的理想,符号/表示对理想取商,因此,表示以为模多项式构造得到的商多项式环。

13、优选的,在取值为1152时,的值为577。

14、第二方面,本发明还提供了一种基于ntru的密钥封装方法,包括:

15、随机生成第一消息;

16、接收第一方面所述的密钥生成方法中的公钥;

17、基于所述第一消息与所述公钥,得到第一共享密钥和第一字节串种子;

18、基于第一字节串种子,得到扰动多项式;

19、基于扰动多项式和第一消息,引入噪声多项式;

20、基于噪声多项式、扰动多项式以及所述公钥,生成密文,实现密钥封装。

21、优选的,基于所述第一消息与所述公钥,得到第一共享密钥和第一字节串种子,包括:

22、将第一消息与公钥拼接,得到第一拼接结果;

23、基于第一拼接结果,调用哈希函数,输出得到第一共享密钥和第一字节串种子。

24、优选的,基于扰动多项式和第一消息,引入噪声多项式,包括:

25、基于扰动多项式,调用哈希函数,得到第一输出结果;

26、基于第一输出结果和第一消息,调用编码函数,生成第一中间多项式;

27、基于第一中间多项式,生成第二中间多项式;

28、基于第二中间多项式,调用哈希函数,输出中间字节串种子;

29、基于中间字节串种子,引入噪声多项式。

30、优选的,基于噪声多项式、扰动多项式以及所述公钥,生成密文,实现密钥封装,具体按照如下公式实现:

31、

32、其中,为所述乘积多项式,且被作为公钥,为扰动多项式,为噪声多项式,为第二中间多项式,表示对多项式进行模约化处理,所述模约化处理包括:将多项式的运算结果的各项系数按照模进行约化,得到第三约化多项式,并将第三约化多项式按照模多项式进行约化,得到第四约化多项式,所述第四约化多项式为各项系数属于且次数小于的第二余式多项式,所述第二余式多项式即为所述密文,表示模整数环,为模数。

33、第三方面,本发明还提供了一种基于ntru的密钥解封装方法,包括:

34、基于第二方面所述的密钥封装方法中生成的密文、如第一方面所述的密钥生成方法中的私钥,计算第三多项式:

35、

36、其中,为第三多项式,为所述密文,为第一多项式,且被作为其中一个私钥,表示对多项式进行模约化处理,所述模约化处理包括:将多项式的运算结果的各项系数按照模进行约化,得到第五约化多项式,并将第五约化多项式按照模多项式进行约化,得到第六约化多项式,第六约化多项式为各项系数属于且次数小于的第三余式多项式,所述第三余式多项式即为第三多项式,表示模整数环,

为模数;

37、对所述第三多项式消除噪声项,具体按照如下计算式计算,得到第四多项式:

38、

39、其中,为第四多项式,为第三多项式,表示对多项式进行模约化处理,所述模约化处理包括:将多项式的各项系数按照模进行约化,得到第七约化多项式,并将第七约化多项式按照模多项式进行约化,得到第八约化多项式,所述第八约化多项式为各项系数属于且次数小于的第四余式多项式,所述第四余式多项式即为第四多项式,表示模整数环,为模数;

40、基于第四多项式,按照如下计算式,得到第五多项式:

41、

42、其中,为第五多项式,为第四多项式,为第二逆多项式,且被作为另一个私钥,对多项式的运算结果进行模约化处理,所述模约化处理包括:将多项式的运算结果的各项系数按照模进行约化,得到第九约化多项式,并将第九约化多项式按照模多项式进行约化,得到第十约化多项式,所述第十约化多项式的各项系数属于且次数小于的第五余式多项式,所述第五余式多项式即为第五多项式;

43、基于第五多项式,按照如下计算式,得到候选消息多项式:

44、

45、其中,为候选消息多项式,为第五多项式,为多项式在第一多项式环中的第三逆多项式,表示对多项式的运算结果进行模约化处理,所述模约化处理包括:将多项式的运算结果的各项系数按照模进行约化,得到第十一约化多项式,并将第十一约化多项式按照模多项式进行约化,得到第十二约化多项式,所述第十二约化多项式为各系数属于且次数小于的第六余式多项式,所述第六余式多项式即为所述候选消息多项式;

46、对所述候选消息多项式进行验证计算,输出第二消息;

47、基于第二消息,输出第二共享密钥和第二字节串种子。

48、优选的,对所述候选消息多项式进行验证计算,输出第二消息,包括:

49、基于所述候选消息多项式,调用哈希函数,输出得到第三字节串种子;

50、基于第三字节串种子,得到第六多项式;

51、基于第六多项式,计算第七多项式;

52、基于第七多项式,调用哈希函数,得到第二输出结果;

53、基于第二输出结果和第五多项式,调用编码函数,输出得到第二消息。

54、优选的,在基于第二消息,输出第二共享密钥和第二字节串种子之后,还包括:

55、基于第二字节串种子,生成第八多项式;

56、判断第八多项式与第七多项式是否相同;

57、若是,输出第二共享密钥,第二共享密钥与第一共享密钥相同;

58、若否,输出终止符。

59、本发明实施例中的一个或多个技术方案,至少具有如下技术效果或优点:

60、本发明提供了一种基于ntru的密钥生成方法,包括:通过提供第一多项式环、第二多项式环、第一多项式和第二多项式,其中该第二多项式环为,第一多项式和第二多项式均在第一多项式环中可逆,第一多项式在第二多项式环中可逆,第一多项式和第二多项式均为三元系数多项式,第一多项式的系数服从取值为1、-1的概率均为,取值为0的概率为,第二多项式的系数服从取值为1、-1的概率均为,取值为0的概率为,其中,均为整数;计算第一多项式在第一多项式环中的第一逆多项式;基于第二多项式、第一逆多项式以及第一多项式环,按照如下公式,得到乘积多项式:,其中,为乘积多项式,为第一逆多项式,为第二多项式,表示对多项式进行模约化处理;计算第一多项式在第二多项式环中的第二逆多项式;将乘积多项式作为公钥,将第一多项式和第二逆多项式作为私钥,通过设置这样的第二多项式环,设置更小的参数,保证解密失败概率依旧低于2-128的同时,产生更短的公钥、私钥以及密文,以适应更低的网络传输流量、更短的通信等待时间以及更小的存储空间占用,进而可在资源受限场景下部署。