你能用java.util.Random找到以前生成的随机数吗？

Question

是否可以使用java.util.Random？找到以前生成的随机数？

---

我在这个网站上找到了信息,它表明它在格式中使用了LCG

数字_{i + 1} =(a*数字_i + c)mod 2 ⁴⁸

其中number的第一个值是seed,并且每次调用nextInt(或类似的东西)时简单地递增1

有没有人有关于它是如何生成的更多信息？或者偏移值是多少？

编辑:我从openjdk 找到了这个源代码

Answer 1

是的,您可以在Random不存储它们的情况下获得之前的值(并且不知道Random像@Andreas建议的对象的原始种子).这是概念验证代码.它nextLong()仅支持恢复呼叫,但也可以恢复其他呼叫.

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;
    }
}

用法示例:

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()));
    }
}

典型输出:

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

这里有两个问题.首先是按nextLong值复制随机种子.这部分(replicateSeed)基于GitHub的代码.下一个问题是反转种子计算公式,因此我们可以将种子从当前更改为前一个.目前OpenJDK的下一个公式是:

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

因此,它只是在模2 ^ 48的整数环中的加法和乘法.这两种操作都是不可逆转的.对于添加,您可以在同一个环中减去.对于乘法,你必须计算反转乘数,这可以解决丢番图方程x*0x5DEECE66DL+y*0x1000000000000L = 1.解决它你得到x = 0xDFE05BCB1365L(选择适合戒指的解决方案).因此,要乘以乘法,您只需要乘以0xDFE05BCB1365L.