2
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Chris Peikert
    Commented Sep 17, 2014 at 23:17
  • $\begingroup$ 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? $\endgroup$
    – Aaron Tracy
    Commented Sep 19, 2014 at 21:41
  • $\begingroup$ That's right. So, for example, the description of Salsa20 will describe the algorithm for computing the generator. $\endgroup$
    – Chris Peikert
    Commented Sep 20, 2014 at 0:23
  • $\begingroup$ Check this video , good introduction with visualization usenix.org/conference/woot14/technical-sessions/presentation/… $\endgroup$
    – sashank
    Commented Sep 22, 2014 at 4:05

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Travis Mayberry
    Commented Sep 23, 2014 at 13:12
  • $\begingroup$ @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? $\endgroup$
    – David Cary
    Commented Sep 24, 2014 at 1:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – Travis Mayberry
    Commented Sep 27, 2014 at 16:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.