# 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.

What I Learned It would be better trying many things, instead of detailed analysis, on CTF Simple strategy is good, but tuning parameters not good. Applying past genius works is definitely better. chronophobia (from idekCTF 2022) #!/usr/bin/env python3 from Crypto.Util.number import * import random import signal

4/14/2023Crypto (blocky4, remake) blocky4 part of source (task.py) def main(): signal.signal(signal.SIGALRM, handler) signal.alarm(60) key = get_key()

2/23/2023
Published on ** HackMD**