Rating: 5.0
1) Just created 5 accounts, wrote down the passwords they gave thay clearly looked like some sort of LCG (random) output.
2) Cracked the LCG using https://tailcall.net/blog/cracking-randomness-lcgs/ as reference
3) Go backwards in the LCG to user account 1
4) Login with the credentials to 1
```
import math
import functools
reduce = functools.reduce
gcd = math.gcd
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, x, y = egcd(b % a, a)
return (g, y - (b // a) * x, x)
def modinv(b, n):
g, x, _ = egcd(b, n)
if g == 1:
return x % n
def crack_unknown_increment(states, modulus, multiplier):
increment = (states[1] - states[0]*multiplier) % modulus
return modulus, multiplier, increment
def crack_unknown_multiplier(states, modulus):
print('states', states)
multiplier = (states[2] - states[1]) * modinv(states[1] - states[0], modulus) % modulus
return crack_unknown_increment(states, modulus, multiplier)
def crack_unknown_modulus(states):
diffs = [s1 - s0 for s0, s1 in zip(states, states[1:])]
zeroes = [t2*t0 - t1*t1 for t0, t1, t2 in zip(diffs, diffs[1:], diffs[2:])]
modulus = abs(reduce(gcd, zeroes))
return crack_unknown_multiplier(states, modulus)
print(crack_unknown_modulus([2586395092071382849559479705257206998,
8948194144096109003529304714220854255, 15309993196120835157499129723184501512, 5386521863033147591042270920884798102, 11748320915057873745012095929848445359]))
# m = 1 # the "multiplier"
# c = 6361799052024726153969825008963647257 # the "increment"
# n = 16285270385112413720426683811263350667 # the "modulus"
class prng_lcg:
m = 1 # the "multiplier"
c = 6361799052024726153969825008963647257 # the "increment"
n = 16285270385112413720426683811263350667 # the "modulus"
def __init__(self, seed):
self.state = seed # the "seed"
def next(self):
self.state = (self.state * self.m + self.c) % self.n
return self.state
def prev(self):
self.state = (self.state - self.c) % self.n
return int(self.state)
#User Number: 682
#Password: 6663557613792518990516576981095459108
gen = prng_lcg(6663557613792518990516576981095459108)
num = 681
while num > 0:
p = gen.prev()
print(num, p)
if p == 2586395092071382849559479705257206998:
print('sanity check: working')
num -= 1
# 6160325624856057770563639672902954513
```
