Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
2  
That is not true out of context. Do you have the complete citation which says that? –  Thomas Jul 8 '13 at 14:40
    
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. –  mikeazo Jul 8 '13 at 14:41
    
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? –  rath Jul 8 '13 at 14:56

1 Answer 1

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.

share|improve this answer
    
+1 for the "note". –  e-sushi Jul 8 '13 at 18:55
    
Can you explain the term 'state' used above –  DDR Jul 9 '13 at 0:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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