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