Description
As a reminder, the RSA system is an asymmetric cryptography mechanism based on the problem of factoring large integers.
For a public exponent e and a size t in bits, two prime numbers p and q are generated such that p - 1 and q - 1 are coprime with e.
The product p * q of t bits defines the public modulus N, then d is computed as the modular inverse of e modulo phi(N) = (p - 1) * (q - 1).
To compute a modular inverse, the extended Euclidean algorithm is often used. However, it is difficult to protect this algorithm against physical attacks.
The goal is to perform RSA key generation without using the Euclidean algorithm.
This challenge is one of a series of three that we strongly advise you to solve in order:
This first challenge simply consists of performing RSA key generation in assembly in order to pass the tests. The following values must be generated:
pandqiqsuch thatq * iq = 1 mod pdpanddq, such thate * dp = 1 mod (p - 1)ande * dq = 1 mod (q - 1)dsuch thate * d = 1 mod phi(N)N = p * q, exactly matching the bit size given as input.
The virtual machine is initialized with a public exponent and a bit size.
Files
- docker-compose.yml
-
assembly.py
20.84 KiB – db186ab7dfb5f5e7f4790f1afc951deda349a8a9565a57b6328da2ba89965525 -
crypto_accelerator.py
5.14 KiB – 4c1f070435b6e4eace3fa19e5a4b661800ec8ad61895e378dab5d892aa89e2a7 -
machine.py
19.96 KiB – 048716eab19f32556b08fbea73a07b641f29fa0ff795abd407ead484e3d5041c -
machine_restricted.py
1.30 KiB – c9b1a3e5f9f5b681efeacd41dec3269c29c92d08ed8c7bb54874cc4c894727fa -
no-divide-just-conquer.py
3.20 KiB – aced4cbb271d638c751594917edd7e7ffc8137f3590f6e1063c1cd6b3dde98c5 -
vm.md
27.75 KiB – 0d241df97205c1ea035561b006926949e768e749d997f43f50569e416ee11cdc
Author
Challenge Instructions
- First, download docker-compose.yml:
curl https://hackropole.fr/challenges/fcsc2025-hardware-no-divide-just-conquer/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.