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
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
Solution
This time, the prime numbers
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
- Factor
into and - Respond with
and
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
$