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)])
- A prime modulo $p$ and a
randomconstant $C$ is fixed. - A binary operator is defined as $f(x_1, x_2) := \frac{x_1 + x_2 + 2Cx_1x_2}{1 - x_1x_2}$
- $f^n(x_1) = f(f^{n - 1}(x_1), x_1)$
- Four secret variables are then chosen randomly
- $a, b\in [0, p - 1]$
- $m, n\in [0, p - 2]$
- We are given the values of $a, b$ and $f(f^m(a), f^n(b))$
- We have 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$.
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*}$$
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!
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.
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$.