P09.低加密指数攻击

加密指数指的是e，e一般选取65535，当e很小，可直接破解。

这类攻击在CTF题中，一般是 e=3

如果e=3，且m^e<n，c开3次根式，得到m。

如果e=3，且m^e>n，那么设k，有：
 c= m^e +kn

爆破k，如果c−kn能开三次根式，得到m.

出题脚本

随机生成flag

import random
import hashlib
import string

#字符串列表
a=string.printable
#随机生成flag
for i in range(10):
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = hashlib.md5(flag.encode()).hexdigest()
    print("flag{" + flag + "}")

e=3 出题脚本

import libnum
import gmpy2

#生成随机素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=3
m="flag{20d6e2da95dcc1fa5f5432a436c4be18}"
#字符串转数字
m=libnum.s2n(m)
n=p*q
phi_n=(p-1)*(q-1)
#求逆元
d=gmpy2.invert(e,phi_n)
c=pow(m,e,n)

print ("n=",n)
print ("e=",e)
print ("c=",c)

e=3 解密脚本

import gmpy2
import libnum

def de(c, e, n):
    k = 0
    while True:
        mm = c + n*k
        result, flag = gmpy2.iroot(mm, e)
        if True == flag:
            return result
        k += 1
e= 3
n=
c=

m=de(c,e,n)
print(m)
print(libnum.n2s(int(m)).decode())

附录多进程爆破脚本

#/usr/bin/python
# coding=utf-8
import gmpy2
from Crypto.PublicKey import RSA
from multiprocessing import Pool
pool = Pool(4)

with open('./pubkey.pem', 'r') as f:
    key = RSA.importKey(f)
    N = key.n
    e = key.e
with open('flag.enc', 'r') as f:
    cipher = f.read().encode('hex')
    cipher = int(cipher, 16)


def calc(j):
    print j
    a, b = gmpy2.iroot(cipher + j * N, 3)
    if b == 1:
        m = a
        print '{:x}'.format(int(m)).decode('hex')
        pool.terminate()
        exit()


def SmallE():
    inputs = range(0, 130000000)
    pool.map(calc, inputs)
    pool.close()
    pool.join()


if __name__ == '__main__':
    print 'start'
    SmallE()