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.

解题过程

∵ C₁ ≡ M^e₁ mod N
 C₂ ≡ M^e₂ mod N
∵ gcd(e₁,e₂) = 1
∴ ∃ x , y ,
 st. e₁ * x + e₂ * y = 1
∴ C₁^x * C₂^y ≡ M^e₁x+e₂y mod N
∴ C₁^x * C₂^y ≡ M mod N
∵ x > 0 , y < 0
∴ C₁^x * C₂^y = C₁^x * (C₂^-1)^-y
  C₂^-1 即为 C₂ 在模N乘法的逆元
∴ M = [(C₁^x) mod n * (C₂^-1)^-y mod n] mod n
∴ M = 1054592380

代码

#include<iostream>
using namespace std;
bool EGCD(long long int a,long long int b,long long int &x,long long int &y)
{
    long long int q,r,x0,x1,x2,y0,y1,y2;
    x0=1;x1=0;y0=0;y1=1;
    while(b)
    {
        r=a%b;
        q=a/b;
        x2=x0-q*x1;
        y2=y0-q*y1;
        a=b;b=r;
        x0=x1;x1=x2;
        y0=y1;y1=y2;
    }
    x=x0;y=y0;
 } 
 long long quick_mul_mod(long long a,long long b,long long n)//(a*b)%n
{
    long long r=0;
    while(b>=1)
    {
        if(b%2==1)//b为奇数 
        {
            b-=1;
            r=(r+a)%n;
        }
        b/=2;
        a=(a+a)%n;//（（a%n）+（a%n））%n=（a+a）%n 
    }
    return r;
}
 long long quick_power_mod(long long a,long long b,long long n)//(a^b)%n
{  
    long long r=1;  
    while(b>=1)
    {  
        if(b%2==1)
        {  
            r=quick_mul_mod(r,a,n);
            b-=1;
        }  
        b/=2;  
        a=quick_mul_mod(a,a,n);//（（a%n）*（a%n））%n=（a*a）%n 
    }  
    return r;  
}  
int main()
{
    long long int N=1889570071;
    long long int e1=1021763679;
    long long int e2=519424709; 
    long long int c1=1244183534;
    long long int c2=732959706;
    long long int M;
    long long int x,y;
    long long int t,cc2;
    EGCD(e1,e2,x,y); 
    cout<<"x ="<<x<<endl;
    cout<<"y ="<<y<<endl;
    EGCD(N,c2,t,cc2); 
    cout<<"c2逆元 ="<<cc2<<endl;
    y=(-y);
    c1=quick_power_mod(c1,x,N);
    c2=quick_power_mod(-cc2,y,N);
    cout<<"c1^x mod n ="<<c1<<endl;
    cout<<"(c2^-1)^(-y) mod n ="<<c2<<endl;
    M=quick_mul_mod(c1,c2,N);
    cout<<"M ="<<M<<endl;
}