This challenge was a cool introduction to Shamir Secret Sharing (SSS).
### msg.enc
```share: (21202245407317581090, 11086299714260406068)coefficient: 93526756371754197321930622219489764824secret message: 1aaad05f3f187bcbb3fb5c9e233ea339082062fc10a59604d96bcc38d0af92cd842ad7301b5b72bd5378265dae0bc1c1e9f09a90c97b35cfadbcfe259021ce495e9b91d29f563ae7d49b66296f15e7999c9e547fac6f1a2ee682579143da511475ea791d24b5df6affb33147d57718eaa5b1b578230d97f395c458fc2c9c36525db1ba7b1097ad8f5df079994b383b32695ed9a372ea9a0eb1c6c18b3d3d43bd2db598667ef4f80845424d6c75abc88b59ef7c119d505cd696ed01c65f374a0df3f331d7347052faab63f76f587400b6a6f8b718df1db9cebe46a4ec6529bc226627d39baca7716a4c11be6f884c371b08d87c9e432af58c030382b737b9bb63045268a18455b9f1c4011a984a818a5427231320ee7eca39bdfe175333341b7c```
## OverviewWe 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 md5from Crypto.Cipher import AESfrom Crypto.Util.Padding import padfrom random import randbytes, seed
x, y = 21202245407317581090, 11086299714260406068hs = 93526756371754197321930622219489764824k = 10n = 18p = 92434467187580489687coeffs = [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 - rhssecret %= p
seed(secret)key = randbytes(16)cipher = AES.new(key, AES.MODE_ECB)flag = cipher.decrypt(ct)
print(flag)```