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