[CQOI2016]密钥破解 题解
题目地址:洛谷:【P4358】[CQOI2016]密钥破解 – 洛谷、BZOJ:Problem 4522. — [Cqoi2016]密钥破解
题目描述
一种非对称加密算法的密钥生成过程如下:
- 任选两个不同的质数p,q
- 计算N=pq,r=(p−1)(q−1)
- 选取小于r,且与r互质的整数e
- 计算整数d,使得ed \equiv 1 \pmod{r}
- 二元组(N,e)称为公钥,二元组(N,d)称为私钥。
当需要加密消息n时,(假设n是一个小于N的整数,因为任何格式的消息都可转为整数表示),使用公钥(N,e),按照n^e \equiv c \pmod{N}运算,可得到密文c,对密文c解密时,用私钥(N,d),按照c^d \equiv n \pmod{N}运算,可得到原文n。算法正确性证明省略。
由于用公钥加密的密文仅能用对应的私钥解密,而不能用公钥解密,因此称为非对称加密算法。通常情况下,公钥由消息的接收方公开,而私钥由消息的接收方自己持有。这样任何发送消息的人都可以用公钥对消息加密,而只有消息的接收方自己能够解密消息。
现在,你的任务是寻找一种可行的方法来破解这种加密算法,即根据公钥破解出私钥,并据此解密密文。
输入输出格式
输入格式:
输入文件内容只有一行,为空格分隔的三个正整数e,N,c。
输出格式:
输出文件内容只有一行,为空格分隔的两个整数d,n。
输入输出样例
输入样例#1:
3 187 45
输出样例#1:
107 12
说明
对于30%的数据,e,N,c \leq 2^{20};
对于100%的数据,e,N,c \leq 2^{62}
题解
本题需要的数学姿势有:Miller-Rabin素性测试与Pollard’s rho算法 | KSkun’s Blog
我一看,N马上一个Pollard-Rho套上去分解因数。p和q都有了你还愁什么d,扩欧一发逆元就出来了。
这不是个板子裸题吗……
代码
// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <algorithm>
typedef long long LL;
inline LL myabs(LL x) {
return x < 0 ? -x : x;
}
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
inline LL mul(LL a, LL b, LL p) {
a %= p; b %= p;
LL res = 0;
while(b) {
if(b & 1) res += a;
if(res >= p) res %= p;
a <<= 1; b >>= 1;
if(a >= p) a %= p;
}
return res;
}
inline LL fpow(LL n, LL k, LL p) {
LL res = 1; n %= p;
for(; k; n = mul(n, n, p), k >>= 1) {
if(k & 1) res = mul(res, n, p);
}
return res;
}
inline LL gcd(LL a, LL b) {
if(a < b) std::swap(a, b);
if(!b) return a;
return gcd(b, a % b);
}
LL p, q;
inline LL pollard_rho(LL x, LL c) {
LL xi = 1ll * rand() * rand() % (x - 1) + 1, y = xi, i = 1, k = 2;
for(;;) {
i++;
xi = (mul(xi, xi, x) + c) % x;
LL g = gcd(myabs(y - xi) % x, x);
if(g > 1 && g < x) return g;
if(xi == y) return x;
if(i == k) {
y = xi;
k <<= 1;
}
}
return x;
}
inline LL exgcd(LL a, LL b, LL &x, LL &y) {
if(!b) {
x = 1; y = 0; return a;
}
LL res = exgcd(b, a % b, x, y);
LL t = x; x = y; y = t - a / b * y;
return res;
}
LL e, N, c;
int main() {
srand(time(NULL));
e = readint(); N = readint(); c = readint();
LL p = N;
while(p >= N) p = pollard_rho(N, 1ll * rand() * rand() % (N - 1) + 1);
LL r = (p - 1) * (N / p - 1);
LL d, y;
exgcd(e, r, d, y);
d = (d % r + r) % r;
LL n = fpow(c, d, N);
printf("%lld %lld", d, n);
return 0;
}