RSA是1977年由罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）一起提出的。当时他们三人都在麻省理工学院工作。RSA就是他们三人姓氏开头字母拼在一起组成的 [1] 。
RSA是被研究得最广泛的公钥算法，从提出到现在已近三十年，经历了各种攻击的考验，逐渐为人们接受，普遍认为是目前最优秀的公钥方案之一。1983年麻省理工学院在美国为RSA算法申请了专利。
RSA是一种非对称加密算法，关于对称加密和非对称加密可以看另一篇文章介绍：
所谓非对称加密：
- 非对称的是信息传递双方的【加解密信息】
- 需要保护的是【解密信息】
- 可以公开的是【加密信息】
RSA算法过程
1）N = P * Q
准备2个很大的质数P和Q，P、Q相乘得到N。
2）Φ(N) = (P – 1) * (Q – 1)
求出N的欧拉函数Φ(N)
3）选择 e 与 Φ(N) 互质即可
随机选取e，使1 < e < Φ(N)
4）e * d ≡ 1 (mod Φ(N)）
d是e在Φ(N)意义下的逆元
(e * d) mod Φ(N) = 1, 1 < d < Φ(N) ，
已知e和Φ(N)的情况下，用扩展欧几里得算法求d
5）【加密钥匙】：(e, N)
加密过程：求“E次方的mod N”
Me % N = C
设被加密的数为M，M为小于N的非负整数，C为密文
6）【解密钥匙】：(d, N)
解密过程：求“D次方的mod N”
Cd % N = M
解密证明：
当M与N互质时：
Cd % N = Me*d % N
= Mk*Φ(N)+1 % N （e * d mod Φ(N) = 1）
= Mk*Φ(N) * M % N
= M % N (欧拉公式)
= M
RSA算法实现
密钥生成代码示例：
/*************************************************************************
> File Name: RSA算法 生成密钥对
https://hitris.club/?p=359
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
#define MAX_N 50000 // 求50000以内的质数
// prime[0]: 素数的数量 = n
// prime[i]: i ∈ [1, n]时 表示第i个素数的值
long long prime[MAX_N + 5] = {0};
// 线性筛初始化质数表
void init_prime() {
for (long long i = 2; i <= MAX_N; i++) {
if (!prime[i]) { // 当前为素数 没有被标记为1
prime[++prime[0]] = i;
}
for (long long j = 1; j <= prime[0]; j++) {
if (i * prime[j] > MAX_N) break;
prime[i * prime[j]] = 1; // 将prime[合数] 标记为1
if (i % prime[j] == 0) break;
}
}
return ;
}
long long gcd(long long a, long long b) {
if (b) return gcd(b, a % b);
return a;
}
long long get_inv(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
long long r = get_inv(b, a % b, y, x);
// x = y
// y = x - k * y
y -= (a / b) * x;
return r;
}
int main() {
srand(time(0));
init_prime();
cout << MAX_N << "以内的素数总数 = " << prime[0] << endl;
cout << "最后一个素数 = " << prime[prime[0]] << endl;
long long p, q, p_ind, q_ind;
do {
p_ind = prime[0] - rand() % 100;
q_ind = prime[0] - rand() % 100;
} while (p_ind == q_ind); // 找到2个大质数的下标
p = prime[p_ind];
q = prime[q_ind];
long long n = p * q, phi_n = (p - 1) * (q - 1);
long long e, d, y;
do {
e = rand() % phi_n; // 随机选取 e ∈ (1, phi_n)
} while (e == 0 || gcd(e, phi_n) != 1); // e 和 phi_n 互质
get_inv(e, phi_n, d, y); // 扩展欧几里得算法求d
d = (((d % phi_n) + phi_n) % phi_n);
assert(e * d % phi_n == 1);
cout << "phi_n = " << phi_n << endl;
cout << "加密密钥 e = " << e << " n = " << n << endl;
cout << "解密密钥 d = " << d << " n = " << n << endl;
cout << "验证：" << e << " * " << d << " % " << phi_n << " = " << e * d % phi_n << endl;
return 0;
} 密钥使用代码示例：
/*************************************************************************
> File Name: 使用rsa生成的密钥进行加解密
************************************************************************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;
long long e, d, n;
long long quick_mod(long long a, long long b, long long c) {
long long ans = 1, temp = a;
while (b) {
if (b & 1) ans = ans * temp % c;
temp = temp * temp % c;
b >>= 1;
}
return ans;
}
int main(int argc, char *argv[]) {
sscanf(argv[1], "%lld", &e);
sscanf(argv[2], "%lld", &n);
sscanf(argv[3], "%lld", &d);
long long m, c;
while (cin >> m) {
c = quick_mod(m, e, n);
cout << m << "^" << e << " % " << n << " = " << c << endl;
cout << c << "^" << d << " % " << n << " = " << quick_mod(c, d, n) << endl;
}
return 0;
}