RSA, DES, AES, etc. all use (relatively) complicated mathematics to encrypt some
ID: 651271 • Letter: R
Question
RSA, DES, AES, etc. all use (relatively) complicated mathematics to encrypt some message with some key. For each of these methods, there have been several documented vulnerabilities found over the years. Some even believe that there is a vulnerability in AES known only to the NSA.
On the other hand, the One-time pad is not only ridiculously simple, but also has been shown to be impossible to crack (if used appropriately).
Say you have some message to be encrypted with length n. Simply generate a random string with length m where m is at least as large as n, and perform modular addition of the random string onto the message.
As long as the random string is generated with a high-enough quality random number generator, and as long as the same one-time pad isn't use on multiple messages, it should be impossible to crack.
If this is true, all we would need to perfect are fast, cryptographically secure deterministic random number generators. Use the key as a starting seed for the RNG and you have a powerful uncrackable encryption scheme which is simple to understand and implement.
Blum-Blum-Shub is a fast, cryptographically secure PRNG, and there are others too.
I have written a C++ program which uses two 2048-bit primes (which match the necessary criteria) for Blum-Blum-Shub and uses a password which the user enters - converted into a starting seed - to run byte-wise modular addition. The process is fast, deterministic, and if the literature I have read is correct then it should be very secure.
So why is so much time and effort invested in coming up with convoluted encryption cyphers when mathematics shows that the simplest is often the best?
Explanation / Answer
The main difficulty with the one-time pad is that it requires pre-arrangement. In order for me to use a one-time pad to communicate with you, we must either have arranged ahead of time for a one-time pad that we will use (which must be as large as our communication will be), or else we must have some secure way of communicating that will allow us to agree on a one-time-pad for use.
If we have a secure channel to communicate so we can agree on a one-time-pad, then why bother? Let's just communicate through the secure channel.
If we don't have a secure channel, then we cannot engage in secret communication ex-nihilo, since we will not have a one-time-pad agreed on.
Now, if you are going to generate the one-time-pad via a pseudo-random number generator, how are you going to get that one-time pad to me? You must tell me your seed (so that I can generate the same pseudo-random sequence and I can decode the message), in which case we are back to the problem of how you tell me what your seed is without a secure channel to communicate with. So now we have two points of vulnerability: the channel we use to communicate so you can give me the seed; and the fact that a pseudo-random number generator is not truly a random number generator, and so may be susceptible to attack as well.
There is also the problem of distribution; to use one-time pads effectively, no pad can be used more than once. There were intercepts that the NSA had from back in the 50s; when the Soviets mistakenly used the same one-time-pads to encode some messages in the 80s, this was enough to break the encryption in both cases. That means that each message will need a new seed and a new password; so each time you want to communicate you need a new seed/key and a new password. It is just too easy to lose the information, or to re-use it by mistake and thus make the entire thing a wash.
One time pads are effective for pre-established channels of communication with low bandwidth; they are almost useless for initiating remote secret communication with someone you have never communicated with before, and they require a lot of bandwidth to use correctly.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.