Can you find previously generated random numbers using java.util.Random?

Question

Is it possible to find previously generated random numbers using java.util.Random?

---

I found information at this website, it indicates that it uses a LCG in the format

number_i+1 = (a * number_i + c) mod 2⁴⁸

where the first value of number is seed and is simply incremented by one every time nextInt (or somthing similar) is called

Does anyone have any more information on how it is generated? or what the offset values are?

Edit: I found this source code from the openjdk

Answer 1

Yes, you can get the previous Random values without storing them (and without knowing the original seed of the Random object like @Andreas suggests). Here's the proof-of-concept code. It supports reverting the nextLong() calls only, but it's possible to revert other calls as well.

public class InvRand {
    private static final long addend = 0xBL;
    private static final long multiplier = 0x5DEECE66DL;
    private static final long invMultiplier = 0xDFE05BCB1365L;
    private static final long mask = 0xFFFFFFFFFFFFL;

    private long seed;

    public InvRand(Random r) {
        seed = prevSeed(replicateSeed(r.nextLong()));
    }

    public long prevLong() {
        seed = prevSeed(seed);
        long b1 = seed >>> 16;
        seed = prevSeed(seed);
        long b2 = seed >>> 16;
        return (b2 << 32) + b1;
    }

    static long replicateSeed(long nextLong) {
        int nextM = (int)(nextLong & 0xFFFFFFFF);
        int nextN = (int)((nextLong - nextM) >> 32);

        long upperMOf48Mask = 0xFFFFFFFF0000L;

        long oldSeedUpperN = ((long)nextN << 16) & mask;
        long newSeedUpperM = ((long)nextM << 16) & mask;

        for (long oldSeed = oldSeedUpperN; oldSeed <= (oldSeedUpperN | 0xFFFF); 
                  oldSeed++) {
            long newSeed = (oldSeed * multiplier + addend) & mask;
            if ((newSeed & upperMOf48Mask) == newSeedUpperM) {
                return newSeed;
            }
        }
        throw new InternalError();
    }

    static long prevSeed(long seed) {
        return ((seed - addend) * invMultiplier) & mask;
    }
}

Usage example:

public static void main(String[] args) {
    Random rand = new Random();
    for(int i=0; i<20; i++) {
        System.out.println("next: " + Long.toHexString(rand.nextLong()));
    }
    InvRand ir = new InvRand(rand);
    for(int i=0; i<20; i++) {
        System.out.println("prev: "+Long.toHexString(ir.prevLong()));
    }
}

Typical output:

next: 76c8febd3eab0fd8
next: 19ea99b87b9c118e
next: 2d69d148285ac86e
next: f466d00f770361e7
next: ca069823ec343ea2
next: f570a154be288a23
next: 3f2f3844ad48b1ea
next: d79ed82cd2e927e
next: 97ffcecf7d9a5b0a
next: d4e1a218dea3fc6f
next: c54e390e8f9486fe
next: 670052e4c52b230
next: ed13a7adac2ffc1c
next: f4e41dc7ada0ea7d
next: 56ffb122ab160d7a
next: cd7ecd6d1236049b
next: ce0597694257008c
next: d32d6ef8c142a09b
next: 2e8bb4f2356ea912
next: f5bf0eb275fb77df
prev: f5bf0eb275fb77df // note numbers are going backwards now
prev: 2e8bb4f2356ea912
prev: d32d6ef9c142a09b
prev: ce0597694257008c
prev: cd7ecd6d1236049b
prev: 56ffb123ab160d7a
prev: f4e41dc8ada0ea7d
prev: ed13a7aeac2ffc1c
prev: 670052e4c52b230
prev: c54e390f8f9486fe
prev: d4e1a219dea3fc6f
prev: 97ffcecf7d9a5b0a
prev: d79ed83cd2e927e
prev: 3f2f3845ad48b1ea
prev: f570a155be288a23
prev: ca069824ec343ea2
prev: f466d00f770361e7
prev: 2d69d148285ac86e
prev: 19ea99b87b9c118e
prev: 76c8febd3eab0fd8

There are two problems here. First is to replicate the random seed by nextLong value. This part (replicateSeed) is based on this code from GitHub. Next problem is to invert the seed calculation formula, so we can change the seed from the current to the previous. Current OpenJDK nextseed formula is:

nextseed = (oldseed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;

So it's just addition and multiplication in ring of integers modulo 2^48. Both operations are inversible. For addition you can just subtract in the same ring. For multiplication you have to calculate the inverted multiplier, which can be done solving Diophantine equation x*0x5DEECE66DL+y*0x1000000000000L = 1. Solving it you get x = 0xDFE05BCB1365L (select the solution which fits the ring). So to inverse the multiplication you just need to multiply by 0xDFE05BCB1365L.