叶文威,马昌社

(华南师范大学计算机学院,广州 510631)

素数在公钥密码算法中广泛使用,公钥密码算法是基于难解性问题设计的,因此不需要像对称密码算法一样需要安全的信道传输密钥,但是公钥密码算法的计算量和大素数生成的资源开销较大。如：RSA算法[1]需要生成2个相同比特长度的素数p和q,然后计算公钥(n,e) (n=p·q),以及计算私钥d=e-1modφ(n),其中e为随机数并与φ(n)互素。因为素数具有分布不均匀性,导致素数生成算法依赖于增量算法来寻找随机数的邻近素数,所以大素数的生成开销较大。

本文是对改进的增量素数生成算法[2]进行改进,改进的增量素数生成算法中,起始状态是选取一个与小素数乘积互素的奇数,每次素性测试失败后,重新随机选取奇数,并将其与小素数的乘积求和。改进的增量素数生成算法在生成较短长度(512 bit)的素数时有更好的性能,但是在生成1 024 bit以上长度的素数时的性能较弱。为了得到一个可拓展长度的快速素数生成算法,本文基于中国剩余定理与门限的理念,设计了基于中国剩余定理的门限素数生成算法(TCPG)。具体地说,TCPG算法通过中国剩余定理求解小素数数组的同余方程组,从而获得初始状态;然后,在素性测试失败后,采用门限思想生成门限值个随机数,再求解同余方程组,从而提高素数生成的效率。

1 TCPG算法

1.1 改进的增量素数生成算法

增量素数生成算法由BRANDT等[5]提出,后来被抽象成算法1[2]的形式。两者的区别是：(1)算法1的初始化变量p与小素数乘积μ互素,小素数乘积通常为2×3×5×…×…≤|p|,其中|p|表示p的比特长度;(2)增量过程从p=p+2变成了p=p+μ。

算法1 改进的增量素数生成算法[2]

Output：素数p

取与μ互素、长度为nbit的随机奇数p

whileT(p)==false do

p=p+μ

end while

返回p

1.2 中国剩余定理素数生成算法

此方程有唯一解：

(1)

中国剩余定理提供了求解同余方程组的方法[12],同时还提供了一种数值映射的方法：选取n个两两互素的正整数m1,m2,…,mn,然后求解同余方程组,得到1个与n个小素数互素的准素数。中国剩余定理素数生成算法(算法2)的核心思想是利用这种数值映射方法寻找素数。

算法2 中国剩余定理素数生成算法

Output：素数p

预计算：

fori=1 tor(n)do

end

主运算：

p=0

whileT(p)==false do

fori=0 tor(n)do

p=p+x×θi

end

end

返回p

1.3 TCPG算法

新课改的环境下，小学三、四年级的科学教师要摒弃一味只重视卷面成绩的传统认识，坚持科学实验的本质，扩展科学实践活动，加大学生动手实验的机会，丰富多样地调动学生的学习兴趣，使学生的创新能力、探究能力、及科学素养得以发展与提升。

算法3 TCPG算法

Input：所需素数比特位数n、Π、门限值t

Output：素数p

预计算：

fori=1 tor(n)do

end

主运算：

c=0,p=0

c=c+x×θi

end

whileT(p)==false do

p←c

fori=r(n)-ttor(n)do

p=p+x×θi

end

end

返回p

2 实验结果与性能分析

本节将首先探究TCPG算法的门限值k对素数生成平均时长的影响,然后基于Miller-Rabin概率素性测试算法[3],将TCPG算法与原生素数生成算法、增量素数生成算法[5]、改进的增量算法[2]、M-J特例算法[7]、改进的M-J算法[8]和中国剩余定理素数生成算法[12](简称CRT)进行对比实验。

2.1 门限值对TCPG算法的性能影响

首先,分析不同门限值k对TCPG算法的性能影响。为了寻找小素数数组中的最优门限值k,研究当TCPG算法生成不同长度的素数时,不同门限值对素数生成平均时长的影响。实验环境为Go语言编程,运行在Intel i3-8350K@4.00 GHz处理器上,对每个k进行10 000次实验。

由图2可知随机数的更新个数和素数生成平均时长没有明显的线性关系,因此,不同小素数的组合都需要通过实验来确定该数组的最优门限值k。本文采用的小素数数组在TCPG算法中生成1个长度为512 bit的素数的最优门限值k为6,所需平均时长为7.80 ms;生成1个长度为1 024 bit的素数的最优门限值k为3,所需平均时长为53.30 ms;生成1个长度为2 048 bit的素数的最优门限值k为18,所需平均时长为505.78 ms。

图2 TCPG算法的不同k值性能分析图Figure 2 Performance analysis diagram of different k values of TCPG algorithm

2.2 素数生成算法性能分析

测试环境为Go语言编程,运行在Intel i3-8350K@4.00 GHz处理器上;TCPG算法在生成长度分别为512、1 024、2 048 bit的素数的门限值均为2.1节得到的最优门限值。

由平均时长和平均素性判定次数(表1)可知TCPG算法生成1个长度为512 bit的素数的平均时长略多于改进的增量算法所需时长,但是,在生成长度为1 024 bit和2 048 bit的素数的平均时长最短：TCPG算法生成1个长度为512 bit的素数的平均时长为7.80 ms,比CRT算法降低了18.6%;生成1个长度为1 024 bit的素数的平均时长为53.30 ms,比CRT素数降低了7%;生成1个长度为2 048 bit的素数的平均时长为505.78 ms,比CRT算法降低了5%。

表1 素数生成算法性能分析Table 1 Performance analysis of prime number generation algorithm

另外,实验算法统一进行30次Miller-Rabin概率素性测试,每个算法生成的素数可信度为(1-(1/4)30)*100%≈100%,也就是说,实验在生成十万个大素数的情况下,最多只有0个假素数,因此实验的结果是可信的。

3 结论

为了提高大素数生成的效率,本文基于中国剩余定理对改进的增量素数生成算法进行了改进,设计了基于中国剩余定理的门限素数生成算法(TCPG)。然后基于Miller-Rabin素性测试算法,将TCPG算法与原生素数生成算法、增量素数生成算法、改进的增量算法、M-J特例算法、改进的M-J算法和中国剩余定理素数生成算法(简称CRT)进行对比实验。实验结果表明TCPG算法生成1个长度为512 bit的素数的平均时长(7.80 ms)略多于改进的增量算法所需时长(7.73 ms),但是,生成长度为1 024 bit和2 048 bit的素数的平均时长最短：TCPG算法在Miller-Rabin素性测试算法下生成1个长度为512 bit的素数的平均时长为7.80 ms,比CRT算法减少1.46 ms;生成1个长度为1 024 bit的素数用时需53.30 ms,比改进的增量素数生成算法、CRT算法分别减少5.50、4.30 ms;生成1个长度为2 048 bit的素数用时需505.78 ms,比改进的增量素数生成算法、CRT算法分别减少106.03、54.54 ms。

本文仅给出了TCPG算法的实现和性能分析,实际应用时需考虑侧信道信息的泄露[13]和算法的安全性问题[14];若要用于RSA方案,则还需要保证使用的是强素数[15]。