假设有一家公司COMPANY,在员工通信系统中用RSA加密消息。COMPANY首先生成了两个大质数P,Q,取得PQ乘积N。并且以N为模数,生成多对不同的公钥及其相应的私钥。COMPANY将所有公钥公开。而不同的员工获得自己的私钥,比如,员工A获得了私钥d1.员工B获得了私钥d2

 

现在,COMPANY将一条相同的消息,同时经过所有公钥加密,发送给所有员工。

此时,就可能出现共模攻击。

 

共模攻击

也称同模攻击,英文原名是 Common Modulus Attack 。

同模攻击利用的大前提就是,RSA体系在生成密钥的过程中使用了相同的模数n。

我们依然以上面的案例展开。

 

假设COMPANY用所有公钥加密了同一条信息M,也就是

c1 = m^e1%nc2 = m^e2%n

 

此时员工A拥有密钥d1他可以通过

m = c1^d1%n

解密得到消息m

同时员工B拥有密钥d2

 

他可以通过

m = c2^d2%n

解密得到消息m

 

如果,此时有一个攻击者,同时监听了A和B接收到的密文c1,c2,因为模数不变,以及所有公钥都是公开的,那么利用同模攻击,他就可以在不知道d1,d2的情况下解密得到消息m。

 

又到了高数时间~

这里就是要论证,当n不变的情况下,知道n,e1,e2,c1,c2 可以在不知道d1,d2的情况下,解出m。

 

首先假设,e1,e2互质

gcd(e1,e2)=1

此时则有

e1*s1+e2*s2 = 1

式中,s1、s2皆为整数,但是一正一负。

 

通过扩展欧几里德算法,我们可以得到该式子的一组解(s1,s2),假设s1为正数,s2为负数.

因为

c1 = m^e1%nc2 = 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

 

也就是证明了命题:当n不变的情况下,知道n,e1,e2,c1,c2 可以在不知道d1,d2情况下,解出m。

 

这里还有一个小问题,顺带说明下。

我们知道解出来s2是为负数。

而在数论模运算中,要求一个数的负数次幂,与常规方法并不一样。

比如此处要求c2的s2次幂,就要先计算c2的模反元素c2r,然后求c2r的-s2次幂。

 

案例

假设模数n固定为1022117,并且产生了(e,d),(e1,d1)两个密钥对。

并且打印出m加密后的密文c1,c2.

求通过e,e1,c1,c2解出m来。

以下是一个可供利用的脚本