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:
In this final challenge, the instruction set of the virtual machine is even more restricted. It will be necessary to use the modular computation coprocessor to perform RSA key generation. This challenge aims to mimic the constraints of a real machine and optimize performance. The coprocessor should be imagined as a dedicated hardware circuit, independent of the processor, executing calculations very efficiently.
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.