安全矩阵

 找回密码
 立即注册
搜索
查看: 242|回复: 0

Crypto-RSA-公钥攻击小结

[复制链接]

81

主题

82

帖子

341

积分

中级会员

Rank: 3Rank: 3

积分
341
发表于 2022-6-23 21:38:58 | 显示全部楼层 |阅读模式
本帖最后由 wangqiang 于 2022-6-23 21:47 编辑

​ Crypto-RSA-公钥攻击小结
一叶飘零  衡阳信安
2022-06-22 07:00 发表于山东
转载地址:Crypto-RSA-公钥攻击小结

前言本篇文章对一些常见的公钥RSA攻击进行小结,欢迎补充
e=1
当e只有1的时候,我们有

当c小于N的时候,c即m
题目如下
  1. N=0x180be86dc898a3c3a710e52b31de460f8f350610bf63e6b2203c08fddad44601d96eb454a34dab7684589bc32b19eb27cffff8c07179e349ddb62898ae896f8c681796052ae1598bd41f35491175c9b60ae2260d0d4ebac05b4b6f2677a7609c2fe6194fe7b63841cec632e3a2f55d0cb09df08eacea34394ad473577dea5131552b0b30efac31c59087bfe603d2b13bed7d14967bfd489157aa01b14b4e1bd08d9b92ec0c319aeb8fedd535c56770aac95247d116d59cae2f99c3b51f43093fd39c10f93830c1ece75ee37e5fcdc5b174052eccadcadeda2f1b3a4a87184041d5c1a6a0b2eeaa3c3a1227bc27e130e67ac397b375ffe7c873e9b1c649812edcd

  2. e=0x1

  3. c=0x4963654354467b66616c6c735f61706172745f736f5f656173696c795f616e645f7265617373656d626c65645f736f5f63727564656c797d
复制代码

此时只要
  1. print libnum.n2s(c)
复制代码
即可

Rabin算法满足条件
e=2,且n可以被分解
(既然n可以被分解,为什么不直接算d?因为不互素,没法求逆元)

通解方法
我们有

此时计算两个值

又因为gcd(p,q)=1
那么有

可以求出两个y,然后再计算下列4值

小性质



计算脚本
  1. import gmpy2import stringfrom Crypto.PublicKey import RSAwith open('pubkey.pem', 'r') as f:
  2.     key = RSA.importKey(f)
  3.     N = key.n
  4.     e = key.ewith open('flag.enc', 'r') as f:
  5.     cipher = f.read().encode('hex')
  6.     cipher = string.atoi(cipher, base=16)q = ......p = ......inv_p = gmpy2.invert(p, q)inv_q = gmpy2.invert(q, p)mp = pow(cipher, (p + 1) / 4, p)mq = pow(cipher, (q + 1) / 4, q)a = (inv_p * p * mq + inv_q * q * mp) % Nb = N - int(a)c = (inv_p * p * mq - inv_q * q * mp) % Nd = N - int(c)for i in (a, b, c, d):
  7.     s = '%x' % i
  8.     if len(s) % 2 != 0:
  9.         s = '0' + s
  10.     print s.decode('hex')
复制代码

低指数攻击满足条件
e很小,通常为3

通解方法
当e很小的时候,我们爆破k,开e次方即可得到m

计算脚本
  1. import gmpyimport libnumfrom Crypto.Util import numberimport gmpy2def getd(e,p,q):
  2.     phi = (p - 1) * (q - 1)
  3.     d = gmpy2.invert(e, phi) % phi
  4.     return ddef getm(m):
  5.     return int(m.encode('hex'), 16)c=....n=....e=3i = 0while 1:
  6.     if (gmpy.root(c + i * n, 3)[1] == 1):
  7.         m = gmpy.root(c + i * n, 3)[0]
  8.         print libnum.n2s(m)
  9.         break
  10.     i = i + 1
复制代码

低指数广播攻击满足条件
当有如下条件

我们有多组(c,n),但是他们都是用同样的公钥加密同样的消息,且这里的公钥是一个低指数

通解方法
此时就可以使用中国剩余定理计算通解
其中

详细链接
  1. http://skysec.top/2018/09/13/Crypto-RSA多等式攻击总结/#多等式之低加密指数广播攻击
复制代码

计算脚本
脚本如下
  1. import gmpy2import gmpyimport libnumquestion = [c1,c2,c3....n1,n2,n3...]N = 1e=10for i in range(len(question)):
  2.     N*=question[i]['n']N_list = []for i in range(len(question)):
  3.     N_list.append(N/question[i]['n'])t_list = []for i in range(len(question)):
  4.     t_list.append(int(gmpy2.invert(N_list[i],question[i]['n'])))sum = 0for i in range(len(question)):
  5.     sum = (sum+question[i]['c']*t_list[i]*N_list[i])%Nsum = gmpy.root(sum,e)[0]print libnum.n2s(sum)
复制代码

Related Message Attack满足条件
当e=3时,我们有如下条件


此时,我们有(c1,c2,n,padding)的值
通解方法


那么就可以使用此攻击,得到通解

详细推导过程见
  1. http://skysec.top/2018/09/15/浅析RSA-Padding-Attack/
复制代码


计算脚本
脚本如下
  1. def getM2(a,b,c1,c2,n):
  2.     a3 = pow(a,3,n)
  3.     b3 = pow(b,3,n)
  4.     first = c1-a3*c2+2*b3
  5.     first = first % n
  6.     second = 3*b*(a3*c2-b3)
  7.     second = second % n
  8.     third = second*gmpy2.invert(first,n)
  9.     third = third % n
  10.     fourth = (third+b)*gmpy2.invert(a,n)
  11.     return fourth % nm = getM2(a,b,c1,c2,n)-padding2print libnum.n2s(m)
复制代码

Winner's Attack满足条件
当题目中

那么即可使用Winner's Attack
更简单的判断方式为:e很大
计算脚本
  1. https://github.com/pablocelayes/rsa-wiener-attack
复制代码

Boneh and Durfee attack
满足条件
当题目中



那么即可使用Boneh and Durfee attack
更简单的判断方式为:e很大,且Winner's Attack无法使用
计算脚本
  1. https://github.com/mimoo/RSA-and-LLL-attacks
复制代码

与Winner's Attack对比
Boneh and Durfee attack的条件需求比Winner's Attack的需求低的多
所以一般情况下,在e很大的情况下,Winner's Attack无法使用可以使用Boneh and Durfee attack

来源:先知(https://xz.aliyun.com/t/2731#toc-0)





回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|安全矩阵

GMT+8, 2022-8-13 15:20 , Processed in 0.010907 second(s), 18 queries .

Powered by Discuz! X4.0

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表