commit 964ca606c70e10f11593870b15da40ff308a8dc4
parent 2be8ae884819af05604da72e86e453f99a810dec
Author: mpizzzle <michael.770211@gmail.com>
Date: Sun, 17 Dec 2017 22:40:12 +0000
set 3 challenge 22 complete
Diffstat:
3 files changed, 107 insertions(+), 42 deletions(-)
diff --git a/set3/crack_mt_seed.py b/set3/crack_mt_seed.py
@@ -0,0 +1,58 @@
+import time
+import random
+
+class mersenne_twister:
+ #Initialize the generator from a seed
+ def __init__(self, seed):
+ self.MT = [0] * 624
+ self.MT[0] = seed
+ self.index = 624
+ for i in range(1, 624): #loop over each element
+ self.MT[i] = int(0xFFFFFFFF & (1812433253 * (self.MT[i - 1] ^ (self.MT[i - 1] >> (30))) + i))
+
+ #Extract a tempered value based on MT[index]
+ #calling twist() every n numbers
+ def extract_number(self):
+ if self.index >= 624:
+ if self.index > 624:
+ raise Exception("Generator was never seeded")
+ #Alternatively, seed with constant value; 5489 is used in reference C code[49]
+ self.twist()
+
+ y = self.MT[self.index]
+ y = y ^ ((y >> 11) & 0xFFFFFFFF)
+ y = y ^ ((y << 7) & 0x9D2C5680)
+ y = y ^ ((y << 15) & 0xEFC60000)
+ y = y ^ (y >> 18)
+
+ self.index += 1
+ return int(0xFFFFFFFF & y)
+
+ #Generate the next n values from the series x_i
+ def twist(self):
+ for i in range(624):
+ x = int(0xFFFFFFFF & ((self.MT[i] & 0x80000000) + (self.MT[(i + 1) % 624] & 0x7fffffff)))
+ xA = x >> 1
+
+ if (x % 2) != 0: #lowest bit of x is 1
+ xA = xA ^ 0x9908B0DF
+
+ self.MT[i] = self.MT[(i + 397) % 624] ^ xA
+ self.index = 0
+
+secret_seed = int(time.time())
+time.sleep(random.randint(40, 1000))
+secret_seed_output = mersenne_twister(secret_seed).extract_number()
+print secret_seed_output
+
+current_time = int(time.time())
+cracked_seed = 0
+
+for i in range(1001):
+ if mersenne_twister(current_time - i).extract_number() == secret_seed_output:
+ cracked_seed = current_time - i
+ break
+
+print mersenne_twister(cracked_seed).extract_number()
+print cracked_seed
+print secret_seed == cracked_seed
diff --git a/set3/mersenne_twister.py b/set3/mersenne_twister.py
@@ -1,42 +0,0 @@
-class mersenne_twister:
- #Initialize the generator from a seed
- def __init__(self, seed):
- self.MT = [0] * 624
- self.MT[0] = seed
- self.index = 624
- for i in range(1, 624): #loop over each element
- self.MT[i] = int(0xFFFFFFFF & (1812433253 * (self.MT[i - 1] ^ (self.MT[i - 1] >> (30))) + i))
-
- #Extract a tempered value based on MT[index]
- #calling twist() every n numbers
- def extract_number(self):
- if self.index >= 624:
- if self.index > 624:
- raise Exception("Generator was never seeded")
- #Alternatively, seed with constant value; 5489 is used in reference C code[49]
- self.twist()
-
- y = self.MT[self.index]
- y = y ^ ((y >> 11) & 0xFFFFFFFF)
- y = y ^ ((y << 7) & 0x9D2C5680)
- y = y ^ ((y << 15) & 0xEFC60000)
- y = y ^ (y >> 18)
-
- self.index += 1
- return int(0xFFFFFFFF & y)
-
- #Generate the next n values from the series x_i
- def twist(self):
- for i in range(624):
- x = int(0xFFFFFFFF & ((self.MT[i] & 0x80000000) + (self.MT[(i + 1) % 624] & 0x7fffffff)))
- xA = x >> 1
-
- if (x % 2) != 0: #lowest bit of x is 1
- xA = xA ^ 0x9908B0DF
-
- self.MT[i] = self.MT[(i + 397) % 624] ^ xA
- self.index = 0
-
-mt = mersenne_twister(5489)
-for i in range(1000):
- print mt.extract_number()
diff --git a/set3/mt19937.py b/set3/mt19937.py
@@ -0,0 +1,49 @@
+def _int32(x):
+ # Get the 32 least significant bits.
+ return int(0xFFFFFFFF & x)
+
+class MT19937:
+
+ def __init__(self, seed):
+ # Initialize the index to 0
+ self.index = 624
+ self.mt = [0] * 624
+ self.mt[0] = seed # Initialize the initial state to the seed
+ for i in range(1, 624):
+ self.mt[i] = _int32(
+ 1812433253 * (self.mt[i - 1] ^ self.mt[i - 1] >> 30) + i)
+
+ def extract_number(self):
+ if self.index >= 624:
+ self.twist()
+
+ y = self.mt[self.index]
+
+ # Right shift by 11 bits
+ y = y ^ y >> 11
+ # Shift y left by 7 and take the bitwise and of 2636928640
+ y = y ^ y << 7 & 2636928640
+ # Shift y left by 15 and take the bitwise and of y and 4022730752
+ y = y ^ y << 15 & 4022730752
+ # Right shift by 18 bits
+ y = y ^ y >> 18
+
+ self.index = self.index + 1
+
+ return _int32(y)
+
+ def twist(self):
+ for i in range(624):
+ # Get the most significant bit and add it to the less significant
+ # bits of the next number
+ y = _int32((self.mt[i] & 0x80000000) +
+ (self.mt[(i + 1) % 624] & 0x7fffffff))
+ self.mt[i] = self.mt[(i + 397) % 624] ^ y >> 1
+
+ if y % 2 != 0:
+ self.mt[i] = self.mt[i] ^ 0x9908b0df
+ self.index = 0
+ #test
+
+mt = MT19937(0)
+print mt.extract_number()
