<- SEETF

Close Enough

2 minutes to read

We are told that some RSA implementation uses a prime number and the next prime number. We are also given the ciphertext:

4881495507745813082308282986718149515999022572229780274224400469722585868147852608187509420010185039618775981404400401792885121498931245511345550975906095728230775307758109150488484338848321930294974674504775451613333664851564381516108124030753196722125755223318280818682830523620259537479611172718588812979116127220273108594966911232629219195957347063537672749158765130948724281974252007489981278474243333628204092770981850816536671234821284093955702677837464584916991535090769911997642606614464990834915992346639919961494157328623213393722370119570740146804362651976343633725091450303521253550650219753876236656017

We got the source code as well:

from Crypto.Util.number import getPrime, bytes_to_long  
from Crypto.PublicKey import RSA
from secret import flag, getNextPrime

p = getPrime(1024)
q = getNextPrime(p)
n = p * q
e = 65537

key = RSA.construct((n, e)).export_key().decode()

with open("key", "w") as f:
    f.write(key)

m = bytes_to_long(flag.encode())
c = pow(m, e, n)
print(f"c = {c}")

Notice that we don’t have function getNextPrime. Moreover, we are given the public key in PEM format:

-----BEGIN PUBLIC KEY-----
MIIBITANBgkqhkiG9w0BAQEFAAOCAQ4AMIIBCQKCAQBKS/xOueb8SyhYskLwm2DT  
hofceXDq73pNlu7CAwf1rTYFfYUgbiaKqkOfyTDurLOVXhWnwcmCRo9HwUUEyHG3
swXS5OoSGmHHplMv8crTLlY+/hCpEFnLSPDcnl7HI7a/oprKpCgeiZOphEiIhm8x
UQqivWqZvGzeV9EfjeaAaPlztu3nuRyfccMjqozreU20f8SNSa9wD6vKqtAgvjv3
VapvlRVHRfPvlWCr09VE8W1qzdWvk0XWnyihd+3ssCgKBXpirylAT1WWZk6d3Ryq
bh7biTpeVqzovEFZpQrm2T8Ym6TMRkbImLo9ObEOyVvP3TyUOUtalgDh1iaqHWkn
AgMBAAE=
-----END PUBLIC KEY-----

We can extract $n$ and $e$ from that file (although we already know that $e = 65537$). Then the idea is to compute $\sqrt{n}$ because we know that $n = p \cdot q$ and $p$ and $q$ are so close (we can guess that are consecutive prime numbers).

So, once $\sqrt{n}$ is computed, we can start decreasing the result until we find a prime number. After that, we just need to increase it to find the next prime number.

Once we have prime numbers $p$ and $q$, the RSA decryption is trivial.

Here we have a Python script that solves the challenge:

#!/usr/bin/env python3

from Crypto.Util.number import isPrime
from Crypto.PublicKey import RSA

from gmpy2 import iroot

c = 4881495507745813082308282986718149515999022572229780274224400469722585868147852608187509420010185039618775981404400401792885121498931245511345550975906095728230775307758109150488484338848321930294974674504775451613333664851564381516108124030753196722125755223318280818682830523620259537479611172718588812979116127220273108594966911232629219195957347063537672749158765130948724281974252007489981278474243333628204092770981850816536671234821284093955702677837464584916991535090769911997642606614464990834915992346639919961494157328623213393722370119570740146804362651976343633725091450303521253550650219753876236656017  

with open('key') as f:
    key = RSA.import_key(f.read())

n = key.n
e = key.e


def get_next_prime(prime: int) -> int:
    test = prime + 2
    while not isPrime(test):
        test += 2
    return test


while True:
    p, _ = iroot(n, 2)

    while not isPrime(p):
        p -= 2

    q = get_next_prime(p)
    n = p * q
    phi_n = (p - 1) * (q - 1)
    d = pow(e, -1, phi_n)
    p = pow(c, d, n)

    if b'SEE{'.hex() in hex(p):
        print(bytes.fromhex(hex(p)[2:]).decode())
        break

$ python3 solve.py
SEE{i_love_really_secure_algorithms_b5c0b187fe309af0f4d35982fd961d7e}

The full script can be found in here: solve.py.