[DAMCTF 2023] - Crack The Key

I have used an RSA key to encrypt the flag. Can you find a way to reconstruct the private key using the public key?

crack-the-key.zip

---

Given files

We are given the following files:

Main python file super_secure_rsa.py

#!/usr/bin/env python3
from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.backends import default_backend
from base64 import b64encode, b64decode
from flag import FLAG

# public key file name
PUB_FILE = 'pub.pem'
FLAG_FILE = 'flag.enc'


# convert key to pem format
def get_pem(key:rsa.RSAPrivateKey|rsa.RSAPublicKey):
    # check the type of key, and create pem is respective format
    if isinstance(key, rsa.RSAPublicKey):
        pem = key.public_bytes(encoding=serialization.Encoding.PEM, format=serialization.PublicFormat.SubjectPublicKeyInfo)
    else:
        pem = key.private_bytes(encoding=serialization.Encoding.PEM, format=serialization.PrivateFormat.PKCS8, encryption_algorithm=serialization.NoEncryption())

    # return the key in pem format
    return pem


# loads in a public key that is saved in PEM format
def load_public_key():
    with open(PUB_FILE, 'rb') as pubf:
        pubkey = serialization.load_pem_public_key(pubf.read(), backend=default_backend())
    return pubkey


# encrypts a plaintext with the provided public key and returns the ciphertext encoded in base 64
def encrypt(pubkey:rsa.RSAPublicKey, ptxt:str) -> str:
    # encrypt the flag using the public key
    ctxt = pubkey.encrypt(ptxt.encode(), padding.PKCS1v15())

    # return the encrypted flag in base 64
    return b64encode(ctxt).decode()


# decrypts a ciphertext (encoded to base 64) with the provided private key and returns the decrypted string
def decrypt(privkey:rsa.RSAPrivateKey, ctxt:bytes) -> str:
    # decode the ciphertext from base 64 and encrypt
    ptxt = privkey.decrypt(b64decode(ctxt), padding.PKCS1v15())

    # return the decrypted string
    return ptxt.decode()


if __name__ == '__main__':
    # Load in the key from PEM file
    pub_key = load_public_key()

    # save public key in PEM format to be printed out
    pub_key_pem = get_pem(pub_key).decode()

    # encrypt the flag using the public key
    enc_flag = encrypt(pub_key, FLAG)

    # write encrypted flag to file
    with open('flag.enc', 'w') as f:
        f.write(enc_flag)

Encrypted flag flag.enc

M1Qgcu5TJPojVpLreDXxEPctgYG7ZSXso0bIcPWeHsorU7Z5MDViiLPMTfCkdB0UtbdZeWNNzJ5EEtqk+nZjxQ==

Public key pub.pem

-----BEGIN PUBLIC KEY-----
MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBAN8YoDOh4Na+z440/O5EZvcrDncG0R7R
bvb3vTn8l13js3CEfAMddkTpTs5xH6Iwi9XFyQnojLI/fS1Pw0CQMn8CAwEAAQ==
-----END PUBLIC KEY-----

Exploitation

The main objective is to recover the private key by extracting values from public key. Here are the steps I followed in order to read the flag:

1. Extract modulus n and exponent e from public key

2. Factorize n in order to get 2 primes numbers p and q (n = p*q) - factor-db

3. Calculate phi with p and q (phi = (p-1)*(q-1))

4. Build d, private exponant

5. Get the private key

There is many ways to solve this challenge. Either exporting the private key and then using the decrypt() function from main file, or by decrypting ourselv the flag, or using openssl.. and probably more. Personally, I used the second one.

Flag

Here is my final script exploit.py

from Crypto.Util.number import inverse
from Crypto.Cipher import PKCS1_v1_5
from Crypto.PublicKey import RSA
from base64 import b64decode

public_key = RSA.importKey(open('pub.pem', 'r').read())
enc_flag = 'M1Qgcu5TJPojVpLreDXxEPctgYG7ZSXso0bIcPWeHsorU7Z5MDViiLPMTfCkdB0UtbdZeWNNzJ5EEtqk+nZjxQ=='

p = 106824314365456746562761668584927045312727977773444260463553547734415788806571
q = 109380489566403719014973591337211389488057388775161611283670009403393352513149
n = public_key.n
e = public_key.e

phi = (p-1)*(q-1)

d = inverse(e, phi)

key = RSA.construct((n, e, d))

# remove padding
cipher = PKCS1_v1_5.new(key)
sentinel = None

enc_flag = b64decode(enc_flag)
flag = cipher.decrypt(enc_flag, sentinel=sentinel)
print(flag)

#dam{4lw4y5_u53_l4r63_r54_k3y5}

🚩 dam{4lw4y5_u53_l4r63_r54_k3y5}

Thank’s for reading !