假設有一家公司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來。

以下是一個可供利用的腳本