brevi moduli

3 minutes to read

We are given the Python source code of the server:

from Crypto.Util.number import isPrime, getPrime, bytes_to_long
from Crypto.PublicKey import RSA

rounds = 5
e = 65537

for i in range(rounds):
    print('*'*10, f'Round {i+1}/{rounds}', '*'*10)

    pumpkin1 = getPrime(110)
    pumpkin2 = getPrime(110)
    n = pumpkin1 * pumpkin2
    large_pumpkin = RSA.construct((n, e)).exportKey()
    print(f'\n🎃Can you crack this pumpkin🎃?\n{large_pumpkin.decode()}\n')

    assert isPrime(_pmp1 := int(input('enter your first pumpkin = '))), exit()
    assert isPrime(_pmp2 := int(input('enter your second pumpkin = '))), exit()  

    if n != _pmp1 * _pmp2:
        print('wrong! bye...')
        exit()

    print()

print(open('flag.txt').read())

Source code analysis

The source code is really simple. It basically creates an RSA private key and shows us the associated public key. We are requested to provide the private key a total of 5 times:

$ nc 94.237.48.144 36050
********** Round 1/5 **********

🎃Can you crack this pumpkin🎃?
-----BEGIN PUBLIC KEY-----
MDcwDQYJKoZIhvcNAQEBBQADJgAwIwIcC5l+O+HbqLmHzutZrecmsJzOiTtoqsNk  
nesPTwIDAQAB
-----END PUBLIC KEY-----

enter your first pumpkin =

RSA background

In RSA, the private key is mainly composed of two prime numbers $p$ and $q$. These numbers are supposed to be large (normally, they have 1024 bits). On the other hand, the public key holds the exponent $e = 65537$ and the modulus $n = p \cdot q$.

The security of this cryptosystem relies on the fact that integer factorization is a computationally hard problem even for powerful computers. Therefore, given the public modulus $n$, we can say that it is impossible to factor it into $p$ and $q$ if no more information is given.

Solution

This time, the prime numbers $p$ and $q$ are very small compared to what the standards recommend. Namely, they are 110-bit integers. There are factorization algorithms that are able to deal with this bit-lengths and are able to factor these modulus in a relatively short time. For instance, the elliptic-curve method (ECM) (also known as Lentra elliptic-curve factorization).

Implementation

The ECM factorization algorithm is implemented in SageMath, as ecm.factor. However, we can use the default factor function because it will actually do the same thing.

As a result, these are the steps to solve each round of the challenge:

Parse the public key and take the modulus $n$
Factor $n$ into $p$ and $q$
Respond with $p$ and $q$

And this is the solution code:

#!/usr/bin/env python3

from pwn import remote, sys
from Crypto.PublicKey import RSA
from sage.all import factor

host, port = sys.argv[1].split(':')
io = remote(host, port)

for _ in range(5):
    io.recvuntil(b'?\n')

    publickey = io.recvuntil(b'-----END PUBLIC KEY-----').decode()
    key = RSA.import_key(publickey)

    (p, _), (q, _) = factor(key.n)
    io.sendlineafter(b'enter your first pumpkin = ', str(p).encode())
    io.sendlineafter(b'enter your second pumpkin = ', str(q).encode())  

io.interactive()

Flag

Here’s the flag:

$ python3 solve.py 94.237.48.144:36050
[+] Opening connection to 94.237.48.144 on port 36050: Done  
[*] Switching to interactive mode

HTB{cracking_pumpkins_and_small_rsa_moduli_for_a_living}
[*] Got EOF while reading in interactive
$