How to determine the next number from java's Random method [closed]

Question

I understand a little how Java's Random class works.

I have two random numbers output from calls to nextInt() from a java.util.Random object in Java. I want to determine the next number output after a third call.

The first two numbers are: $-1952542633$ and $-284611532$, how can I determine the next number given only this information?

Answer 1

In Java, if you do not seed the Random object, then it will seed itself. According to that same documentation, it uses a "linear congruential PRNG"...

This means it will easily be cracked if you have two values.

Such a PRNG will have an "internal state", which will change after each generation of a "random" number by applying the following linear process:

$$X_{n+1} = \left( a X_n + c \right)~~\bmod~~m$$ where we call $X_n$ the state at the step $n$, $a$ is the "multiplier", $c$ is the "increment" and $m$ is the "modulus".

Now, Wikipedia tells us that Java is using 25214903917 as multiplier and 11 as an increment and has a modulus equal to $2^{48}$.

Finally you need to know that java.util.Random won't spit all of its internal state into your random numbers: 32 bits only of the internal state are revealed by a call to nextInt().

So, we just one value, it would be hard, but since you have 2 different values, you can easily bruteforce the seed used and thus find the next value by calling nextInt with that seed.

Here is a snippet of code, which produces the correct result (I believe... This is only my fourth time trying out Java), I didn't felt like bruteforcing the bitwise AND operation to reverse it to the actual initial state, I let this as an exercise to a motivated fellow:

import java.util.Random;

public class lol {
    // implemented after https://docs.oracle.com/javase/7/docs/api/java/util/Random.html
    public static int next(long seed) {
        int bits=32;
        long seed2 = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
        return (int)(seed2 >>> (48 - bits));
    }

    public static void main(String[] args) {
        System.out.println("Starting");
        long i1 = -1952542633L;
        long i2 = -284611532L;
        long seed =0;
        for (int i = 0; i < 65536; i++) {
            seed = i1 *65536 + i;
            if (next(seed) == i2) {
                System.out.println("Seed found: " + seed);
               break;
            }
        }
        Random random = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48) - 1));
        int o1 = random.nextInt();
        int o2 = random.nextInt();
        System.out.println("So we have that nextInt is: "+o1+" and the third one is: "+o2+" with seed: "+seed);

    }
}

Which produces the following output:

Starting
Seed found: -127961833934689
So we have that nextInt is: -284611532 and the third one is: -1527300283 with seed: -127961833934689

And so I think your third integer would be $-1527300283$.