题目描述
C++中数据的类型与长度参考：
因此，C++最大能支持的十进制是19位的整数。如果要支持更大的整数，需要实现Big Number类。RSA目前比较安全的密钥长度是2048位二进制，即是617位的十进制。因此，C++自带的数据类型无法实现安全的RSA密钥加解密。
为了降低难度，该题不要求实现大数支持，因此只使用C++自带的long long 数据类型。
该实验主要包含三部分：1. 公私钥的生成。在公私钥生成中，有p、q、e三个参数是随机选择的，其中p、q要求是质数，因此需要实现一个函数检查一个整数是否是质数。由p、q的乘积可以得到n：n=p*q，以及n的欧拉函数: φ(n) = (p-1)*(q-1)。e是在(1, φ(n))之间随机选取的整数，需要满足gcd(e, φ(n)) = 1，因此，需要通过扩展欧几里得算法验证取得的e是与φ(n)互质的。d可以通过扩展欧几里得算法求得 。以满足，即。
公钥为（n, e）,私钥为（n,d）
检查一个整数是否为质数-Rabin-Miller算法，请参考：Miller-Rabin素性测试算法详解_Nicetomeetu-的博客-CSDN博客_millerrabin素数测试算法或Miller Rabin算法详解 – 自为风月马前卒 – 博客园或BZOJ3667: Rabin-Miller算法 – 自为风月马前卒 – 博客园
扩展欧几里得算法：请参考：【算法学习】扩展欧几里得算法详解及C++代码实现_行仔ovo的博客-CSDN博客_欧几里得算法c++
2. 加密过程，使用加密算法c = m^e mod n，计算出密文c；
3.解密过程，使用私钥d和解密算法m = c^d mod n, ，计算m；
加密和解密过程需要做幂运算取余，如果直接先做幂运算再取余，则很容易出现溢出，因此，我们需要采用快速幂运算取余算法，请参考：https://jlice.top/p/7tbs7/
因此，该次实验主要难点在于以下三个算法的理解与实现：
1. Rabin-Miller算法
2. 扩展欧几里得算法
3. 快速幂取余算法
根据前面的算法，我们知道明文和密文都不能大于n，假设n的长度为L，对于明文，我们需要按照L-1的长度对其分组然后再加密，每组的密文长度L。解密的时候使用L的长度对其进行分组然后解密，每组的明文长度为L-1。分组按照整数从低到高（即从右往左）
输入
第一行是p
第二行是q
第三行是e
第四行是待加密数据
第五行是待解密数据
输出
第一行输出p是否是质数
第二行输出q是否是质数
第三行打印n
第四行打印d
第五行显示输入第四行的加密结果
第六行显示输入第五行的解密结果
输入样例1
67
43
13
281
2154
输出样例1
Yes
Yes
2881
853
325
54
AC代码
#include<iostream>
#include<cmath>
using namespace std;
typedef long long ll;ll mod_mul(ll a, ll b, ll mod)
{ll res = 0;while (b){if (b & 1)res = (res + a) % mod;a = (a + a) % mod;b >>= 1;}return res;
}ll mod_pow(ll a, ll n, ll mod)
{ll res = 1;while (n){if (n & 1)res = mod_mul(res, a, mod);a = mod_mul(a, a, mod);n >>= 1;}return res;
}// Miller-Rabin随机算法检测n是否为素数
bool Miller_Rabin(ll n)
{if (n == 2)return true;if (n < 2 || !(n & 1))return false;ll m = n - 1, k = 0;while (!(m & 1)){k++;m >>= 1;}for (int i = 1; i <= 20; i++) // 20为Miller-Rabin测试的迭代次数{ll a = rand() % (n - 1) + 1;ll x = mod_pow(a, m, n);ll y;for (int j = 1; j <= k; j++){y = mod_mul(x, x, n);if (y == 1 && x != 1 && x != n - 1)return false;x = y;}if (y != 1)return false;}return true;
}//扩展欧几里得算法
void extend_gcd(long long a, long long b, long long& x, long long& y) {if (b == 0) {x = 1, y = 0;return;}extend_gcd(b, a % b, x, y);long long tmp = x;x = y;y = tmp - (a / b) * y;
}
long long getInv(long long a, long long mod) {long long x, y;extend_gcd(a, mod, x, y);while (x < 0) {x = x + mod;}return x;
}//快速幂运算取余算法
ll qiumi(ll a, ll b, ll m)
{int r = 1 % m;while (b){if (b & 1)r= r * a % m;a = a * a % m;b >>= 1;}return r;
}ll jiami(ll m,ll e,ll n)
{int len_n = 0, len_m = 0, t;//计算n的长度t = n;while (t){t = t / 10;len_n++;}//计算明文的长度t = m;while (t){t = t / 10;len_m++;}ll ans = 0;if (len_m > len_n) {ll right =0, left = 0;int t = pow(10, len_n - 1);right = m % t; //分组left = (m - right)/t;right = qiumi(right, e, n); //分组加密left = qiumi(left, e, n);ans = left * pow(10, len_n) + right;}else{ans = qiumi(m, e, n);}return ans;
}ll jiemi(ll c, ll d, ll n)
{int len_n = 0, len_c = 0, t;//计算n的长度t = n;while (t){t = t / 10;len_n++;}//计算密文的长度t = c;while (t){t = t / 10;len_c++;}ll ans = 0;if (len_c > len_n){ll right = 0, left = 0;int t = pow(10, len_n);right = c % t; //分组left = (c - right)/t;right = qiumi(right, d, n); //分组解密left = qiumi(left, d, n);ans = left * pow(10, len_n-1) + right;}else{ans = qiumi(c, d, n);}return ans;
}int main()
{ll p, q, e, n, m, c, fn, d, m1, c1;;cin >> p >> q >> e >> m >> c;//判断p、q是否为质数if (Miller_Rabin(p))cout << "Yes" << endl;if (Miller_Rabin(q))cout << "Yes" << endl;//计算n和fn；if (Miller_Rabin(p) && Miller_Rabin(q)){n = p * q;fn = (p - 1) * (q - 1);}cout << n << endl;//用扩展欧几里得算法求dd = getInv(e, fn);cout << d << endl;//加密c1 = jiami(m, e, n);cout << c1 << endl;//解密m1 = jiemi(c, d, n);cout << m1 << endl;return 0;
}