Some progress for the future me: The problem can be reduced to a Combination Sum problem. In particular, we can generate the range of possible primes as the sum of the array (range can be from ord(a) * <some_value> to ord(z) * 1020). We can use a DP approach to solve this as we have a lot of incremental sum, however, storage might be an issue. Some trimming can be done to ensure the solution does not exceed the length How the array.

I did not manage to solve this. Have to search on Github for some solution (very shameless to admit). I made some mistakes in solving the problem, which will be mentioned below. The challenge is similar to the so easy rsa challenge in HITCON 2021, in which maple3142 has a good blog entry about. Denote the Linear Congruential Generator (LCG) function as $f(x) = ax + b$, we have $q = f^x(p)$ for some unknown $x \in [2, 1000]$.

This is pretty much a Cryptopals challenge. Solution for those who understand Vietnamese is available at this link. Understanding how to solve this challenge in the Cryptopals intended way requires a deep understanding into how group theory works. A cheating way to solve this is to search the name of the challenge on Github, and there should be Python/Sage solutions. Leaving this challenge to the future me who “hopefully” understand in the future.

The challenge gives us a Fibonacci LFSR, with unknown taps, but we are provided 2048 bits of the output of LFSR. We have to first recover the taps, then from the taps we will recover the initial value. To recover the taps from the given output, we can use the Berlekamp Massey algorithm. We are provided with 2048 bits, which is more than enough (we need more than $384 * 2 = 768$ bits).

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.