Solve Week 1 Question 2 in Stanford Crypto Course

w1q2.py

CT = (210205973, 22795300, 58776750, 121262470, 264731963, 140842553, 242590528, 195244728, 86752752)
P = 295075153L   # about 2^28

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

    def next(self):
        # x_{i+1} = 2*x_{i}+5  (mod p)
        self.x = (2*self.x + 5) % P

        # y_{i+1} = 3*y_{i}+7 (mod p)
        self.y = (3*self.y + 7) % P

        # z_{i+1} = x_{i+1} xor y_{i+1}
        return (self.x ^ self.y)
    

#guess x0
for x0 in range(P,0,-1):
	tmp = CT[0] ^ ((2*x0+5)%P)
	if tmp>P:
		continue
	y0 = (196716769 * (tmp -7))%P	#196716769= inverse_mod(3,P)
	prng = WeakPrng(P, x0, y0)
	if (prng.next() != CT[0]):
		print x0, y0
	flag = True
	for i in range(1, 9):
		if prng.next() != CT[i]:
			flag = False
			break
	if flag==True:
		print 'prng.next()=',prng.next()
		print 'x0=',x0,'y0=',y0