2018百越杯Crypto-RSA

题目下载

第一步利用openssl把n和e求出来：

可以发现n不算太大，丢到大数分解网站里可以得到：

p：184333227921154992916659782580114145999
q：336771668019607304680919844592337860739

到这里常规解就会报错了，参考了下大佬的wp：

同时看encrypt函数，可以看见有个try … except ，而且flag.enc 中的数据很大，说明初始的 n 并不是最后加密的 N 值(因为RSA加密需要公钥n的长度至少是大于消息的长度的, 否则加密出来的密文会无法解密. PKCS#1 v1.5的python实现中, 如果公钥n长度小于要加密的消息, 加密会失败)

#!/usr/bin/env python2.7
import gmpy2
import libnum
from Crypto.Util.number import getPrime
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_v1_5
from base64 import b64decode

m = b64decode(open('flag.enc','r').read())
n = 62078208638445817213739226854534031566665495569130972218813975279479576033261
e = 9850747023606211927
q = 184333227921154992916659782580114145999
p = 336771668019607304680919844592337860739
i=1

while 1:
        print i
        i+=1
        n=q*p
        if n >= int(m.encode('hex'),16):
                d = libnum.invmod(e,(p-1)*(q-1))
                prikey = RSA.construct((int(n),int(e),int(d)))
                key = PKCS1_v1_5.new(prikey)
                m = key.decrypt(m,None)
                break
        else:
                p = gmpy2.next_prime(p**2+q**2)
                q = gmpy2.next_prime(2*q*p)
                e = gmpy2.next_prime(e**2)

print m