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.

This challenge is about the Dual_EC_DRBG random number generator, which is famous for being backdoored by the NSA so they can predict the output after reading only 32 bytes of the random stream. This excellent video should demonstrate how to generate the point $Q$ so that we can easily recover the state of the PRNG given that we know the relation of $P = dQ$, where $d$ is the secret component only known by the NSA.