This is a writeup of the solution to the CRYPTO challenge of the m0leCon 2021 Finals.

⚠️ Code blocks need to be executed in a Sage environment. They won't work with the vanilla Python interpreter.

## Challenge

I took years to generate this ciphertext, how fast will you decrypt it?

Flag format:

`ptm{...}`

Note: this challenge was released as a "speedrun" in the original CTF (first solvers get more points). The first correct solution was submitted after 8 minutes.

Author: @Drago_1729

Attached with the problem description is its source code: `slooow.zip`

:

`chall.py`

containing the Python source code of an encryption function`output.txt`

containing the encrypted flag

## Preliminary observations

`chall.py`

```
p = (1 << 255) - 19
```

Declared at the top is `p`

, a prime number.

```
def encrypt(flag):
res = []
for i, c in enumerate(flag):
val = f(10**(20+i))
mask = int.from_bytes(sha256(str(val)).digest(), "big")
num = int.from_bytes(sha256(c.encode()).digest(), "big")
res.append((mask*num) % p)
return res
```

Next, we can see the encryption algorithm. For every letter of the plaintext, identified by the index $i$, it computes a value `val`

using function `f`

with argument $10^{20 + i}$. That value and the character are hashed separately and then multiplied together modulo `p`

. The result is appended into an array and returned.

```
def f(n):
res = 5
for _ in range(n):
res = (res**2-2) % p
return res
```

Taking a closer look at function `f`

we can see that the function $x_n = x_{n - 1}^2 - 2 \ \text{mod} \ p$ (where $x_0 = 5$) is iterated `n`

times. Keeping in mind that `n`

will be *at least* $10^{20}$, we can safely assume that it is impractical to compute `f`

as is.

`output.txt`

```
[28335972461715929029549703474744235564956581966750837731515436991813559294419,
37403273962683825476706766986016116652096926190225822145906203630154751124127,
...
20683259830940408896673758833391608352503039219404794272476581194379608541097,
55414473181295446142015440809398852386813618115944521051995707998928249796248]
```

The output file contains an array of 54 integers, of 256 bits each. We can safely assume that this is the output of the `encrypt`

function with the flag given as plaintext.

## Searching for a closed form solution

Knowing that it is fairly impractical to get any information from the sha256 output digests, we must find a way to simplify function `f`

, ideally bringing down the complexity from $\mathcal{O}(N)$ to $\mathcal{O}(1)$, where $N=n$.

Searching around for closed form solutions to iterated functions, we can learn that:

$$x_n \mapsto a x_{n - 1}^{2}+b x_{n - 1} +{\frac {b^{2}-2b-8}{4a}}$$

has a closed form:

$$n \mapsto {\frac {2\alpha ^{2^{n}}+2\alpha ^{-2^{n}}-b}{2a}}$$

where:

$$\alpha ={\frac {2ax_0+b\pm {\sqrt {(2ax_0+b)^{2}-16}}}{4}}$$

In our specific case we have coefficients $a = 1$ and $b = 0$.

So now we can simply calculate $\alpha$, plug it into the closed form along with $n = 10^{20+i}$ and decode every character of the flag?

Not so fast... The iterated function for which we found a closed form generates an **always increasing sequence of integers**. Our function `f`

operates under $\text{mod} \ p$, so instead we get a still huge but eventually **cyclic sequence of integers**. To get to our desired close form we must keep this in mind.

## A walk in the finite field woods

Taking a closer look at the equation for $\alpha$, we can observe that it's in the form of a quadratic formula. So $\alpha$ is the root of a second degree polynomial with coefficients $a = 2$, $b = -(2ax_0 + b)$ and $c = 2$. In our case the polynomial would look like $2x^2 - 10x + 2$. Our objective now is to **find the roots of this polynomial** $\text{mod} \ p$.

We can represent the polynomial ring in one indeterminate over a finite field $\text{GF}(p)$. We can then find the roots of this polynomial:

```
sage: F.<alpha> = GF(p)
sage: R.<x> = PolynomialRing(F, 'x')
sage: f = 2 * x^2 - 10 * x + 2
sage: f.roots(multiplicities=False)
[]
```

Oh! No roots? That seems odd. Let's check if the polynomial is irreducible in this polynomial ring.

```
sage: f.is_irreducible()
True
```

We can leverage field extension theory to deduce that this is due to the fact that the roots of a second degree polynomial do not belong to $\text{GF}(p)$, but instead they are part of $\text{GF}(p^2)$.

```
sage: F.<alpha> = GF(p^2)
sage: R.<x> = PolynomialRing(F, 'x')
sage: f = 2 * x^2 - 10 * x + 2
sage: roots = f.roots(multiplicities=False)
sage: roots
(7135491744499822517601019775201591905370636666957345689383307065704368190844*alpha + 32515768181578960114693256139772772916002814499888813854556049534830466505399,
50760552874158275194184472729142362021264355665862936330345484938252196629105*alpha + 25380276437079137597092236364571181010632177832931468165172742469126098314555)
```

Bingo! We have $\alpha \ \text{mod} \ p$.

## Big powers

Now we can apply the mapping $n \mapsto {\frac {2\alpha ^{2^{n}}+2\alpha ^{-2^{n}}-b}{2a}}$ to retrieve the $n$-th element of the sequence $\text{mod} \ p$. Taking into account our coefficient, we can simplify the mapping to $n \mapsto \alpha ^{2^{n}}+\alpha ^{-2^{n}}$.

So let's compute the $10^{20}$-th element:

```
sage: roots[0]^(2^(10^20))+roots[0]^(-2^(10^20))
OverflowError: exponent must be at most 9223372036854775807
```

We have a small problem, the $2^{10^{20}}$ has $30102999566398119522$ decimal digits, while the maximum supported exponent has only $19$ decimal digits. We need to find a way to simplify this power.

Luckily we can leverage the multiplicative order of $\alpha$, defined for $a \ \text{mod} \ p$ as the smallest positive integer $k$ such that $a^k \equiv 1 \ \text{mod} \ p$. Using this notion we can deduce that $a^n \ \text{mod} \ p = a^{n \ \text{mod} \ k} \ \text{mod} \ p$, so instead of computing the power we can computer the power $\text{mod} \ k$ using the square-and-multiply algorithm.

Knowing this we can finally rewrite `f`

as:

```
def f(i):
cc = roots[0]^2.powermod(i, roots[0].multiplicative_order())
return cc + 1 / cc
```

## Cracking the code

Having greatly simplified function `f`

, we can simply brute-force each character by computing sha256 digests of printable character.

```
dictionary = {}
for i in printable:
dictionary[int.from_bytes(sha256(i.encode()).digest(), "big")] = i
def match(mask, c):
for item in dictionary:
if (item * mask) % p == c:
return dictionary[item]
raise Exception("No match found")
def decrypt(cypher):
res = []
for i, c in enumerate(cypher):
val = f(10^(20+i))
mask = int.from_bytes(sha256(str(val).encode()).digest(), "big")
res.append(match(mask, c))
return res
```

Executing `decrypt`

on the output yields the correct flag!

```
sage: "".join(decrypt(output))
```