> # ♻️ 资源
> **大小:** 19.7MB
> **文档链接:**[**https://www.yuque.com/sxbn/ks/100010263**](https://www.yuque.com/sxbn/ks/100010263)
> **➡️ 资源下载:**[**https://download.csdn.net/download/s1t16/87354376**](https://download.csdn.net/download/s1t16/87354376)
> **注:更多内容可关注微信公众号【神仙别闹】,如当前文章或代码侵犯了您的权益,请私信作者删除!**
> ![qrcode_for_gh_d52056803b9a_344.jpg](https://cdn.nlark.com/yuque/0/2023/jpeg/2469055/1692147256036-49ec7e0c-5434-4963-b805-47e7295c9cbc.jpeg#averageHue=%23a3a3a3&clientId=u8fb96484-770e-4&from=paste&height=140&id=u237e511a&originHeight=344&originWidth=344&originalType=binary&ratio=1.25&rotation=0&showTitle=false&size=8270&status=done&style=none&taskId=ud96bf5f7-fe85-4848-b9c2-82251181297&title=&width=140.1999969482422)
# RSA大作业 实验报告
## 程序使用说明
![image-20201112164314790.png](https://cdn.nlark.com/yuque/0/2024/png/2469055/1708225927775-b5472cfe-01e2-4b65-bb68-a1cb2ddc8b44.png#averageHue=%23f1f1f1&clientId=u2496c55a-89c3-4&from=paste&height=671&id=ufa2b7587&originHeight=839&originWidth=1246&originalType=binary&ratio=1.25&rotation=0&showTitle=false&size=27836&status=done&style=none&taskId=u9c05aea7-1092-4e1c-b8cc-29aaac51956&title=&width=996.8)
双击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左右,看着自己的程序在一点点变快,这个过程真的很让人有成就感!
没有合适的资源?快使用搜索试试~ 我知道了~
基于QT(C++)实现(图形界面)应用密码学大作业【100010263】
共57个文件
qm:21个
dll:19个
cpp:5个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 192 浏览量
2022-12-30
11:54:06
上传
评论
收藏 19.8MB ZIP 举报
温馨提示
详情介绍:https://www.yuque.com/sxbn/ks/100010263 在本次大作业中,实现了如下基本算法: 加、减、乘、除、移位、幂取模的高精度算法 利用快速幂和牛顿迭代法加速取模运算 中国剩余定理 Miller Rabin检测
资源推荐
资源详情
资源评论
收起资源包目录
100010263-基于QT(C++)实现(图形界面)应用密码学大作业.zip (57个子文件)
rsa-homework
doc
report.pdf 526KB
image-20201112164314790.png 27KB
src
rsatoy.h 513B
Integer.cpp 14KB
RSAToy.pro 1KB
rsatoy.cpp 2KB
RSAToy.pro.user 22KB
main.cpp 181B
RSA.cpp 23KB
Test.h 879B
rsatoy.ui 11KB
Integer.h 2KB
RSA.h 1KB
Test.cpp 5KB
LICENSE 1KB
bin
libGLESV2.dll 2.41MB
Qt5Gui.dll 5.78MB
RSAToy.exe 106KB
imageformats
qjpeg.dll 238KB
qsvg.dll 31KB
qtga.dll 31KB
qtiff.dll 374KB
qwebp.dll 491KB
qgif.dll 38KB
qicns.dll 45KB
qwbmp.dll 29KB
qico.dll 40KB
Qt5Core.dll 5.56MB
Qt5Svg.dll 327KB
Qt5Widgets.dll 5.29MB
translations
qt_lv.qm 150KB
qt_sk.qm 123KB
qt_cs.qm 171KB
qt_de.qm 184KB
qt_ja.qm 127KB
qt_fi.qm 171KB
qt_da.qm 166KB
qt_ko.qm 128KB
qt_fr.qm 162KB
qt_pl.qm 159KB
qt_ar.qm 156KB
qt_it.qm 157KB
qt_bg.qm 161KB
qt_gd.qm 185KB
qt_es.qm 161KB
qt_en.qm 23B
qt_uk.qm 155KB
qt_ca.qm 175KB
qt_hu.qm 157KB
qt_he.qm 135KB
qt_ru.qm 154KB
iconengines
qsvgicon.dll 43KB
platforms
qwindows.dll 1.29MB
libEGL.dll 21KB
opengl32sw.dll 19.95MB
D3Dcompiler_47.dll 3.98MB
README.md 7KB
共 57 条
- 1
资源评论
神仙别闹
- 粉丝: 2687
- 资源: 7649
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功