I a have a question about PRNGs and this is my very first experience with them. I have the following generator that takes a 56-bit seed 'p' during initialization and then chooses both X and Y randomly from the interval [0, p].
Every time it is called, it returns the output of the next function:
def next(self): self.x = (2*self.x + 5) % self.p self.y = (3*self.y + 7) % self.p return (self.x ^ self.y)
I have the first 9 outputs of the generator and i need to predict the next output.
prng_output = [210205973, 22795300, 58776750, 121262470, \ 264731963, 140842553, 242590528, 195244728, 86752752]
I have thought of the solution which turned out to be correct by VERY slow, so apparently there must be another way to solve it.
My solution was to constrain the range of values for p according to the given output. Also, generate all values for X and for every value of X, calculate the first 9 values according to the previous equation and XOR it with the output to get Y. Finally, check of the sequence of Ys is valid or not (also according to the previous equation).
After some reading i knew that a reduced state (reduce the number of bits) of the generator can be determined.
So my question is how to crack the given generator ? and what is the 'reduced state' of the generator and how to use it ?
So if someone can help me with some details or a 'useful' link to read to understand more, i would be thankful.