NKOJ 3614(CQOI 2016) 密钥破解（Pollard Rho）

发表于 |
字数统计: 791字 | 阅读时长 ≈ 4min

P3614【CQOI2016 Day2】密钥破解

问题描述

一种非对称加密算法的密钥生成过程如下：
        1.任选两个不同的质数p,q；
        2.计算N=pq，r=(p-1)(q-1)；
        3.选取小于r，且与r互质的整数e；
        4.计算整数d，使得ed≡1 mod r；
        5.二元组(N,e)称为公钥，二元组(N,d)称为私钥。

当需要加密消息n时（假设n是一个小于N的整数，因为任何格式的消息都可以转为整数表示），使用公钥(N,e)，按照
ne≡c mod N
运算，可以得到密文c。
对密文解密时，用私钥(N,d)，按照
cd≡n mod N
运算，可以得到原文n。算法正确性证明省略。
由于公钥加密的密文仅能用对应的私钥解密，而不能用公钥解密，因此称为非对称加密算法。通常情况下，公钥有消息的接收方公开，而私钥由消息的接收方自己持有。这样任何发消息的人都可以用公钥对消息加密，而只有消息的接收方自己能够解密消息。
现在，你的任务是寻找一种可行的方法来破解这种加密算法，即根据公钥破接出私钥，并据此解密密文。

输入格式

输入文件内容只有一行，为空格分隔的3个正整数e,N,c。

输出格式

输出文件内容只有一行，为空格分隔的2个整数d,n。

样例输入

3 187 45

样例输出

107 12

提示

样例解释：
    样例中p=11，q=17。

数据范围：
对于30%的测试数据，N≤$10^6$；
对于50%的测试数据，N≤$10^{14}$；
对于100%的测试数据，N≤$2^{62}$；

此题需要

  1. Pollard Rho算法
  2. 快速幂
  3. 快速乘
  4. 求逆元

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	ll x1,y1,r;
	if(b==0){x=1;y=0;return a;}
	r=exgcd(b,a%b,x1,y1);
	x=y1;y=x1-a/b*y1;
	return r;
}
ll gcd(ll a,ll b)
{return b==0?a:gcd(b,a%b);}
ll QC(ll a,ll b,ll c)
{
	ll ans=0;a%=c;
	while(b)
	{
		if(b&1)ans=(ans+a)%c;
		b>>=1;
		a=(a+a)%c;
	}
	return ans;
}
ll QM(ll a,ll b,ll c)
{
	ll ans=1;a%=c;
	while(b)
	{
		if(b&1)ans=QC(ans,a,c);
		b>>=1;
		a=QC(a,a,c);
	}
	return ans;
}
void P_RHO(ll x,ll &p,ll &q)
{
	ll a=1,y1,y2,t;
	while(1)
	{
		y1=y2=rand()%x;y1=(QC(y1,y1,x)+a)%x;
		while(1)
		{
			if(y1==y2)break;
			t=gcd(y1>y2?y1-y2:y2-y1,x);
			if(t!=1){p=t;q=x/t;return;}
			y2=(QC(y2,y2,x)+a)%x;
			y1=(QC(y1,y1,x)+a)%x;
			y1=(QC(y1,y1,x)+a)%x;
		}
		a++;
	}
}
int main()
{
	ll e,N,c,p,q,d,n,r,t,m;
	scanf("%lld%lld%lld",&e,&N,&c);
	P_RHO(N,p,q);
	r=(p-1)*(q-1);
	t=exgcd(e,r,d,m);
	d=(d%r+r)%r;
	n=QM(c,d,N);
	cout<<d<<" "<<n;
}