Skip to content

Instantly share code, notes, and snippets.

@raullenchai
Created March 27, 2012 18:46
Show Gist options
  • Save raullenchai/2219060 to your computer and use it in GitHub Desktop.
Save raullenchai/2219060 to your computer and use it in GitHub Desktop.
Solve Week 1 Question 2 in Stanford Crypto Course
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment