CodeFest CTF 2017 - Russia Writeupby
September 23, 2017
Reading the source file we understand that the
private_key and the
public_key are one of the prime numbers generated by
valid_primes_sieve(). They are also greater than
(d+1)*max_input = 11 * 255.
We can compute the list of all the valid private keys.
public_key are different, we only need to try 29.
First Step: modular arithmetics
The first step of the encryption algorithm is to compute
(priv_key*(d+1)*x)%(pub_key) for each
x in the input.
In order to reverse this step we need the modular multiplicative inverse mmi of
We compute an inverse key for each candidate
Second Step: random salt
In the second step a random integer in [1, 3] is added to each value of the cypher text. Since the cypher text is 11 values long, there are only 311 = 177147 possible combinations, few enough to try them all.
Where reverse is
- vk = private_key
- ik = inverse_key
- pk = public_key
(vk*(d+1) * ik) % pk = 1for definition of mmi
(vk*(d+1)*x) * ik % pk = (vk*(d+1)*ik) * x % pkfor commutativity of the multiplication
It follows that
((vk*(d+1)*x) * ik) % pk = 1 * x % pk = x % pk