简单RSA破解

问题描述

Alice decides to use RSA with the public key N = 1889570071. In order to guard against transmission errors, Alice has Bob encrypt his message twice, once using the encryption exponent e1 = 1021763679 and once using the encryption exponent e2 = 519424709. Eve intercepts the two encrypted messages
c1 = 1244183534 and c2 = 732959706. Assuming that Eve also knows N and the two encryption exponents e1 and e2. Please help Eve recover Bob’s plaintext without finding a factorization of N.

分析

Alice 给 Bob发送的密文是用两个不同密钥e₁、e₂加密两次得到的。即如图：

易知：

其中：

可以用扩展欧几里得算法解得u、v，故有:

如果gcd（e₁, e₂）刚好等于1，那么Eve就破解了密码。

实现

#include <iostream>
#include <gmp.h>
#include <gmpxx.h>

using namespace std;

//扩展欧几里得算法求u、v
mpz_class gcdEx (mpz_class a, mpz_class b, mpz_class &u, mpz_class &v)
{
    if(b==0)
    {
        u = 1, v = 0;
        return a;
    }
    else
    {
        mpz_class r = gcdEx(b, a % b, u, v); /* r = GCD(a, b) = GCD(b, a%b) */
        mpz_class t = u;
        u = v;
        v = t - a/b * v;
        return r;
    }
}

//快速幂取模
mpz_class fast_exp (mpz_class a, mpz_class b, mpz_class c)
{
    mpz_class ans=1;   //记录结果
    a=a%c;   //预处理，使得a处于c的数据范围之下
    while(b!=0)
    {
        if(b % 2 != 0) ans = (ans * a) % c;   //如果该位是1，那么a是需要乘进结果的
        b>>=1;    //移位操作，其实就是遍历b的每一位
        a = (a * a) % c;   //不断的加倍
    }
    return ans;
}

//快速乘取模
mpz_class F_mul(mpz_class a, mpz_class b, mpz_class c) {
    mpz_class ans = 0;
    a %= c;
    while (b != 0) {
        if (b % 2 != 0) ans = (ans + a) % c;
        a = (a + a) % c;
        b >>= 1;
    }
    return ans;
}


int main ()
{
    mpz_class N("1889570071", 10);
    mpz_class e1("1021763679", 10);
    mpz_class e2("519424709", 10);
    mpz_class c[2];
    c[0].set_str("1244183534", 10);  c[1].set_str("732959706", 10);
    mpz_class s[2];
    mpz_class r = gcdEx (e1, e2, c[0], c[1]);
    mpz_class rev, x;
    int tn = 0;
    if (s[1] < 0) tn = 1;
    gcdEx(N, c[tn], x, rev);
    if (rev < 0) rev = (rev + N) % N;
    mpz_class res = F_mul(fast_exp(rev, -s[tn], N), fast_exp(c[!tn], s[!tn], N), N);
    cout << res << endl;
    return 0;
}

得到结果：1054592380