双击RSAToy.exe运行程序,界面主要分为两部分:
-
左侧为RSA密钥生成部分,可以选择RSA-768,RSA-1024或者RSA-2048作为标准,并点击Generate Key按钮生成密钥。生成完成后,密钥中的$$p,q,n,e,d$$都会显示在文本框中。
-
右侧为消息发送部分,用户可以在消息输入框输入要发送的消息(目前只支持ASCI编码),并点击Send Message按钮即可发送消息。RSA算法会对消息先进行加密、再进行解密,并将加密和解密的结果都显示在对应的文本框中。
(注:目前仅支持1080P分辨率,在较高分辨率如2k\3k\4k下界面可能会显示异常)
在本次大作业中,实现了如下基本算法:
- 加、减、乘、除、移位、幂取模的高精度算法
- 利用快速幂和牛顿迭代法加速取模运算
- **剩余定理
- Miller Rabin检测
在RSA密钥的生成过程中,大素数生成是时间瓶颈,因此在素数生成过程中,我使用了以下方法来进行优化或加速:
在Miller Rabin算法中,需要多次进行幂取模运算$$a^d\pmod n$$,其中$$a, d, n$$均为大整数,经过测试,这一步是Miller Rabin判据最耗时的步骤,因此,对这一步进行优化非常关键。对幂取模这一步运算做优化,最直观和简单的算法是快速幂算法。
在计算$$a^d\pmod n$$时,如果$$d$$为偶数,那么可以计算$$(a^\frac{d}{2})^2\pmod n$$,如果$$d$$为奇数,那么可以计算$$(a^\frac{d-1}{2})^2a\pmod n$$,根据维基百科,快速幂的伪代码为:
function modular_pow(base, exponent, modulus) is
if modulus = 1 then
return 0
Assert :: (modulus - 1) * (modulus - 1) does not overflow base
result := 1
base := base mod modulus
while exponent > 0 do
if (exponent mod 2 == 1) then
result := (result * base) mod modulus
exponent := exponent >> 1
base := (base * base) mod modulus
return result
不难发现,朴素的幂取模算法的时间复杂度为$$O(d)$$,而使用了快速幂之后,时间复杂度为$$O(log(d))$$.以$$RSA-768$$为例,$$d$$在二进制下是$$384$$位的整数,因此经过384次迭代即可得到结果,相比线性复杂度,节省了相当多的时间。
使用快速幂算法之后,发现计算$$a^d\pmod n$$的时间仍然很长,发现主要是计算$$a \mod n$$比较耗时,因为计算$$a \mod n$$需要使用高精度除法,当$$a
因此我使用了基于牛顿迭代法的求模算法,记$$n$$在二进制下有$$m$$位,该算法通过寻找$$n'$$,使得$$(nn')=1<<2m$$,这里$$<<$$是左移符号,这样$$a=a-((ann')<<2m)\pmod n$$.并且$$a\mod n$$与$$a-((ann')<<2m)\mod n$$的值非常接近(事实上它们在大多数情况下是相等的),从而大大减少了减法的次数。
问题的关键在于:如何寻找$$n'$$,这里我使用的是牛顿迭代法,定义函数$$f(x)=\frac{1<<2m}{x}-n$$,那么函数的零点即为$$n'$$,从而可以使用牛顿迭代法求解。在实验中发现,通常经过10-20次迭代,就可以找到$$n'$$.
同时,注意到,如果要计算多个$$a_0, a_1,...a_k$$对$$n$$的模,牛顿迭代法只需要计算一次即可,这又大大减少了取模的时间。
这一步优化是整个算法中最为关键的一步,如果不使用该方法,在几分钟的时间内甚至跑不完一次完整的Miller Rabin检测。
因为寻找素数的过程是可并行的,所以我利用了c++的多线程库,使用多线程来寻找素数。
我使用了多个线程同时判断整数的素性,并设置一个标志位,一旦某个线程找到一个素数,它将会修改此标志位,其余线程检查到标志位被修改后将会立刻退出。我使用了C++中的mutex来保护标志位以避免冲突。
- 随机递增搜索。在寻找素数时,不必每次都随机生成一个数,然后判断它的素性。而是首先生成一个奇数$$n$$,如果$$n$$不是素数,就给$$n$$加$$2$$,重复此过程。在RSA-768下,平均需要380次即可找到一个素数。
- 利用小素数优化。对一个未知素性的整数进行Miller Rabin检测之前,可以先尝试该整数能否整除小素数,以检测该整数的素性。因为Miller Rabin检测相对比较耗时,这样做可以尽可能减少Miller Rabin检测的次数。在实现中,我使用了$$10000$$以内的所有素数,在RSA-768下,平均找到每个素数仅需47次Miller Rabin检测。
操作系统: Windows 10
CPU: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz 1.99GHz
编程语言:C++
编译器:Microsoft Visual C++ Compiler16.4.29806.167
集成开发环境:Qt Creator(Qt 5.9.9 MSVC2015 64bit)
在上述实验环境中,分别在RSA-768,RSA-1024和RSA-2048三种标准下生成100次公钥和密钥,并计算平均耗时,结果如下表所示:
RSA | RSA-768 | RSA-1024 | RSA-2048 |
---|---|---|---|
Time(s) |
附:一开始我是用的是MinGW编译器,不论怎么优化,生成RSA-768平均需要2s。走投无路之下,改用MSVC编译器,没想到速度快了4倍,真是蛋疼啊。。。。。。
这次大作业个人感觉很有趣,像是回到了大一写代码的时候!其实如果按照老师课上讲的内容,不去自己找资料、想办法的话,实现出的RSA肯定是慢的离谱。我一开始就实现了非常基础的版本,慢到跑不出结果,后来请教了别人,才发现可以用牛顿迭代法、用小素数来减少Miller Rabin检测的素数。我的实现从一开始跑不出结果、到2s跑出结果、最后将结果稳定在0.4s左右,看着自己的程序在一点点变快,这个过程真的很让人有成就感!