截至：11月07日23:59提交作業(yè)
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文檔，交鏈接颖御。提示：簡單題寓落，不同于共用模數(shù)攻擊纠俭。
公匙N=1889570071雳锋，加密指數(shù)e1 = 1021763679颂砸，e2 = 519424709
密文c1 = 1244183534灶轰，c2 = 732959706
首先假設(shè)谣沸，e1，e2互質(zhì)
即gcd(e1,e2)=1
此時(shí)有e1*s1+e2*s2 = 1
式中笋颤，s1乳附、s2皆為整數(shù)，但是一正一負(fù)伴澄。
通過擴(kuò)展歐幾里德算法赋除，我們可以得到該式子的一組解（s1,s2），假設(shè)s1為正數(shù),s2為負(fù)數(shù).
因?yàn)?/p>
c1 = m^e1%n
c2 = m^e2%n
所以
(c1^s1*c2^s2)%n = ((m^e1%n)^s1*(m^e2%n)^s2)%n
根據(jù)模運(yùn)算性質(zhì)非凌，化簡
(c1^s1*c2^s2)%n = ((m^e1)^s1*(m^e2)^s2)%n
即
(c1^s1*c2^s2)%n = (m^(e1^s1+e2^s2))%n
又因?yàn)?/p>
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
