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是否為奇數(shù)
result = (result * a) % N;
a = (a * a) % N;
b /= 2;
}
return result;
}
