2.2　RSA数据加密、解密算法实验

2.2.1　实验内容

1. 实验目的

通过实验，让学生充分理解和掌握RSA算法。

2. 实验内容与要求

（1）编程实现RSA加、解密软件，并调试通过。

（2）利用RSA对某一数据文件进行单次加密和解密操作。

（3）提供大素数生成功能：可产生长度最大可达300位十六进制数（约合360位十进制数）的大素数，可以导出素数，也可以从文件中导入素数，也可以产生一个指定长度的随机大素数。

3. 实验环境

（1）平台：Windows或Linux。

（2）编程语言：C、C++、Python任选其一，建议由教师指定。

（3）RSA加密、解密函数库（由教师提供，或要求学生从互联网上搜索下载）。鼓励不使用已有的加密、解密函数库，而是完全自己实现所有代码。

2.2.2　gmpy2简介

gmpy2是Python的一个扩展库，是对GMP的封装，与其早期版本gmpy相比，经过调整和封装，gmpy2使用起来要方便得多。

GMP高精度算术运算库（GNU Multiple Precision Arithmetic Library）是一个开源的高精度运算库，不仅支持普通的整数、实数、浮点数的高精度运算，还支持随机数生成，尤其是提供了非常完备的数论中的运算接口，比如Miller-Rabin素数测试算法、大素数生成、欧几里德算法、求域中元素的逆、Jacobi符号、legendre符号等。很多Python版本的RSA算法的实现使用了gmpy2扩展库提供的功能函数。

gmpy扩展库的源码下载地址为https://github.com/aleaxit/gmpy，gmpy2扩展库的源码下载地址为https://pypi.python.org/pypi/gmpy2/。

下面是利用gmpy2实现的大数分解的示例代码：

上述代码将大数63281217910257742583918406571分解为125778791843321和5031151 67373251。分解所需的时间与运行平台有关。

下面的示例Python代码是寻找1000以内的素数。

下面以ubuntu 18.04操作系统为例，介绍gmpy2的安装过程。

gmpy2依赖GMP、MPFR、MPC三个库，因此在Linux上安装前得先安装这三个库。

需要在Python 3.6中进行，用python --version查看版本，如果是3.6就直接做第一步，如果不是就进行预准备。

预准备工作如下：

（1）sudo apt-get install git python-virtualenv libssl-dev libffi-dev build-essential libpython3-dev python3-minimal authbind virtualenv //安装Python 3.6.9

（2）update-alternatives --list python //如果报错update-alternatives: error: no alternatives for python，则做下一步，没有则下一步不用做

（3）update-alternatives --install /usr/bin/python python /usr/bin/python2.7 1 update-alternatives --install /usr/bin/python python /usr/bin/python3.6 1

（4）update-alternatives --config python //可以看到几个Python版本的候选项，选择Python 3.6的编号

（5）python --version //确认这时候Python已经是3.6.9版本了

下面是正式的安装过程：

（1）先建立两个文件夹。

（2）测试有没有安装m4模块，安装GMP。

出现No manual entry for m4，说明没有安装m4模块。所以先安装m4模块，防止编译GMP时报错：

开始安装GMP：

（3）安装MPFR。

（4）安装MPC。

（5）安装gmpy2。

（6）检查。

命令行进入Python模式后，输入import gmpy2没报错就成功了：

说明：关于m4、GMP、MPFR及MPC的下载，可以选择使用最新版本，也可以不选择使用最新版本。GMP官网地址为https://gmplib.org/，MPFR官网地址为http://www.mpfr.org/mpfr-current/#download，MPC官网地址为http://www.multiprecision.org/mpc/download.html。注意：MPFR要使用最新版，如果要使用GMP和MPC的其他版本，则替换版本号即可。

版本在2-2.1.0b1以上的gmpy2在执行python setup.py build_ext --static=$HOME/static install时会报错，所以这里选取的是低版本的2-2.1.0a1。

2.2.3　实验示例

RSA算法的详细介绍参考教材2.5.1节。

1. 示例代码（Python语言）

2. 运行结果

（1）运行平台：Windows 10。

（2）编译环境：Python 2.7、gmpy2。

运行结果如图2-2所示。