Edgar Allan Poe, the renowned American poet and writer, was captiva...
The price of sending a letter in the United States has steadily inc...
### One-time pad The one-time pad (OTP) is a type of encryption th...
According to historical accounts, such as Suetonius' "Lives of the ...
Rudolf Ivanovich Abel, whose real name was William August Fisher, w...
#### Caesar cipher A Caesar cipher, also known as a shift cipher, ...
Whitfield Diffie and Martin Hellman are two renowned American crypt...
The message encoded in this ciphertext was deciphered in 1994. The ...
RSA is an asymmetric encryption algorithm that builds upon the grou...
Fermat's little theorem is named after the 17th-century French math...
Despite the original estimate, the prime factors were actually foun...
Two numbers are considered relatively prime (or coprime) if their g...
I -
A new kind of cipher that would
take millions of
to break
by Martin Gardner
"Few persons can be made to believe
that it is not quite an easy thing to invent
a method of secret writing which shall
baffle investigation. Yet it may be
roundly asserted that human ingenuity
cannot concoct a cipher which human
ingenuity cannot resolve."
he upward creep of postal rates
accompanied by the deterioration
of postal service is a trend that
inay or may not continue, but as far as
"[most private communication is con-
cerned, in a few decades it probably will
matter. The reason is simple. The
: transfer of information will probably be
much faster and much cheaper by "elec-
tronic mail" than by conventional postal
- systems. Before long it should be possi-
ble to go to any telephone, insert a mes-
sage into an attachment and dial a num-
ber. The telephone at the other end will
print out the message at once.
Government agencies and large busi-
nesses will presumably be the first to
make extensive use of electronic mail,
followed by small businesses and pri-
vate individuals. When this starts to
happen, it will become increasingly de-
. sirable to have fast, efficient ciphers to
safeguard information from electronic
eavesdroppers. A similar problem is in-
volved in protecting private information
stored in computer memory banks from
snoopers who have access to the mem-
. ory through data-processing networks.
It is hardly surprising that in recent
years a number of mathematicians have
asked themselves: Is it possible to devise
a cipher that can be rapidly encoded and
decoded by computer, can be used re-
peatedly without changing the key and
01 23456789ABCDEFGH
A Caesar cipher with a 10-shift
is unbreakable by sophisticated crypt-
analysis? The surprising answer is yes.
The breakthrough is scarcely two years
old, yet it bids fair to revolutionize the
entire field of secret communication. In-
' deed, it is so revolutionary that all previ-
ous ciphers, together with the tech-
niques for cracking them, may soon
fade into oblivion.
An unbreakable code can be unbreak-
able in theory or unbreakable only in
practice. Edgar Allan Poe, who fancied
himself a skilled cryptanalyst, was con-
vinced that no cipher could be invented
that could not also be "unriddled." Poe
was certainly wrong. Ciphers that are
unbreakable even in theory have been in
use for half a century. They are "one-
time pads," ciphers that are used only
for a single message. Here is a sim-
ple example based on a shift cipher,
sometimes called a Caesar cipher be-
cause Julius Caesar used it.
First write the alphabet, followed by
the digits 0 through 9. (For coding pur-
poses 0 represents a space between
words, and the other digits are assigned
to punctuation marks.) Below this write
the same sequence cyclically shifted to
the right by an arbitrary number of
as is shown in color in the illustra-
tion on this page. Our cipher consists in
taking each symbol in the plaintext (the
message), finding it in the top row, and
replacing it with the symbol directly be-
low it. The result is a simple substitution
cipher, easily broken by any amateur.
In spite of its simplicity, a shift cipher
can be the basis of a truly unbreakable
The trick is simply to use a dif-
ferent shift cipher for each symbol in
the plaintext, each time choosing the
amount of shift at random. This is easily
done with the spinner shown in the top
illustration on the opposite page. Sup-
pose the first word of plaintext is
We spin the arrow and it stops on
tells us to use for encoding T a Caesar
cipher in which the lower alphabet is
shifted 10 steps to the right, bringing A
below K as is shown in the illustration.
T, therefore, is encoded as J. The same
procedure is followed for every symbol
in the plaintext. Before each symbol is
encoded, the arrow is spun and the low-
er sequence is shifted accordingly. The
result is a ciphertext starting with j and
a cipher "key" starting with K. Note
that the cipher key will be the same
length as the plaintext.
To use this one-time cipher for send-
ing a message to someone—call him Z—
we must first send Zthe key. This can be
done by a trusted courier. Later we send
to Z, perhaps by radio, the ciphertext. Z
decodes it with the key and then de-
stroys the key. The key must not be used
again because if two such ciphertexts
were intercepted, a cryptanalyst might
have sufficient structure for breaking
It is easy to see why the one-time ci-
pher is uncrackable even in principle.
Since each symbol can be represented
by any other symbol, and each choice of
representation is completely random,
there is no internal pattern. To put it
another way, any message whatever
having the same length as the ciphertext
is as legitimate a decoding as any other.
Even if the plaintext of such a coded
message is found, it is of no future help
to the cryptanalyst because the next
time the system is used the randomly
chosen key will be entirely different.
One-time pads are in constant use to-
day for special messages between high
military commanders, and between gov-
ernments and their high-ranking agents.
The "pad" is no more than a long list of
random numbers, perhaps printed on
many pages. The sender and receiver
must of course have duplicate copies.
The sender uses page 1 for a cipher, then
destroys the page. The receiver uses his
page 1 for decoding, then destroys his
When the Russian agent Rudolf
Abel was captured in New York in
he had a one-time pad in the form
of a booklet about the size of a postage
stamp. David Kahn, who tells the story
in his marvelous history The Codebreak-
says that the one-time pad is the
standard method of secret radio com-
munication used by the U.S.S.R. The fa-
mous "hot line" between Washington
and Moscow also makes use of a one-
time pad, the keys being periodically de-
livered through the two embassies.
If the one-time pad provides absolute
secrecy, why is it not used for all secret
communication? The answer is that it is
too impractical. Each time it is em-
ployed a key must be sent in advance,
and the key must be at least as long as
the anticipated message. "The problem
of producing, registering, distributing
and canceling the keys," writes Kahn,
"may seem slight to an individual who
has not had experience with military
communications, but in wartime the
volumes of traffic stagger even the signal
Hundreds of thousands of words
may be enciphered in a day; simply to
generate the millions of key characters
required would be enormously expen-
sive and time-consuming. Since each
Let i
ing it i
Until r
kind v
has en<
Then i
ation \
from t
in the
ly desi;
ciple tl
but on]
for mi]
sity. T
by the
in 197
per "N
ory, Ni
able ci
the mi
can be
they c;
and th
from y
A actu
As sig
made ]
man c;
Such a
teger x
it has a
back ti
for col
tion an
tion a
to disc
that gi'
a trapi
hard H
less on
is hide
the bui
message must have its unique key, appli-
cation of the ideal system would require
shipping out on tape at the very least the
equivalent of the total communications
volume of a war."
Let us qualify Poe's dictum by apply-
ing it only to ciphers that are used re-
peatedly without any change in the key.
Until recently all cipher systems of this
kind were known to be theoretically
breakable provided the code breaker
has enough time and enough ciphertext.
Then in 1975 a new kind of cipher was
proposed that radically altered the situ-
ation by supplying a new definition of
"unbreakable," a definition that comes
from the branch of computer science
known as complexity theory. These new
ciphers are not absolutely unbreakable
in the sense of the one-time pad, but in
practice they are unbreakable in a much
stronger sense than any cipher previous-
ly designed for widespread use. In prin-
ciple these new ciphers can be broken,
but only by computer programs that run
for millions of years!
The two men responsible for this re-
markable breakthrough are Whitfield
Difne and Martin E. Hellman, both
electrical engineers at Stanford Univer-
sity. Their work was partly supported
by the National Science Foundation
in 1975 and was reported in their pa-
per "New Directions in Cryptography"
on Information The-
ory, November, 1976). In it Dime and
Hellman show how to create unbreak-
able ciphers that do not require advance
sending of a key or even concealment of
the method of encoding. The ciphers
can be efficiently encoded and decoded,
they can be used over and over again
and there is a bonus: the system also
provides an "electronic signature" that,
unlike a written signature, cannot be
forged. If Zreceives a "signed" message
from A, the signature proves to Z that
A actually sent the message. Moreover,
signature cannot be forged by an
eavesdropper or even by Z
These seemingly impossible feats are
made possible by what Dime and Hell-
man call a trapdoor one-way function.
Such a function has the following prop-
(1) it will change any positive in-
teger x to a unique positive integer y; (2)
it has an inverse function that changes y
back to x; (3) efficient algorithms exist
for computing both the forward func-
tion and its inverse: (4) if only the func-
tion and its forward algorithm are
known, it is computationally infeasible
to discover the inverse algorithm.
The last property is the curious one
that gives the function its name. It is like
a trapdoor: easy to drop through but
hard to get up through. Indeed, it is im-
possible to get up through the door un-
less one knows where the secret button
is hidden. The button symbolizes the
"trapdoor information." Without it one
cannot open the door from below, but
the button is so carefully concealed that
9 A
Randomizer for encoding a "one-time pad"
the probability of finding it is practically
Before giving a specific example, let
us see how such functions make the new
cryptographic systems possible. Sup-
pose there is a group of businessmen
who want to communicate secrets to one
another. Each devises his own trapdoor
function with its forward and backward
algorithms. A handbook is published in
which each company's encoding (for-
ward) algorithm is given in full. The de-
coding (inverse) algorithms are kept se-
cret. The handbook is public. Anyone
can consult it and use it for sending a
secret message to any listed company.
Suppose you are not a member of the
group but you want to send a secret mes-
sage to member Z First you change
your plaintext to a long number, using a
standard procedure given in the hand-
book. Next you look up Z's forward al-
gorithm and your computer uses it for
rapid encoding of the ciphertext. This
new number is sent to Z. It does not
matter at all if the ciphertext is over-
heard or intercepted because only Z
knows his secret decoding procedure.
There is no way a curious cryptanalyst,
studying Z's public encoding algorithm,
can discover Z's decoding algorithm. In
principle he might find it, but in practice
that would require a supercomputer and
a few million years of running time.
An outsider cannot "sign" a message
to Z, but any member of the group can.
Here is the devilishly clever way the sig-
nature works. Suppose A wants to sign a
message to Z. He first encodes the plain-
text number by using his own secret in-
verse algorithm. Then he encodes the
ciphertext number a second time, using
Z's public algorithm. After Z receives
the ciphertext he first transforms it by
applying his own secret decoding algo-
rithm, then he applies A s public encod-
ing algorithm. Out comes the message!
Z knows that only A could have sent
this doubly encoded ciphertext because
it made use of A s secret algorithm. A
"signature" is clearly unforgeable. Z
cannot use it to send a message purport-
ing to come from A because Z still does
A ciphertext challenge worth $100
The answers to last month's bisection problems
__ 1
i j
Dividing polyominoes into four congruent parts
not know ,4 's secret decoding algorithm.
Not only that, but if it were to become
necessary at some future time to prove
to a third party, say a judge in a court of
law, that A did in fact send the message,
this can be done in a way that neither A,
Z nor anyone else can dispute.
Dime and Hellman suggested in their
paper a variety of trapdoor functions
that might be used for such systems.
None is quite what is desired, but early
this year there was a second break-
through. Ronald L. Rivest, Adi Shamir
and Leonard Adleman, computer scien-
tists at the Massachusetts Institute of
Technology, developed an elegant way
to implement the Diffie-Hellman system
by using prime numbers.
Rivest obtained his doctorate in com-
puter science from Stanford University
in 1973 and is now an associate profes-
sor at M.I.T. Once he had hit on the
brilliant idea of using primes for a pub-
lic cipher system, he and his two collab-
orators had little difficulty finding a sim-
ple way to do it. Their work, supported
by grants from the NSF and the Office of
Naval Research, appears in On Digital
Signatures and Public-Key Cryptosystems
(Technical Memo 82, April, 1977), is-
sued by the Laboratory for Comput-
er Science, Massachusetts Institute of
Technology, 545 Technology Square,
Cambridge, Mass. 02139. The memo-
randum is free to anyone who writes
Rivest at the above address enclosing
a self-addressed, 9-by-12-inch clasp en-
velope with 35 cents in postage.
To explain Rivest's system we need a
bit of background in prime-number the-
ory. The fastest-known computer pro-
grams for deciding whether a number is
prime or composite (the product of
primes) are based on a famous theory of
Fermat's stating that if p is prime, and a
is any positive number less than p. then
= i (modulo p). Suppose we want
to test a large odd number n (all primes
except 2 are of course odd) for primali-
ty. A number a is selected at random
and raised to the power of n 1, then
divided by n. If the remainder is not
n cannot be prime. For example,
22i-i = 4 (modulo 21), therefore 21 is
composite. What, however, is the con-
nection between 2 (the randomly chosen
a) and 3 and 7, the two prime factors of
21? There seems to be no connection
whatever. For this reason Fermat's test
is useless in finding prime factors. It
however, provide a fast way of
proving that a number is composite.
Moreover, if an odd number passes the
Fermat test with a certain number of
random as, it is almost certainly prime.
This is not the place to go into more
details about computer algorithms for
testing primality, which are extremely
fast, or algorithms for factoring com-
posites, all of which are infuriating-
ly slow. I content myself with the fol-
lowing facts, provided by Rivest. They
dramatize the staggering gap in the re-