CodeFest CTF 2017 - Russia Writeup

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.

    candidates = [prime for prime in valid_primes_sieve().values() if prime > (d+1)*max_input]
    print(len(candidates)) # prints 30

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.

    inverse_keys = [mmi(candidate*(d+1), public_key) for candidate in candidates if candidate != public_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¹¹ = 177147 possible combinations, few enough to try them all.

    for s0 in range(1, 4):
        for s1 in range(1, 4):
            ...
            for s10 in range(1, 4):
                reverse([s0, s1, s2, s3, s4, s5, s6, s7, s8, s9, s10])

Where reverse is

def reverse(salt):
    for inverse_key in inverse_keys:
        plain_text = [((inverse_key * (ciphter_text[i] - salt[i])) % public_key) for i in range(len(cipher_text))]
        respects_limits = True
        for value in plain_text:
            respects_limits = respects_limits and (value < 256 and value >= 2)
        if respects_limits:
            print(mmi(inverse_key, pk)/11)

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