[CQOI2016]密钥破解 题解

[CQOI2016]密钥破解 题解

题目地址:洛谷:【P4358】[CQOI2016]密钥破解 – 洛谷、BZOJ:Problem 4522. — [Cqoi2016]密钥破解

题目描述

一种非对称加密算法的密钥生成过程如下:

  1. 任选两个不同的质数p,q
  2. 计算N=pq,r=(p−1)(q−1)
  3. 选取小于r,且与r互质的整数e
  4. 计算整数d,使得ed \equiv 1 \pmod{r}
  5. 二元组(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;
}


发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据