Pseudo Random Generator with same output

Question

I came across an article about Car remote entry system at http://auto.howstuffworks.com/remote-entry2.htm In the third bullet, author says,

Both the transmitter and the receiver use the same pseudo-random number generator. When the transmitter sends a 40-bit code, it uses the pseudo-random number generator to pick a new code, which it stores in memory. On the other end, when the receiver receives a valid code, it uses the same pseudo-random number generator to pick a new one. In this way, the transmitter and the receiver are synchronized. The receiver only opens the door if it receives the code it expects.

Is it possible to have two PRNG functions producing same random numbers at the same time?

Answer 1

In PRNG functions, the output of the function is dependent on a 'seed' value, such that the same output will be provided from successive calls given the same seed value. So, yes.

An example (using C#) would be something like:

// Provide the same seed value for both generators:
System.Random r1 = new System.Random(1);
System.Random r2 = new System.Random(1);

// Will output 'True'
Console.WriteLine(r1.Next() == r2.Next());

This is all of course dependent on the random number generator using some sort of deterministic formula to generate its values. If you use a so-called 'true random' number generator that uses properties of entropy or noise in its generation, then it would be very difficult to produce the same values given some input, unless you're able to duplicate the entropic state for both calls into the function - which, of course, would defeat the purpose of using such a generator...

In the case of remote keyless entry systems, they very likely use a PRNG function that is deterministic in order to take advantage of this feature. There are many ICs that provide this sort of functionality to produce random numbers for electronic circuits.

Edit: upon request, here is an example of a non-deterministic random number generator which doesn't rely upon a specified seed value: Quantum Random Number Generator. Of course, as freespace points out in the comments, this is not a pseudorandom number generator, since it generates truly random numbers.

Answer 2

Most PRNGs have an internal state in the form of a seed, which they use to generate their next values. The internal logic goes something like this:

nextNumber = function(seed);
seed = nextNumber;

So every time you generate a new number, the seed is updated. If you give two PRNGs that use the same algorithm the same seed, function(seed) is going to evaluate to the same number (given that they are deterministic, which most are).

Applied to your question directly: the transmitter picks a code, and uses it as a seed. The receiver, after receiving it, uses this to seed its generator. Now the two are aligned, and they will generate the same values.

Answer 3

As Erik and Claudiu have said, ad long as you seed your PRNG with the same value you'll end up with the same output.

An example can be seen when using AES (or any other encryption algorithm) as the basis of your PRNG. As long as you keep using an inputs that match on both device (transmitter and receiver) then the outputs will also match.