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 documentation of the virtual machine is available on this page.
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
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.