This challenge was a cool introduction to Shamir Secret Sharing (SSS).

### msg.enc

```
share: (21202245407317581090, 11086299714260406068)
coefficient: 93526756371754197321930622219489764824
secret message: 1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c
```

## Overview
We are given some parameters : `p = 92434467187580489687 , k = 10 , n = 18`

At first glance, we can see that the coefficients array (**coeffs**) is initialized with a random secret value, say **s**. `self.coeffs = [self.secret]`

This value is later used as seed to generate the random AES key which is used to encrypt the flag.

-----

The coeffs array contain repeated md5 hashes of the initial secret value. Of course this hash is converted to an integer. That is:

- element 0 : secret = s
- element 1 : md5(secret) = hs
- element 2 : md5(md5(secret)) = hhs ...

and so on and so forth. This repeats `n = 18` times.

By the end of `create_pol` **coeffs** will contain only the first `k=10` hash values because of `self.coeffs = self.coeffs[:self.k]`.

The important part are the two arrays, `x_vals` and `y_vals`.

**x** is just some random value `< p` but **y** is calculated based on the corresponding x value and the coefficients array as below:

`y = (s + hs * x + hhs * x^2 + hhhs * x^3 + ... + hhhhhhhhhs * x^9) % p (1)`

## Solution

We are given the md5 hash of the secret value. That means that we can hash it, then hash again and again to recover all the coefficients but the secret.

We know all the hash values and just one pair of `x, y` values. Let's solve (1) for the secret:

```
secret = (y - hs * x - hhs * x^2 - hhhs * x^3 - ... - hhhhhhhhhs * x^9) % p =
= [y - (hs * x + hhs * x^2 + hhhs * x^3 + ... + hhhhhhhhhs * x^9)] % p
```

Now we can subtitute for the coefficients that we calculated above, the x and y value to get the secret, find the key and decrypt the flag.

## solve.py
```
from hashlib import md5
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from random import randbytes, seed

x, y = 21202245407317581090, 11086299714260406068
hs = 93526756371754197321930622219489764824
k = 10
n = 18
p = 92434467187580489687
coeffs = [hs]

ct = bytes.fromhex('redacted_for_the_sake_of_brevity')

def next_coeff(val):
return int(md5(val.to_bytes(32, byteorder="big")).hexdigest(),16)

def calc_coeffs():
for i in range(1, k-1):
coeffs.append(next_coeff(coeffs[i-1]))

def calc_rhs():
sum = 0
for i in range(len(coeffs)):
sum += coeffs[i] * x**(i+1)
return sum % p

calc_coeffs()
rhs = calc_rhs()

secret = y - rhs
secret %= p

seed(secret)
key = randbytes(16)
cipher = AES.new(key, AES.MODE_ECB)
flag = cipher.decrypt(ct)

print(flag)
```