Chinaunix首页 | 论坛 | 博客
  • 博客访问: 799606
  • 博文数量: 145
  • 博客积分: 6619
  • 博客等级: 准将
  • 技术积分: 1606
  • 用 户 组: 普通用户
  • 注册时间: 2008-02-29 14:06
文章分类

全部博文(145)

文章存档

2019年(3)

2018年(3)

2017年(5)

2015年(5)

2014年(7)

2013年(5)

2012年(11)

2011年(15)

2010年(14)

2009年(14)

2008年(63)

分类: 网络与安全

2019-04-15 12:46:54

原理

引子
假设有一家公司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次幂。

案例

点击(此处)折叠或打开

  1. n = 1022117
  2. p = 1013
  3. q = 1009
  4. #936
  5. fn = (p-1)*(q-1)
  6. e = 17
  7. d = 180017
  8. m = int("h1".encode("hex"),16)
  9. c1 = m**e%n
  10. e1 = 5
  11. d1 = 816077
  12. c2 = m**e1%n
  13. print n
  14. print e
  15. print e1
  16. print c1
  17. print c2
假设模数n固定为1022117,并且产生了(e,d),(e1,d1)两个密钥对。
并且打印出m加密后的密文c1,c2.
求通过e,e1,c1,c2解出m来。
以下是一个可供利用的脚本

点击(此处)折叠或打开

  1. #coding=utf-8
  2. def egcd(a, b):
  3.   if a == 0:
  4.     return (b, 0, 1)
  5.   else:
  6.     g, y, x = egcd(b % a, a)
  7.     return (g, x - (b // a) * y, y)
  8. def modinv(a, m):
  9.   g, x, y = egcd(a, m)
  10.   if g != 1:
  11.     raise Exception('modular inverse does not exist')
  12.   else:
  13.     return x % m
  14. def main():
  15.   n = int(raw_input("input n:"))
  16.   c1 = int(raw_input("input c1:"))
  17.   c2 = int(raw_input("input c2:"))
  18.   e1 = int(raw_input("input e1:"))
  19.   e2 = int(raw_input("input e2:"))
  20.   s = egcd(e1, e2)
  21.   s1 = s[1]
  22.   s2 = s[2]
  23.   # 求模反元素
  24.   if s1<0:
  25.     s1 = - s1
  26.     c1 = modinv(c1, n)
  27.   elif s2<0:
  28.     s2 = - s2
  29.     c2 = modinv(c2, n)
  30.   m = (c1**s1)*(c2**s2)%n
  31.   print m
  32. if __name__ == '__main__':
  33.   main()

点击(此处)折叠或打开

  1. from gmpy2 import *
  2. import libnum

  3. n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929

  4. e1 = 17
  5. e2 = 65537
  6. s = gcdext(e1, e2)
  7. s1 = s[1]
  8. s2 = -s[2]

  9. c1 = libnum.s2n(open("./veryhardRSA/flag.enc1", 'rb').read())
  10. c2 = libnum.s2n(open("./veryhardRSA/flag.enc2", 'rb').read())
  11. c2 = invert(c2, n)
  12. m = (pow(c1,s1,n) * pow(c2 , s2 , n)) % n
  13. print libnum.n2s(m)

阅读(307) | 评论(0) | 转发(0) |
0

上一篇:Base64编码简介

下一篇:没有了

给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册