一种基于GPU的后量子密码Kyber并行加速方法与流程

一种基于gpu的后量子密码kyber并行加速方法
技术领域
1.本发明涉及后量子密码技术领域，具体为一种基于gpu的后量子密码kyber并行加速方法。


背景技术：

2.后量子密码算法（post-quantum cryptography，pqc）的研究起源于shor算法的提出，该算法可以在量子计算机上高效地解决大部分的数论问题，包括rsa、椭圆曲线密码等公钥密码算法的底层基础问题；因此，研究如何在量子计算机面前保持密码学安全性成为了一个紧迫的问题；后量子密码算法研究的主要目标是设计一种能够在未来量子计算机的攻击下仍然能够保持安全性的密码算法；这些算法通常基于一些更为困难的数学问题，例如基于格的密码算法、基于哈希函数的密码算法、基于编码的密码算法等，并且通常使用一些比较复杂度较高的数学结构，例如格、多项式环等。
3.目前，当有海量数据请求时，大部分会选择增加设备的部署量来满足需求，还要配套负载均衡设备，导致成本的不断增加。因此无论是从安全层面还是经济层面，后量子密码的优化都是亟待解决的重点，为此我们提出一种基于gpu的后量子密码kyber并行加速方法用于解决上述问题。


技术实现要素：

4.本发明的目的在于提供一种基于gpu的后量子密码kyber并行加速方法，以解决上述背景技术中提出的问题。
5.为实现上述目的，本发明提供如下技术方案：一种基于gpu的后量子密码kyber并行加速方法，包括如下步骤，步骤1：在gpu设备上分配若干的内存空间，将cpu主机需要传输的数据通过cpu主机传输到gpu设备上；步骤2：在数据传输过程中，将数据存储到gpu设备中的全局内存中，将全局内存中存储的数据复制到共享内存中，步骤3：将传输的数据通过ntt快速数论变换算法分成若干独立计算任务，将计算任务分配给不同的线程；步骤4：利用gpu设备计算架构中的线程块和线程格，确保多个线程访问共享内存的同步性；步骤5：将每个线程计算完成的数据存储到共享内存中，同时将共享内存中的计算完成的数据复制到全局内存中，便于数据从gpu设备传输到cpu主机；优选的，步骤1中传输的数据为n维的多项式，对cpu设备内存和gpu设备的全局内存及常量内存进行初始化。
6.优选的，设置cpu设备和gpu设备对应的接口api函数，设置传输数据大小，数据类型，传输方向。
7.优选的，ntt快速数论变换算法所需的n/2个旋转因子存储到gpu设备的常量内存中。
8.优选的，通过ntt快速数论变换算法将多项式拆分为n/2对技术任务，将每对技术任务分配给gpu设备上的不同gpu线程。
9.优选的，gpu设备中的每个gpu线程进行计算的时候，从共享内存提取数据。
10.优选的，ntt快速数论变换算法设有若干ntt映射层，当第一层ntt映射并行完成后，顺序运行剩余映射，每一层需改变线程运算的距离、线程的起始位置以及旋转因子的大小，并且在每一层映射完成后都需要同步线程，直至全部ntt映射完成。
11.优选的，步骤2中共有三个同时进行的线程；线程1：cpu设备与gpu设备数据传输线程；线程2：将传输的数据存储到gpu设备中的全局内存中；线程3：将全局内存存储是数据复制到共享内存中。
12.与现有技术相比，本发明的有益效果是：第一、提高算法的执行速度：通过gpu并行化ntt运算，可以利用多个线程同时执行单个ntt运算，从而大幅降低ntt以及kyber的计算时延，提高算法的执行速度。
13.第二、降低算法的内存占用量：采用优化的存储和访存方案可以降低kyber算法中空间占用量，并且可以有效提升ntt的计算效率，降低算法的内存占用量。
14.第三、适用于嵌入式平台：kyber加速后可以在嵌入式平台上运行，通过减少计算时延和内存占用量，可以在资源受限的嵌入式芯片上实现kyber算法，从而扩展了kyber算法的应用范围。
附图说明
15.图1为本发明的原理示意图；图2为本发明多线程组合操作ntt模块的算法流程示意图；图3为本发明ntt模块在全并行模式下的线程运行流程示意图；图4为格密码算法kyber中最耗时的多项式乘法运算示意图；图5为本发明一种基于gpu的后量子密码kyber并行加速设备的一种硬件结构图。
具体实施方式
16.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
17.参考图1，将后量子密码优化方法与gpu单指令多线程并行技术相融合，构建两者软硬协同优化的系统方法，将后量子密码的高性能、高安全的迫切需求作为出发点，用gpu并行加速平台作为实验工具，针对gpu平台高性能密码的并行机理，从线程并行、访存优化、指令优选等角度完善基于后量子密码的gpu并行机制。
18.参考图4，利用多个线程同时执行单个ntt运算，可以大幅降低ntt以及格密码算法的计算时延；同时由于在计算ntt的过程中需要预计算大量的旋转因子，本发明将旋转因子
存储在高效的常量内存中；由于 ntt 的运算过程中涉及大量的内存访问操作，内存访问操作在嵌入式平台中占用较高的时钟周期，ntt 的运算过程中涉及大量的内存访问操作，内存访问操作在嵌入式平台中占用较高的时钟周期，本发明将数据存储至共享内存中，而共享内存具有较高的带宽，这意味着可以减少内存带宽的消耗。
19.参考图2和图3，kyber的ntt计算过程可以被分解为多个计算任务，这些计算任务可以被gpu并行处理，通过优化并行计算，可以将多个计算任务同时分配给gpu进行处理，从而提高吞吐率。
20.图3中展示的是8维的多项式，3层ntt映射，将8维的多项式拆分为4对计算任务，每一个线程处理一对计算任务，每一对技术任务的数据采用数组类型存储，并随着层数的加深，改变线程运算中内存地址之间的距离，在内存访问方面，通过将计算任务数组存储至共享内存中，将旋转因子存储至常量内存，从而减少对全局内存的访问。
21.具体的，输入一个256维的多项式，kyber具有7层ntt映射，具体的优化步骤如下：步骤1：在gpu设备上分配足够的内存空间，以存储需要传输的数据，设置传输数据的大小为256、数据类型为short、传输方向为主机传向设备，将ntt所需要的128个旋转因子存储至常量内存；步骤2：cpu主机数据传输至gpu设备，并将传输的数据存储至gpu中的全局内存中，使用另一个线程将全局内存的数据复制到共享内存中，通过使用gpu设备的编程语言和cpu主机库提供的数据类型和类型转换函数来确保数据类型的匹配。
22.步骤3：256维的多项式通过ntt运算分解为128对计算任务，并将128对计算任务单元分给不同的gpu线程；步骤4：结合 cuda 的线程块和线程格的机制，确保含有计算任务的多线程在访问相同内存区域时的同步，当第一层ntt映射并行完成后，顺序运行剩余6层映射，每一层需改变计算任务的距离、线程的起始位置以及旋转因子的大小，并且在每一层映射完成后都需要同步线程，直至7层ntt映射全部完成；步骤5：将每个线程计算完成的数据存储到共享内存中，同时将共享内存中的计算完成的数据复制到全局内存中，便于数据从gpu设备传输到cpu主机；256维的多项式以向量的形式存储在gpu设备的全局内存和共享内存中，通过将数据缓存在共享内存中，可以在多个线程之间共享数据，并且不需要每次都从全局内存中读取或写入，而共享内存具有较高的带宽，这意味着可以减少内存带宽的消耗，共享内存只能被同一块多处理器上的线程访问，因此不同的块之间不会发生竞争。
23.每个计算任务线程执行如下公式：执行如下公式：执行如下公式：其中，表示下标为的系数，表示下标为的系数，表示技术任务的线程，表示线程运算中内存地址之间的距离。
24.如图5所示，为本发明一种基于gpu的后量子密码kyber并行加速设备的一种硬件结构图，除了图5所示的处理器、内存、网络接口、以及非易失性存储器之外，实施例中装置所在的任意具备数据处理能力的设备通常根据该任意具备数据处理能力的设备的实际功能，还可以包括其他硬件，对此不再赘述。上述装置中各个单元的功能和作用的实现过程具体详见上述方法中对应步骤的实现过程，在此不再赘述。
25.对于装置实施例而言，由于其基本对应于方法实施例，所以相关之处参见方法实施例的部分说明即可。以上所描述的装置实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本发明方案的目的。本领域普通技术人员在不付出创造性劳动的情况下，即可以理解并实施。
26.本发明实施例还提供一种计算机可读存储介质，其上存储有程序，该程序被处理器执行时，实现上述实施例中的一种基于gpu的后量子密码kyber并行加速设备。
27.所述计算机可读存储介质可以是前述任一实施例所述的任意具备数据处理能力的设备的内部存储单元，例如硬盘或内存。所述计算机可读存储介质也可以是任意具备数据处理能力的设备的外部存储设备，例如所述设备上配备的插接式硬盘、智能存储卡(smart media card，smc)、sd卡、闪存卡(flash card）等。进一步的，所述计算机可读存储介质还可以既包括任意具备数据处理能力的设备的内部存储单元也包括外部存储设备。所述计算机可读存储介质用于存储所述计算机程序以及所述任意具备数据处理能力的设备所需的其他程序和数据，还可以用于暂时地存储已经输出或者将要输出的数据。
28.尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。

技术特征：
1.一种基于gpu的后量子密码kyber并行加速方法，其特征在于：包括如下步骤，步骤1：在gpu设备上分配若干的内存空间，将cpu主机需要传输的数据通过cpu主机传输到gpu设备上；步骤2：在数据传输过程中，将数据存储到gpu设备中的全局内存中，将全局内存中存储的数据复制到共享内存中，步骤3：将传输的数据通过ntt快速数论变换算法分成若干独立计算任务，将计算任务分配给不同的线程；步骤4：利用gpu设备计算架构中的线程块和线程格，确保多个线程访问共享内存的同步性；步骤5：将每个线程计算完成的数据存储到共享内存中，同时将共享内存中的计算完成的数据复制到全局内存中，便于数据从gpu设备传输到cpu主机；根据权利要求1所述的一种基于gpu的后量子密码kyber并行加速方法，其特征在于：步骤1中传输的数据为n维的多项式，对cpu设备内存和gpu设备的全局内存及常量内存进行初始化。2.根据权利要求2所述的一种基于gpu的后量子密码kyber并行加速方法，其特征在于：设置cpu设备和gpu设备对应的接口api函数，设置传输数据大小，数据类型，传输方向。3.根据权利要求2所述的一种基于gpu的后量子密码kyber并行加速方法，其特征在于：ntt快速数论变换算法所需的n/2个旋转因子存储到gpu设备的常量内存中。4.根据权利要求2所述的一种基于gpu的后量子密码kyber并行加速方法，其特征在于：通过ntt快速数论变换算法将多项式拆分为n/2对技术任务，将每对技术任务分配给gpu设备上的不同gpu线程。5.根据权利要求2所述的一种基于gpu的后量子密码kyber并行加速方法，其特征在于：gpu设备中的每个gpu线程进行计算的时候，从共享内存提取数据。6.根据权利要求1所述的一种基于gpu的后量子密码kyber并行加速方法，其特征在于：ntt快速数论变换算法设有若干ntt映射层，当第一层ntt映射并行完成后，顺序运行剩余映射，每一层需改变线程运算的距离、线程的起始位置以及旋转因子的大小，并且在每一层映射完成后都需要同步线程，直至全部ntt映射完成。7.根据权利要求1所述的一种基于gpu的后量子密码kyber并行加速方法，其特征在于：步骤2中共有三个同时进行的线程；线程1：cpu设备与gpu设备数据传输线程；线程2：将传输的数据存储到gpu设备中的全局内存中；线程3：将全局内存存储是数据复制到共享内存中。8.一种基于gpu的后量子密码kyber并行加速装置，其特征在于：包括存储器和一个或多个处理器，所述存储器中存储有可执行代码，所述一个或多个处理器执行所述可执行代码时，用于实现权利要求1-8任一项所述的一种基于gpu的后量子密码kyber并行加速方法。9.一种计算机可读存储介质，其特征在于：其上存储有程序，该程序被处理器执行时,实现权利要求1-8任一项所述的一种基于gpu的后量子密码kyber并行加速方法。

技术总结
本发明公开了一种基于GPU的后量子密码Kyber并行加速方法，包括线程并行、访存优化、指令优选等角度完善基于后量子密码的GPU并行机制；本发明利用多个线程同时执行单个NTT运算，可以大幅降低NTT以及格密码算法的计算时延；同时由于在计算NTT的过程中需要预计算大量的旋转因子，本发明将旋转因子存储在高效的常量内存中；由于NTT的运算过程中涉及大量的内存访问操作，内存访问操作在嵌入式平台中占用较高的时钟周期，本发明将数据存储至共享内存中，而共享内存具有较高的带宽，这意味着可以减少内存带宽的消耗。以减少内存带宽的消耗。以减少内存带宽的消耗。


技术研发人员：张峰 董建阔 吉欣怡 石建 韩朝阳
受保护的技术使用者：杭州后量子密码科技有限公司
技术研发日：2023.06.05
技术公布日：2023/9/23