example.py

import random
import gmpy2
from Crypto.Cipher import AES
import sys
import os
# Linear Congruential Generator breaker example
P = 295075153L # This will work as our LCG "secret"

class WeakPrng(object):
    def __init__(self, p):   # generate seed with 56 bits of entropy
        self.p = p
        self.x = random.randint(0, p)

    def next(self):
        self.x = (2*self.x + 5) % self.p # On this case, our 'a' and 'c' are 2 and 5 respectivelly. 
        return self.x  
  
def calc_det(i,j,X): #This determinant along with the GCD will allow us to get 'p' with a very high probability!
	""" Calculate the values for the matrix[lattice] """
	a1 = X[i] - X[0]
	b1 = X[i+1] - X[1]
	a2 = X[j] - X[0]
	b2 = X[j+1] - X[1]

	""" Calculate the determinant """
	det = a1*b2 - a2*b1
	return abs(det)

def GCD(a,b):
	""" Euclidean Algo"""
	a = abs(a)
	b = abs(b)
	while a:
			a,b = long(b%a),a
	return b

prng = WeakPrng(P)
X = []
for i in range(0, 10):
	X.append(prng.next())
	print "output #%d: %d" % (i, X[i])
Det_X = []
Det_X.append(calc_det(1,2,X))
print Det_X
Det_X.append(calc_det(2,3,X))
print Det_X
Det_X.append(calc_det(3,4,X))
print Det_X
Det_X.append(calc_det(4,5,X))
print Det_X

found_p = GCD(Det_X[0], Det_X[1])
found_p = GCD(found_p, Det_X[2])
found_p = GCD(found_p, Det_X[3])
print found_p # This is our 'p'! Using only 5 intercepted numbers generated by the LCG we were able to succesfully break the "secret" modulo! Now its easy to find out 'a' and 'c'


# To find 'a' and 'c' we need to solve the simple equation:
#	a = ((x3 - x4)*INVERSE_MODULE((x2-x3),p))%p
# And:
# c = (x4 - a*x3)%p
# Where x2, x3, x4 are all numbers generated by the LCG that we got already!

mod_inv_a = gmpy2.invert((X[2]-X[3]), found_p) # Here we find the modular inverse of x2-x3 with modulo p
print (X[2]-X[3])%found_p
found_a = ((X[3] - X[4])*mod_inv_a)%found_p
print found_a #found_a will be the correct a with high probability.

found_c = (X[4] - found_a*X[3])%found_p
print found_c #found_c will be the correct a with high probability, clearly depending on the correctness of a

print "Now we found: %d as P, %d as a and %d as c, so we can forge the LCG!" % (found_p, found_a, found_c)