Randomness

The Mersenne Twister (MT) is a non-cryptographic pseudorandom number generator (PRNG). Its goal is to generate uniformly random numbers in the range $[0,2^{32}-1]$ or $[0,2^{64}-1]$. However, unlike cryptographic pseudorandom generators, MT does not provide forward or backward resistance. The detailed algorithm description can be found on this page.

We focus on the version of MT that produces pseudorandom integers of length $32$ bits. As explained on this page, MT keeps $624$ $32$-bit integers as its internal states. To generate randomnesses, the algorithm simply computes a linear combination of $3$ out of $624$ integers in a fixed order. Although the states are constantly updated when invoking MT, the future states can be predicted if previous states are exposed.

In this challenge, you will be given some random numbers generated by a MT. Your goal is to recover all the states and predict the next pseudorandom number that will be generated from this MT.

When you get the answer $r$, validate it by solve.

In this challenge, we continue our exploration with Mersenne Twister. Similar to the previous challenge, you will be given the first $624$ random numbers generated by a MT. Denote the MT states as $x_0,x_1,...,x_623$, your goal is to recover $x_1$.

When you get the answer $r$, validate it by solve.

RSA (Rivest-Shamir-Adleman) is a public-key cryptosystem that contains encryption and digital signatures. The security of RSA relies on the hardness of factoring the product of two large prime numbers. Specifically, RSA's key generator will sample two primes $(p,q)$ and compute $N=p*q$. The values of $(p,q)$ will stay hidden and $N$ will be published as a public parameter. All cryptographic schemes based on RSA will be broken if an attack successfully factors $N$ and obtain $(p,q)$.

In this challenge, you will be given a $4096$-bit $N$ and your goal is to find two $2048$-bit prime numbers $(p,q)$ that factors $N$. Luckily, both $(p,q)$ are sampled by a non-cryptographic PRNG random.randint(min_prime, max_prime) and seeded by a very weak seed using random.seed(seed). The key generator was very careless to set the seed to be in the range $[2^{8},2^{9}-1]$.