happy

Happy (crypto, 242p, 36 solved)

In the challenge we get encrypted flag, rsa public key and encryption code. The code performs generation of RSA-CRT key (although in a bit convoluted way, to make sure there are safe primes used). Then encryption of the flag is performed using RSA with OAEP SHA1 padding. Unusually the modulus N is here p*q**k, but on its own it doesn't yet cause any issues. From the modulus size of 2300 bits, and minimum bitsize for primes set for 700, we can deduce that p and q are about 765 bits long and k=2.

The key to solve the problem is to notice this:

cf = p.pow(q ** (k - 1) * (q - 1) - 1, q ** k)

and then

def public_key
    Key.new(@attr.reject{|k, v| [:p, :q, :d1, :d2, :ce].include?(k)})
end

The cf parameter is what is normally known as qInv, and in our case cf = modinv(p,q^2). But if you look closely at the public key construction, the omitted parameters are :p, :q, :d1, :d2, :ce. There is no parameter ce but there was cf!

This means that actually the value of cf is still stored in the public key, alongside e and N.

In conclusion, we know a small part of RSA-CRT private key -> we know value qInv such that qInv*p == 1 mod q**2

What we would like to calculate is p (or q). Let's rephrase that into an equation:

f(x) = qInv*x - 1 == 0 mod q**2

We want to solve such equation, because non-trivial root of this polynomial has to be p. Once it's written like this, it's pretty clear that it look a lot like polynomial for Coppersmith theorem. Just to recap:

Given polynomial f(x) such that f(x) == 0 mod N there is a polynomial algorithm to calculate small roots of such polynomial mod some factor of N bigger than N^beta (where beta can be anything 0<beta<1). Small in this case mean that for polynomial of degree d they have to be smaller than N^(beta^2)/d.

In our case p is of similar order to q, so about N^1/3 and degree of the polynomial is 1. We know that q^2 is about N^2/3 and is a factor of N, so we can look for roots modulo N^2/3 thus beta = 0.6. And with this constraint we should be able to find roots smaller than N^(4/9), and we know p is about N^1/3 so N^3/9, so it's smaller than the bound, and we should be able to find it.

We proceed with the code:

def main():
    e = 65537
    N = 5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911
    qinv = 25895436290109491245101531425889639027975222438101136560069483392652360882638128551753089068088836092997653443539010850513513345731351755050869585867372758989503310550889044437562615852831901962404615732967948739458458871809980240507942550191679140865230350818204637158480970417486015745968144497190368319745738055768539323638032585508830680271618024843807412695197298088154193030964621282487334463994562290990124211491040392961841681386221639304429670174693151
    
    P.<x> = PolynomialRing(Zmod(N), implementation='NTL')
    pol = x*qinv - 1
    pol = pol.monic()
    roots = pol.small_roots(X=2**765, beta=0.6)
    print("Potential solutions:")
    for p in roots:
        q = isqrt(int(N)/int(p))
        phi = (p-1)*(q-1)*q
        d = inverse_mod(e, phi)
        print(d)

main()

And almost immediately we get back d = 313643312579885910144930879740792443079046797319702735470940304815114423813387207622962378717692956907985131193206173468032955155911357015790117906931310982300638685119345225585365379933984401550490180088069653940748930777249398681018529181837718088338410634951815720591986027326920386342449211862769317826747179543111987382083071211027548820393280953703100868439675930431579069835763288141197755585262721361909904809472100941962440764955942607730932895387899109482973057485978370088173899965076238641801547197089631820258212320243267074873219925727866388979716767504927253295557727184298435208619716766017226260721754210366993951047440280419099305076176216010566878368093440228299300269753

Now we only need to decrypt the flag. It's a bit tricky, since unlike in most CTFs, it's not textbook RSA but OAEP.

To decrypt the flag we need:

from Crypto.PublicKey import RSA
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes, serialization
from cryptography.hazmat.primitives.asymmetric import padding


def main():
    e = 65537L
    N = 5452318773620154613572502669913080727339917760196646730652258556145398937256752632887555812737783373177353194432136071770417979324393263857781686277601413222025718171529583036919918011865659343346014570936822522629937049429335236497295742667600448744568785484756006127827416640477334307947919462834229613581880109765730148235236895292544500644206990455843770003104212381715712438639535055758354549980537386992998458659247267900481624843632733660905364361623292713318244751154245275273626636275353542053068704371642619745495065026372136566314951936609049754720223393857083115230045986813313700617859091898623345607326632849260775745046701800076472162843326078037832455202509171395600120638911
    d = 313643312579885910144930879740792443079046797319702735470940304815114423813387207622962378717692956907985131193206173468032955155911357015790117906931310982300638685119345225585365379933984401550490180088069653940748930777249398681018529181837718088338410634951815720591986027326920386342449211862769317826747179543111987382083071211027548820393280953703100868439675930431579069835763288141197755585262721361909904809472100941962440764955942607730932895387899109482973057485978370088173899965076238641801547197089631820258212320243267074873219925727866388979716767504927253295557727184298435208619716766017226260721754210366993951047440280419099305076176216010566878368093440228299300269753
    key = RSA.construct((N, e, d))
    pemkey = key.exportKey()
    encrypted = open("flag.enc", 'rb').read()
    private_key = serialization.load_pem_private_key(
        pemkey,
        password=None,
        backend=default_backend()
    )
    original_message = private_key.decrypt(
        encrypted,
        padding.OAEP(
            mgf=padding.MGF1(algorithm=hashes.SHA1()),
            algorithm=hashes.SHA1(),
            label=None
        )
    )
    print(original_message)


main()

Which finally gives TWCTF{I_m_not_sad__I_m_happy_always}