RSA攻击之共模攻击[转]

  • 2016-05-23
  • 4,166
  • 6
引子

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

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

此时,就可能出现共模攻击。
共模攻击
也称同模攻击,英文原名是 Common Modulus Attack 。
同模攻击利用的大前提就是,RSA体系在生成密钥的过程中使用了相同的模数n。
我们依然以上面的案例展开。
假设COMPANY用所有公钥加密了同一条信息M,也就是

c1 = m^e1%n
c2 = 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%n
c2 = 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
p = 1013
q = 1009
#936
fn = (p-1)*(q-1)
e = 17
d = 180017
m = int("h1".encode("hex"),16)
c1 = m**e%n
e1 = 5
d1 = 816077
c2 = m**e1%n
print n
print e
print e1
print c1
print c2

假设模数n固定为1022117,并且产生了(e,d),(e1,d1)两个密钥对。
并且打印出m加密后的密文c1,c2.
求通过e,e1,c1,c2解出m来。
以下是一个可供利用的脚本

#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(raw_input("input n:"))
  c1 = int(raw_input("input c1:"))
  c2 = int(raw_input("input c2:"))
  e1 = int(raw_input("input e1:"))
  e2 = int(raw_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 = (c1**s1)*(c2**s2)%n
  print m
if __name__ == '__main__':
  main()

附图一张。
Referer
http://diamond.boisestate.edu/~liljanab/ISAS/course_materials/AttacksRSA.pdf
http://crypto.stackexchange.com/questions/16283/how-to-use-common-modulus-attack

评论

  • dlamyh

    您好,想问一下共模攻击后,知道明文、密文、N、e能否求出d?谢谢

    • ByStudent

      如果e不大的话,应该是可以的,直接开方

  • 迪克

    這腳本在遇到數字太大的狀況會跑超級慢
    可以把m = (c1**s1)*(c2**s2)%n
    改成這m = (pow(c1,s1,n)*pow(c2,s2,n))%n

你必须 登录 才能发表评论.