#!/usr/bin/python3 s =  p = 0 def init(): global s,p s = [i for i in range(0,64)] p = 0 return def randgen(): global s,p a = 3 b = 13 c = 37 s0 = s[p] p = (p + 1) & 63 s1 = s[p] res = (s0 + s1) & ((1<<64)-1) s1 ^= (s1 << a) & ((1<<64)-1) s[p] = (s1 ^ s0 ^ (s1 >> b) ^ (s0 >> c)) & ((1<<64)-1) return res def jump(to): # Deleted... return def check_jump(): ... check_jump() init() for a in range(31337):randgen() flag = open("flag.txt").read() assert len(flag) == 256 enc = b"" for x in range(len(flag)): buf = randgen() sh = x//2 if sh > 64:sh = 64 mask = (1 << sh) - 1 buf &= mask jump(buf) enc += bytes([ ord(flag[x]) ^ (randgen() & 0xff) ]) print ("%r" % enc) open("enc.dat","wb").write(bytearray(enc))
The given python script implements a random number generator like xorshift but 64 internal states. The script requires to generate number quite a lot of times and define utility to do it
jump. But it is deleted, so our purpose is to implement a fast
So, in such a case, we want to use the mathematical tool recurrence formula and matrix exponentiation. If we could show the xorshift algorithm as the recurrence formula and accumulate them into the matrix multiplication, it becomes very easy to repeat.
For this purpose, we are thinking of the and make each state a vector who has 64 elements. On the , XOR operation is equivalent to the addition. As treating each state as the vector, we can use matrix operation to update all states at once.
Luckily, knowing the matrix means the left/right shift operation, we can write down all operations about xorshift in the matrix context. For example, updating
s1 is shown in the following, where
means x bit left shift matrix and means right shift matrix.
Now nothing is hard. The following formula updates internal states simultaneously.
In this form, multiple times update can be shown using the matrix exponentiation. Let the above formula as . For example,
jump(n) is made by .
So now, we can easily implement
jump using the matrix form of xorshift. As the large size (642 * 642) matrix, the calculation is heavy. However, this method is faster than in other ways. On my laptop, 30minutes - 1hour to finish and yield all the keys by the following script.