Background
I've been reading and trying to wrap my head around various questions/answers that relate to finding the seed from Java.util.Random given its output from nextInt().
The implementation of nextInt(int bound) is:
public int nextInt(int bound) {
if (bound <= 0)
throw new IllegalArgumentException("bound must be positive");
if ((bound & -bound) == bound) // i.e., bound is a power of 2
return (int)((bound * (long)next(31)) >> 31);
int bits, val;
do {
bits = next(31);
val = bits % bound;
} while (bits - val + (bound-1) < 0);
return val;
}
The implementation of next(int bits) is:
protected int next(int bits) {
long oldseed, nextseed;
AtomicLong seed = this.seed;
do {
oldseed = seed.get();
nextseed = (oldseed * multiplier + addend) & mask;
} while (!seed.compareAndSet(oldseed, nextseed));
return (int)(nextseed >>> (48 - bits));
}
where the multiplier is 0x5DEECE66DL, the addend is 0xBL, and the mask is (1L << 48) - 1. These are hexadecimal values where the L is Java convention for long conversion.
By calling nextInt() without a bound, the full 32-bits are returned from next(32) instead of dropping bits with bits % bound.
Questions
-
Without completely bruteforcing the full $2^{48}$ possibilities, how would I go about finding the current seed after $x$ amount of calls to
nextInt(n)(assuming the bound is never a power of 2)? For example, let's assume I want to find the seed given 10 calls tonextInt(344)[251, 331, 306, 322, 333, 283, 187, 54, 170, 331]. -
How can I determine the amount of data I'd need to find the correct seed, not just another one that produces the same starting data?
-
Does this change given bounds that are either odd/even?
Aucun commentaire:
Enregistrer un commentaire