# Some Note for UIUCTF2022 Crypto Challenges

## wringing_rings

import sympy as sp
import random
import signal
from secret import FLAG

secret = random.SystemRandom().randint(1, 500_000)

_MAX = 10 ** (len(str(secret)) - 1)

# generating a polynomial
def _f(secret, minimum=3):
    coeffs = [secret] + [
        random.SystemRandom().randint(1, _MAX) for _ in range(minimum - 1)
    ]

    # print("Secret Polynomial:")
    # f_str = str(secret)
    # for i, coeff in enumerate(coeffs[1:]):
    #     f_str += " + " + str(coeff) + "*x^" + str(i + 1)
    # print(f_str)

    def f(x):
        res = 0
        for i, coeff in enumerate(coeffs):
            res += coeff * x ** (i)

        return res

    return f

def gen_shares(secret, minimum=3):
    f = _f(secret, minimum)
    shares = [(i + 1, f(i + 1)) for i in range(minimum)]
    return shares


def challenge(secret, minimum=3):
    shares = gen_shares(secret, minimum)
    points = random.sample(shares, minimum - 1)
    points.sort()
    return points


def main():
    minimum = 10
    points = challenge(secret, minimum)

    print("[SSSS] Known shares of the secret polynomial: ")
    for point in points:
        print(f"       {point}")
    print()

    signal.alarm(60)
    guess = int(input("[SSSS] Enter my secret: "))
    if guess == secret:
        print(f"[SSSS] Correct! {FLAG}")
    else:
        print("[SSSS] Incorrect...")

if __name__ == "__main__":
    main()

This is related to [Shamir's Secret Sharing(SSS) scheme](https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing). But secret polynomial is integer polynomial, not over finite field.

### Interpolation of Polynomial
The scheme is based on the fact that univarite polynomial $f(x)$ whose degree $d$ is uniquely determined as distinct $(d+1)$ points $(x_0, f(x_0)),\ldots,(x_d, f(x_d))$. This fact can be explained as [Chinese Remainder Theorem(CRT)](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) over univariate polynomial.

If $f(x_i)=y_i$, then
$$
f(x) = y_i \mod{(x-x_i)}
$$
by [polynomial remainder theorem](https://en.wikipedia.org/wiki/Polynomial_remainder_theorem). CRT states that we can recover polynomial $F(x)$ such that
$$
F(x) = y_i \mod{(x-x_i)}\ (i=0,1,\ldots, d)
$$ uniquely defined over
$$
\mod{\prod_i{ (x-x_i)}}\ .
$$ $\deg(F)=d$ (same as $f(x)$) and $\deg(\prod_i{(x-x_i)})=d+1$, we have $F(x)=f(x)$ by modulus uniqueness.

[Lagrange Interpolation](https://en.wikipedia.org/wiki/Lagrange_polynomial) represents explicit formula of recovered polynomial.

$$
F(x)=\sum_i y_i \frac{\prod_{j\ne i} (x-x_j)}{\prod_{j\ne i}(x_i-x_j)}
$$

Note that the polynomial may not be over the integer ring $\mathbb{Z}[x]$, but the rational field $\mathbb{Q}[x]$. This causes an vulnerablility for integer version of SSS.

### My First Solution of the Challenge
In the challenge, we have to find secret whose determined as $f(0)=\mathbb{secret}$ for degree 9 polynomial $f(x)$ by given 9 points. At first glance, we cannot recover unique polynomial $f(x)$ by 9 points only. However, the condition that recovered polynomial is over $\mathbb{Z}[x]$ is so restrictive.

My solution is straightforward. I recovered polynomial $f(x)$ by adding symbolical point $(0, t)$ ($t$ is variable). Then, I solved the equation for all coefficient of $f(x)$ is in $\mathbb{Z}$, that is, the numerator modulo the denominator is $0$. The solution is $\mathbb{secret}$.

This leads me the folowing code.

from pwn import *
import cypari2
from Crypto.Util.number import *
from sympy.ntheory.modular import solve_congruence

proc = remote('ring.chal.uiuc.tf', 1337)
proc.recvline()
proc.recvline()

minimum = 10
points = []
for _ in range(minimum-1):
    points.append(eval(proc.recvline().strip(b'\n').split(b"       ")[1]))
print(points)

pari = cypari2.Pari()

result = None
for ele in points:
    if result == None:
        result = pari.Mod(ele[1], (pari('x') - ele[0]))
    else:
        result = pari.chinese(result, pari.Mod(ele[1], (pari('x')-ele[0])))
print(result)
result = pari.chinese(result, pari.Mod(pari('t'), pari('x')))
print(result)

tequ = []
resultpol = result.lift()
for i in range(1, minimum):
    coef = pari.polcoeff(resultpol, i, pari('x'))
    numer = pari.numerator(coef, 1)
    denom = int(pari.denominator(coef, 1))
    tequ.append((-inverse(int(pari.polcoeff(numer, 1, pari('t'))), denom)*int(pari.polcoeff(numer, 0, pari('t'))), denom))
sol = (solve_congruence(*tequ))
print(sol)
sol = sol[0]

print(proc.recvuntil(b': '))
proc.sendline(str(sol).encode())
print(proc.recvline())

### (nearly) uniqueness
On CTF, I obtained flag and it works repeatedly, I think that recovered polynomial is unique. @grhkm pointed why it is, I could not explain exactly. But we can understand nearly uniqueness by using CRT construction.

Given 9 points $(x'_0, y'_0),\ldots,(x'_8, y'_8)$, we can recover $F'(x)$ such that $F'(x'_i)=y'_i\ (i=0,\ldots,8)$. $F'(x)$ is uniquely defined $\mod \prod_i{(x-x'_i)}$. So we have
$$
f(x) = F'(x) + c(x) \prod_i{(x-x'_i)}\ .
$$
$\deg(f)=9$, $\deg(\prod_i{(x-x'_i)})=9$ and $\deg(F')=8$, so $\deg(c)=0$, that is, $c(x)$ is a constant. And $\prod_i{(x-x'_i)}$ is monic, so $c(x) \in \mathbb{Z}$. Then, $F'(x) \in \mathbb{Z}[x]$. By substituting $x=0$, we have
$$
\mathbb{secret} = F'(0) + c \prod_i{(-x'_i)}\ .
$$
This means that $\mathbb{secret}$ is uniquely defined $\mod{\prod_i{x'_i}}$.

So I did not have to recover symbolic polynomial. I only have to compute $F'(0) \mod \prod_i{(-x'_i)}$.

On this challenge, ${\prod_i{x'_i}}$ is $10!/a$ for some $a\in \{1,\ldots,10\}$.
We know $1<=\mathbb{secret}<=500000$, but $10!/7=518400>500000$, so my solution is unique if $a<=7$. Even if $a=10$, $10!/10= 362880$, then my (smallest) solution is correct with the probability $362880/500000=0.73$. The overall probability is

>>> sum([min(((10*9*8*7*6*5*4*3*2*1)/i)/500000, 1.0) for i in range(1, 10+1)])/10
0.9439359999999999

Of cource, we can compute $c$ and check that recovered polynomial is valid (all coefficients except secret is positive and $<=\mathbf{\_ MAX}$) for reliablity of solution.