洛谷P5451 密码学第三次小作业

传送门

题目背景

1977年，罗纳德·李维斯特（Ron Rivest）、阿迪·萨莫尔（Adi Shamir）和伦纳德·阿德曼（Leonard Adleman）提出了RSA 加密算法。RSA 加密算法是一种非对称加密算法，其可靠性由极大整数因数分解的难度决定。换言之，对一极大整数做因数分解愈困难，RSA 算法愈可靠。假如有人找到一种快速因数分解的算法的话，那么用 RSA 加密的信息的可靠性就肯定会极度下降。

RSA 的基本原理如下：

公钥与私钥的产生
随机选择两个不同大质数 pp 和 qq，计算 N=p\times qN=p×q
根据欧拉函数性质，求得 r=\varphi (N)=\varphi §\varphi (q)=(p-1)(q-1)r=φ(N)=φ§φ(q)=(p−1)(q−1)
选择一个小于 rr 的正整数 ee，使 ee 和 rr 互质。并求得 ee 关于 rr 的乘法逆元 dd，有 ed\equiv 1 \pmod red≡1(modr)
将 pp 和 qq 的记录销毁。此时，(N,e)(N,e) 是公钥，(N,d)(N,d) 是私钥。
消息加密：首先需要将消息 mm 以一个双方约定好的格式转化为一个小于 NN，且与 NN 互质的整数 nn。如果消息太长，可以将消息分为几段，这也就是我们所说的块加密，后对于每一部分利用如下公式加密：
n^{e}\equiv c\pmod N
n
e
≡c(modN)

消息解密：利用密钥 dd 进行解密
c^{d}\equiv n\pmod N
c
d
≡n(modN)

题目描述

现在有两个用户由于巧合，拥有了相同的模数 NN，但是私钥不同。设两个用户的公钥分别为 e_1e
1
​
和 e_2e
2
​
，且两者互质。明文消息为 mm，密文分别为：

c
1
​
=m
e
1
​

modN
c
2
​
=m
e
2
​

modN
​

现在，一个攻击者截获了 c_1c
1
​
，c_2c
2
​
，e_1e
1
​
，e_2e
2
​
，NN，请帮助他恢复出明文 mm 。

输入格式

输入包含多组数据，第一行一个整数 TT 表示数据组数，保证 1\le T\le 10^41≤T≤10
4
。接下来依次描述每组数据，对于每组数据：

一行包含五个正整数 c_1c
1
​
，c_2c
2
​
，e_1e
1
​
，e_2e
2
​
，NN，保证 2^{8}< N < 2^{63}2
8
63
，NN 有且仅有两个素因子，其余数据严格按照上述RSA算法生成。
输出格式
对于每组数据，输出 11 行：

一个非负整数 mm，请选手务必在输出时保证 0\le m

输入输出样例

输入 #1复制
1
1502992813 2511821915 653507 57809 2638352023
输出 #1复制
19260817

说明/提示

版权信息
来自 2018 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2018），感谢 Pony.ai 对此次比赛的支持。

上代码：

#include
#include
#define ll long long
#define Starseven main
using namespace std;
ll read();
void write(ll);
ll c1,c2,e1,e2,N;

ll Multi(ll a,ll b,ll p){
	ll re=0;
	while(b){
		if(b&1) re=(re+a)%p;
		b>>=1;
		a=(a*2)%p;
	}
	return re%p;
}

ll Get_exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;return a;
	}
	ll temp=Get_exgcd(b,a%b,x,y);
	ll t=x;x=y;y=t-a/b*y;
	return temp;
}

ll Power(ll a,ll b,ll p){
	ll re=1;
	while(b){
		if(b&1) re=Multi(re,a,p);
		b>>=1;
		a=Multi(a,a,p);
	}
	return re%p;
}

int Starseven(void){
	int t=read();
	while(t--){
		c1=read(),c2=read(),e1=read(),e2=read(),N=read();
		//cout<
		ll x,y;
		ll judge=Get_exgcd(e1,e2,x,y); 
		while(x<0){
			x+=e2,y-=e1;
		}
		ll a=Power(c1,x,N),b=Power(c2,-y,N); 
		ll f,g;
		ll hh=Get_exgcd(b,N,f,g);
		ll ans=Multi(f,a,N);
		ans=(ans+N)%N;
		write(ans);
		puts("");
	}
	return 0;
} 

ll read(){
	char ch=getchar();
	ll re=0,op=1;
	while(ch<'0'||ch>'9'){
		if(ch=='-') op=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		re=re*10+ch-'0';
		ch=getchar();
	}
	return re*op;
}

void write(ll x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return ;
}
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