# rsa

**Repository Path**: ycdfwzy/rsa

## Basic Information

- **Project Name**: rsa
- **Description**: RSA的C++实现
- **Primary Language**: Unknown
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 8
- **Forks**: 2
- **Created**: 2020-11-11
- **Last Updated**: 2025-07-18

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# RSA作业文档

## 简介

本次课程作业我实现了RSA算法，RSA-768的密钥生成时间约为**240ms**，RSA1024的密钥生成时间约为**714ms**，RSA-2048的密钥生成时间约为**30000ms**。达到了作业的要求。

在此基础上，我实现了利用RSA对任意字符串加密解密的功能，具体见`使用说明`一节。

## 环境

* CPU： Intel(R) Core(TM) i7-9700F
* 内存：16.0 GB
* 操作系统：Windows 10 Pro Education 19041.630
* 语言： C++
* 编译器：MSCV ( Visual Studio 2019 Community Edition )

## 使用说明

双击`rsa.exe`可执行文件，运行程序，用户可以输入以下指令：

* `G`：生成RSA密钥，需要再输入一个数字作为RSA密钥长度。下图是生成长度为1024位的RSA密钥的一次运行截图

  ![](pic/G.png)

* `E`：加密字符串，执行该指令需要首先运行过`G`指令生成RSA密钥。下图是加密字符串`I love RSA!`的运行截图

  ![](pic/E.png)

* `D`：解密字符串，执行该指令需要首先运行`G`指令生成RSA密钥和`E`指令加密字符串。下面是解密`I love RSA!`的运行截图

  ![](pic/D.png)

* `Q`：退出程序

  ![](pic/Q.png)


## 实现亮点

一些基础的算法再文档中就不再阐述，这里关键阐述对部分算法的优化策略。

### 优化除法/取模

最基础的除法算法是竖式除法，商位时用二分的方法，复杂度为 $\mathcal{O}(mn\cdot log_2(B))$ （被除数的位数是$n$，除数的位数是$m$，存储的进制为$B$）。经过测试，基于该除法的RSA算法，RSA-768平均耗时为2000ms，RSA-1024平均耗时为4000ms。利用VS的Profiler分析运行时间，如下图，可以发现，最大的瓶颈在于除法的计算

![](pic/naive_profiler.png)

为此，我改进了除法的计算。仍然采用竖式除法的思路，仅改良竖式商位时的方法。下面是商位的伪代码

```
r是被除数的一段
a是除数
s是当前的商位
while r >= a
	t := max{1, r的最高位 / (a的最高位 + 1)}
	r := r - t * a
	s := s + t
```

显然这个算法是正确的，这里的while循环最多只会进行$log_2 B$次，实际上达到$log_2 B$次是非常极端的情况，在大多数，可以认为这里只有常数次的循环。这样改良后的除法，复杂度依然是 $\mathcal{O}(mn\cdot log_2(B))$ ，但是常数比原算法小得多。



### 优化扩展欧几里得

在计算公私钥时，需要用到扩展欧几里得算法，也就是计算$e$和$\varphi(n)$的扩欧。$\varphi(n)$必然是一个大数，而$e$只要与$\varphi(n)$互质，就可以任意选。我们可以检查$100000$以内的所有质数$h$，只要$\varphi(n)$不是$h$的倍数，就可以确定$h$与$\varphi(n)$互质（这样的$h$是必然存在的，因为$100000$以内所有质数的积远远大于$2^{1024}$，所以$\varphi(n)$不可能与$100000$以内的所有质数都互质）。我们就选取这样的$h$作为公钥$e$，再用扩展欧几里得计算私钥$d$。回忆扩展欧几里得的迭代算法，一开始计算exgcd($\varphi(n)$, $e$)，第一次迭代计算exgcd($e$, $\varphi(n)\ mod\ e$)，显然$e$和$\varphi(n)\ mod\ e$都是$100000$以内的数，之后的迭代都可以在32位整型数字下进行运算，也就是说只有一次迭代是涉及到大整数计算的。这可以节省大量的时间。

### 优化常数

常数优化在本次实验中显得尤为重要，在优化除法那部分就提到过，普通除法的计算时间是2~4s，离1s的时限也就差一个2左右的常数。

优化常数的思路有很多，比如大整数的进制尽量用2的整次幂，这样取模可以用位运算代替；尽量避免无用的数据移动，例如

```c++
// a, b都是大整数
a = a + b
```

程序会先用一个临时变量存储`a+b`结果，再将结果复制到`a`中。而如果我们写成下面的形式

```c++
a += b
```

就可以避免一次数据的复制。

更具体的，在实现上文的优化除法的时，有一步运算是

```
r := r - t * a
```

如果直接这么实现，因为是大整数运算，需要2次遍历数位、2次复制数据，非常的浪费，用VS的Profiler分析得到下图

![](pic/opt1_profiler.png)

生成1024位的密钥耗时约4000ms，其中接近95%的时间消耗在除法函数上，更进一步分析除法中的耗时，如下图，几乎所有的耗时都在（约3700ms）`r=r-t*a`这条语句上。

![](pic/opt1_profiler_code.png)

为了优化这部分的时间，我实现了一个专门的函数，专门处理`r-t*a`这样计算（也就是上图第666行所示的语句），这样只需要1次遍历数位，无需数据复制，在用Profiler分析一下运行时间：

![](pic/opt2_profiler.png)

![](pic/opt2_profiler_code.png)

可以看到，总时间缩减为了482ms，更重要的是，除法耗时仅占总耗时的约60%，修改的语句从原来的92%下降到44%，效果非常显著。

### 丰富的测试用例

在完成代码的时候，考虑到手动实现大数容易出错，我基本保证了每实现一个功能（如大数进制转换、加减乘除、位移等），都会做一个测试用例，保证在编写下一个功能时，前面的功能没有错误，大大减少了Debug的时间。下图第一张是测试进制转换的部分代码，第二张是最终通过所有测试截图。

![](pic/test.png)

![](pic/test_result.png)



## 实验感想

本次实验帮助我更深入地学习了RSA算法，不过我觉得整个作业的重点在于优化算法而不是实现算法。

我的代码还有不少优化的空间：

* 采用NTT优化乘法运算
* 采用牛顿迭代法或者蒙哥马利法加速除法运算
* 在生成素数阶段采用多线程加速
* ……

由于个人水平有限，以及时间限制，我没有更进一步实现更好的RSA算法，算是本次实验的一点遗憾。