Problem:

    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 e1and e2. Please help Eve recover Bob’s plaintext without finding a factorization of N.

Solution:

    According to RSA，c1 = m ^ e1 (mod N), c2 = m ^ e2 (mod N)。zAccording to GCD，gcd(e1,e2) = 1， and according to EGCD, e1·x + e2·y = gcd(e1,e2) = 1, then we get x and y.

    在mod(N)运算之下，c1^x · c2^y = (m^e1)^x · (m^e1)^y = m^(e1·x + e2·y) = m^1 = m.

    m mod N = (c1^x · c2^y) mod N = (c1^x mod N · c2^y mod N) mod N.

    0 < m < N, so m = m  mod N

Code

#include<iostream>

using namespace std;

const long long N = 1889570071;

const long long e1 = 1021763679;

const long long e2 = 519424709;

const long long c1 = 1244183534;

const long long c2 = 732959706;

long long EGCD(long long, long long, long long &, long long &);

long long FastModularExponentiation(long long, long long);

int main()

{

long long m, x, y;

EGCD(e1, e2, x, y);

cout << “x = " << x << endl << "y = " << y << endl;

m = FastModularExponentiation(c1, x) * FastModularExponentiation(c2, y) % N;

cout << "m = " << m << endl;

system("pause");

return 0;

}

long long EGCD(long long a, long long b, long long &x, long long &y)

{

long long result, t;

if (b == 0)

{

x = 1;

y = 0;

return a;

}

result = EGCD(b, a%b, x, y);

t = x;

x = y;

y = t - (a / b)*y;

return result;

}

long long FastModularExponentiation(long long a, long long b)//快速幂求余算法a^b%N

{

long long result = 1;

a %= N;

while (b)

{

if (b & 1)//b是否为奇数

result = (result * a) % N;

a = (a * a) % N;

b /= 2;

}

return result;

}