HACKVent 2014 - Day 17 writeup
I’ve sign up for the Hackvent event made by the guys from www.hacking-lab.com, which is a advent-like hacking competition. Every day there is a new challenge posted at midnight which has a to solved at best in the same day, the challenge becoming increasingly more difficult every week completed. The aim in every puzzle is to find either a qr-encoded x-mas ball with lead to the validation code, or a secret human-readable string which gives you the former ball when feeding into a validator (the “Ball-O-Matic”).
Here’s the write-up for the challenge at day 17, in which we will crush handshake.
RZA distant cousin Part :
For the Day 17 Hackvent challenge, we were given the following instructions :
The instructions are pretty straightforward : we have to break RSA encryption ! Fortunately, the chosen primes number are ridiculously low. The difficulty in this challenge is to automate the process in order to relieve ourselves from a really boring task.
First we have to find the two primes numbers which forms n, which means we have to factor n :
It’s not really readable, but it’s a little python function which test all integer between 1 and root square of n. It’s quite fast actually.
Now that we have p and q, we can compute
phi = (p-1)*(q-1) which is the modulus used to compute d. d, the decryption key, is the modular inverse of e in N/phiN :
Using the number d, we get decrypt the ciphertext c using the following equation :
dec = (int(c)**d) % (n)
Since there is 178 public keys to break and the task is highly parallelizable, it’s recommended to use threads or any other mutliprocessing tool (or even better, a GPU based routine). Don’t forget to output the worker’s index since the decoded texts won’t be in order.
This python script is quite efficient :
After some formating and ascii conversion, we get the following text :
God could create the world in six days because he didn't have to make it compatible with the previous version. If we're supposed to work in Hex, why have we only got 0xA fingers?