问题描述
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.
分析
Alice 给 Bob发送的密文是用两个不同密钥e1、e2加密两次得到的。即如图：
易知：
其中：
可以用扩展欧几里得算法解得u、v，故有:
如果gcd（e1, e2）刚好等于1，那么Eve就破解了密码。
实现
#include <iostream>
#include <gmp.h>
#include <gmpxx.h>
using namespace std;
//扩展欧几里得算法求u、v
mpz_class gcdEx (mpz_class a, mpz_class b, mpz_class &u, mpz_class &v)
{
if(b==0)
{
u = 1, v = 0;
return a;
}
else
{
mpz_class r = gcdEx(b, a % b, u, v); /* r = GCD(a, b) = GCD(b, a%b) */
mpz_class t = u;
u = v;
v = t - a/b * v;
return r;
}
}
//快速幂取模
mpz_class fast_exp (mpz_class a, mpz_class b, mpz_class c)
{
mpz_class ans=1; //记录结果
a=a%c; //预处理，使得a处于c的数据范围之下
while(b!=0)
{
if(b % 2 != 0) ans = (ans * a) % c; //如果该位是1，那么a是需要乘进结果的
b>>=1; //移位操作，其实就是遍历b的每一位
a = (a * a) % c; //不断的加倍
}
return ans;
}
//快速乘取模
mpz_class F_mul(mpz_class a, mpz_class b, mpz_class c) {
mpz_class ans = 0;
a %= c;
while (b != 0) {
if (b % 2 != 0) ans = (ans + a) % c;
a = (a + a) % c;
b >>= 1;
}
return ans;
}
int main ()
{
mpz_class N("1889570071", 10);
mpz_class e1("1021763679", 10);
mpz_class e2("519424709", 10);
mpz_class c[2];
c[0].set_str("1244183534", 10); c[1].set_str("732959706", 10);
mpz_class s[2];
mpz_class r = gcdEx (e1, e2, c[0], c[1]);
mpz_class rev, x;
int tn = 0;
if (s[1] < 0) tn = 1;
gcdEx(N, c[tn], x, rev);
if (rev < 0) rev = (rev + N) % N;
mpz_class res = F_mul(fast_exp(rev, -s[tn], N), fast_exp(c[!tn], s[!tn], N), N);
cout << res << endl;
return 0;
}
得到结果：1054592380
