61 lines
1.7 KiB
Python
61 lines
1.7 KiB
Python
#!/usr/bin/env python3
|
|
"""
|
|
solve_lcg.py
|
|
|
|
Recover LCG parameters a, c modulo 2^32 from three consecutive outputs x0, x1, x2.
|
|
Usage:
|
|
python3 solve_lcg.py x0 x1 x2
|
|
Example:
|
|
python3 solve_lcg.py 123 456 789
|
|
If successful prints a, c, and the next output.
|
|
"""
|
|
import sys
|
|
|
|
M = 2**32
|
|
|
|
def modinv_pow2(x):
|
|
"""
|
|
Compute modular inverse of x modulo 2^32 if it exists.
|
|
For modulus 2^k, inverse exists iff x is odd.
|
|
Uses Newton-Raphson to invert modulo 2^32.
|
|
"""
|
|
if x % 2 == 0:
|
|
return None
|
|
# initial inverse mod 2
|
|
inv = 1
|
|
# Newton iteration: inv = inv*(2 - x*inv) mod 2^n doubles correct bits each step
|
|
for _ in range(5): # 2^1 -> 2^32 in 5 iterations (1->2->4->8->16->32)
|
|
inv = (inv * (2 - (x * inv) % M)) % M
|
|
return inv % M
|
|
|
|
def recover_params(x0, x1, x2):
|
|
diff1 = (x1 - x0) % M
|
|
diff2 = (x2 - x1) % M
|
|
inv = modinv_pow2(diff1)
|
|
if inv is None:
|
|
return None, None
|
|
a = (diff2 * inv) % M
|
|
c = (x1 - (a * x0) % M) % M
|
|
return a, c
|
|
|
|
def next_value(x, a, c):
|
|
return (a * x + c) % M
|
|
|
|
if __name__ == "__main__":
|
|
if len(sys.argv) != 4:
|
|
print("Usage: python3 solve_lcg.py x0 x1 x2")
|
|
sys.exit(1)
|
|
x0 = int(sys.argv[1]) & 0xffffffff
|
|
x1 = int(sys.argv[2]) & 0xffffffff
|
|
x2 = int(sys.argv[3]) & 0xffffffff
|
|
a, c = recover_params(x0, x1, x2)
|
|
if a is None:
|
|
print("Could not invert difference; try different consecutive outputs.")
|
|
sys.exit(1)
|
|
print("Recovered parameters:")
|
|
print("a = 0x%08x (%u)" % (a, a))
|
|
print("c = 0x%08x (%u)" % (c, c))
|
|
nxt = next_value(x2, a, c)
|
|
print("Predicted next (decimal):", nxt)
|
|
print("Predicted next (hex): 0x%08x" % nxt)
|