0CTF Finals 2021 | ezrsa+

#0ctf2021finals

from Crypto.Util.number import *
from secret import flag
from os import urandom

def gen(n_size, m_size):
    alpha = 0.5
    delta = 0.03
    d_size = int(delta * n_size)
    k_size = int((alpha + delta - 0.5) * n_size)
    c_size = int(n_size * (1 - alpha - 2 * delta))
    while True:
        while True:
            d_p = getRandomNBitInteger(d_size)
            d_q = getRandomNBitInteger(d_size)
            k = getRandomNBitInteger(k_size)
            l = getRandomNBitInteger(k_size)
            if GCD(k ,l) == 1 and GCD(d_p, k) == 1 and GCD(d_q, l) == 1:
                break
        e = inverse(d_p, k) * inverse(l, k) * l + inverse(d_q, l) * inverse(k, l) * k
        c = getRandomNBitInteger(c_size)
        e += c * k * l
        assert e * d_q % l == 1
        assert e * d_p % k == 1
        p = (e * d_p - 1) // k + 1
        q = (e * d_q - 1) // l + 1
        if isPrime(p) and isPrime(q):
            mask = 2 ** m_size - 1
            return (p * q, e), (d_p, d_q, p, q), (d_p & mask, d_q & mask) 

def encrypt(m, pk):
    n, e = pk
    return pow(m, e, n)

n_size = 2000
m_size = 12
pk, sk, hint = gen(n_size, m_size)
flag = urandom(n_size // 8 - len(flag) - 1) + flag
enc = encrypt(int(flag.hex(), 16), pk)

print(pk)
print(hint)
print(enc)
'''
(5943169364392579648240628105465400265561630477719849140342288893646282358845864829196464904298425034495515703590715696166689341849788423790118035115884268058450057766891418761627136386260375534474238287294722575087291704432681906513559934960801746158191355141430407698622886747610818853554584519369492697299961587570531415598410602926850787615266600194130088653542080297272898142822126215764285317511778718862825024939241749996811603610592132845393755564618871967716819173935553139267269362451423802419847919801412517294612793840767037662589233422389282092051866024514599213445596030685325227269609799, 1762727270442607836236621349004505613506359415168929966540357011133047321101203605340201016757203407375680206339341465088639129039278027484128644822299382121442456525803635369125157261704416172232695058332167310707999473221769390010733123910955508477009411113166141188309425895082608534271594076218827)
(1361, 1475)
4531542437692818645025309324015912433184165181252393791711464775823247402127139569010657935303362440253951226047224610112010632226435610975118324658493911658016955717228741291266124372004503735693124810068041692730706167827666860062121413284053921548345924563903211959003376490264228814415500106847482893238907846512437694006785527867729127228361388592714377847012086312471372061723017560705890925568994607972832373362380226566506368932968108567819188587148829190811891555283157485379418388715910299951228404648535235675640369275644493614250037857212768450860647393276921502407057557208885073276533644
'''

0CTF Finals 2021 | ezrsaに比べて、magicが渡されなくなり、代わりにの下位2bitが追加で渡されるようになった。

https://github.com/M0urn3r/My-Public-CTF-Challenges#ezRSA+

RSA-CRT