# CodeFest CTF 2017 - Russia Writeup

by chq-matteo
September 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 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 311 = 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

1. `(vk*(d+1) * ik) % pk = 1` for definition of mmi
2. `(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`