一种后量子密钥封装算法的轻量化实现方法与流程

1.本发明涉及网络空间安全技术领域，特别涉及一种后量子密钥封装算法的轻量化实现方法。


背景技术：

2.本发明所基于的技术为amin abdulrahman等人在参考文献1(amin abdulrahman,jiun-peng chen,yu-jia chen,vincent hwang,matthias j.kannwischer,and bo-yin yang.multi-moduli ntts for saber on cortex-m3 and cortex-m4.cryptology eprint archive,report 2021/995,2021.https://ia.cr/2021/995.)、参考文献2(amin abdulrahman,vincent hwang,matthias j.kannwischer,and daan sprenkels.faster kyber and dilithium on the cortex-m4.in giuseppe ateniese and daniele venturi,editors,applied cryptography and network security-20th international conference,acns 2022,rome,italy,june 20-23,2022,proceedings,volume 13269 of lecture notes in computer science,pages 853
–
871.springer,2022.)中所提出的性能优化技术，这两篇论文在内存和计算资源相对而言更加充裕的arm cortex-m4上提出了一种后量子密钥封装算法的高效实现方法，他们的方案以更多内存占用换取更高效的后量子密钥封装算法，有效提高了算法的整体实现效率，然而其内存占用比他们所提出的轻量化实现大接近两倍。因此，这种性能优化技术其它内存、计算资源受限的物联网设备上的可用性亟待进一步研究。具体地，该技术的技术方案包括以下步骤：
3.非对称乘法：amin abdulrahman等人观察到在kyber的矩阵向量乘法as中，我们需要计算该计算中矩阵a的ntt域表示的每一行均需要与多项式向量s的ntt域表示进行向量内积运算。因此，通常我们需要缓存s的ntt域表示参考文献2提出如果数论转换ntt(number theoretic transform)是不完整ntt，就可以利用这个点进行进一步地性能优化；nist后量子密钥封装算法标准kyber正是装备了不完整ntt，其ntt支持7层数论变换，因此在ntt域中的两个元素进行点乘运算时该点乘运算需要128个2
×
2的教科书乘法运算(schoolbook multiplications)。2
×
2的教科书乘法运算形如：其中论文参考文献2指出在计算时，每个私钥会被重复利用k次，因此也会被重复计算k次。他们提出了一种通过额外内存空间缓存的方案，降低k-1次的128个系数的模乘运算。论文参考文献1为点乘算法实现了两个不同的变体，其中一个仅用于矩阵向量乘法中矩阵的第一行与私钥的乘法运算，而另一个用于矩阵剩余的行。第一个变体除了
计算点乘算法，它还单独存储了的结果，并将合并存储在一个多项式的两个相邻16位系数中。第二种变体通过加载多项式的两个相邻缓存值来节省两个蒙哥马利乘法运算和每两个多项式所需的一个旋转因子加载。另外，预计算的向量也可以在加密中矩阵向量乘法之后的向量内积中重新使用，进一步提升kyber的实现效率。
4.更好的累加技术：此外，参考文献1、2还在矩阵向量乘法和向量内积中提出另一种性能优化技术：更好的累加技术。对于矩阵向量乘法中输出向量的一个元素的计算，总共需要k次点乘运算和k-1次累加加法。他们提出不在每次点乘运算之后直接约简每个系数，而是利用延迟约简和一个256次的32位数组，将所有k个点乘运算结果都被累加到32位数组之后才进行系数约简，这种技术还可以用于计算向量内积。对于实现，他们实现了三种缓存和非缓存点乘函数的变体：一种输入16位数组并输出32位数组，一种输入未约简的32位数组并输出一个32位数组，以及输入未约简的32位数组并输出已约简后的16位数组。对于第二种函数，对32位值的操作可直接使用smla{b，t}因此可以省略额外的累加操作。由于kyber素数很小，这些未约简系数的总和永远不会溢出32位有符号整数：对于kyber中使用非对称乘法的矩阵向量乘法中的向量输入是ntt的输出，由于它位于或来自非对称乘法的缓存蒙哥马利乘法结果(-q，q)。使用[8]中的即时方法生成的矩阵系数小于q。因此，乘法之一的最大结果是属于(-q2,q2)之间。对于k∈{2，3，4}的k次累加结果，我们最大得到kq2＝4q2《2
26
，这远低于带符号的32位整数可表示的最大值。


技术实现要素：

[0005]
本发明的目的在于提供一种后量子密钥封装算法的轻量化实现方法，以克服现有技术中的不足。
[0006]
为实现上述目的，本发明提供如下技术方案：
[0007]
本技术公开了一种后量子密钥封装算法的轻量化实现方法，包括如下步骤：
[0008]
s1：获取kyber的系统参数k；
[0009]
s2：依据该系统参数k获取矩阵a，获取私钥向量s；
[0010]
s3：利用ntt数论变换对矩阵a、向量s中的多项式元素进行转换，求取ntt域的私钥元素和ntt域的矩阵元素；
[0011]
s4：通过矩阵向量乘法对ntt域的私钥元素和ntt域的矩阵元素进行点乘运算，获取多项式c的系数并进行存储；
[0012]
s5：通过多项式c进行k次累加，获取乘积向量，并存储。
[0013]
作为优选，所述s4包括如下子步骤：
[0014]
s41：定义一个向量数组，所述向量数组包括k个结构体，所述结构体用于存储半个256次多项式(即128次多项式)。
[0015]
s42：将矩阵a分为第一部分和第二部分，第一部分为矩阵a的第一行，第二部分为矩阵a的剩余行；
[0016]
s43：定义一个可变结构体，用于存储512次16位数组；
[0017]
s43：对矩阵a的第一部分与向量s进行点乘运算，并将私钥的奇数次系数与旋转因子的模乘乘积存储在向量数组中，获取多项式c的系数，将数据存储于可变结构体中；
[0018]
s44：从向量数组中获取私钥的奇数次系数与旋转因子的模乘乘积，对矩阵a的第二部分与向量s进行点乘运算，避免重复计算，将数据存储于可变结构体中。
[0019]
作为优选，所述s43包括如下子步骤：
[0020]
s431：从矩阵a的第一部分中获取矩阵元素的奇数次系数；
[0021]
s432：从私钥中获取私钥的奇数次系数、私钥的偶数次系数，通过私钥的奇数次系数获取私钥的奇数次系数与旋转因子的模乘乘积；
[0022]
s432：将私钥的奇数次系数与旋转因子的模乘乘积存储至向量数组中；
[0023]
s433：通过私钥的奇数次系数与旋转因子的模乘乘积、矩阵元素的奇数次系数、私钥的偶数次系数计算获取矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积；
[0024]
s434：通过128个2
×
2的教科书乘法运算获取多项式c的系数。
[0025]
作为优选，所述s43包括如下子步骤：
[0026]
s435：通过强制类型转换将可变结构体转换为256次的32位数组；
[0027]
s436：通过可变结构体对s434中多项式c的系数进行缓存。
[0028]
作为优选，所述s44包括如下子步骤：
[0029]
s441：从向量数组中获取私钥的奇数次系数与旋转因子的模乘乘积；
[0030]
s442：从矩阵a的第二部分中获取矩阵元素的奇数次系数，从私钥中获取私钥的偶数次系数；
[0031]
s443：通过私钥的奇数次系数与旋转因子的模乘乘积、矩阵元素的奇数次系数、私钥的偶数次系数计算获取矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积；
[0032]
s444：通过128个2
×
2的教科书乘法运算获取多项式c的系数。
[0033]
作为优选，所述s44包括如下子步骤：
[0034]
s445：通过强制类型转换将可变结构体转换为256次的32位数组；
[0035]
s446：通过可变结构体对s444中多项式c的系数进行缓存。
[0036]
作为优选，所述s5包括如下子步骤：
[0037]
s51：对可变结构体内的数据进行累加；
[0038]
s52：对32位的可变结构体内的数据进行约简，使其约简为系数为16位的多项式c，所述多项式c的数据为可变结构体中的前256个16位系数存储；
[0039]
s52：通过多项式c获取乘积向量的元素；
[0040]
s53：输出乘积向量。
[0041]
本发明公开了一种后量子密钥封装算法的轻量化实现装置，包括存储器和一个或多个处理器，所述存储器中存储有可执行代码，所述一个或多个处理器执行所述可执行代码时，用于实现上述的一种后量子密钥封装算法的轻量化实现方法。
[0042]
本发明公开了一种计算机可读存储介质，其上存储有程序，该程序被处理器执行时，实现上述的一种后量子密钥封装算法的轻量化实现方法。
[0043]
本发明的有益效果：
[0044]
(1)、在本发明针对非对称乘法所提出的轻量化方法中，结构体poly_half只占用128个16位有符号整数，相对原来的性能优化技术所用的结构体poly(256个16位有符号整
数)，降低了一半的内存占用量(256字节)。由于kyber中的密钥是一个多项式向量，因此需要使用多项式向量结构体polyvec存储，其由个poly组成(k＝2，3，4)，对于三种不同安全强度的kyber来说，分别降低了0.5kb、0.75kb以及1kb内存占用，该方法可适用于kyber的密钥生成、公钥加密算法和公钥解密算法中，有效降低了密钥封装算法的整体内存占用；
[0045]
(2)、本发明针对更好的累加技术所提出的轻量化方法，由于结构体poly(256个16位有符号整数)占用0.5kb内存，而该轻量化方法省略了额外的一个多项式存储公钥，该算法能为密钥生成算法降低0.5kb的内存占用；
[0046]
(3)、本发明所提出的轻量化方法极大地降低了密钥封装算法的整体内存占用，然而这些内存优化技术并不影响参考文献1、2中提出的性能优化技术所带来的性能提升，这使得我们在内存、计算资源受限的物联网平台中能部署更优的性能优化技术，进一步提升密钥封装算法的运行效率。
[0047]
本发明的特征及优点将通过实施例结合附图进行详细说明。
附图说明
[0048]
图1是本发明一种后量子密钥封装算法的轻量化实现方法的步骤示意图；
[0049]
图2是本发明的流程示意图；
[0050]
图3是本发明的点乘算法的示意图；
[0051]
图4是本发明的装置示意图；
具体实施方式
[0052]
为使本发明的目的、技术方案和优点更加清楚明了，下面通过附图及实施例，对本发明进行进一步详细说明。但是应该理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限制本发明的范围。此外，在以下说明中，省略了对公知结构和技术的描述，以避免不必要地混淆本发明的概念。
[0053]
参阅图1，本发明实施例提供一种后量子密钥封装算法的轻量化实现方法，通过对现有性能优化技术进行深入分析研究，研究后量子密钥封装系统中核心计算过程中的内存占用，通过内存复用和内存优化方案降低现有性能优化技术中核心计算过程的内存占用。包括在点乘运算中，利用32位物联网平台特点以及现有性能优化特点，提出比现有技术降低一半内存占用的方法；在矩阵向量乘法和向量内积的计算过程中，分析计算过程中的大内存占用系数，通过内存复用进一步降低密钥封装的内存占用，而且以上内存优化不会影响整体性能，因此，本发明所提出的一种后量子密钥封装算法的轻量化实现方法，使后量子密钥封装算法在性能和内存方面更适用于物联网场景中的内存、计算资源受限的物联网设备中。
[0054]
一种后量子密钥封装算法的轻量化实现方法，主要用于降低kyber密钥封装算法中的核心运算矩阵向量乘法的占用内存，包括如下步骤：
[0055]
s1：获取kyber的系统参数k；
[0056]
s2：依据该系统参数k获取矩阵a，获取私钥向量s；
[0057]
s3：利用ntt数论变换对矩阵a、向量s中的多项式元素进行转换，求取ntt域的私钥元素和ntt域的矩阵元素；
[0058]
s4：通过矩阵向量乘法对ntt域的私钥元素和ntt域的矩阵元素进行点乘运算，获取多项式c的系数并进行存储；
[0059]
s5：通过多项式c进行k次累加，获取乘积向量，并存储。
[0060]
所述s2包括如下内容：在一种可行的实施例中，k＝3；
[0061]
以kyber密钥封装算法的矩阵向量乘法c＝as为例，其实现流程如图2所示。其中大写加粗字母a代表矩阵a，为k阶矩阵；小写加粗字母s和c代表向量s和乘积向量c，为k阶向量；k是kyber中的系统参数(在kyber的三种安全等级的方案中，k分别等于2，3和4)；矩阵、向量中的每个元素均为256次的多项式；本实施例中以k＝3为例阐述该运算的具体运行步骤。该矩阵向量乘法运算可分为k次k阶向量乘法运算c＝as，每次向量乘法运算需要依次将向量a(向量a可由矩阵a中取得)和向量s的对应多项式元素a
l
和s
l
相乘并累加得到一个多项式c，这个多项式c最后将构成向量c的第k个元素。为方便表述，以下令小写未加粗字母a和s分别表示向量a和s的对应多项式元素a
l
和s
l
。
[0062]
对于n阶(kyber的n＝256)多项式a和s的乘法运算，kyber的参数选择使其可以使用数论变换ntt来降低多项式乘法运算的时间复杂度。利用ntt，在执行矩阵向量乘法之前，kyber先将矩阵a、向量s中的每个多项式元素a和s转换为ntt域的矩阵元素和ntt域的私钥元素
[0063]
所述s4包括如下子步骤：
[0064]
s41：定义一个向量数组，所述向量数组包括k个结构体，所述结构体用于存储半个256次多项式(即128次多项式)。
[0065]
s42：将矩阵a分为第一部分和第二部分，第一部分为矩阵a的第一行，第二部分为矩阵a的剩余行；
[0066]
s43：定义一个可变结构体，用于存储512次16位数组；
[0067]
s43：对矩阵a的第一部分与向量s进行点乘运算，并将私钥的奇数次系数与旋转因子的模乘乘积存储在向量数组中，获取多项式c的系数，将数据存储于可变结构体中；
[0068]
s44：从向量数组中获取私钥的奇数次系数与旋转因子的模乘乘积，对矩阵a的第二部分与向量s进行点乘运算，避免重复计算，将数据存储于可变结构体中。
[0069]
经过ntt转换之后的多项式乘法的乘积即为点乘运算，该运算包含128个2
×
2的教科书乘法运算，该运算的具体计算公式如图3所示。每个2
×
2的教科书乘法运算形如：2的教科书乘法运算形如：通过约简可得通过约简可得由此可见，多项式c的每个系数的计算仅需要2或3次模乘运算以及1次加法运算，其中由于私钥向量s在矩阵向量乘法中需要被反复使用k次，因此中的1次模乘运算私钥的奇数次系数与旋转因子的模乘乘积也需要被重复计算k次。
[0070]
下文中s4中的非对称算法即可用于此处以减少重复计算私钥与旋转因子的模乘运算，从而提高点乘运算的计算效率。此外，在计算c的每个系数时，还需要1次加法运算，并且每个点乘运算的乘积多项式还需要和k-1个点乘运算的乘积多项式进行累加(见图2最右侧的
累加运算c＝a
·
s＝a0s0+a1s1+a2s2)，由于kyber中的多项式的每个系数均存储在16位有符号整数中，传统的解决方案通常将各项乘积分别求模乘结果后、累加后再对累加结果求1次模约简运算，此时多项式c的每个系数都是约简结果(例如当使用蒙哥马利算法求模约简时，约简结果的范围在(-q,q)中，kyber中的模数q＝3329)。在图2最右侧的累加运算后，其结果可以被存储于16位有符号整数中。
[0071]
后文中s5中更好的累加技术即可用于此处减少对各项乘积的模约简操作，然后用32位有符号数组存储累加后的多项式c。
[0072]
针对参考文献1、2中提出的非对称乘法，本发明在不具有simd指令集的低端32位物联网平台上提出了新的缓存技术，该缓存技术仅需半个256次多项式(即128次多项式)的存储空间来存储私钥的奇数次系数与旋转因子的模乘乘积减少了一半用于存储的方案的空间。由于nist后量子密钥封装算法kyber系统中没有定义半个多项式的结构体，我们定义了用于存储128次多项式的结构体poly_half以及polyvec_half，并利用此结构体重新为点乘算法实现了两个不同的变体：
[0073]
其中：poly_half是一个包含128个16位数据的数组；polyvec_half包含了k个poly_half；是一个基于poly_half的k维向量。
[0074]
所述s43包括如下子步骤：
[0075]
s431：从矩阵a的第一部分中获取矩阵元素的奇数次系数；
[0076]
s432：从私钥中获取私钥的奇数次系数、私钥的偶数次系数，通过私钥的奇数次系数获取私钥的奇数次系数与旋转因子的模乘乘积；
[0077]
s432：将私钥的奇数次系数与旋转因子的模乘乘积存储至向量数组中；
[0078]
s433：通过私钥的奇数次系数与旋转因子的模乘乘积、矩阵元素的奇数次系数、私钥的偶数次系数计算获取矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积；
[0079]
s434：通过128个2
×
2的教科书乘法运算获取多项式c的系数。
[0080]
s43中，在处理矩阵向量乘法as中矩阵的第一行与私钥的点乘运算时，该运算需要计算128个2
×
2的教科书乘法运算。
[0081]
每个2
×
2的教科书乘法运算形如：2的教科书乘法运算形如：其中其中在计算矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积的过程中，我们先计算私钥的奇数次系数与旋转因子的模乘乘积并将其单独存储在polyvec_half类型的内存s
′
中，而现有技术还需要同时缓存而该项可直接从私钥处读取，因此本发明省略了额外存储该项的代价，只需要额外存储私钥的奇数次系数与旋转因子的模乘乘积的内存，这对于k阶的私钥向量能节省大量内存。
[0082]
所述s43包括如下子步骤：
[0083]
s435：通过强制类型转换将可变结构体转换为256次的32位数组；
[0084]
s436：通过可变结构体对s434中多项式c的系数进行缓存。
[0085]
所述s44包括如下子步骤：
[0086]
s441：从向量数组中获取私钥的奇数次系数与旋转因子的模乘乘积；
[0087]
s442：从矩阵a的第二部分中获取矩阵元素的奇数次系数，从私钥中获取私钥的偶数次系数；
[0088]
s443：通过私钥的奇数次系数与旋转因子的模乘乘积、矩阵元素的奇数次系数、私钥的偶数次系数计算获取矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积；
[0089]
s444：通过128个2
×
2的教科书乘法运算获取多项式c的系数。
[0090]
s44中，在处理矩阵向量乘法中矩阵的剩余行与私钥的点乘运算时，该运算同样需要计算128个2
×
2的教科书乘法运算。然而，与上一个变体不同的是，在计算矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积的过程中，我们可以直接从s43中计算并存储在polyvec_half类型的内存s’中读取私钥的奇数次系数与旋转因子的模乘乘积进而与相乘得到从而避免重复计算在一定程度上提升点乘运算的计算效率。而涉及的计算，这些系数可直接从矩阵a和私钥中读取。
[0091]
所述s44包括如下子步骤：
[0092]
s445：通过强制类型转换将可变结构体转换为256次的32位数组；
[0093]
s446：通过可变结构体对s444中多项式c的系数进行缓存。
[0094]
所述s5包括如下子步骤：
[0095]
s51：对可变结构体内的数据进行累加；
[0096]
s52：对32位的可变结构体内的数据进行约简，使其约简为系数为16位的多项式c，所述多项式c的数据为可变结构体中的前256个16位系数存储；
[0097]
s52：通过多项式c获取乘积向量的元素；
[0098]
s53：输出乘积向量。
[0099]
在利用32位有符号数组累加向量乘积的k项多项式乘法乘积的和之后(c＝a
·
s＝a0s0+a1s1+a2s2)，需要在最后一次累加运算之后将存储于32位有符号数组的未约简乘积的每个系数进行约简，约简后的乘积c将作为矩阵向量乘法的乘积向量c的一个元素，并参与kyber算法的后续运算。
[0100]
针对参考文献1、2中提出的更好的累加技术，通过细致的内存分析，本发明在密钥对生成算法中发现用于存储公钥的多项式pkp与保存累加中间结果的256次32位数组可以复用部分内存，即公钥多项式可以复用256次32位数组的部分内存进行运算。因此本发明定义一个用于存储512次16位多项式的poly_double结构体(1kb)，该结构体既可以通过类型转换将其转换为用于存储256次16位多项式的poly(0.5kb)，也可以转换为用于存储256次32位数组的中间结果1kb)。该技术通过复用poly_double结构体的内存，可以省略一个额外多项式存储公钥，进一步降低了kyber的内存占用。
[0101]
具体地，在kyber的公钥密钥生成协议中，我们需要计算一个矩阵向量乘法as并将其结果存储在一个多项式pkp中。为此，现有技术定义了一个多项式pkp以及一个256次32位数组缓存矩阵向量乘法运算中的中间结果。本发明则只需要申请一个类型为poly_double的内存空间(相当于减少了一个多项式的内存空间)，在计算矩阵向量乘法as过程中，我们先通过强制类型转换将poly_double类型的数组转换成256次的32位数组，利用该内存缓存矩阵向量乘法运算中的中间结果。在矩阵向量乘法最后一步，把中间结果约简为系数为16位的多项式pkp，该多项式可直接利用poly_double类型中的前256个16位系数存储。
[0102]
本发明一种后量子密钥封装算法的轻量化实现装置的实施例可以应用在任意具备数据处理能力的设备上，该任意具备数据处理能力的设备可以为诸如计算机等设备或装置。装置实施例可以通过软件实现，也可以通过硬件或者软硬件结合的方式实现。以软件实现为例，作为一个逻辑意义上的装置，是通过其所在任意具备数据处理能力的设备的处理器将非易失性存储器中对应的计算机程序指令读取到内存中运行形成的。从硬件层面而言，如图4所示，为本发明一种后量子密钥封装算法的轻量化实现装置所在任意具备数据处理能力的设备的一种硬件结构图，除了图4所示的处理器、内存、网络接口、以及非易失性存储器之外，实施例中装置所在的任意具备数据处理能力的设备通常根据该任意具备数据处理能力的设备的实际功能，还可以包括其他硬件，对此不再赘述。上述装置中各个单元的功能和作用的实现过程具体详见上述方法中对应步骤的实现过程，在此不再赘述。
[0103]
对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本发明方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。
[0104]
本发明实施例还提供一种计算机可读存储介质，其上存储有程序，该程序被处理器执行时，实现上述实施例中的一种后量子密钥封装算法的轻量化实现装置。
[0105]
所述计算机可读存储介质可以是前述任一实施例所述的任意具备数据处理能力的设备的内部存储单元，例如硬盘或内存。所述计算机可读存储介质也可以是任意具备数据处理能力的设备的外部存储设备，例如所述设备上配备的插接式硬盘、智能存储卡(smart media card，smc)、sd卡、闪存卡(flash card)等。进一步的，所述计算机可读存储介质还可以既包括任意具备数据处理能力的设备的内部存储单元也包括外部存储设备。所述计算机可读存储介质用于存储所述计算机程序以及所述任意具备数据处理能力的设备所需的其他程序和数据，还可以用于暂时地存储已经输出或者将要输出的数据。
[0106]
以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换或改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种后量子密钥封装算法的轻量化实现方法，其特征在于：包括如下步骤：s1：获取kyber的系统参数k；s2：依据该系统参数k获取矩阵a，获取私钥向量s；s3：利用ntt数论变换对矩阵a、向量s中的多项式元素进行数论转换，获取ntt域的私钥元素和ntt域的矩阵元素；s4：通过矩阵向量乘法对ntt域的私钥元素和ntt域的矩阵元素进行点乘运算，求取多项式c的系数并进行存储；s5：通过多项式c进行k次累加，获取乘积向量，并存储。2.如权利要求1所述的一种后量子密钥封装算法的轻量化实现方法，其特征在于：所述s4包括如下子步骤：s41：定义一个向量数组，所述向量数组包括k个结构体，所述结构体用于存储半个256次多项式(即128次多项式)。s42：将矩阵a分为第一部分和第二部分，第一部分为矩阵a的第一行，第二部分为矩阵a的剩余行；s43：定义一个可变结构体，用于存储512次16位数组；s43：对矩阵a的第一部分与向量s进行点乘运算，并将私钥的奇数次系数与旋转因子的模乘乘积存储在向量数组中，获取多项式c的系数，将数据存储于可变结构体中；s44：从向量数组中获取私钥的奇数次系数与旋转因子的模乘乘积，对矩阵a的第二部分与向量s进行点乘运算，避免重复计算，将数据存储于可变结构体中。3.如权利要求2所述的一种后量子密钥封装算法的轻量化实现方法，其特征在于：所述s43包括如下子步骤：s431：从矩阵a的第一部分中获取矩阵元素的奇数次系数；s432：从私钥中获取私钥的奇数次系数、私钥的偶数次系数，通过私钥的奇数次系数获取私钥的奇数次系数与旋转因子的模乘乘积；s432：将私钥的奇数次系数与旋转因子的模乘乘积存储至向量数组中；s433：通过私钥的奇数次系数与旋转因子的模乘乘积、矩阵元素的奇数次系数、私钥的偶数次系数计算获取矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积；s434：通过128个2
×
2的教科书乘法运算获取多项式c的系数。4.如权利要求3所述的一种后量子密钥封装算法的轻量化实现方法，其特征在于：所述s43包括如下子步骤：s435：通过强制类型转换将可变结构体转换为256次的32位数组；s436：通过可变结构体对s434中多项式c的系数进行缓存。5.如权利要求2所述的一种后量子密钥封装算法的轻量化实现方法，其特征在于：所述s44包括如下子步骤：s441：从向量数组中获取私钥的奇数次系数与旋转因子的模乘乘积；s442：从矩阵a的第二部分中获取矩阵元素的奇数次系数，从私钥中获取私钥的偶数次系数；s443：通过私钥的奇数次系数与旋转因子的模乘乘积、矩阵元素的奇数次系数、私钥的偶数次系数计算获取矩阵元素、私钥的奇数次系数与旋转因子的模乘乘积；
s444：通过128个2
×
2的教科书乘法运算获取多项式c的系数。6.如权利要求5所述的一种后量子密钥封装算法的轻量化实现方法，其特征在于：所述s44包括如下子步骤：s445：通过强制类型转换将可变结构体转换为256次的32位数组；s446：通过可变结构体对s444中多项式c的系数进行缓存。7.如权利要求1所述的一种后量子密钥封装算法的轻量化实现方法，其特征在于：所述s5包括如下子步骤：s51：对可变结构体内的数据进行累加；s52：对32位的可变结构体内的数据进行约简，使其约简为系数为16位的多项式c，所述多项式c的数据为可变结构体中的前256个16位系数存储；s52：通过多项式c获取乘积向量的元素；s53：输出乘积向量。8.一种后量子密钥封装算法的轻量化实现装置，其特征在于：包括存储器和一个或多个处理器，所述存储器中存储有可执行代码，所述一个或多个处理器执行所述可执行代码时，用于实现权利要求1-7任一项所述的一种后量子密钥封装算法的轻量化实现方法。9.一种计算机可读存储介质，其特征在于：其上存储有程序，该程序被处理器执行时,实现权利要求1-7任一项所述的一种后量子密钥封装算法的轻量化实现方法。

技术总结
本发明公开了一种后量子密钥封装算法的轻量化实现方法，包括如下步骤：S1：获取Kyber的系统参数k；S2：依据该系统参数k获取矩阵A，通过私钥获取向量s；S3：利用NTT数论变换对矩阵A、向量s中的多项式元素进行转换，获取NTT域的私钥元素和NTT域的矩阵元素；S4：通过矩阵向量乘法对NTT域的私钥元素和NTT域的矩阵元素进行点乘运算，获取多项式c的系数并进行存储；S5：通过多项式c进行k次累加，获取乘积向量，并存储。存储。存储。


技术研发人员：张峰 黄军浩 陈东龙 戴望辰 石建 韩朝阳
受保护的技术使用者：杭州后量子密码科技有限公司
技术研发日：2023.06.05
技术公布日：2023/9/12