0
$\begingroup$

I am new to this cryptography and in the source from which i study it is said that if we know the first few bits of a pseudo random sequence we can predict the whole of it.How is it possible? The source:http://www.youtube.com/watch?v=NjedHm04ETM move to 7min 40sec and this is the source.

$\endgroup$
  • 2
    $\begingroup$ That is not true out of context. Do you have the complete citation which says that? $\endgroup$ – Thomas Jul 8 '13 at 14:40
  • $\begingroup$ You'll have to give more detail in your question for it to be answerable. What is the source? How is the pseudorandom sequence generated? In other words, we need more context to be able to answer your question. $\endgroup$ – mikeazo Jul 8 '13 at 14:41
  • $\begingroup$ To view Dan Boneh's lectures on Coursera you need to sign up. They are uploaded on YouTube however, could you post that link instead? Is it this one? $\endgroup$ – rath Jul 8 '13 at 14:56
3
$\begingroup$

All psuedo random generators keep some limited state to calculate the next number in the sequence. you can think of it like a function $\delta(S)= \{output, S'\}$ with $S$ the internal state of the generator and represented by a finite number of bits.

This means that the number of states is limited (though it can be very big: a standard mersenne twister holds 2500 bytes of state)

As such if you get $n$ bytes of output with $n$ is larger than the number of bytes in the state then you can reasonably predict the current state of the output given enough time.

Note that if you group 256 bytes of output together and pass it though a sha-256 then it will take a very long time for you to restore first the original output of the generator and then the state when you know only the hash output. This is exactly how a secure PRNG works.

$\endgroup$
  • $\begingroup$ Can you explain the term 'state' used above $\endgroup$ – Nithin Jose Jul 9 '13 at 0:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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