RSA(第十届蓝桥杯省赛C++A组E题) 解题报告 Apare_xzc_rsa加密算法蛮力法c++

RSA(第十届蓝桥杯省赛C++A组E题) 解题报告

xzc 2019/4/4 (边看World Final B站直播边写的)

---

题目链接

---

题面:(开始码字)

  RSA是一种经典的加密算法。它的基本加密过程如下。

  首先生成两个大质数p,q, 令n = p*q,设d与(p-1)*(q-1)互质，则可以找到e,使得d*e除以(p-1)*(q-1)的余数为1

  n,d,e组成了私钥，n,d构成了公钥。

  当使用公钥加密一个整数X时(X<=n-1)，计算C = X^d mod n，则C是加密后的密文。

  当收到密文C时，可以使用私钥解开，计算公式为：X = C^e mod n。

  例如：当p = 5, q = 11, n = 55, e = 27。

  若加密数字24,得24^3 % 55 = 19。

  解密数字19，得19^27 % 55 = 24。

  现在你知道公钥中n = 1001733993063167141,d = 212353,同时，你截获了别人发送的密文C = 20190324,请问，原文是多少？

码字码得好累啊~

---

题意：
  给一个n,分解质因数成p*q, 然后计算d关于(p-1)*(q-1)的逆元，结果为e,
求C^e % n的结果
  n = 1001733993063167141
  d = 212353
  c = 20190324

---

解题过程：

1. 我们肯定要把n分解质因数，我首先想到了欧拉筛素数，然后晒了一发1E8以内的素数，想用这些素数去分解n

//筛素数
const int maxn = 1e8+10;
int a[maxn];
int sushu[maxn/10];
bool notPrime[maxn]; ///筛素数分解不出来，目测是9位数*10位数 
int cnt;
void getPrime(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!notPrime[i]) sushu[cnt++] = i;
		for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
		{
			notPrime[i*sushu[j]] = true;
			if(i%sushu[j]==0) break; 
		} 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

然后分解质因数：

//#define LL long long
void fenjie(LL x)
{
	cout<<x<<" = 1";
	for(int i=0;i<cnt&&sushu[i]<=x/sushu[i];++i)
	{
		while(x%sushu[i]==0)
		{
			cout<<" * "<<sushu[i];
			x /= sushu[i];
		}
	}
	if(x>1) cout<<" * "<<x;
	cout<<endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

结果是这样的：1001733993063167141 = 1 * 1001733993063167141
显然没分解出来，就是说p和q都是大于1E8的大质数
欧拉筛筛不出来，我又不会杜教筛，所以还是暴力吧

void BF(LL x) //蛮力法
{
	cout<<x<<" = "; 
	for(LL i=1e8+1;i<x;i+=2)
	{
		if(x%i==0)
			cout<<i<<" * ",x/=i;
	}
	cout<<x<<endl;
}
1
2
3
4
5
6
7
8
9
10

结果：

1001733993063167141 = 891234941 * 1123984201
1

好了，现在我们知道了：
p = 891234941
q = 1123984201
这种题，暴力也用不了10s,以后还是写暴力吧…

LL y = (p-1)*(q-1); //y = 1001733991047948000
1

接下来我们来求逆元：
因为这个mod = y = 1001733991047948000,它不是个质数
我们要求：
d(212353)关于y(1001733991047948000)的乘法逆元

• 法一：求y的欧拉函数k = euler(y), rev = d^(k-1)%mod
• 法二：用拓展欧几里得算法：exgcd复习<-戳这里

我用的exgcd:

//#define LL long long
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(b==0)
	{
		d = a; x = 1; y = 0; return;
	}
	exgcd(b,a%b,d,y,x);
	y -= (a/b)*x;
}
LL rev(LL t,LL m)
{
	LL d,x,y;
	exgcd(t,m,d,x,y);
	return (x%m+m)%m;
}
LL e = rev(d,y); //e = 823816093931522017
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

然后，我们求c^e%mod
c = 20190324
e = 823816093931522017
mod = 1001733993063167141
注意：
由于这里的mod>1e18太大，快速幂相乘的时候会爆long long的!
这个时候，我们就要用到快速乘

LL fast_product(LL a,LL b,LL mod)//快速乘
{
	LL ans = 0;
	while(b)
	{
		if(b&1) ans = (ans+a)%mod;
		a = (a+a)%mod;
		b>>=1;
	}
	return ans;
} 
1
2
3
4
5
6
7
8
9
10
11

然后，我们用快速乘来写快速幂

LL fast_pow(LL a,LL b,LL mod)//快速幂
{
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = fast_product(ans,a,mod);
		a = fast_product(a,a,mod);
		b>>=1;		
	} 
	return ans;
}

1
2
3
4
5
6
7
8
9
10
11
12

最后答案为：579706994112328949

---

附上完整代码：

///Author: xzc
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e8+10;
const LL n = 1001733993063167141ll;
const LL p = 891234941ll;
const LL q = 1123984201ll;
const LL d = 212353;
const LL c = 20190324;
int a[maxn];
int sushu[maxn/10];
bool notPrime[maxn]; ///筛素数分解不出来，目测是9位数*10位数 
int cnt;
void getPrime(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!notPrime[i]) sushu[cnt++] = i;
		for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
		{
			notPrime[i*sushu[j]] = true;
			if(i%sushu[j]==0) break; 
		} 
	}
	for(int i=0;i<20;++i) cout<<sushu[i]<<" ";cout<<endl;
}
void fenjie(LL x)
{
	cout<<x<<" = 1";
	for(int i=0;i<cnt&&sushu[i]<=x/sushu[i];++i)
	{
		while(x%sushu[i]==0)
		{
			cout<<" * "<<sushu[i];
			x /= sushu[i];
		}
	}
	if(x>1) cout<<" * "<<x;
	cout<<endl;
}
void BF(LL x)
{
	cout<<x<<" = "; 
	for(LL i=1e8+1;i<x;i+=2)
	{
		if(x%i==0)
			cout<<i<<" * ",x/=i;
	}
	cout<<x<<endl;
}
void exgcd(LL a,LL b,LL &d,LL &x,LL &y)
{
	if(b==0)
	{
		d = a; x = 1; y = 0; return;
	}
	exgcd(b,a%b,d,y,x);
	y -= (a/b)*x;
}
LL rev(LL t,LL m)
{
	LL d,x,y;
	exgcd(t,m,d,x,y);
	return (x%m+m)%m;
}
LL fast_product(LL a,LL b,LL mod)
{
	LL ans = 0;
	while(b)
	{
		if(b&1) ans = (ans+a)%mod;
		a = (a+a)%mod;
		b>>=1;
	}
	return ans;
} 
LL fast_pow(LL a,LL b,LL mod)
{
	LL ans = 1;
	while(b)
	{
		if(b&1) ans = fast_product(ans,a,mod);
		a = fast_product(a,a,mod);
		b>>=1;		
	} 
	return ans;
}
int main()
{
	//getPrime(maxn-5);
	//fenjie(n);
	BF(n);
	LL y = (p-1)*(q-1);
	LL e = rev(d,y);
	LL answer = fast_pow(c,e,n);
	cout<<answer<<endl;

	return 0;
}
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

---

后记: 大数分解质因数还是很难的，18位的大数暴力分解了出来，位数再多一点儿，没有私钥，是很难解码的~

---