RSA自查表（内含脚本）

RSA自查表

• • Before
  • RSA
  • • 原理
    • 攻击类型
    • • 低加密指数分解攻击
      • • e=2 把c开平方求解
        • e=2 Rabin算法
        • e=3 小明文攻击
      • 低解密指数攻击(Wiener's Attack)
      • Boneh and Durfee attack
      • 低加密指数广播攻击
      • 共模攻击
      • 模不互素
      • e与phi 不互素
      • • e与phi不互素，存在公因子x（x！=e）
        • e与phi不互素，存在公因子x（x==e即e为phi的一个因子）
      • Coppersmith攻击
      • • 已知m的高位(Known High Bits Message Attack)
        • 已知p的高位(Factoring with High Bits Known)
        • 已知d的低位(Patial Key Exposure Attack)
        • 短填充攻击 明文高位相同(Ralated Message Attack)
      • dp泄露、dq泄露
      • Least Significant Bit Oracle Attack
  • Other

Before

RSA自查

最近写了很多RSA的题，然后总结亿下下。

RSA

原理

消息传递：

Alice需要向Bob传递消息m：

Bob 向 Alice 传递公钥（n，e）；

Alice 利用公钥（n，e）对消息m进行加密，得到密文c，然后将密文c传递给Bob；

Bob利用私钥（n，d）对密文c进行解密，得到消息m

RSA：

随机产生两个整数p，q（其中p，q互素）

求出 n = p * q

求出n的欧拉函数 phi = （p-1）*（q-1）

公钥 e：随机产生 e（其中 e 和 phi 互素）

私钥 d：ed ≡ 1 （ mod phi ）

加密算法：

解密算法：

攻击类型

低加密指数分解攻击

e=2 把c开平方求解

已知e，c ，求m

import gmpy2
import libnum
c=  
e=2
m=gmpy2.isqrt(c)
m=int(m)
m=libnum.n2s(m)
print(m)

e=2 Rabin算法

Rabin算法

Rabin加密的典型特征：e=2

Rabin密码体制下

密钥生成：p≡q≡3 mod 4 n为公钥，p、q为私钥

加密算法：c ≡ m ^ 2 mod n （m为明文分组，c为密文分组）

解密算法：求 c 模 n 的平方根

根据费马小定理计算m在模p和模q下的平方根mp和mq：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-naYWAXSf-1605780433201)(C:\Users\MECHREVO\AppData\Roaming\Typora\typora-user-images\image-20201112205519336.png)]

使用扩展的欧几里得算法来查找yp和yq：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TYgMUs6t-1605780433212)(C:\Users\MECHREVO\AppData\Roaming\Typora\typora-user-images\image-20201112205848753.png)]

根据中国剩余定理求得4个mon是的平方根：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Usnh7fpI-1605780433219)(C:\Users\MECHREVO\AppData\Roaming\Typora\typora-user-images\image-20201112210019607.png)]

这四个值之一是原始明文m mm

先分解得到p，q，然后解密

import gmpy2
import libnum
def Rabin_decrypt(c, p, q, e=2):  n = p * q  mp = pow(c, (p + 1) / 4, p)  mq = pow(c, (q + 1) / 4, q)  yp = gmpy2.invert(p, q)  yq = gmpy2.invert(q, p)  r = (yp * p * mq + yq * q * mp) % n  rr = n - r  s = (yp * p * mq - yq * q * mp) % n  ss = n - s  return (r, rr, s, ss)  e=2
n=
p=
q=
c=
#c= int(open('./flag.enc','rb').read().encode('hex'),16)
r,rr,s,ss=Rabin_decrypt(c, p, q, e=2)
print(libnum.n2s(r))
print(libnum.n2s(rr))
print(libnum.n2s(s))
print(libnum.n2s(ss))

e=3 小明文攻击

两种情况

① m^3

② m^3>n，也就是 (m^3+i*n)mod n =c （直接爆破 i 的值）

github上有EXP

import gmpy2
import libnum
n=
c=
def n2s(num):t = hex(num)[2:]if len(t) % 2 == 1:t = '0' + treturn ''.join([chr(int(b, 16)) for b in [t[i:i + 2] for i in range(0, len(t), 2)]])
i=0
while 1:res=gmpy2.iroot(c+i*n,3)if(res[1]==True):print(libnum.n2s(res[0]))breaki=i+1#i=0开始就是第一种情况
#i=1开始就是第二种情况

低解密指数攻击(Wiener’s Attack)

e过大或过小，已知n，e，c，求d，进而求m

github上有轮子

import RSAwienerHacker
import hashlib
import gmpy2
e = 
n = 
c = 
d=RSAwienerHacker.hack_RSA(e,n)
print(d)
#m=pow(c,d,n)
#print(m)
#放在rsa-wiener-attack-master目录下

Boneh and Durfee attack

与低解密指数攻击相类似，但比低解密指数攻击更强，e非常大，接近于N，可以解决d

我们知道如果我们要使用wiener‘s Attack（低解密指数攻击）时，有一个点要知道的就是他的e要很大，但wiener’s Attack使用时对d有一定要求的，d要求小于N的三分之一的四分之一次方

假定d比此刻的限定要大时，我们可以尝试用Boneh and Durfee attack

github上的轮子

参考blog

这个Boneh and Durfee攻击在19年强网杯出现过一次，可以复现19年强网杯的时候康康，然后那一题主要考的就是RSA，六关都是RSA不同攻击手段，过段世界全都复现完在放吧~

不过也是因为这题我才想到要总结一下RSA的攻击类型，这些都是题外话辣~

继续继续~~

低加密指数广播攻击

e比较小，且模数n不同，密文c不同，明文m相同，加密指数e相同

import gmpy2
import time
from Crypto.Util.number import long_to_bytesdef CRT(items):N = reduce(lambda x, y: x * y, (i[1] for i in items))result = 0for a, n in items:m = N / nd, r, s = gmpy2.gcdext(n, m)if d != 1: raise Exception("Input not pairwise co-prime")result += a * s * mreturn result % N, N
# 读入 e, n, c
e 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！