This is about a particular weakness of the Shamir’s secret sharing scheme. During the share reassembly process, Shamir’s secret sharing does not provide a way to verify the correctness of each share being used. Verifiable secret sharing aims to verify that shareholders are honest and not submitting fake shares. The basis of Shamir’s secret sharing is on Lagrange basis polynomials. My solution is based on the computationally efficient approach of the scheme.

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}$.

I solve this challenge with some misinterpretations, but in the end I got the correct overall theme: Legendre Symbols. I guess I got lucky with the local testing and derive the correct relation. The challenge, as suggested by the category, is about the ElGamal construction. More information can be found at this Wikipedia link, or any textbook in cryptography should cover this. The very first observation is that each iteration of the while loop is operating 1 bit of the flag at a time, starting from the last bit of the flag.

This challenge marks a really important point in my CryptoHack journey. I have conquered a lattice related challenge knowing what is going on. Lattices have been something I have zero idea about (and I would looove to stay away from), but thanks to the incredible help and explanation from Kel Zin, I can say I understand 0.01% of how lattices work now. If we write the problem in mathematical terms, we have the following:

The challenge uses a LCG to generate plaintext, key and IV. To receive the flag we must present the AES-CBC encrypted plaintext given the key and IV, only we don’t know the key. The LCG resets a new state every 16 states (from the refresh function). Observing the code, we can learn that: The last 8 bytes of the plaintext and the first 8 bytes of the key are derived from some 16 consecutive states The last 8 bytes of the key and the first 8 bytes of the IV are derived from some 16 consecutive states.