RSA密码算法设计与实现
1. 创建资源
开始实验之前，您需要先创建实验相关资源。
在实验室页面，单击创建资源。
（可选）在实验室页面左侧导航栏中，单击云产品资源列表，可查看本次实验资源相关信息（例如IP地址、子用户信息等）。
说明：资源创建过程需要3～5分钟（视资源不同开通时间有所差异，ACK等资源开通时间较长）。完成实验资源的创建后，您可以在云产品资源列表查看已创建的资源信息，例如：子用户名称、子用户密码、AK ID、AK Secret、资源中的项目名称等。
实验环境一旦开始创建则进入计时阶段，建议学员先基本了解实验具体的步骤、目的，真正开始做实验时再进行创建。
资源创建成功，可在左侧的资源卡片中查看相关资源信息以及RAM子账号信息
2. 实验原理
实验原理
公钥密码的基本思想
将密钥 K 一分为二: Ku 和 Kr 。Ku专门加密， Kr专门解密，Ku ≠ Kr。
由 Ku 不能计算出 Kr ， 于是可将 Ku 公开，密钥 Kr 保密。
由于 Ku ≠ Kr 且由 Ku 不能计算出 Kr ， 所以 Kr 便成为用户的指纹，于是可方便地实现数字签名。
一个公开密钥系统明文、公开密钥 Ku、私有秘钥 Kr、加密算法、解密算法和密文这六要素组成。RSA 密码被誉为是一种风格优雅的公开密钥密码。既可用于加密，又可用于数字 签名，安全、易懂，是目前应用最广泛的公钥密码之一。
RSA 算法的数学基础
欧拉函数
对于任意给定的正整数 n，欧拉函数用于计算在小于等于 n 的正整数之中，与 n 互质的正整数的个数，用 φ(n)表示。
欧拉函数对以下定理成立:
(1) 如果 n 可以分解成两个互质的整数之积，即 n = p×q，则有 φ(n) = φ(pq) = φ(p)φ(q);
(2) 一个数 p 如果是质数，则小于它的所有正整数都与它互质，即 φ(p) = p-1;
由上述可知，如果一个数 n 可以分解为两个质数 p 和 q 的乘积，则有: φ(n) = (p-1)(q-1)
欧拉定理
如果两个正整数 a 和 n 互质，则 n 的欧拉函数 φ(n)可以让下面的等式成立:
模反元素
根据欧拉定理，有:
令 
，得:
b 就是 a 的模反元素，b 不唯一。
如果两个正整数 a 和 n 互质，那么一定可以找到整数 b ，使得 ab-1 被 n 整除，或者说 ab 被 n 除的余数是1。
RSA 加解密算法
随机选取两个大素数 p 和 q ，而且保密;
计算 n = p×q，将 n 公开;
计算小于 n 并且与 n 互质的整数的个数，即欧拉函数 φ(n)=(p-1)(q-1)，对 φ(n) 保密;
随机选取一个正整数e，1 < e < φ(n) 且 e 和 φ(n) 互质，即 gcd(e,φ(n)) = 1，将 e 公开;
根据 ed = 1 mod φ(n)，求出 e 的模反元素 d，并对 d 保密;
加密运算:
解密运算:
加密密钥 Ku =<n,e>，解密密钥 Kr=<n,d>。
*解密过程推导
因 
，所以存在整数 k，使得 
。
因此，
对于 
，即
，实际实现中，n 是两个大素数 p 和 q 的乘积，明文 M 会被分成几个较小的数进行加密，所以 
和 n 互质，那么根据欧拉定理，
≡ 1 (mod n)。所以
成立。
RSA 密码安全性，参数应该选择
(1) p 和 q 要足够大，从而乘积 n 足够大;
(2) p 和 q 应该为强素数; (文献指出，只要(p-1)、(p+1)、(q-1)和(q+1)四个数之一只有小的素因子，n 就容易分解)
(3) (p-1) 和 (q-1) 的最大公因子要小，如果最大公因子太大，易受迭代加密攻击;
(4) e 随机且含 1 多比较安全，但是加密速度慢。有的学者建议取 e = 216+1 = 65537，它是素数，且二进制表示中只含两个 1;
(5) d 要足够大才安全。
大素数产生
产生一个足够大的随机数，然后通过素性测试算法判断该随机数是否为素数。 常用的素性测试算法:
Solovay-Strassen素性测试
Miller-Rabin素性测试
实验工具
Openssl 是一个功能强大的工具包，它集成了众多密码算法及实用工具。我们可以利用它提供的命令台工具生成密钥、证书来加密解密文件，也可以在利用其提供的 API 接口在代码中对传输信息进行加密。
Openssl 提供了秘钥证书管理、消息摘要生成、对称加密和非对称加密等，如下是常用的命令，详细使用方法见附录
简单实现的例子:
生成 RSA 私钥并查看。
查看一下生成的密钥的 n、e、d 值。
私钥的定义参考。
根据私钥生成公钥并查看(PEM 格式)。
公钥加密文件。
私钥解密文件。
3. 实验内容
实验内容
利用工具软件实现简化版的RSA的加解密过程。
用C/C++/Python实现32位RSA密码的加解密算法，为简化代码量，可利用RSATool生成 p、q、e、d。
* 加分项:
(1) 代码实现大素数的生成过程，可以随机一个大的正奇数，然后用 Miller-Rabin 素性测试判断其是否为素数;
(2) 代码实现正整数 e 的生成;
(3) 代码实现模反元素 d 的计算;
个人独立完成，撰写实验报告(包含实验思路，实验结果截图等)，并提交源代码，不得抄袭。 代码运行请打印出每一步的结果，包含选取的大素数 p 和 q，n，正整数 e，公钥和私钥，明文，密文。要求输入自定义明文，加密得到密文，解密再得到原明文。
4. 附录
附录
实验链接：https://developer.aliyun.com/adc/scenario/e6bd64f7205344b5bb7a80c4b5a04f10
