LIT CTF 2023 - polypoint

Description

Category: Cryptography

This encryption scheme is mathematically unbreakable if you don’t have all the keys! You learnt so in grade school, right?

Downloads:

• encode.py
• encoded.txt

Resolution

1. Overview

We have two files:

• encode.py which allows us to find out how to recover the flag;
• encoded.txt the output of encoded.py (contains 10 tuples (x, y)).

In encoded.py we have the varoables:

• poly which contians the flag as long integer and 10 random integers between $10^{11}$ and $10^{12}$;
• 10 random integers from between the same range x;
• 10 integers y after some operations with x and integers in poly.

2. Polynomial

Let’s introduce some notations for the rest of the writeup:

Let $p_{0}, … p_{10}$ the integers from the list poly. Then $p_{0}$ is the flag as long int.

Let $(x_{i}, y_{i})$ the tuple (x, y) at the i-th line (start from 0) in encoded.txt. For example: $x_{0} = 816183152786$

The name of the challenge polypoint should refer to Polynomial and we can indeed find it in the script:

for _ in range(10):
    x = gen.randrange(pow(10, 11), pow(10, 12))
    v = 1
    y = 0
    for i in range(11):
        y += poly[i] * v
        v *= x
    print(f"({x},{y})")

which corresponds to this equation:

\[y_{i} = p_{0} * 1 + p_{1} * x_{i}^{1} + ... + p_{10} * x_{i}^{10} \tag{1}\]

for each $i \in [0 .. 9]$.

And $p_{i}$ are the coefficients of the polynomial of degree 10.

3. Recover $p_{0}$

The coefficients of a polynomial can be recovered if we know enough information about it.

Here we only have 10 equations for 11 unknowns ($p_{i}$) which are not enough to recover the polynomial’s coefficients.

It’s like trying to find a unique straight line (defined with two parameters) knowing only one point, there are an infinite number of lines passing through a point.

But if we know some constrains about the polynomial, we can greatly reduce the number of polynomials that match ours.

And we indeed have constains on $p_{i}$:

• there are integers (obvious but very important);
• there are between $10^{11}$ and $10^{12}$.

Those constrains may not be enough but it worths a try. Here is my Python script to solve it using Z3Prover:

from z3 import *
from ast import literal_eval

L = open("encoded.txt", "r").readlines()
XY = [literal_eval(l.strip()) for l in L]
X, Y = list(zip(*XY))

constrains = []

for i in range(11):
    exec(f"p{i} = Int('p{i}')")
    exec(f"constrains.append(p{i} >= 10**11)")
    exec(f"constrains.append(p{i} <= 10**12)")

for i in range(10):
    exec(f"x{i} = Int('x{i}')")
    exec(f"x{i} = X[i]")
    exec(f"y{i} = Int('y{i}')")
    exec(f"y{i} = Y[i]")

s = Solver()

for i in range(10):
    eq = 0

    for j in range(11):
        exec(f"eq += p{j} * x{i}**j")

    exec(f"s.add(y{i} == eq)")

assert s.check() == sat

We got no errors, that means the problem can be solved.

We solve it and retrieve $p_{0}$ to get the flag:

c = s.model()[p0].as_long()

import binascii
flag = binascii.unhexlify(hex(c)[2:])
print(flag)

LITCTF{h4h4_1ts_n0t_th4t_345y__almOst_ThEre_hAVe_somE_gibbeRish__d6570c3b3f}