Pseudo Random Generators

In the previous post, I discussed about the two paradigms of generating Random Numbers. Now in the case of OTP cipher, using it practically does not make any sense because if one had a "secure" way to transfer the 'n' bit string to the receiver, he may use that way to transmit his original message itself and the whole idea of need of cipher would be scrapped. 

So in order to make our first "Good" cipher practically applicable, lets replace the key with the total random key to pseudo random key. Now before generating a pseudo Random key, lets see how a Pseudo Random Generator (PRG) works.

So basically PRG is an algorithm which takes a really small sample space called "seed space" lets say a 's' bit string and like the case in previous scenario, where we had a message of length of n bits, here the key point will be that the "seed space" will be much much smaller than the message space. 

This means that lets say seed space is 32 bits long, we can safely have message space of order of megabytes or even gigabytes. The only difference is that a PRG will be basically a deterministic algorithm(it should always be a deterministic algorithm) therefore there will be no randomness in it, the only thing that will be random is the 'seed space' and it will deterministically map it to the key space which will "appear" to be random but will not be random at all. Now while we know as per information theory by Claude Shannon, in order to maintain the perfect secrecy, key should be greater than or equal to the message length. Here we have a long key space to XOR the message with but basically the criteria length of "key" which is supposed to be greater than or equal to that of the message space is not fulfilled as the "seed space" is acting as "key" in this scenario, ergo the lemma of perfect secrecy is not fully accomplished.