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:
The objective is the same as in the first challenge: to produce code that generates RSA keys. However, in this second challenge, access to certain instructions in the virtual machine is restricted to prevent the use of the Euclidean algorithm.
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.