題目：
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.
由于兩次加密温鸽，只是公鑰的指數(shù)e變化，而公鑰和私鑰的模數(shù)N沒(méi)有變化，此時(shí)错森，就可能出現(xiàn)共模攻擊。
共模攻擊利用的大前提就是，RSA體系在生成密鑰的過(guò)程中使用了相同的模數(shù)N。
題中的Bob用公鑰加密了同一條信息M猾封，就是
c1 = M^e1 % N
c2 = M^e2 % N
此時(shí)，Alice可以通過(guò)私鑰來(lái)解密
M = c1^d1 % N
M = c2^d2 % N
得到明文M弟晚。
如果攻擊者獲得了c1忘衍，c2，知道密鑰中的N卿城，e1枚钓，e2，則可以在不知道d1瑟押，d2的情況下搀捷，解出M。
首先由于e1，e2都是質(zhì)數(shù)嫩舟，所以?xún)烧呋ベ|(zhì)氢烘，即
gcd(e1, e2) = 1
此時(shí)則有
e1*t1 + e2*t2 = 1
式中，t1家厌、t2皆為整數(shù)播玖，但是一正一負(fù)。
通過(guò)擴(kuò)展歐幾里得算法饭于，我們可以得到該式子的一組解(t1, t2)蜀踏，假設(shè)t1為正數(shù)，t2為負(fù)數(shù)掰吕。因?yàn)椋?br>
c1 = M^e1 % N
c2 = M^e2 % N
所以
(c1^t1 * c2^t2) % N = ((M^e1 % N)^t1 * (M^e2 % N)^t2) % N
根據(jù)模運(yùn)算性質(zhì)果覆，可以化簡(jiǎn)為
(c1^t1 * c2^t2) % N = ((M^e1)^t1 * (M^e2)^t2) % N
即
(c1^t1 * c2^t2) % N = (M^(e1^t1 + e2^t2)) % N
又前面提到
e1*t1 + e2*t2 = 1
所以
(c1^t1 * c2^t2) % N = (M^1) % N
(c1^t1 * c2^t2) = M
不過(guò)，M是小于N的數(shù)值殖熟，所以
M = (c1^t1 *c2^t2) % N
就是說(shuō)局待，當(dāng)N不變時(shí)，知道n菱属，e1钳榨，e2，c1纽门，c2可以在不知道d1重绷，d2情況下，解密得到明文M膜毁。
由于t2是負(fù)數(shù)，而在數(shù)論模運(yùn)算中愤钾，要求一個(gè)數(shù)的負(fù)數(shù)次冪瘟滨，與常規(guī)方法并不一樣。比如此處要求c2的t2次冪能颁，就要先計(jì)算c2的模反元素c2r杂瘸，然后求c2r的-t2次冪。
Python程序解法如下：
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(input("input n:"))
c1 = int(input("input c1:"))
c2 = int(input("input c2:"))=
e1 = int(input("input e1:"))
e2 = int(input("input e2:"))
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 #m = (c1**s1)*(c2**s2)%n
print (m)
if __name__ == '__main__':
main()
其中伙菊，代入數(shù)值：
n = 1889570071
c1 = 1244183534
c2 = 732959706
e1 = 1021763679
e2 = 519424709
由此得到最后的明文M為1054592380败玉。
