RSA partical attack

Posted on Edited on

#已知p的高位

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

已知前144位，则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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)

只知道前142位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n =
p4 = #已知P的高位,最后面8位二进制，也就是两位十六进制要参与爆破，所以要用00补充
e =
pbits = #P原本的位数


for i in range(0,256):# 要爆破的8位二进制数，为2**8==256，表示0~255
    p4 =
    p4 = p4 + int(hex(i),16)
	kbits=pbits - 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高位

1
2
3
4
5
6
7
8
9
10
11
def phase2(high_m, n, c):
    R.<x> = PolynomialRing(Zmod(n), implementation='NTL')
    m = high_m + x
    M = m((m^3 - c).small_roots()[0])
    print(hex(int(M))[2:])

n = 
c = 
high_m = 

phase2(high_m, n, c)

#已知d的低位

如果知道d的低位，低位约为n的位数的1/4就可以恢复d。已知私钥的512位的低位 Partial Key Exposure Attack(部分私钥暴露攻击)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def partial_p(p0, kbits, n): 
    PR.<x> = PolynomialRing(Zmod(n)) 
    nbits = n.nbits() 
    f = 2^kbits*x + p0 
    f = f.monic() 
    roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3)  # find root < 2^(nbits//2-kbits) with factor >= n^0.3
    if roots:
         x0 = roots[0]
         p = gcd(2^kbits*x0 + p0, n)
         return ZZ(p)
 
def find_p(d0, kbits, e, n): 
    X = var('X') 
    for k in range(1, e+1): 
        results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits) 
        for x in results: 
            p0 = ZZ(x[0]) 
            p = partial_p(p0, kbits, n) 
            if p: 
                return p 
if __name__ == '__main__':
 
    n = 
    e = 
    d = 
    
    beta = 0.5
    epsilon = beta^2/7
     
    nbits = n.nbits() 
    #print("nbits:%d:"%(nbits))
    #kbits = floor(nbits*(beta^2+epsilon)) 
    kbits = nbits - d.nbits()-1 
    #print("kbits:%d"%(kbits))
    d0 = d & (2^kbits-1)
    #print("lower %d bits (of %d bits) is given" % (kbits, nbits))
    p = find_p(d0, kbits, e, n)
    print("found p: %d" % p)
    q = n//p
    print(d)
    print(inverse_mod(e, (p-1)*(q-1)))