RSA已知高位攻击

背景

已知e，n，c（其中n太大，分解不了），和p的高位或m的高位或d的高位

基础知识

（1）生成一个以x为符号的一元多项式环

PR.<x> = PolynomialRing(Zmod(n))

（2）定义求解的函数

f = x + p4

（3）多项式小值根求解及因子分解，其中X表示求解根的上界

roots = f.small_roots(X=2^kbits, beta=0.4)

coppersmith的定理：

对任意的a > 0 ， 给定N = PQR及PQ的高位(1/5)(logN,2)比特，我们可以在多项式时间logN内得到N的分解式。这是三个因式的分解。也就是说我们现在是由理论依据的，已知高位是可以在一定时间内分解N。

Coppersmith证明了在已知p和q部分比特的情况下，若q和p的未知部分的上界X和Y满足XY <= N 0.5则Ｎ的多项式可以被分解。这里的0.5可以替换成其他的数，具体原因不详。

已知p高位

知道p的高位为p的位数的约1/2时即可
已知e,n爆破 1024的P，至少需要知道前576位二进制，即前144位16进制

脚本：

n=
p4=            #已知P的高位
e=
pbits=          #P原本的位数

kbits=pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits,beta=0.4)
# 经过以上一些函数处理后，n和p已经被转化为10进制
if roots:
    p= p4 + int(roots[0])
    print ("n",n)
    print ("p",p)
    print ("q",n//p)

已知m高位

由于$m^{e} \equiv c \pmod{n} $，已知m的高位，我们不妨设低位数据为x，高位数据后面缺的补0并设为mh，则前式可写为$(mh+x)^{e} \equiv c \pmod{n} $，进一步可写为模n下的多项式：$f=(mh+x)^{e}-c $

n = 
c = 
e =
high_m = 
R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
m = high_m + x
M = m((m^e - c).small_roots()[0])
print(hex(int(M))[2:])

RSA已知高位攻击_m0_57291352的博客-CSDN博客_rsa高位攻击