Python-random-module-cracker
Python-random-module-cracker copied to clipboard
Implement offsetting to previous internal states
While reading into some PRNG cracking, I learned that it is possible to recover any previous states of the Mersenne Twister after it has been cracked. See this post for the algorithm used:
https://jazzy.id.au/2010/09/25/cracking_random_number_generators_part_4.html
The main change is the addition of the untwist() method, which is the Java algorithm from the article above translated to Python:
def untwist(self):
w, n, m = 32, 624, 397
a = 0x9908B0DF
# I like bitshifting more than these custom functions...
MT = [self._to_int(x) for x in self.mt]
for i in range(n-1, -1, -1):
result = 0
tmp = MT[i]
tmp ^= MT[(i + m) % n]
if tmp & (1 << w-1):
tmp ^= a
result = (tmp << 1) & (1 << w-1)
tmp = MT[(i - 1 + n) % n]
tmp ^= MT[(i + m-1) % n]
if tmp & (1 << w-1):
tmp ^= a
result |= 1
result |= (tmp << 1) & ((1 << w-1) - 1)
MT[i] = result
self.mt = [self._to_bitarray(x) for x in MT]
In the implementation, I found it easier to work with bit-shifting and XORing directly, but I noticed most of the code uses custom functions for that. You may want to clean up the implementation to use those custom functions, but this simply translates the self.mt into integers for the algorithm and then translates them back to bit arrays in the end.
To ease in using this untwist() method, an offset(n) method was made that works for positive and negative numbers, to set the state back to a previous one by untwisting.
def offset(self, n):
if n >= 0:
[self._predict_32() for _ in range(n)]
else:
[self.untwist() for _ in range(-n // 624 + 1)]
[self._predict_32() for _ in range(624 - (-n % 624))]
There are some details like the randbelow() function possibly advancing the state multiple times, and a note about this is added to the README.
I have also written a couple of tests to make sure this all works as expected.
@tna0y I see the repository is a bit inactive, but any chance can this be merged?