RSA简介

明文 MM，密文 CC。

n>Mn>M，且 nn 为两个不相同大质数的乘积 n=pqn=pq，1<e<φ(n)1<e<\varphi(n) 与 φ(n)\varphi(n) 互素，ed≡1(modφ(n))ed\equiv1\pmod{\varphi(n)}。

公钥 n,en,e，私钥 dd，利用分解大质因数的困难来保证数据安全。

加密 C=Me mod nC= M^e\bmod n。

解密 M=Cd mod nM= C^d\bmod n。

证明解密的正确性

当 gcd⁡(M,n)=1\gcd(M,n)=1，由扩展欧拉定理 Cd≡Med≡Med  mod  φ(n)≡M(modn)C^d\equiv M^{ed}\equiv M^{ed\ \bmod\ \varphi(n)}\equiv M\pmod n。

当 gcd⁡(M,n)≠1\gcd(M,n)\neq 1，p∣Mp\mid M 或 q∣Mq\mid M，不妨设 M=kpM=kp。根据费马小定理有 (kp)q−1≡1(modq)(kp)^{q-1}\equiv 1\pmod q。设非负整数 rr 满足 ed=rφ(n)+1ed=r\varphi(n)+1。显然有 [(kp)q−1]r(p−1)≡1(modq)[(kp)^{q-1}]^{r(p-1)}\equiv1\pmod q，即 (kp)r(p−1)(q−1)≡1(modq)(kp)^{r(p-1)(q-1)}\equiv1\pmod q。根据积性函数的性质，φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)，故 (kp)rφ(n)≡(kp)ed−1≡1(modq)(kp)^{r\varphi(n)}\equiv (kp)^{ed-1}\equiv 1\pmod q，两边同时乘 kpkp，有 (kp)ed≡kp(modq)(kp)^{ed}\equiv kp\pmod q；可以写成 (kp)ed=sq+kp(kp)^{ed}=sq+kp，s∈Ns\in\mathbb N。容易得到 p(kedped−1−k)=sqp(k^{ed}p^{ed-1}-k)=sq，所以 p∣sp\mid s，不妨令 s=tps=tp，t∈Nt\in\mathbb N。于是有 (kp)ed=tpq+kp(kp)^{ed}=tpq+kp，即 (kp)ed=kp+tn(kp)^{ed}=kp+tn；将 M=kpM=kp 代入得到 Med=M+tnM^{ed}=M+tn，显然有 Med≡M(modn)M^{ed}\equiv M\pmod n。解密时，Cd≡Med≡M(modn)C^d\equiv M^{ed}\equiv M\pmod n。

证毕。

解码思路

输入 nn，用 Pollard-Rho 算法分解质因数 p,qp,q，算法导论给出的期望时间复杂度是 O(min⁡(p,q))O(\sqrt{\min(p,q)})，接着计算 φ(n)=(p−1)(q−1)\varphi(n)=(p-1)(q-1)。输入 ee，用扩展欧几里得算法解线性同余方程 ed≡1(modφ(n))ed\equiv 1\pmod{\varphi(n)}，时间复杂度 O(log⁡φ(n))O(\log \varphi(n))。输入 CC，用快速幂 O(log⁡d)O(\log d) 得到 MM。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef __int128 bll;
vector<ll>primeFactor;
ll QuickPower(ll a, ll b, ll MOD)
{
	a %= MOD;
	ll res = 1 % MOD;
	while (b)
	{
		if (b & 1)
		{
			res = (bll)res * (bll)a % MOD;
		}
		b >>= 1;
		a = (bll)a * (bll)a % MOD;
	}
	return res;
}
bool MillerRabin(ll n, int repeat)
{
	if (n == 2 || n == 3)
	{
		return true;
	}
	else if (n % 2 == 0 || n == 1)
	{
		return false;
	}
	// 将n-1分解成2^s*d
	ll d = n - 1;
	int s = 0;
	while (!(d & 1))
	{
		++s;
		d >>= 1;
	}
	while (repeat--)
	{
		// 取随机数[2,n-2]
		ll a = rand() % (n - 3) + 2;
		ll x = QuickPower(a, d, n);
		ll y = 0;
		for (int i = 1;i <= s;i++)
		{
			y = (bll)x * (bll)x % n;
			if (y == 1 && x != 1 && x != n - 1)
			{
				return false;
			}
			x = y;
		}
		if (y != 1)
		{
			return false;
		}
	}
	return true;
}
ll PollardRho(ll n, ll c)
{
	ll x = rand() % (n - 2) + 1;
	ll y = x, i = 1, k = 2;
	while (1)
	{
		++i;
		x = (bll)x * (bll)x % n + c + n;
		ll d = abs(__gcd(y - x, n));
		if (1 < d && d < n)
		{
			return d;
		}
		else if (y == x)
		{
			return n;
		}
		else if (i == k)
		{
			y = x;
			k <<= 1;
		}
	}
}
void FindPrimeFactor(ll n, ll c)
{
	if (n == 1)
	{
		return;
	}
	if (MillerRabin(n, 50))
	{
		primeFactor.emplace_back(n);
		return;
	}
	ll p = n;
	while (p >= n)
	{
		p = PollardRho(p, c--);
	}
	FindPrimeFactor(p, c);
	FindPrimeFactor(n / p, c);
}
void ExtendGCD(ll a, ll b, ll& x, ll& y)
{
	if (!b)
	{
		x = 1;
		y = 0;
		return;
	}
	ExtendGCD(b, a % b, x, y);
	ll temp = x;
	x = y;
	y = temp - a / b * y;
}
int main()
{
	ll n, e, C;
	cin >> n >> e >> C;
	// 分解质因子
	FindPrimeFactor(n, 107);
	ll p = primeFactor.front();
	ll q = primeFactor.back();
	// 计算欧拉函数值
	ll phi = (p - 1) * (q - 1);
	ll x = 0, y = 0;
	// 求逆元
	ExtendGCD(e, phi, x, y);
	ll d = (x % phi + phi) % phi;
	// 解密
	ll M = QuickPower(C, d, n);
	cout << M << endl;
	return 0;
}

样例

输入1

1
7081 1789 5192

输出1

1
1615

输入2

1
7081 1789 2604

输出2

1
2823

输入3

1
7081 1789 4222

输出3

1
1130

用中国剩余定理优化

解密时 M=Cd mod nM=C^d\bmod n，若 nn 是很大的数，会爆long long，可用中国剩余定理优化。

令 M1=Cd mod pM_1=C^d\bmod p，M2=Cd mod qM_2=C^d\bmod q，注意求 M1M_1 和 M2M_2 时用扩展欧拉定理降幂。有线性同余方程组 $\left\{\begin{matrix}x\equiv M_1\pmod p\\x\equiv M_2\pmod q\end{matrix}\right.$，由于p⊥qp\bot q，xx 必有解。设 pp 模 qq 的逆元为 p′p'，qq 模 pp 的逆元为 q′q'，根据中国剩余定理，其解集为 $\{x|k\in\mathbb Z, x=M_1q'q+M_2pp'+kn\}$；其中 CdC^d 也是一个解，设 Cd=M1q′q+M2pp′+k∗nC^d=M_1q'q+M_2pp'+k^\ast n，则 M=Cd mod n=(M1q′q+M2pp′) mod nM=C^d\bmod n=(M_1q'q+M_2pp')\bmod n。