Description
We recovered a message that was encrypted by an old server using RSA-CRT. Unfortunately, the server being a very bad shape, it can only perform a single signature at a time (or a decryption operation, which is the same operation) but this operation goes wrong. We believe that an error is introduced during the computation of one the two modular exponentiations.
You need to recover the private key to decrypt the message.
The server performs the encryption in the following way (in Python):
m = int.from_bytes(b "Test message", "big")
c = pow(m, e, n)
The server performs the decryption (or signature) as follows:
n = p * q
dp = d % (p - 1)
dq = d % (q - 1)
cp = pow(m, dp, p)
cq = pow(m, dq, q)
_, a, b = egcd(p, q) # Extended GCD
m = (a * p * cq + b * q * cp) % n
To convert the message into a sequence of bytes, use:
m = m.to_bytes((m.bit_length() + 7) // 8, "big")
Files
Author
Challenge Instructions
- First, download docker-compose.yml:
curl https://hackropole.fr/challenges/fcsc2023-hardware-un-truc-qui-cloche/docker-compose.public.yml -o docker-compose.yml - Launch the challenge by executing in the same folder:
docker compose up - Then, in another console, access the challenge with Netcat:
nc localhost 4000
In case you encounter problems, please consult the FAQ.
Flag
Submit your solution
You can submit your writeup for this challenge. Read the FAQ to learn how to proceed.
You need to be logged in to submit a writeup.
Writeups
There are no public solutions for this challenge yet, but you can submit yours after getting the flag.