# Understanding Pseudo Random Generators

I've been taking a crypto course online. I have a good idea how PRG's and Stream Ciphers work, but I'd love to get some input to help visualize what is actually happening. I understand a seed is used, then expanded into a keyspace. Is this correct?

So: $G: \{0,1\}^s \to \{0,1\}^n , n \verb|>>| s$

From what I understand.. For a generator (function $G$) a random seed from all $s$ bit seedspace is mapped to an $n$ bit string.

I'm having trouble conceptualizing is the "mapping" of the random seed to the key (I might be totally incorrect with the way I'm phrasing this). Is this process laid out in the actual cipher (e.g., CSS, Salsa20) or there something else going on?

• There will be an algorithm that computes the function $G$, i.e., the algorithm will take some $s$-bit input $k$ and will output the $n$-bit value $G(k)$. The algorithm is typically described as a mathematical procedure, or in a programming language. Sep 17 '14 at 23:17
• Thanks @ChrisPeikert That really helps, I appreciate you taking the time to answer this. So that algorithm, the mathematical procedure is described in the protocol for each algorithm? Sep 19 '14 at 21:41
• That's right. So, for example, the description of Salsa20 will describe the algorithm for computing the generator. Sep 20 '14 at 0:23
• Check this video , good introduction with visualization usenix.org/conference/woot14/technical-sessions/presentation/… Sep 22 '14 at 4:05

The way I picture it, a pseudorandom number generator (PRNG) has a box of bytes called "internal state".

Seeding the PRNG sets that box of bytes to some deterministic function of the seed.

Every time you ask the PRNG for another number, the PRNG "stirs the pot" to some new state -- using a deterministic function of the previous state. The PRNG also generates an output integer that is some function of one or more bytes in the box of internal state.

I'm not sure where you are getting the "n" in your question -- every PRNG I've ever encountered will continue to produce numbers indefinitely, no matter how many numbers it has already generated since you seeded the PRNG.

The size of the box, the specific deterministic functions used by some PRNG, etc. are generally spelled out in detail in the description of that PRNG.

You may be interested in CipherSaber, Salsa20, Fortuna, etc.

• The theoretical definition of a PRG is a function which maps a uniformly random seed to a larger, but fixed size, string which is indistinguishable from random to all deterministic, polynomial time adversaries. As long as you have a PRG with at least one bit of stretch (i.e. $n-s \geq 1$), though, you can bootstrap it into one which has stretch polynomial in the security parameter. Sep 23 '14 at 13:12
• @TravisMayberry: Would you mind telling me what "n" is for RC4/CipherSaber, Salsa20, or some other real PRNG implementation? Or are you pointing out a difference between the theoretical definition, and what I see in practice? Sep 24 '14 at 1:09
• Yes, there is a gap between the theory and practice. A PRG is a very specific theoretical construct which has the above definition. A PRNG is usually meant to describe a more practical and less strictly defined concept of an algorithm which outputs some large (but not infinite) series of pseudorandom numbers. Sep 27 '14 at 16:42