# CodeFest CTF 2017 - Russia Writeup

bySeptember 23, 2017

### Private Keys

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.

Because `private_key`

and `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^{[1]} we need the modular multiplicative inverse **mmi** of `priv_key*(d+1)`

modulo `pub_key`

.

We compute an inverse key for each candidate `private_key`

.

### 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 3^{11} = 177147 possible combinations, few enough to try them all.

Where reverse is

## Proof

Let

- vk = private_key
- ik = inverse_key
- pk = public_key

Given that

`(vk*(d+1) * ik) % pk = 1`

for definition of**mmi**`(vk*(d+1)*x) * ik % pk = (vk*(d+1)*ik) * x % pk`

for commutativity of the multiplication

It follows that `((vk*(d+1)*x) * ik) % pk = 1 * x % pk = x % pk`