共模攻击

假设 有一条信息m，用公钥加密信息(使用了相同的模数n)：

c1 = m^e1 mod n
c2 = m^e2 mod n

可以利用密钥d1，d2来解密：

m = c1^d1 mod n
m = c2^d2 mod n

此时如果有一个攻击者，得到了密文c1、c2，因为公钥公开，而模数相同，攻击者姐可以破解密文获得信息。 此时已知信息： c1, c2, e1, e2, n

gcd(e1, e2) = 1
m = c1^d1 mod n
m = c2^d2 mod n

求出m。

接下来就到了高数时间。 e1,e2互质

gcd(e1,e2)=1

则有

e1*s1 + e2*s2 = 1

这里涉及到欧几里德扩展算法，可以看我另一篇文章： 欧几里德算法及扩展算法 因为

c1 = m^e1 mod n
c2 = m^e2 mod n  

所以

(c1^s1*c2^s2) mod n = ((m^e1 mod n)^s1*(m^e2 mod n)^s2) mod n

即

(c1^s1*c2^s2) mod n = (m^(e1^s1 + e2^s2)) mod n

所以

(c1^s1*c2^s2) mod n = (m^(1)) mod n

即

c1^s1*c2^s2= m

得证，可求出m。

• 注意： 从前面的式子e1*s1 + e2*s2 = 1可以知道，s1、s2中有一个为负数，而负数次幂运算，比如这里求c2的s2次幂，需要先计算c2的模反元素c2r，然后再求c2r的-s2次幂。