の Oracle (旧姓 Sun) 実装について話している場合はjava.util.Random、十分な知識があれば可能です。
Random48 ビットのシードと線形合同ジェネレーターを使用します。これらは暗号的に安全なジェネレーターではありません。これは、状態のサイズが小さいため (ブルートフォース可能です!)、出力がそれほどランダムではないという事実です (多くのジェネレーターは、特定のビットで短いサイクル長を示します。つまり、これらのビットは、他のビットがランダムに見える場合)。
Randomのシード更新は次のとおりです。
nextseed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1)
これは非常に単純な関数であり、計算によってシードのすべてのビットがわかっている場合は逆にすることができます。
seed = ((nextseed - 0xBL) * 0xdfe05bcb1365L) & ((1L << 48) - 1)
0x5DEECE66DL * 0xdfe05bcb1365L = 1mod 2 48以降。これにより、任意の時点での単一のシード値で、過去および将来のすべてのシードを回復できます。
Randomただし、シード全体を明らかにする関数はないため、少し賢くする必要があります。
さて、明らかに、48 ビットのシードでは、少なくとも 48 ビットの出力を観察する必要があります。そうしないと、操作する単射 (したがって可逆) 関数が明らかにありません。運が良かった: returnであるため、64 ビットの出力 (必要以上) が生成されnextLongます。((long)(next(32)) << 32) + next(32);実際、おそらくnextDouble(53 ビットを生成する) で間に合わせるか、他の関数を繰り返し呼び出すだけで済みます。これらの関数は、シードのサイズが限られているため、2 48を超える一意の値を出力できないことに注意してください (したがって、たとえば、決して生成されない 2 64 -2 48 longが存在します)。nextLong
を具体的に見てみましょうnextLong。とが両方とも 32 ビット量(a << 32) + bである数値を返します。が呼び出される前にシードにしましょう。次に、 をの上位 32 ビットとし、 をの上位32 ビットとします。と をそれぞれとの下位 16 ビットとする。absnextLongt = s * 0x5DEECE66DL + 0xBLatu = t * 0x5DEECE66DL + 0xBLbucdtu
cとdは 16 ビットの量であるため、(1 つしか必要ないため) 力ずくで実行するだけで済むことに注意してください。2 16はわずか 65536 であり、コンピューターとしては非常に小さいため、かなり安価です。しかし、もう少し賢く、もっと速い方法がないか見てみましょう。
あります(b << 16) + d = ((a << 16) + c) * 0x5DEECE66DL + 11。したがって、いくつかの代数を実行する(b << 16) - 11 - (a << 16)*0x5DEECE66DL = c*0x5DEECE66DL - dと、mod 2 48が得られます。cとdはどちらも 16 ビット量であるためc*0x5DEECE66DL、最大 51 ビットです。これは便利なことに、
(b << 16) - 11 - (a << 16)*0x5DEECE66DL + (k<<48)
は、多くても 6 に等しいものc*0x5DEECE66DL - dがあります (とkを計算するより洗練された方法がありますが、境界が非常に小さいため、ブルートフォースする方が簡単です)。cdk
残りの modが 16 ビット (再び mod 2 48k ) である値を否定する値が得られるまで、 のすべての可能な値をテストして、との両方の下位 16 ビットを回復します。その時点で、完全なシードがあるため、最初の式を使用して将来のシードを見つけるか、2 番目の式を使用して過去のシードを見つけることができます。0x5DEECE66DLtu
アプローチを示すコード:
import java.util.Random;
public class randhack {
public static long calcSeed(long nextLong) {
final long x = 0x5DEECE66DL;
final long xinv = 0xdfe05bcb1365L;
final long y = 0xBL;
final long mask = ((1L << 48)-1);
long a = nextLong >>> 32;
long b = nextLong & ((1L<<32)-1);
if((b & 0x80000000) != 0)
a++; // b had a sign bit, so we need to restore a
long q = ((b << 16) - y - (a << 16)*x) & mask;
for(long k=0; k<=5; k++) {
long rem = (x - (q + (k<<48))) % x;
long d = (rem + x)%x; // force positive
if(d < 65536) {
long c = ((q + d) * xinv) & mask;
if(c < 65536) {
return ((((a << 16) + c) - y) * xinv) & mask;
}
}
}
throw new RuntimeException("Failed!!");
}
public static void main(String[] args) {
Random r = new Random();
long next = r.nextLong();
System.out.println("Next long value: " + next);
long seed = calcSeed(next);
System.out.println("Seed " + seed);
// setSeed mangles the input, so demangle it here to get the right output
Random r2 = new Random((seed ^ 0x5DEECE66DL) & ((1L << 48)-1));
System.out.println("Next long value from seed: " + r2.nextLong());
}
}