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.

分析：

RSA加密可得以下两条式子（M是明文）
C₁=M^e₁ mod N
C₂=M^e₂ mod N
由题目易知e_１和e₂互素，即
gcd(e₁,e₂)=1
由扩展欧几里得算法便可得出
e₁s+e₂t=1
假设t<0, s>0, 则有
C₁^s * (C₂^-1)^-t mod N
=C₁^s * C₂^t mod N
=M^e₁s * M^e₂t mod N
=M^e₁s+e₂t mod N
=M mod N
=M

结论：

1、由扩展欧几里得算法求出s, t.
2、在 mod N的条件下求出C₂^-1.
3、计算 C₁^s * (C₂^-1)^-t mod N, 结果即为明文M.

实现代码：

#include <iostream>
#include<gmp.h>
#include<gmpxx.h>
using namespace std;

//a*b mod c
mpz_class Mul(mpz_class a,mpz_class b,mpz_class c)
{
    mpz_class temp=0;
    while(b!=0)
    {
        if(b%2==1)
        {
            --b;
            temp=(temp+a)%c;
        }
        b/=2;
        a=(a+a)%c;
    }
    return temp;
}

// a^b mod c
mpz_class Pow(mpz_class a,mpz_class b,mpz_class c)
{
    mpz_class temp=1;
    while(b!=0)
    {
        if(b%2==1)
        {
            temp=Mul(temp,a,c);
        }
        b /=2;
        a=Mul(a,a,c);
    }
    return temp;
}

//a*s+b*t=gcd(a,b)=1 (a>b)
void exGcd(mpz_class a, mpz_class b,mpz_class &s,mpz_class &t)
{
    mpz_class temp;
    mpz_class q,r,x1=1,x2=0,y1=0,y2=1;
    mpz_class tmp_a=a;
    mpz_class tmp_b=b;
    while((r=tmp_a%tmp_b)!=0)
    {
        q=tmp_a/tmp_b;
        temp=x2;
        x2=x1-q*x2;
        x1=temp;
        temp=y2;
        y2=y1-q*y2;
        y1=temp;
        tmp_a=tmp_b;
        tmp_b=r;
    }
    s=x2;
    t=y2;
}

int main()
{
    mpz_class e1=1021763679;
    mpz_class e2=519424709;
    mpz_class c1=1244183534;
    mpz_class c2=732959706;
    mpz_class n=1889570071;

    mpz_class s,t;
    exGcd(e1,e2,s,t);
    if(s<0)
    {
        s=-s;
        mpz_invert(c1.get_mpz_t(),c1.get_mpz_t(),n.get_mpz_t());
    }
    if(t<0)
    {
        t=-t;
        mpz_invert(c2.get_mpz_t(),c2.get_mpz_t(),n.get_mpz_t());
    }
    cout<<"the result is "<<Mul(Pow(c1,s,n),Pow(c2,t,n),n)<<endl;

    return 0;
}

结果：

the result is 1054592380