Skip to main content
IBM 
ShopSupportDownloads
IBM HomeProductsConsultingIndustriesNewsAbout IBM
IBM : developerWorks : Security : Education - online courses
Introduction to cryptology: Pt. 3
Download tutorial zip fileView letter-sized PDF fileView A4-sized PDF fileE-mail this tutorial to a friend
Main menuSection menuGive feedback on this tutorialPreviousNext
2. Background and reminders
  


Impossible things with random numbers, part 2 page 5 of 8


Finding a way of making one-time pads (OTPs) from PRGs is something like a philosopher's stone for beginning cryptologists. One-time pads, you may recall, have the wonderful property of being provably and unconditionally secure. As long as genuinely random data (of the same length as the message being encoded) is used only once, an attacker has absolutely no way of deciphering which message (of the given length) was encoded. Further, an attacker's failure here is not just a computational matter of exceeding the MIPS of all the computers that exist (or might be built), but rather the mathematical fact that nothing distinguishes an actual crack from a false decipherment.

Of course, OTPs have the inconvenient quality of requiring the out-of-channel exchange of a great deal of key material. And the key material gets used up automatically as messages are sent (unlike the keys in other algorithms which can be reused over many messages without being consumed, per se). As a consequence, a lot of beginners develop an understandable desire to combine the provable security of OTPs with the finite key distribution requirements of other systems. The result is, frequently, a system that will generate "keys" for a purported OTP system by using pseudo-random generators. PRGs can keep generating new "key" material indefinitely; and at a first pass, these keys appear to have the same statistical and stochastic properties as true random key material.

The catch is that pseudo-random key generators really do not have the same deep properties as true random keys. Many PRGs are quite good, but in the end, their entropy is as finite as their algorithms and seeds; they always exhibit cyclical patterns. Mind you, finding these patterns might require serious cryptanalysis. And in the best case (such as with many good stream ciphers), the security provided by PRGs is quite adequate -- even comparable with other strong systems. But this is no free lunch: A PRG is not really an OTP.


Main menuSection menuGive feedback on this tutorialPreviousNext
PrivacyLegalContact