# CSCamp CTF Quals 2k13: Crypto - Predictor


can you predict the next number in the sequence?

[51751041,236753494,190402293,48644501,297659248,230684862,7697029,173742959,126005793]

The code used to create those numbers is

import random
i = 295075153L
x = random.randint(0, i)
y = random.randint(0, i)
for j in range (1,10):
x = (2*x + 5) % i
y = (3*y + 7) % i
print (x^y)

The flag will be the next number in the sequence

# cat predictor.py
#!/usr/bin/python

import random 

i = 295075153

def sequence(x,y):
 for j in range (1,11):
  x = (2*x + 5) % i
  y = (3*y + 7) % i
  print (x^y)

y = 0
while True:
 y1 = (3*y + 7) % i
 x1 = y1^51751041
 x2 = (2*x1 + 5) % i
 y2 = (3*y1 + 7) % i
 if x2^y2 == 236753494:
  print "y = " + str(y)
  x = 0
  '''
  while True:
   if x1 == (2*x + 5) % i:
    print "x = " + str(x)
    sequence(x,y)
    exit()
   x += 1
  '''
  x = (i + x1 - 5) / 2
  print "x = " + str(x)
  sequence(x,y)
  exit()
 y += 1
# ./predictor.py
y = 173565935
x = 268355495
51751041
236753494
190402293
48644501
297659248
230684862
7697029
173742959
126005793
103605566

2 comments:

bibo said...
This comment has been removed by the author.
bibo said...

No need second loop to find x when you had x1 at first loop