Date: Tue, 27 Jun 1995 11:30:44 EDT
From: "Randy Nichols, ACA Pres." <75542.1003@compuserve.com>
Message #3c
Three Classical Ciphers From Russkaya Kriptologia Historica
(continued)
ONE-TIME PAD (OTP)
The One-Time Pad is truly an unbreakable cipher system. There are
many descriptions of this cipher. One of the better descriptions
is by Bruce Schneier. (14) It consists of a nonrepetitive truly
random key of letters or characters that is used just once. The
key is written on special sheets of paper and glued together in a
pad. The sender uses each key letter on the pad to encrypt
exactly one plaintext letter or character. The receiver has an
identical pad and uses the key on the pad, in turn, to decrypt
each letter of the ciphertext. (19)
Each key is used exactly once and for only one message. The
sender encrypts the message and destroys the pad's page. The
receiver does the same thing after decrypting the message. New
message - new page and new key letters/numbers - each time. (14)
The one-time pad is unbreakable both in theory and in practice.
Interception of ciphertext does not help the cryptographer break
this cipher. No matter how much ciphertext the analyst has
available, or how much time he had to work on it, he could never
solve it. (1)
The reason is that no pattern can be constructed for the key.
The perfect randomness of the one time system nullifies any
efforts to reconstruct the KEY or PT via horizontal or lengthwise
analysis, via cohesion, via re-assembly (such as Kasiski or
Kerckhoff's columns) via repeats or via internal framework
erection. (1), (14), (15), (16)
Brute force (trial and error) might bring out the true plaintext
but it would also yield every other text of the same length, and
there is no way to tell which is the right one. The worst of it
is that the possible solutions increase as the message lengthens.
Supposing the key were stolen, would this help to predict future
keys? No, because a random key has no underling system to
exploit. If it did, it would not be random. (1)
A random key sequence XORed with a nonrandom PT message produces a
completely random ciphertext message and no amount of computing
will change that. (14) The OTP can be extended to encryption
of binary data. Instead of letters, we use bits. (14)
FRESH KEY DRAWBACK
The OTP has a drawback - the quantities of fresh key required.
For military messages in the field (a fluid situation) a practical
limit is reached. It is impossible to produce and distribute
sufficient fresh key to the units. During WWII, the US Army's
European-theater HQs transmitted, even before the Normandy
invasion, 2 million five (5) letter code groups a day! It would
of therefor consumed 10 million letters of key every 24 hours -
the equivalent of a shelf of 20 average books. (16)
RANDOMNESS
The real issue for the OTP, is that the keys must be truly random.
Attacks against the OTP must be against the method used to
generate the key itself. (14) Pseudo-random number generators
don't count; often they have nonrandom properties. Reference (14)
Chapter 15, discusses in detail random sequence generators and
stream cipher. I take exception to his remarks regarding keyboard
latency measurement. IMHO, people's typing patterns are anything
but random (especially us two finger types). (14) (18)
OTP SIMPLE EXAMPLE W/O SUPERENCIPHERMENT OR XOR
Begin with a cipher (A=1, B=2 ...)
PT: T A X A T I O N I S T H E F T
CE: 20 1 24 1 20 9 15 14 9 19 20 8 5 6 20
>From a table of truly random numbers:
10480 15011 01536 02011 81647 91646 69719 22368
45673 25595 85393 30995 89198 27982 24130 48360
22527 97265 76393 64809 15179 42167 ....
Add the cipher equivalent to the random key:
T A X A T I
20 1 24 1 20 9
10480 15011 01536 02011 81647 91646
----- ----- ----- ----- ----- -----
10500 15012 01560 02012 81667 91655
Transmit new CT:
10500 15012 01560 02012 81667 91655 69734 .....
Receiver subtract key out of message and decodes equivalents.
Many variations exist. Note T1 .ne. T2 .ne. T(i)
(17) in CT: A1 .ne. A2 .ne. A(i) etc
Random numbers can be found in newspapers (WSJ), phonebooks
and trade magazines, etc.
HISTORICAL CONSIDERATIONS
The OTP originated from the work of Gilbert Vernam in 1917.
Vernam worked for ATT. He got his idea from the French
telegrapher Emile Baudot. Baudot code replaces letters with
electrical impulses, called units. Every character was given 5
units that either signified a pulse of electrical current
("marks") or its absence ("spaces") during a given time period.
[ 32 combinations in all ]. In 1917, paper tape was used and the
marks and spaces were read by metallic fingers. Vernam
essentially automated the process and devised a cipher on it.
(22), (26)
In modern terms, key bits were added modulo 2 to plaintext bits
on a bit by bit basis. If X = x1, x2, x3.. denotes the PT, and
K = k1, k2, k3 .. the keystream, Vernam's cipher produces a CT
bit stream Y = Ek(X) = y1, y2, y3.. , where y(i) = (X(i)+
k(i)) mod 2 for i =1,2,3.. Implementation by the exclusive-OR
function for each pair of PT -Key bits as in a linear feedback
shift register. (20), (27)
Major Joseph Mauborgne extended Vernam's work. He found
repetitions in keys after two tapes. It made the code susceptible
to analysis by superimposition [Kerckhoff reconstruction].
He combined the Vernam cipher with the U.S. Army Signal Corp
nonrepeating key. (16) He welded together the randomness of the
key in the Vernam with the nonrepeatability of the key from
the Signal Corp. (23), (24) (25)