 |
A new kind of cipher that would take millions of years 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."
--EDGAR ALLAN POE
The upward creep of postal rates accompanied by the deterioration
of postal service is a trend that may or may not continue,but as far as most
private communication is concerned, in a few decades it probably will not
matter. The reason is simple.
The transfer of information will probably be much faster and much cheaper
by "electronic mail"than by conventional postal systems.
Before long it should be possible to go to any telephone, insert a message
into an attachment and dial a number.
The telephone at the other end will print out the message at once.
Government agencies and large businesses will presumably be the first to
make extensive use of electronic mail,followed by small businesses and private
individuals.
When this starts to happen,it will become increasingly desirable to have
fast, efficient ciphers to safeguard information from electronic
eavesdroppers.
A similar problem is involved in protecting private information stored in
computer memory banks from snoopers who have access to the memory 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 repeatedly without changing the key and is unbreakable by sophisticated
cryptanalysis?
The surprising answer is yes.
The breakthrough is scarcely two years old, yet it bids fair to revolutionize
the entire field of secret communication.
Indeed, it is so revolutionary that all previous ciphers, together with the
techniques for cracking them,may soon fade into oblivion.
An unbreakable code can be unbreakable in theory or unbreakable only in practice.
Edgar Allan Poe,who fancied himself a skilled cryptanalyst, was convinced
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 once, for a single message.
Here is a simple example based on a shift cipher, sometimes called a Caesar
cipher because Julius Caesar used it.
First write the alphabet,followed by the digits 0 through 9.
(For coding purposes 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 units,for example:
A B C D E F G H I J K L M N O P Q R
0 1 2 3 4 5 6 7 8 9 A B C D E F G H
S T U V W X Y Z 0 1 2 3 4 5 6 7 8 9
I J K L M N O P Q R S T U V W X Y Z.
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 below
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 code. The trick is simply to use a different shift cipher for
each symbol in the plaintext, each time choosing the amount of shift at random.
This is easily done with a spinner like those used in board games.
Suppose the first word of plaintext is THE. We spin the arrow and it stops
on K. This 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
above. 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 lower sequence is shifted accordingly. The result is a ciphertext
starting with J and acipher "key" starting with K. Note that the cipher key
will be the same length as the plaintext.
To use this one-time cipher for sending a message to someone--call him Z--we
must first send Z the 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 destroys the key. The key must not be used again because if two such
ciphertexts were intercepted, a cryptanalyst might have sufficient structure
for breaking them.
It is easy to see why the one-time cipher 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 today for special messages between high
military commanders, and between governments 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 page. When the
Russian agent Rudolf Abel was captured in New York in 1957, 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 Codebreakers," says that
the one-time pad is the standard method of secret radio communication used
by the U.S.S.R.
The famous "hot line" between Washington and Moscow also makes use of a one-time
pad, the keys being periodically delivered 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 employed 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 staffs. Hundreds of thousands of words may
be enciphered
in a day:
simply to generate the millions of key characters required would be enormously
expensive and time-consuming. Since each message must have its unique key,
application 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 applying it only to ciphers that are used
repeatedly without any change in the key. Until recently all cipher systems
of this kind were known to be theoretically breakable provided the codebreaker
has enough time and enough ciphertext. Then in 1975 a new kind of cipher
was proposed that radically altered the situation 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 previously designed for widespread
use.
In principle these new ciphers can be broken, but only by computer programs
that run for millions of years!
The two men responsible for this remarkable breakthrough are Whitfield Diffie
and Martin E. Hellman, both electrical engineers at Stanford University.
Their work was partly supported by the National ScienceFoundation in 1975
and was reported in their paper "New Directions in Cryptography" (IEEE
Transactions on Information Theory," November, 1976).
In it Diffie and Hellman show how to create unbreakable 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 Z receives
a "signed" message from A, the signature proves to Z that A actually sent
the message. Moreover, A's signature cannot be forged by an eavesdropper
or even by Z himself! These seemingly impossible feats are made possible
by what Diffie and Hellman call a trapdoor one-way function. Such a function
has the following properties: (1) it will change any positive integer 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
function and its inverse;
(4) if only the function 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 impossible to get up through the door unless 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 the probability of finding it is practically zero.
Before giving a specific example, let us see how such functions make the
new cryptographic systems possible. Suppose there is a groupof 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 (forward) algorithm is given in full. The
decoding (inverse) algorithms are kept secret. 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 message
to member Z. First you change your plaintext to a long number, using a standard
procedure given in the handbook. Next you look up Z's forward algorithm 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 overheard 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 signature works.
Suppose A wants to sign a message to Z. He first encodes the plaintext number
by using his own secret inverse 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 algorithm, then
he applies A's public encoding 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's "signature" is clearly unforgeable.
Z cannot use it to send a message purporting to come from A because Z still
does not know A'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.
Diffie 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 breakthrough. Ronald L. Rivest, Adi
Shamir and Leonard Adleman, computer scientists 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 computer science from Stanford University
in 1973 and is now an associate professor at M.I.T. Once he had hit on the
brilliant idea of using primes for a public cipher
system, he and his two collaborators had little difficulty finding a
simple 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), issued by the Laboratory
for Computer Science, Massachusetts Institute of Technology, 545 Technology
Square, Cambridge, Mass. 02139. The memorandum is free to anyone who writes
Rivest at the above address enclosing a self-addressed, 9-by-12-inch clasp
envelope with 35 cents in postage.
To explain Rivest's system we need a bit of background in prime-number theory.
The fastest-known computer programs 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 a[sup
(p-1)]=1 (modulo p). Suppose we want to test a large odd number n (all primes
except 2 are of course odd) for primality. A number a is selected at random
and raised to the power of n-1, then divided by n. If the remainder
is not 1, n cannot be prime. For example, 2[sup (21-1)]=4 (modulo 21), therefore
21 is composite. What, however, is the connection 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 does, 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 a's, 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
composites, all of which are infuriatingly slow. I content myself with the
following facts, provided by Rivest. They dramatize the staggering gap in
the required computer time between the two kinds of testing.
For example, to test a 130-digit odd number for primality requires at the
most (that is, when the number actually is prime) about seven minutes on
a PDP-10 computer. The same algorithm takes only 45 seconds to find the first
prime after 2 to the power of 200. (It is a 61-digit number equal to 2[sup
200]+235.)
Contrast this with the difficulty of finding the two prime factors of a 125-
or 126-digit number obtained by multiplying two 63-digit primes. If the best
algorithm known and the fastest of today's computers were used, Rivest estimates
that the running time required would be about 40 quadrillion years!
(For a good discussion of computer methods of factoring into primes,
see Donald E. Knuth's "Seminumerical Algorithms," Section 4.5.4.)
It is this practical impossibility, in any foreseeable future, of factoring
the product of two large primes that makes the M.I.T. public-key cipher system
possible.
To explain how the system works, the M.I.T. authors take as an example of
plaintext a paraphrase of a remark in Shakespeare's "Julius Caesar" (Act
1, Scene 2): ITS ALL GREEK TO ME.
This is first changed to a single number, using the standard key:
A=01, B=02,..., z=26, with 00 indicating a space between words.
The number is 09201900011212000718050511002015001305.
The entire number is now encoded by raising it to a fixed power s, modulo
a certain composite number r. The composite r is obtained by randomly selecting
(using a procedure given in the M.I.T. memorandum) two primes,p and q, each
of which is at least 40 digits long, and multiplying them together.
The number s must be relatively prime to p-1 and q-1. Numbers s and r are
made public, to be used in the encoding algorithm. The encoding operation
can be done very efficiently even for enormous values of r; indeed, it requires
less than a second of computer time.
The two prime factors of r are withheld, to play a role in the secret inverse
algorithm. This inverse algorithm, used for decoding,consists in raising
the ciphertext number to another power t, then reducing it to modulo r. As
before, this takes less than a second of computer time.
The number t, however, can be calculated only by someone who knows p and
q, the two primes that are kept secret.
If the message is too long to be handled as a single number, it can be broken
up into two or more blocks and each block can be treated as a separate number.
I shall not go into more details. They are a bit technical but are clearly
explained in the M.I.T. memo.
To encode ITS ALL GREEK TO ME, the M.I.T. group has chosen s=9,007 and
r=1143816257578888676692357799761466120102182967212423625625618429357
06935245733897830597123563958705058989075147599290026879543541.
The number r is the product of a 64-digit prime p and a 65-digit prime q,
each randomly selected.
The encoding algorithm changes the plaintext number (09201...) to the following
ciphertext number:
1999351314978051004523171227402606474232040170583914631037037174062597
16089489275043 09920962672582675012893554461353 823769748026.
As a challenge to SCIENTIFIC AMERICAN readers the M.I.T. group has encoded
another message, using the same public algorithm. The ciphertext is:
9686 9613 7546 2206
1477 1409 2225 4355
8829 0575 9991 1245
7431 9874 6951 2093
0816 2982 2514 5708
3569 3147 6622 8839
8962 8013 3919 9055
1829 9451 5781 5154.
Its plaintext is an English sentence. It was firstchanged to a number by
the standard method explained above, then the entire number was raised to
the 9,007th power (modulo r) by the shortcut method given in the memorandum.
To the first person who decodes this message the M.I.T. group will give $100.
To prove that the offer actually comes from the M.I.T. group,the following
signature has been added:
167178611503808442460152713891683982454369010323583112178350384469290626
55448792237114490509578608655662496577974840004057020373.
The signature was encoded by using the secret inverse of the encoding algorithm.
Since the reader has no public encoding algorithm of his own, the second
encoding operation has been omitted. Any reader who has access to a computer
and the instructions in the M.I.T. memorandum can easily read the signature
by applying the M.I.T. group's public encoding algorithm,that is, by raising
the above number to the power of 9,007, then reducing it to modulo r. The
result is
06091819200019151222051800230914190015140500082114041805040004151212011819.
It translates (by the use of the standard key) to FIRST SOLVER WINS ONE HUNDRED
DOLLARS. This signed ciphertext could only come from the M.I.T. group because
only its members know the inverse algorithm by which it was produced.
Rivest and his associates have no proof that at some future time no one will
discover a fast algorithm for factoring composites as large as the r they
used or will break their cipher by some other scheme they have not thought
of. They consider both possibilities extremely remote.
Of course any cipher system that cannot be proved unbreakable in the absolute
sense of one-time pads is open to sophisticated attacks by modern cryptanalysts
who are trained mathematicians with powerful computers at their elbow.
If the M.I.T. cipher withstands such attacks, as it seems almost certain
it will, Poe's dictum will be hard to defend in any form.
Even in the unlikely event that the M.I.T. system is breakable there are
probably all kinds of other trapdoor functions that can provide virtually
unbreakable ciphers. Diffie and Hellman are applying for patents on cipher
devices based on trapdoor functions they have not yet disclosed.
Computers and complexity theory
are pushing cryptography into an exciting phase, and one that may be
tinged with sadness. All over the world there are clever men and women, some
of them geniuses, who have devoted their lives to the mastery of modern
cryptanalysis. Since World War II even those government and
military ciphers that are not one-time pads have
become so difficult to break that the talents of these experts have gradually
become less useful. Now these people are standing on trapdoors that are about
to spring open and drop them completely from sight.
