一种改进的大素数乘法的设计与实现_达斯孟.pdf

SOFTWARE软 件2023第 44 卷 第 1 期2023 年Vol.44,No.1作者简介：达斯孟（1986）,男,蒙古族,内蒙古鄂尔多斯人,硕士研究生,高级工程师,研究方向：社保大数据应用与研究、非对称加密算法等。一种改进的大素数乘法的设计与实现达斯孟（鄂尔多斯市人力资源和社会保障局，内蒙古鄂尔多斯 017400）摘要：RSA 算法作为应用较为广泛的非对称加密算法,经过蒙哥马利模乘等算法的优化后主要基于有限域运算中大数的加法运算和乘法运算,数位规模通常在 1024 位甚至更高。大数的乘法运算随着参与运算位数的增加会导致 RSA 算法的运行时间效率下降。随着多核处理器架构的普及,如何在多核多线程并行运算背景下提高 RSA 算法效率就成为解决 RSA 算法性能瓶颈的关键。本文通过多核并行运算背景下分析大数乘法算法从而提出一种改进的适应多核运算的大数相乘算法,依靠此算法提高 RSA 算法和大规模科学计算中高精度浮点数运算效率。关键词：非对称加密算法；RSA；大数乘法运算；COMBA 算法中图分类号：TP393 文献标识码：A DOI：10.3969/j.issn.1003-6970.2023.01.027本文著录格式：达斯孟.一种改进的大素数乘法的设计与实现J.软件,2023,44(01):104-106Design and Implementation of an Improved Multiplication of Large Prime Numbers DA Simeng(Ordos Human Resources and Social Security Bureau,Ordos Inner Mongolia 017400)【Abstract】：As a widely used asymmetric encryption algorithm,the RSA algorithm is mainly based on the addition and multiplication of large numbers in finite field operations after the optimization of Montgomery modular multiplication and other algorithms.The digital scale is usually 1024 bits or even higher.The multiplication of large numbers will lead to a decrease in the running time efficiency of the RSA algorithm as the number of bits involved in the operation increases.With the popularization of multi-core processor architecture,how to improve the efficiency of RSA algorithm in the context of multi-core and multi-thread parallel computing has become the key to solving the performance bottleneck of RSA algorithm.This paper analyzes the multiplication algorithm of large numbers in the context of multi-core parallel computing,and proposes an improved multi-core multiplication algorithm for large numbers.Relying on this algorithm,it improves the efficiency of high-precision floating-point arithmetic in RSA algorithm and large-scale scientific computing.【Key words】：asymmetric encryption algorithm;RSA;big integer multiplication;COMBA algorithm设计研究与应用0 引言RSA 密码算法作为迄今最成熟最广泛应用的公钥密码体制,由于其安全性高、抗数学攻击能力强等优点而被广泛用于 SoC 智能芯片等各领域1。RSA 算法的安全性是基于数论和计算复杂性理论,即计算两个大素数乘积是十分容易的,但是想要很快将两个大素数的乘积分解,求出它的因子在计算上是困难的,至今还没有一种方法能够很好地将其破解2。计算机科学领域近年来涌现出了很多关于 RSA 算法研究,包括了软件和硬件领域。作为 RSA 算法的提出人Rivest 提出了硬件思路,而 Shamir and Adleman 则提出了先进的模运算的算法3。RSA 加密算法迄今为止已经成功商业运营超过 40 年,由于计算性能和 RSA 算法研究的深入进行,在 2001 年 Lenstra and Verheul 得出结论表明如果想要在 2040 年仍然确保 RSA 算法的安全性,就要将目前流行的 1024 位的秘钥扩大三倍4。随着多核多线程架构的诞生和普遍使用。由于 RSA 算法的使用范围非常广泛,且很多项目并没有专门针对 RSA算法的硬件加速器支持,因此本文聚焦在多核并行计算背景下从纯软件角度提升 RSA 算法运行的时间性能。105达斯孟：一种改进的大素数乘法的设计与实现RSA 算法的运行性能的关键点在于模幂运算即C=Me mod n 和 M=Cd mod n。模幂运算通常会被分解为一系列的模乘运算实现优化。许多现代密码学算法都强烈依赖于对大整数的模运算,所需大整数通常是素数或两个素数的乘积。因此提升 RSA 算法性能相关研究的一个重点方向在于有限域中如何提升大数运算性能。在模幂运算中通常有大概 25%的运算时间用于乘法操作5,因此近年来关于大数相乘算法的研究一直是 RSA算法性能提升的重点。提高加密算法效率的一种有效方式是在有限域中提高大数乘法的效率6。目前软件提高大整数乘法算法的研究主要集中在两方面：（1）基于现有大数乘法运算较为成熟的算法例如基线算法、Karatsuba 算法、Toom-Cook3算法进行算法优化和性能调优；（2）随着多核多线程CPU 的普及,通过提高算法的并行度进而提升算法的时间性能。本文结合上述两种研究思路,通过引入一种更适应多核多线程运算规则的大数乘法算法,从而提高整个 RSA 算法的运行时间效率。1 大数相乘算法效率比较与改进的大数相乘算法目前的处理器对于二进制数位的移位运算会比乘法要快很多,因此可以使用左移位操作代替乘以 2 的次幂,乘以不同数的乘法也可以用一连串的移位和加减法来代替。大数相乘的算法主要有基线算法、傅立叶相乘算法、Karatsuba 乘法、Toom-Cook3 相乘算法。Karatsuba乘法和 Toom-Cook3 相乘算法的核心思路是一致的,只不过在应用分治操作时 Karatsuba 乘法是分为两部分,而 Toom-Cook3 相乘算法则是分为三部分。由于中国余数定理使得 RSA 算法的操作数的规模减小了一半,因此即使 4096 位的大数运算也可以减半位 2048 位,因此本文基于上述原因对于所需位数十分庞大的傅立叶相乘不做过度赘述。我们分别对多线程运行情况下在运算规模被分解为较小位数的情况下对 Karatsuba 乘法、Toom-Cook3-way 相乘和基线相乘法进行性能分析并比较其在 64 位、128 位、512 位、768 位、1024 位、1536 位、2048 位等 7 种较常见情况下的理论复杂度和消耗时间6。下面我们介绍 COMBA 算法,想要了解 COMBA 技术首先来看一下两个大数相乘的过程。例如需要对 X 和Y 两个 5 位的大数相乘,每一个大数位为 b 个二进制位。其结果存放在目标数组 T 里面,则在构造 Tn 的元素时对其中所要存放的元素在得到两个相乘的大数的时候已经可以确定了,并且它们之间满足如公式（1）所示的关系：X0Yn-1+X1Yn-2+X2Yn-3+Xn-1Y0=Tn-1 （1）也就是说 T 的元素的位置也就是 n-1 等于上述公式里面的等式左边的 X 和 Y 的下标的和。因此就可以在没有进行完整的大数相乘的时候,甚至是任何时候,得到想得到的任何一个位置上的目标数组 T 的值,也就是XY 的任何位置上的值（此时可以不考虑进位）。这就是 COMBA 算法优势所在。下面通过 COMBA 算法的大数相乘的伪代码进行比较来说明其效率明显提升的原因,下面再看一下 COMBA 算法的伪代码。Algorithm CombaMul(a,d,T)Input:T=(T2k-1,T2,T1)b,a=(ak-1,a1,a0)b,d=(dk-1,d1,d0)b,R=bkOutput:T=a*dStep1 loc=2k-1,temp=0Step2 for ix from 0 to loc 1 by1 do Step2.1 ty=MIN(k,ix)Step2.2 tx=ix ty Step 2.3 iy=MIN(k tx,ty+1)Step 2.4 for iz from 0 to iy 1 do Step 2.4.1 temp=temp+atx+iybty iy Step 2.5 Tix=temp mod b Step 2.6 temp=temp lg b Step3.Return T我们看到在 CombaMul(a,d,T)函数里,和前面的基线算法相比具有两个重大的优点。（1）CombaMul 函数的运算过程是垂直式的运算,在运算 Ti 的时候可以利用公式（1）的等式来构造出该列的值,也就是 Ti 的值。同时由于 Temp 值可以常驻 CPU 寄存器,因此可以降低内存访问次数。这在乘法运算当中起着非常关键的作用。（2）基线算法需要在每一次的 Temp 的计算结果后进行一次 mod 操作取个位和位移操作取进位的过程,也就是说在需要 k2次的 mod 操作和位移操作,而在CombaMul 函数中由于只是在每一列的结束的时候才进行 mod 操作和位移操作,因此其次数只是需要 2k-1次。从而提升了效率。如表 1 所示展示了基线算法、Karatsuba 算法与 COMBA 算法在 n 位大数相乘时所需乘法、加法、存储操作的次数。表 1 三种算法的计算成本比对Tab.1 Comparison of computational cost of three algorithms算法名称乘法操作数 加法操作数存储操作数复杂度Comban23n22nO(n2)Karatsuba234n3n2+4n+2234n+112n+1O(nl.584)基线n24n2n2+nO(n2)2 性能测试与分析笔者基于英特尔酷睿 i7-10700F 处理器（8 核心 16106软 件第 44 卷 第 1 期SOFTWARE线程,主频 2.90GHz）和 Win32 平台 MSVC 编译器环境对上述程序 COMBA 大数相乘算法进行代码实现,并与基线算法、Karatsuba 算法、TOMMCOOK-3 算法在不同大数规模（分别为 64 位、128 位、512 位、768位、1024 位、1536 位、2048 位）下相乘结果进行了比较,结果如图 1 所示（运算结果时间单位为毫秒,循环次数为 10000 次）。从图 1 中可以看出多核多线程背景下在 64 位到2048 位大数相乘过程中 COMBA 算法始终保持着时间效率的优势。其中在 64 位时比效率排名第二的基线算法提高 88.6%,在 128 位时