截至：11月07日23:59提交作业
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.
选做，交电子版，写成md文档，交链接。提示：简单题，不同于共用模数攻击。
公匙N=1889570071，加密指数e1 = 1021763679，e2 = 519424709
密文c1 = 1244183534，c2 = 732959706
首先假设，e1，e2互质
即gcd(e1,e2)=1
此时有e1*s1+e2*s2 = 1
式中，s1、s2皆为整数，但是一正一负。
通过扩展欧几里德算法，我们可以得到该式子的一组解（s1,s2），假设s1为正数,s2为负数.
因为
c1 = m^e1%n
c2 = m^e2%n
所以
(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n
根据模运算性质，化简
(c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n
即
(c1^s1*c2^s2)%n = (m^(e1^s1+e2^s2))%n
又因为
e1*s1+e2*s2 = 1
所以
(c1^s1*c2^s2)%n = (m^(1))%n
(c1^s1*c2^s2)%n = m^%n
即
c1^s1*c2^s2 = m
代码：
#!/usr/bin/python
#coding=utf-8
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
def main():
n = int(1889570071)
c1 = int(1244183534)
c2 = int(732959706)
e1 = int(1021763679)
e2 = int(519424709)
s = egcd(e1, e2)
s1 = s[1]
s2 = s[2]
#求模反元素
if s1<0:
s1 = - s1
c1 = modinv(c1, n)
elif s2<0:
s2 = - s2
c2 = modinv(c2, n)
m = (pow(c1,s1,n)*pow(c2,s2,n))%n
print (m)
if __name__ == '__main__':
main()
所以，最后答案是1054592380
