14

Is it possible to reverse a pseudo random number generator? For example, take an array of generated numbers and get the original seed. If so, how would this be implemented?

dpr
  • 10,591
  • 3
  • 41
  • 71
Cenregoth
  • 173
  • 1
  • 1
  • 6
  • 2
    i would think that there is always more than one seed that can generate a sequence of numbers no matter what the length...you can probably find a seed but there should be more than one...and even if you find one it might not be right since the next number in the sequence is unknown – Logan Murphy Nov 04 '14 at 20:03
  • 1
    Let's assume that the equation to get the next pseudo-random number is invertible. Given a number generated by the formula, you can then apply the inverse to get the previous pseudo-random number. Is this the seed? How do you know? If you apply the inverse formula once more, is that the seed? Or should you apply the inverse 12,842 more times? – beaker Nov 04 '14 at 20:31

3 Answers3

7

This is absolutely possible - you just have to create a PRNG which suits your purposes. It depends on exactly what you need to accomplish - I'd be happy to offer more advice if you describe your situation in more detail.

For general background, here are some resources for inverting a Linear Congruential Generator: Reversible pseudo-random sequence generator

pseudo random distribution which guarantees all possible permutations of value sequence - C++

And here are some for inverting the mersenne twister: http://www.randombit.net/bitbashing/2009/07/21/inverting_mt19937_tempering.html http://b10l.com/reversing-the-mersenne-twister-rng-temper-function/

Community
  • 1
  • 1
Jonathan Basile
  • 649
  • 1
  • 10
  • 20
0

In general, no. It should be possible for most generators if you have the full array of numbers. If you don't have all of the numbers or know which numbers you have (do you have the 12th or the 300th?), you can't figure it out at all, because you wouldn't know where to stop.

You would have to know the details of the generator. Decoding a linear congruential generator is going to be different from doing so for a counter-based PRNG, which is going to be different from the Mersenne twister, which is going to be different with a Fibonacci generator. Plus you would probably need to know the parameters of the generator. If you had all of that AND the equation to generate a number is invertible, then it is possible. As to how, it really depends on the PRNG.

thugthrasher
  • 29
  • 2
  • Are there any of these for which if you knew the index and a few characters you would still not be able to reverse it? – Andrew Aug 30 '19 at 13:50
  • Ah: https://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator "CSPRNG requirements fall into two groups: first, that they pass statistical randomness tests; and secondly, that they hold up well under serious attack, even when part of their initial or running state becomes available to an attacker." – Andrew Aug 30 '19 at 13:56
0

Use the language Janus a time-reversible language for doing reversible computing.

You could probably do something like create a program that does this (pseudo-code):

x = seed
x = my_Janus_prng(x)
x = reversible_modulus_op(x, N) + offset

Janus has the ability to give to you a program that takes the output number and whatever other data it needs to invert everything, and give you the program that ends with x = seed.

I don't know all the details about Janus or how you could do this, but just thought I would mention it.

Clearly, what you want to do is probably a better idea because if the RNG is not an injective function, then what should it map back to etc.

So you want to write a Janus program that outputs an array. The input to the Janus inverted program would then take an array (ideally).

MathCrackExchange
  • 595
  • 1
  • 6
  • 25