# RSA 大作业 实验报告
## 程序使用说明
![](https://www.writebug.com/myres/static/uploads/2021/12/29/66c3fd96d3f0d6e9ec583d7de8b437b0.writebug)
双击 RSAToy.exe 运行程序,界面主要分为两部分:
1. 左侧为 RSA 密钥生成部分,可以选择 RSA-768,RSA-1024 或者 RSA-2048 作为标准,并点击 Generate Key 按钮生成密钥。生成完成后,密钥中的
$$
p,q,n,e,d
$$
都会显示在文本框中。
2. 右侧为消息发送部分,用户可以在消息输入框输入要发送的消息(目前只支持 ASCI 编码),并点击 Send Message 按钮即可发送消息。RSA 算法会对消息先进行加密、再进行解密,并将加密和解密的结果都显示在对应的文本框中。
(注:目前仅支持 1080P 分辨率,在较高分辨率如 2k\3k\4k 下界面可能会显示异常)
## 算法实现亮点
在本次大作业中,实现了如下基本算法:
1. 加、减、乘、除、移位、幂取模的高精度算法
2. 利用快速幂和牛顿迭代法加速取模运算
3. 中国剩余定理
4. 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$$,根据维基百科,快速幂的伪代码为:
```c++
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
$$
时,将会使用相当多次的减法,从而导致这一步非常耗时。
因此我使用了基于牛顿迭代法的求模算法,记
$$
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 来保护标志位以避免冲突。
#### 其它小优化
1. 随机递增搜索。在寻找素数时,不必每次都随机生成一个数,然后判断它的素性。而是首先生成一个奇数
$$
n$$,如果
$$
n
$$
不是素数,就给
$$
n
$$
加
$$
2$$,重复此过程。在 RSA-768 下,平均需要 380 次即可找到一个素数。
2. 利用小素数优化。对一个未知素性的整数进行 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) |
$$
0.41749
$$
|
$$
0.93251
$$
|
$$
7.66868
$$
|
附:一开始我是用的是 MinGW 编译器,不论怎么优化,生成 RSA-768 平均需要 2s。走投无路之下,改用 MSVC 编译器,没想到速度快了 4 倍,真是蛋疼啊。。。。。。
## 感想和收获
这次大作业个人感觉很有趣,像是回到了大一写代码的时候!其实如果按照老师课上讲的内容,不去自己找资料、想办法的话,实现出的 RSA 肯定是慢的离谱。我一开始就实现了非常基础的版本,慢到跑不出结果,后来请教了别人,才发现可以用牛顿迭代法、用小素数来减少 Miller Rabin 检测的素数。我的实现从一开始跑不出结果、到 2s 跑出结果、最后将结果稳定在 0.4s 左右,看着自己的程序在一点点变快,这个过程真的很让人有成就感!
基于C++实现 RSA 大作业【100012184】
版权申诉
168 浏览量
2023-05-15
11:04:08
上传
评论
收藏 19.8MB ZIP 举报
神仙别闹
- 粉丝: 2680
- 资源: 7667
最新资源
- 基于Matlab的图像分割系统+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 基于MATLAB指纹门禁GUI设计源码+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 基于Matlab的仪表指数识别系统霍夫曼变换+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 基于MATLAB 的霍夫曼变换答题卡识别带GUI界面+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 基于MATLAB 疲劳驾驶检测专识别GUI源码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 基于matlab的虫害侵蚀系统带Gui界面+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 基于Matlab的教室人数统计系统 可以统计正脸情况下的人数+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计
- 基于MATLAB的水果分级系统,带GUI界面+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 基于MATLAB的车票发票识别系统带GUI界面+源代码+全部数据+文档说明+详细注释+使用说明+截图(高分课程设计)
- 微信小程序电商实战课程SpringBoot2+Vue3+Element plus.rar
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈