Blog by grhkm

Algebra (831 pts, 14 solves)

Introduction

Our team Black Bauhinia participated in the TetCTF 2022 which spans two days. Algebra is the hardest Crypto challenge in the CTF. Mystiz and I (grhkm) together spent around 7 hours on this challenge.

Problem Statement

Description: I threw some arbitrary operator into a finite field and, interestingly, I got a group!

Service: nc 139.162.61.222 13374

Binary: https://drive.google.com/file/d/1_fe-o44NH3pjHVLS_Bk965BPHO6QnVvO/view?usp=sharing

Solution Outline

$x_3 = f(x_1, x_2)$ satisfies $\frac{1}{x_3} = [x^0]\left[\big(x + \frac{1}{x_1}\big)\big(x + \frac{1}{x_2}\big)\text{.monic()}\right]\ \text{mod}\ (x^2 + 2Cx + 1)$, where $[x^0]P(x)$ is the constant term of the polynomial after reduction. From this, we obtain $c = f^m(a)f^n(b) = [x^0]\left[\big(x - a^{-1}\big)^m\big(x - b^{-1}\big)^n\right]\ \text{mod}\ (x^2 + 2Cx + 1)$. Realizing that $\sqrt{C^2 - 1}$ exists in $\mathbb{F}_p$, we apply CRT to get two relations $(r_i - a^{-1})^m(r_i - b^{-1})^n \equiv k(r_i - c^{-1})$ where $k$ is the linear coefficient. Dividing the two equations gives the desired fa, fb and fc.

Disclaimer

There was quite a lot of luck, random guessing, looking through irrelevant papers and ranting on Twitter. Instead of showing all that, I will first go through the final solution with proof. I will then show how one might approach future similar problems i.e. how one could have solved the problem semi-systematically. That way, everyone learns instead of seeing an IMO-inequality-like solution!

Problem Objective

We are given a single script algebra.py.

from random import randint

p = 50824208494214622675210983238467313009841434758617398532295301998201478298245257311594403096942992643947506323356996857413985105233960391416730079425326309
C = 803799120267736039902689148809657862377959420031713529926996228010552678684828445053154435325462622566051992510975853540073683867248578880146673607388918

INFINITY = "INF"

def op(x1, x2):
    # Returns (x1 + x2 + 2 * C * x1 * x2) / (1 - x1 * x2)
    if x2 == INFINITY:
        x1, x2 = x2, x1
    if x1 == INFINITY:
        if x2 == INFINITY:
            return (-2 * C) % p
        elif x2 == 0:
            return INFINITY
        else:
            return -(1 + 2 * C * x2) * pow(x2, -1, p) % p
    if x1 * x2 == 1:
        return INFINITY
    return (x1 + x2 + 2 * C * x1 * x2) * pow(1 - x1 * x2, -1, p) % p

def repeated_op(x, k):
    s = 0
    while k > 0:
        if k & 1:
            s = op(s, x)
        k = k >> 1
        x = op(x, x)
    return s

assert op(op(2020, 2021), 2022) == op(2020, op(2021, 2022)) # associativity
assert repeated_op(2022, p - 1) == 0 # order p - 1

a, b = [randint(0, p - 1) for _ in range(2)]
m, n = [randint(0, p - 2) for _ in range(2)]
c = op(repeated_op(a, m), repeated_op(b, n))
print(a)
print(b)
print(c)

# give me f(a), f(b), f(c)
fa = int(input())
fb = int(input())
fc = int(input())
print(pow(fa, m, p), pow(fb, n, p), fc)
if pow(fa, m, p) * pow(fb, n, p) % p == fc:
    flag = 'FLAG' * 30
    print(flag[:pow(fc, 4, p)])

Interestingly, the assertion statements hint at that the operator is associative and has order $p - 1$.

Solution

From this point onwards, all arithmetic are under $\mathbb{F}_p[x]$. First, investigating the operator in Sage shows the operator is indeed associative and commutative.

sage: f = lambda x, y: (x + y + 2 * C * x * y) / (1 - x * y)
sage: C = var('C')
sage: x, y, z = var('x, y, z')
sage: (f(f(x, y), z) - f(x, f(y, z))).full_simplify()
0
sage: (f(x, y) - f(y, x)).full_simplify()
0

This means that the notation $f(x_1, x_2, \ldots, x_n)$ is not ambiguous.

Here, there is a theorem that seems to be unknown to the public. It is called the Mystiz God Theorem, which states that

Given the correct time of the day (preferably 3-6am), a hard enough problem and that no one is observing him on Discord, Mystiz will turn into a God and solve every Crypto challenge.

Here, the theorem’s conditions are satisfied, and he proposed the following. Consider the polynomial $\big(x - \frac{1}{x_1}\big)\big(x - \frac{1}{x_2}\big)\ \text{mod}\ (x^2 + 2Cx + 1)$. We have

$$\begin{align*} \big(x - \frac{1}{x_1}\big)\big(x - \frac{1}{x_2}\big) &\equiv x^2 - \frac{x_1 + x_2}{x_1x_2}x + \frac{1}{x_1x_2} \\ &\equiv -(2C + \frac{x_1 + x_2}{x_1x_2}\big)x + \big(\frac{1}{x_1x_2} - 1\big) \\ &\equiv -\frac{x_1 + x_2 + 2Cx_1x_2}{x_1x_2}x + \frac{1 - x_1x_2}{x_1x_2} \\ &\equiv -\frac{x_1 + x_2 + 2Cx_1x_2}{x_1x_2}\big(x - \frac{1 - x_1x_2}{x_1 + x_2 + 2Cx_1x_2}\big) \\ &\equiv k(x - \frac{1}{f(x_1, x_2)})\ \text{for some}\ k. \end{align*}$$

Mystiz God Theorem Use Case

From this, it is easy to see that

$$\big(x - \frac{1}{x_1}\big)\big(x - \frac{1}{x_2}\big)\big(x - \frac{1}{x_3}\big)\equiv k_1\big(x - \frac{1}{f(x_1, x_2)}\big)\big(x - \frac{1}{x_3}\big)\equiv k_2\big(x - \frac{1}{f(x_1, x_2, x_3)}\big)\ \text{mod}\ (x^2 + 2Cx + 1)$$

$$\prod_{i=1}^n \big(x - \frac{1}{x_i}\big)\equiv k\big(x - \frac{1}{f(x_1, x_2, \ldots, x_n)})\ \text{mod}\ (x^2 + 2Cx + 1)$$

In particular, we have

$$k\Big(x - \frac{1}{f(f^m(a), f^n(b))}\Big)\equiv\Big(x - \frac{1}{a}\Big)^m\Big(x - \frac{1}{b}\Big)^n\ \text{mod}\ (x^2 + 2Cx + 1)$$

From this it is hard to get any information, as $k$ is a complicated expression dependent on $a$ and $b$. Instead, we hope to factor $x^2 + 2Cx + 1$ into linear factors. Going back to Sage, we see that this is indeed possible:

sage: p = 50824208494214622675210983238467313009841434758617398532295301998201478298245257311594403096942992643947506323356996857413985105233960391416730079425326309
sage: C = 803799120267736039902689148809657862377959420031713529926996228010552678684828445053154435325462622566051992510975853540073683867248578880146673607388918
sage: x = PolynomialRing(GF(p), 'x').gen(0)
sage: (x^2 + 2 * C * x + 1).factor()
(x + 22028781193260601150215372852743243072534054369034373355826026755141703972839605913903845829450804221333172177888152011390316978343515577032315535048272856)
* (x + 30403025541489493604800988683343385662063299229646452236323267699080879682775308287796866138143113667746438130490796553103815494624941972144707891591831289)

Denote the two roots be $r_1$ and $r_2$ i.e. $x^2 + 2Cx + 1\equiv(x - r_1)(x - r_2)\ \text{mod}\ p$. Taking the modulo relation above modulo each of the linear factors, we have

$$k\Big(x - \frac{1}{c}\Big)\equiv\Big(x - \frac{1}{a}\Big)^m\Big(x - \frac{1}{b}\Big)^n\ \text{mod}\ (x - r_i).$$

Notice that $x - a\equiv r - a\ \text{mod}\ (x - r)$. Therefore, we have

$$\begin{cases}k\Big(r_1 - \frac{1}{c}\Big)\equiv\Big(r_1 - \frac{1}{a}\Big)^m\Big(r_1 - \frac{1}{b}\Big)^n\ \text{mod}\ (x - r_1) \\ k\Big(r_2 - \frac{1}{c}\Big)\equiv\Big(r_2 - \frac{1}{a}\Big)^m\Big(x - \frac{1}{b}\Big)^n\ \text{mod}\ (x - r_2).\end{cases}$$

Since all the terms are numbers i.e. constant polynomials, we can conveniently get rid of the modulo’s:

$$\begin{cases}k\Big(r_1 - \frac{1}{c}\Big)\equiv\Big(r_1 - \frac{1}{a}\Big)^m\Big(r_1 - \frac{1}{b}\Big)^n\ \text{mod}\ p \\ k\Big(r_2 - \frac{1}{c}\Big)\equiv\Big(r_2 - \frac{1}{a}\Big)^m\Big(r_2 - \frac{1}{b}\Big)^n\ \text{mod}\ p.\end{cases}$$

Finally, recall that our goal is to

Provide three non-trivial values $f_a$, $f_b$ and $f_c$ such that $f_a^mf_b^n\equiv f_c\ \text{mod}\ p$.

Do you see it?

.

.

.

Dividing the equations, we get

$$\frac{cr_1 - 1}{cr_2 - 1}\equiv\Big(\frac{ar_1 - 1}{ar_2 - 1}\Big)^m\Big(\frac{br_1 - 1}{br_2 - 1}\Big)^n\ \text{mod}\ p$$

That’s it!

I was so excited and I SHOULD BE

Code

from pwn import *

r = remote('139.162.61.222', 13374)
INFINITY = "INF"
p = 50824208494214622675210983238467313009841434758617398532295301998201478298245257311594403096942992643947506323356996857413985105233960391416730079425326309
C = 803799120267736039902689148809657862377959420031713529926996228010552678684828445053154435325462622566051992510975853540073683867248578880146673607388918

def send(s):
    r.sendline(str(s).encode())

a = PolynomialRing(GF(p), 'a').gen(0)
r1, r2 = [GF(p)(-u.coefficients()[0]) for u, _ in factor(a ** 2 + 2 * C * a + 1)]

x = PolynomialRing(GF(p), 'x').quotient(x ** 2 + 2 * C * x + 1).gen(0)
a, b, c = [ZZ(r.recvline()) for _ in range(3)]
a, b, c = Mod(a, p), Mod(b, p), Mod(c, p)
r.sendline(str((a * r1 - 1) / (a * r2 - 1)).encode())
r.sendline(str((b * r1 - 1) / (b * r2 - 1)).encode())
r.sendline(str((c * r1 - 1) / (c * r2 - 1)).encode())
print(r.recvline().decode().strip())

Flag: TetCTF{1_just_l0v3_th3_un1t_c1rcl3_s0_much}


Motivation

Here, I suggest a path one might try to systematically find the form above. The thing I like about this approach is most of this is doable on paper apart from the final computations.

Firstly, it is natural to look for fixed point of the function. So let’s try!

$$\begin{align*} f(x_1, x_2) &= x_1 \\\\ \frac{x_1 + x_2 + 2Cx_1x_2}{1 - x_1x_2} &= x_1 \\\\ x_1 + x_2 + 2Cx_1x_2 &= x_1 - x_1^2x_2 \\\\ x_2(x_1^2 + 2Cx_1 + 1) &= 0 \end{align*}$$

We see that the roots of $x_1^2 + 2Cx_1 + 1$ are fixed points. In Sage, we can further verify that $\left(\frac{C^2 - 1}{p}\right) = 1$, so such $x_1$ indeed exists. It is then natural to guess that the group structure might be a quotient ring, and that $M(x) = x^2 + 2Cx + 1$ is the quotient.

Mystiz suggesting ideas

Now let’s take a look at $f(x_1, x_2)$ under our assumption.

$$\begin{align*} f(x_1, x_2) &\equiv \frac{x_1 + x_2 + 2Cx_1x_2}{1 - x_1x_2} \\\ f(x_1, x_2) &\equiv \frac{\frac{1}{x_1} + \frac{1}{x_2} + 2C}{\frac{1}{x_1x_2} - 1} \\\ \left(\frac{1}{x_1x_2} - 1\right)f(x_1, x_2) &\equiv \frac{1}{x_1} + \frac{1}{x_2} + 2C \\\ (x_1x_2 - 1)f(\frac{1}{x_1}, \frac{1}{x_2}) &\equiv x_1 + x_2 + 2C \end{align*}$$

We see that the right-hand side has a linear expression $x_1 + x_2 + 2C$, while the left-hand side has a product $x_1x_2 - 1$. We might think of something like Vieta’s Theorem or quadratic factoring in general, where we have $(x - x_1)(x - x_2) = x^2 - (x_1 + x_2)x + x_1x_2$. What if we try it here?

$$\begin{align*} (x_1 + x_2 + 2C)x &\equiv x_1x_2 - 1 &\mod{x^2 + 2Cx + 1} \\\ (x^2 + 2Cx + 1) - (x_1 + x_2 + 2C)x + (x_1x_2 - 1) &\equiv 0 &\mod{x^2 + 2Cx + 1} \\\ x^2 - (x_1 + x_2)x + x_1x_2 &\equiv 0 &\mod{x^2 + 2Cx + 1} \\\ (x - x_1)(x - x_2) &\equiv 0 &\mod{x^2 + 2Cx + 1}\end{align*}$$

Woah! So to summarise, we have that

$$(x_1 + x_2 + 2C)x - (x_1x_2 - 1)\equiv (x - x_1)(x - x_2)\mod{x^2 + 2Cx + 1}.$$

Now notice that the root of the linear term is $\frac{x_1x_2 - 1}{x_1 + x_2 + 2C} = \frac{1}{f(\frac{1}{x_1}, \frac{1}{x_2})}$, which means we can write the relation as

$$\begin{align*}k(x - \frac{1}{f(\frac{1}{x_1}, \frac{1}{x_2})}) &\equiv (x - x_1)(x - x_2) &\mod{x^2 + 2Cx + 1} \\\ k(x - \frac{1}{f(x_1, x_2)}) &\equiv (x - \frac{1}{x_1})(x - \frac{1}{x_2}) &\mod{x^2 + 2Cx + 1}\end{align*}$$

The rest is the same as above.

Other Methods

In our Solution section, we found that $x\mapsto\frac{r_1x - 1}{r_2x - 1}$ is the desired map. Indeed, many people (such as @hellman and @rkm0959) solved it by letting the map be $x\mapsto\frac{ax + b}{cx + d}$ and looked at fixed points / points with small orders.

In the CTF, Mystiz and I also found that when we change $C$ to random values, sometimes points have order $p^2 - 1$ instead of $p - 1$. This is now explained, as $x^2 + 2Cx + 1 = (x - r_1)(x - r_2)$ have roots in $\mathbb{F}_{p^2}$ when $C^2 - 1$ is a quadratic non-residue, which the field has order $p^2 - 1$.