# Some Note for UIUCTF2022 Crypto Challenges ## wringing_rings ```python= 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. ```python= 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 ```python= >>> 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.