Armory

This is about Shamir’s secret sharing scheme, where the main idea is based on having sufficient points to fully define a polynomial curve. A polynomial of degree $t - 1$ can only be constructed if $t$ points (shares) are known.

In this challenge, only the first share is known, so it seems like we do not have any way of retrieving the value. However, we can observe two points:

• The coefficient $c_i$ is generated by calculating the SHA-256 hash of the previous coefficient $c_{i - 1}$. Hence, with $c_1$ known, we can generate coefficients $c_2, c_3, …$.
• The $x$ coordinate of the point generated is the coefficients themselves. Denote the polynomial used to be $f$, then the points in the shares are $f(c_1), f(c_2), …$

Hence, as we are given minimum=3, the polynomial is of degree 2. The form of the polynomial is thus $c_2 * x ^ 2 + c_1 * x + s$, where $s$ is the unknown secret. We have the coordinate of a point, which is $(c_1, y)$, where $y$ is the second number obtained from the single share.

The secret $s$ can thus be derived from $s = y - c_2 * c_1 ^ 2 + c_1 * c_1$. Note that all operations are done under the prime modulo given, but for the sake of typing is omitted.

Python Implementation:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import hashlib

p = 77793805322526801978326005188088213205424384389488111175220421173086192558047
FLAG = b"crypto{???????????????????????}"

# Denote secret (the flag) as s
# The polynomial will be c2 * x ^ 2 + c1 * x + s = y
# From the challenge code, x = c1, and c2 = sha256(c1) 
c1, y = (105622578433921694608307153620094961853014843078655463551374559727541051964080, 25953768581962402292961757951905849014581503184926092726593265745485300657424)
c2 = hashlib.sha256(int.to_bytes(c1, 32, 'big')).digest()
c2 = int.from_bytes(c2, 'big')

# Calculate c2 * c1 ^ 2 + c1 * c1
pol = (c2 * pow(c1, 2, p) + c1 * c1) % p

# s = y - pol
print(int.to_bytes((y - pol) % p, len(FLAG), 'big'))