CTF_RSA_低加密指数攻击脚本

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

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

如果e=3，且m^en，那么设k，有：  c= m^e  kn   爆破k，如果c?kn可开三次根式，得到m. 

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   "}") 

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) 

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()