The One-Time Pad: What is it?
By DdUcation
http://www.to2600.org
1.1 "Introduction"
1.2 "How Does It Work?"
1.3 "The Random Number Problem"
1.4 "The 'Delivery of Pad' Problem"
1.5 "Public-Key Encryption And The One-Time Pad"
1.6 "Who Uses it?"
1.7 "Conclusion"
1.8 "Shoutouts!"
1.1 "Introduction":
It has been called the "perfect encryption scheme" by more then
one cryptography expert, but (as we will soon see) nothing is perfect.
Invented in 1917 by Major Joseph Mauborgne and AT&T's Gilbert Vernam
(notice: unlike many other papers I have read, I have NOT cited the
Russians or the Soviet Union as the original authors!) the One-Time
Pad is a simple and unbreakable encryption scheme. Simple enough
to be used by an elementary-school graduate, and supposedly unbreakable
by any of today's current technologies. The One-Time Pad gets its name
from the fact that it was originally a key, written down on a pad of
paper, used to encrypt and decrypt messages sent back and forth between
military personnel.
1.2 "How Does It Work?"
The One-Time Pad is a surprisingly simple "Substitution Cipher"
in it's functionality. First, write your message. Then write down a
series of characters from the alphabet which are completely random and
as long, if not longer, then your message. This series of characters
is now your key. Now assign numbers to each letter in the alphabet
(i.e. 1 to 26) Now the cryptographer uses one letter from the key, for
every letter in the message, with the formula:
K = Key character, M = Message character, C = ciphered character
M + K mod 26 = C
So the cipher text is the message text + the Key text modulo 26. "What
the hell is 'Modulo'" you ask? Modulo is concept used in Number Theory.
Let me
give you an example. If we have the number 8, then we say "8
mod 26 = K", then K = 8-26 = -18 = 1*-18 = 2*-9 etc. Where 8 mod 26 is
always equal to the second number in the multiplication (i.e. -18,-9).
And so 8 mod 26 = -18 or -9.
In the examples here we will say that 8 mod 26 = -18. If you still don't
understand then I suggest you google search for "modulo", or simply goto
http://www.cacr.math.uwaterloo.ca/hac/ and download the chapter 2, which
talks about the Mathematical Background. Back to how all this junk works:
So if we assign the number 1 to 26 to all the letters in the alphabet
(where A=1...Z=26) and then take the message:
ONETIMEPAD
and the Key:
TBFRGFARFM
And M+Kmod26
=O+Tmod26
=15+20mod26
=15+(20-26)
=9
=I
Therefore C = I
Following this formula for each and every letter we get C=
IPKLPSFHGQ
to decode we simply reverse the process:
as M + Key mod 26 = C
Then as C - Key mod 26 = M
"But wait a second. This is just a simple Substitution cipher, what
happens if someone finds out what key I'm using?"
They can't, because after you're done encrypting and decrypting the message,
you destroy the portion of the Pad from which you've taken the key. Thus
you never reuse the same key twice (that's the idea anyway) and there are no
patterns or correlations which can be made from one letter to the next. So
even if an individual were somehow able to find a copy of the message and the
cipher text, there would be no way for them to decrypt future intercepted msgs
which were encrypted. The most amazing thing about this is that for different
keys and cipher text combinations, come different decrypted messages!
For example, taking the ciphertext which we got from the message "ONETIMEPAD",
and decrypting it with a different Key, we get a phrase which makes sense, but
is not the original message:
C = IPKLPSFHGQ
K = POYYAEAAZX
which decrypts to : "SALMONEGGS" NOT "ONETIMEPAD".
And so even when supposedly logical data is extracted from the ciphertext,
the one-time pad still keeps it's original message secret.
1.3 "The Random Number Problem"
Despite the appearance of complete security and perfect cryptology,
there are some essential problems with One-Time Pads, the least of which is the
user's ability to access a reliable source of random characters from which to
construct the Pad. If there is ANY pattern held within the key which (after
several attempts and examinations of separate messages back and forth between
individuals) can be revealed by a cryptologist, then the jig is up. After
discovering any kind of pattern in the supposed random pad, a good cryptologist
can then exploit that to decrypt a series of messages wherein this pattern lays.
While I acknowledge the strictly theoretical stance I am taking, it must also
be noted that as we advance further and further technologically, the
possibility of the theoretical occurring comes closer and closer. In any case,
it should be noted that a proper One-Time Pad is completely random, and that
anything less then that would be potentially crackable.
1.4 "The Delivery Of The Pad Problem"
Another inherent difficulty lies in the delivery of the pad itself.
While several supposedly secure protocols have been established for the
transferring of keys and passwords (i.e. Neuman-Stublebine, Multiple-Public
Key protocols etc.) they are slow, tedious, and exploitable. The difficulty
with the one-time pad is that if at any point a large section of it should
become accessible to outsiders (without the user's notice) then the entire
system's privacy is immediately compromised.
1.5 "Public-Key Encryption And The One-Time Pad"
Currently the most widespread protocol in transferring keys for
cryptography is through Public-Key Cryptography Protocols. Public-Key
Cryptography, while being essentially secure, can be compromised should an
individual gain access to the KDC, or load key-logging programs onto the
computers of individuals who use it. In addition it could be suggested that
those parties who use One-Time Pads are most probably utilizing Public-Key
Cryptography in order to transfer those Pad files. And so we see how it may
be possible to access the One-Time Pad files which are essential to the
secure transmission of data across such a network.
1.6 "Who Uses It?"
It has been suggested, and there is a great deal of evidence, that
the military is a primary user of One-Time Pad cryptography. One-Time Pad's
are NOT practical in any sense of the word. They require extremely tight
protocols and the mathematical know-it-all to pull off a completely random
key generator which will go forever. I suggest that only government would
bother with such large expense for secrecy.
1.7 "Conclusion"
In conclusion, when dealing with one-Time Pad use, special attention
MUST be paid to randomization, and ESPECIALLY to the protocols and security
measures put in place to keep the Pad a secret. One-Time Pad's are
completely impractical unless the most extreme cases of privacy are necessary.
If you're interested in learning more about cryptography I would strongly
suggest "Applied cryptography" by Bruce Schneier as it's where I got the
Keys and Messages which I used in the example. PEACE!
1.8 "Shoutouts!" and add shouts. because shouts are fun
I'd like to give shoutouts to dec0de, theclone, Kris, caesium,
grinthock, HiMY, to2600, barrie2600, my Dad (because I love him and he's
in the hospital after suffering a heart-attack)
edited by dec0de