[JAVA] Back calculation of the transition of the internal seed of Random

background

Java has a random number class called java.util.Random. It can be used as follows:

python


int s = 32198541;
Random r = new Random(s); //Seed can be specified
int a = r.nextInt(24); //Something returns for an integer from 0 to 23
int b = r.nextInt(24);
int c = r.nextInt(24);

Now, how is ʻa obtained from shere? It is clear that Random contains internal variables, becauseRandom # nextIntreturns different values even if the same value is eaten. Here we name the variableseed` (which is actually the name internally).

Constructor behavior

Shows what the Random constructor is doing with almost Java pseudocode.

long seed;

Random(long seed)
{
	this.seed = (seed ^ 0x5DEECE66DL) & 0xFFFFFFFFFFFFL;
}

In fact, this is the only one. After bit-XORing a strange value to the given seed, only the lower 48 bits are extracted. 0x5DEECE66DL is 25214903917 in decimal and the prime factorization is 7 * 443 * 739 * 11003.

Behavior of nextInt

A bold simplification of the behavior of Random # nextInt looks like this.

int nextInt(int bound)
{
	seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
	return ((int) (seed >> 17)) % bound;
}

It is divided into an update part of the seed and an output part of the random value obtained from the current seed.

Summary

Summarizing these, the relationship between the seed given first and nextInt is roughly as follows.

long seed = 32198541; //Seed value to give

//First seed disturbance
seed = (seed ^ 0x5DEECE66DL) & 0xFFFFFFFFFFFFL;

// nextInt
long seed2 = seed;
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
long seed3 = seed;
int a = ((int) (seed >> 17)) % 24;

// nextInt
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
int b = ((int) (seed >> 17)) % 24;

// nextInt
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
int c = ((int) (seed >> 17)) % 24;

problem

Here is the problem. If we know the seed3 in the code above, is it possible to easily find the seed2? Perhaps if you learn the theory of random number generation, it will be a task that will end with a single blow, but ignore such things and do your best in vain.

approach

Organize the problem

Create x = f (z) when the following equation exists.

z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL

Here, + 0xBL can be managed by playing with the value a little, so remove it. Then it can be simplified to the next problem.

z = x * 0x5DEECE66DL % 0x1000000000000L
x = f(z)

If you know this f, you can calculate the seed one step before.

Assumption 1

0 <= x <= 0xFFFFFFFFFFFFL、 When z = x * 0x5DEECE66DL% 0x1000000000000L, x and z are bijective.

Bijection is like the relationship between numbers and order when shuffling numbered cards. If you are strong in mathematics, this is a problem that ends with a single blow, but I'm not sure, so think appropriately.

First, what if z = x * 7% 10? x * 7% 10 at 0> = x> = 9 becomes 0 7 4 1 8 5 2 9 6 3 and is bijective. In the case of z = x * 5% 10, 0 5 0 5 0 5 0 5 0 5 is not bijective. When z = x * y% 10, there were four ys where x and z were bijective, 1 3 7 9.

Assumption 2

Here, the following is assumed.

When 0 <= x <m, z = x * y% m, If the greatest common divisor of y and m is 1, then x and z are bijective.

Since it is impossible for one x to have multiple zs, when multiple xs correspond to one z, it is not bijective. z = x * 10% 100 is not bijective because it overlaps with x = 0 when x is a multiple of 10. This can be thought of as looping every 10 when x is incremented from 0 by 1. That is, when z = x * 3% 100, a loop occurs when x exceeds the range and reaches 100, but when z = x * 10% 100, 10 loops can be created. It is not a bijection because it ends up.

When does x * y make the loop shorter than m, in other words, return to x * y% m == 0? The fact that x * y is divisible by m means that x * y is a multiple of m. And if all the factors of m are also included in x * y, it will be a multiple of m. For example, 12 (= 2 * 2 * 3) * 15 (= 3 * 5) is a multiple of 60 (= 2 * 2 * 3 * 5). Then, when y does not contain any divisor of m, x loops every m. If y contains one divisor of m, x will be enough together with the divisor of y even if the divisor is not enough.

In summary, if the greatest common divisor of y and m is 1, then x and z are bijective. For the time being, let's assume that Assumption 2 is correct. Then, since 0x5DEECE66DL = 25214903917 = 7 * 443 * 739 * 11003, the greatest common divisor with 0x1000000000000L is 1, so assumption 1 is also correct.

Assumption 3

Looking at the series 0 7 4 1 8 5 2 9 6 3 of z = x * 7% 10, the ones place of 0 21 12 3 24 15 6 27 18 9 multiplied by 3 is the order. Notice that. That is, x = z * 3% 10.

Therefore, the following is assumed.

When 0 <= x <m, z = x * y% m, There exists a w that satisfies x = z * w% m.

Due to the symmetry of the definition, for the only companion to y, the only companion to w is y.

Substitution gives z = (z * w% m) * y% m. Since the (z * w% m) * y part is the same even if it increases by m, there is no point in % m at z * w% m. So you can write z = z * w * y% m. For z, * w * y% m is still z, which probably means w * y% m == 1.

For the time being, I tried to enumerate y: w when m = 100, 64 in the script.

m=100


1:1|3:67|7:43|9:89|11:91|13:77|17:53|19:79|21:81|23:87|27:63|29:69
31:71|33:97|37:73|39:59|41:61|43:7|47:83|49:49|51:51|53:17|57:93|59:39
61:41|63:27|67:3|69:29|71:31|73:37|77:13|79:19|81:21|83:47|87:23|89:9
91:11|93:57|97:33|99:99

m=64


1:1|3:43|5:13|7:55|9:57|11:35|13:5|15:47|17:49|19:27
21:61|23:39|25:41|27:19|29:53|31:31|33:33|35:11|37:45|39:23
41:25|43:3|45:37|47:15|49:17|51:59|53:29|55:7|57:9|59:51
61:21|63:63

1:1|3:2B|5:D|7:37|9:39|B:23|D:5|F:2F
11:31|13:1B|15:3D|17:27|19:29|1B:13|1D:35|1F:1F
21:21|23:B|25:2D|27:17|29:19|2B:3|2D:25|2F:F
31:11|33:3B|35:1D|37:7|39:9|3B:33|3D:15|3F:3F

y:wWhenw:yIt can be confirmed that. Also,y * w % mWas calculated to be all 1. for that reasonm = 100WhenyWhenwの1の位をかけるWhen必ず1の位が1になる。そのため1の位は必ず1:1|3:7|7:3|9:9When対応している。九九表の中で1の位が1である場所はそこしかないのだ。

And it can be used as a function to find x properly as follows.

52 = 76 * 27 % 100
76 = 52 * 63 % 100

27 * 63 = 1701

The same calculation can be done with a larger number.

3596 = 7852 * 273 % 10000
7852 = 3596 * 6337 % 10000

273 * 6337 = 1730001

Assumption 3 is correct for the time being. Probably looking for a w such as y * w% m == 1 is a sufficient condition to calculate x = f (z).

Split by digit

By the way, you can search for the companion of 0x5DEECE66DL by pushing GPGPU, but I confirmed the interesting property that" the 1st place is fixed when m = 100". This should also be true for hexadecimal numbers. In fact,m = 64At the time of 1st place1:1|3:B|5:D|7:7|9:9|B:3|D:5|F:FThere is a correspondence called. Only with this combination0001It seems that the binary number cannot be generated in the lower 4 bits. When actually multiplied, the remainder divided by 16 becomes 1 as shown below.

0x1 * 0x1 =   1 =  0 * 16 + 1
0x3 * 0xB =  33 =  2 * 16 + 1
0x7 * 0x7 =  49 =  3 * 16 + 1
0x5 * 0xD =  65 =  4 * 16 + 1
0x9 * 0x9 =  81 =  5 * 16 + 1
0xF * 0xF = 225 = 14 * 16 + 1

What can be said from this is that the 1st place of the 0x5DEECE66DL is 0x5. This alone requires 1/16 the amount of calculation. However, when m = 64, there is no reason why it can be done in hexadecimal notation but not in 256 decimal notation. Perhaps it's okay to separate every two digits in hexadecimal.

So, try to find the companion w of z = x * 0x6D% 0x100. The companion is 0x65 and 0x6D * 0x65 = 0x2B01. With this, it can be predicted that the last two digits of the companion of 0x5DEECE66DL are 0x65.

The companion of z = x * 0xE66D% 0x10000 is 0x1365, and when multiplied, it becomes 0x11750001. This calculation can be done by generating the candidates of the companion in order and checking if it becomes 1 by * 0xE66D% 0x10000, but since we know that the last two digits of the companion are 0x65, You only have to loop the remaining two digits.

The companion to z = x * 0x5DEECE66DL% 0x1000000000000L is 0xDFE05BCB1365L and 0x5DEECE66DL * 0xDFE05BCB1365L = 0x86E9000000000001. Now we can find the inverse function of the multiplication part.

z = x * 0x5DEECE66DL & 0xFFFFFFFFFFFFL
x = z * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL

After that, add a little + 0xBL part and you're done.

z = (x * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL
x = (z - 0xBL) * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL

Conclusion

The seed of Random can be calculated back as follows.

long seed = 0x32522523;
seed = (seed * 0x5DEECE66DL + 0xBL) & 0xFFFFFFFFFFFFL;
System.out.println(String.format("%x", seed));
seed = (seed - 0xBL) * 0xDFE05BCB1365L & 0xFFFFFFFFFFFFL;
System.out.println(String.format("%x", seed));

result


86e8d09b41f2
32522523

Recommended Posts

Back calculation of the transition of the internal seed of Random
I investigated the internal processing of Retrofit
Looking back on the basics of Java
Minecraft 1.12.2 Back calculation of world seeds from world map
[Java] How to get the URL of the transition source
I tried to summarize the state transition of docker
Do not easily round the result of decimal calculation
Monitor the internal state of Java programs with Kubernetes
Rails6: Input the initial data of ActionText using seed