2016 ASIS CTF RSA

Crypto & Math

2016.09.12 02:39


import gmpy
import re
from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
from pwn import log

def npqe(p, q, e) :
	n = p * q
	phi = (p-1) * (q-1)
	d = gmpy.invert(e, phi)
	pubkey = RSA.construct((long(n), long(e), long(d), long(q), long(p)))
	enc = open('flag.enc', 'rb').read().decode('base64')
	key = PKCS1_v1_5.new(pubkey)
	try :
		dec = key.decrypt(enc, 'verify')
		if bool(re.search('ASIS', dec)) :
			print dec
			return 1
	except :
		return 0

def main() :
	p = 311155972145869391293781528370734636009
	q = 315274063651866931016337573625089033553
	e = 12405943493775545863
	l = log.progress('Find p,q,e ing...')
	for _ in range(10) :
		l.status('%d th.'%(_+1))
		if npqe(p, q, e) :
			l.success('Find Flag!!!')
			break
		p = gmpy.next_prime(p**2 + q**2)
		q = gmpy.next_prime(2*p*q)
		e = gmpy.next_prime(e**2)

if __name__ == '__main__' :
	main()