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.
解：由题意可知：
c1=M^e1 mod N
c2=M^e2 mod N
计算得知：gcd(e1,e2)=1 即e1与e2 互质
则由扩展欧几里得算法可知：e1r+e2s=1(存在 r,s且 r>0,s<0)
c2^s= c2^(-1(-s)) ; c2 c2^(-1)=1 mod N
再由扩展欧几里得算出: c2^(-1)
因此：(c1^r * c2^(-1(-s) ) mod N
=(c1^r * c2^s) mod N
= ((M^e1 mod N)^r * (M^e2 mod N)^s) mod N
=(M^(e1r) * M^(e2s)）mod N
=(M^(e1r+e2*s)) mod N
=M mod N
即可求出原文M
代码如下：

#include<iostream>
#include"string.h"
using namespace std;

typedef long long int lli;

lli gcd(lli e1,lli e2)
{
    if(e1%e2==0) return e2;
    return gcd(e2,e1%e2);
}

void exgcd(lli e1,lli e2,lli g,lli &s,lli &t)  //用扩展欧几里得算法求s,t,g=gcd(e1,e2)
{
    lli q,r=-1;
    lli x,y;
    lli x0=1;
    lli x1=0;
    lli y0=0;
    lli y1=1;
    lli a=e1;
    lli b=e2;
    while(r!=g)
    {
        r=a%b;
        q=a/b;
        x=x0-q*x1;   //迭代求x,y
        x0=x1;
        x1=x;
        y=y0-q*y1;
        y0=y1;
        y1=y;
        a=b;
        b=r;
    }
    s=x;
    t=y;
}

int transmit(lli r,char *exp)    //将r转换成二进制保存在字符数组exp中
{
    int i=0;
    while(r!=0)
    {
      exp[i++]=r%2+'0';
      r=r/2;
    }
    return i;
}

lli mul_mod(lli c,char *exp,lli n,int length)   //求c^exp mod n的值，length为exp的长度，即转换后的二进制串的长度
{
    lli x=1;
   for(int i=length-1;i>=0;i--)
   {
       x=x*x;
       x=x%n;
       if(exp[i]=='1')
       {
           x=x*c;
           x=x%n;
       }
   }
   return x;
}

int main()
{
    lli e1=1021763679;
    lli e2=519424709;
    lli c1=1244183534;
    lli c2=732959706;
    lli n=1889570071;
    lli r,s,ic2,q;
    lli x,y,m;
    int length;
    char exp[64];
    memset(exp,0,sizeof(exp));
    lli temp=gcd(e1,e2);
    exgcd(e1,e2,temp,r,s);    //求r,s
    exgcd(n,c2,1,q,ic2);        //求c2在mod n乘法下的逆元ic2
    length=transmit(r,exp);
    x=mul_mod(c1,exp,n,length);
    length=transmit(-s,exp);       //s<0,-s>0
    y=mul_mod(ic2,exp,n,length);
    m=(x*y)%n;
    cout<<"result:"<<m<<endl;
}

result:1054592380