题目
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.
解题过程
由题可知：Eve知道N、C1、C2、e1、e2，要破解M
∵ C1≡ Me1mod N
C2≡ Me2mod N
∵ gcd(e1,e2) = 1//此处说明两者互质
∴ ∃ x , y ,//根基欧几里得扩充定理可知
e1* x + e2* y = 1
∴ C1x* C2y≡ Me1x+e2ymod N
∴ C1x* C2y≡ M mod N
∵ x > 0 , y < 0
∴ C1x* C2y= C1x* (C2-1)-y
C2-1即为 C2在模N乘法的逆元
∴ M = [(C1x) mod n * (C2-1)-ymod n] mod n
∴ M = 1054592380
此为解题思路
代码如下：
#include
using namespace std;
typedef long long L;
L exgcd(L a, L b, L &x, L &y)//ax+by=1返回a,b的gcd，同时求的一组满足题目的最小正整数解，也就是解题思路中的x,y
{
L ans, t;
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ans = exgcd(b, a%b, x, y);
t = x;
x = y;
y = t - (a / b)*y;
return ans;
}
L expmod(L a, L b, L n)//快速幂求余算法a^b%n
{
L res = 1;
a %= n;
while (b)
{
if (b & 1)//b是否为奇数
res = (res * a) % n;
a = (a * a) % n;
b /= 2;
}
return res;
}
void main()
{
L n = 1889570071;
L e1 = 1021763679;
L e2 = 519424709;
L c1 = 1244183534;
L c2 = 732959706;
L m, u, v, t, t1, t2, t3;
exgcd(e1, e2, u, v);
cout << u << endl << v << endl;
t1 = expmod(c1, u, n);
t2 = expmod(c2, v, n);
t3 = t1 * t2;
t = expmod(t3, 1, n);
m = t;
cout << m << endl;
}
