攻击条件
Rabin 算法的特征在于 e=2
攻击原理
图片.png
如果p,q是形为4k+3的不同素数(
p≡q≡3(mod4)),则
图片.png
详细解密过程
IMG_20190807_105416.jpg
图片.png
例子
题目：破解加密数据
题目来源：2019年工业信息安全技能大赛
题目描述：
图片.png
下载附件,得到py文件
m = "unknown"
e = 2
n = 0x6FBD096744B2B34B423D70C8FB19B541
assert(int(m.encode('hex'), 16) < n)
c = pow(int(m.encode('hex'), 16),e,n)
print c
#109930883401687215730636522935643539707
e=2，很明显的Rabin算法
将n转化为10进制，再将n分解
解密脚本
import gmpy2
import libnum
c = 109930883401687215730636522935643539707
p = 10848126018911527523
q = 13691382465774455051
n = p*q
u = pow(c,(p+1)/4,p)
v = pow(c,(q+1)/4,q)
# sp+tq=1
s = gmpy2.invert(p,q) # (p^-1) mod q
t = gmpy2.invert(q,p) # (q^-1) mod p
x = (t*q*u+s*p*v)%n
y = (t*q*u-s*p*v)%n
print libnum.n2s(x%n)
print libnum.n2s((-x)%n)
print libnum.n2s(y%n)
print libnum.n2s((-y)%n)
