# m0leCon CTF 2020 Teaser — King Exchange

*all images are clickable*

The given zip-archive contains two files: a python script and its output.

**server.py**:

**output.txt**:

```
(70584838528566138057920558091160583247156394376694509226477175997005624, 47208562635669790449305203114934717034939475647594168392271311241505021)
(28274152596231079767179933954556001021066477327209843622539706192176128, 99565893173481261433550089673695177934890207483997197067732588009694082)
aaa21dce78ef99d23aaa70e5d263719de9245f33b8a9e2a0a63c8847dba61296c5a1f56154b062d3a347faa31b8d8030
```

The encryption algorithm is straightforward: it uses AES-ECB with unknown key and prints out a ciphertext.

```
aaa21dce78ef99d23aaa70e5d263719de9245f33b8a9e2a0a63c8847dba61296c5a1f56154b062d3a347faa31b8d8030
```

We need to recover the key, let’s find out how it was generated.

The challenge performs some kind of Diffie-Hellman key exchange with unknown modulus `p`

(we will back to this later). It means that server generates two secret values `a`

and `b`

, multiplies the generator `g`

by these secret values and prints out resulting `A = g * a`

and `B = g * b`

.

```
g = (0x43bf9535b2c484b67c68cb98bace14ae9526d955732e2e30ac0895ab6ba,
0x4a9f13a6bd7bb39158cc785e05688d8138b05af9f1e13e01aaef7c0ab94)
A = (70584838528566138057920558091160583247156394376694509226477175997005624,
47208562635669790449305203114934717034939475647594168392271311241505021)
B = (28274152596231079767179933954556001021066477327209843622539706192176128,
99565893173481261433550089673695177934890207483997197067732588009694082)
```

The shared key (the same key for AES encryption) is calculated as `S = A * b = B * a`

.

We need to obtain `a`

or `b`

, that means we need to solve a well-known discrete logarithm problem.

The main mystery there is *which group we’re working in*? Let’s take a closer look on functions `multiply`

and `add_points`

.

`multiply(P, n)`

is a simple double-and-add algorithm for faster `P * n`

multiplication.

This `P + Q`

operation is not so obvious (at least at the first sight), but it reminded me the addition law on Edwards elliptic curves:

It brought me to a solution. The `d`

parameter in denominator is a curve parameter which has the form:

If we set `d = 0`

in the fractions below then we will get our addition algorithm — notice that the both numerators of fractions are equal to our `add_points`

result. But what will happen if we set `d = 0`

in Edwards curve equation?

That’s right! With `d = 0`

it becomes just a circle. That case is also mentioned in Wikipedia article:

Ok, now we’ve got the curve we’re working on. `A`

, `B`

and `g`

are points on the circle.

Remember unknown modulus `p`

? Now we are able to recover it. From circle equation we get:

`A[0]^2 + A[1]^2 == 1 (mod p)`

`B[0]^2 + B[1]^2 == 1 (mod p)`

Move `1`

to the left side and rewrite the module condition:

`A[0]^2 + A[1]^2 - 1 == k1 * p`

`B[0]^2 + B[1]^2 - 1 == k2 * p`

Now `p`

is the common divisor (probably, greatest) of the left sides of the equation. Using Euclidean algorithm we could recover it.

The given `p`

is prime, so we’re lucky, it is our modulus! But we still need to solve discrete logarithm.

After some searching I’ve found a question on StackExchange, where the author is asking why we use elliptic curves instead of other curves (such a circle) in cryptography. The answer gives a link to paper with a proof that the discrete logarithm in the circle group is no stronger than the discrete logarithm over the underlying field.

There was suggested a map (paragraph 3) from a circle group to `Fp[W]/(W^2 + 1)`

(where `Fp = GF(p)`

):

So I’ve tried to rewrite it in sage and run standart `discrete_log`

function.

We’re lucky again, after some seconds it was printed the secret `b`

! In the general case we would need to check smoothness of the field order and other parameters, but here it’s not required — sage did its job.

Now we easily can calculate `shared`

key and decrypt the flag:

The flag is `ptm{c1rcl3s_r_n0t_4s_53cur3_4s_ell1ps3s}`

.