|
|
 |
|
|
|
register |
bbs |
search |
rss |
faq |
about
|
|
|
meet up |
add to del.icio.us |
digg it
|
|
|
|
A mathematical recreation from an old issue of S
Mathematical Games
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 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 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 code
breaker 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 Science Foundation 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 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 (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=1143816257578888676692357799761466120102182967212423625625618429357069352457338978305971235639587058989075147599290026879543541.
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:
199935131497805100452317122740260647423204017058391463103703717406259716089489275043
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 first changed 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:
167178611503808442460152713891683982454369010323583112178350384469290626554487922371144905095786086562496577974840004057020373.
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.
SCIENTIFIC AMERICAN August 1977 Volume 237 Number 2 Pages 120-124
Scientific American (ISSN 0036-8733), published monthly by Scientific
American, Inc., 415 Madison Avenue, New York, N.Y. 10017-1111. Copyright 1994
by Scientific American, Inc. All rights reserved. Except for one-time
personal use, no part of any issue may be reproduced by any mechanical,
photographic or electronic process, or in the form of a phonographic
recording, nor may it be stored in a retrieval system, transmitted or
otherwise copied for public or private use without written permission of the
publisher. For information regarding back issues, reprints or permissions,
E-mail [email protected].
Transmitted: 94-08-05 09:21:34 EDT
|
|
|
To the best of our knowledge, the text on this page may be freely reproduced and distributed.
If you have any questions about this, please check out our Copyright Policy.
totse.com certificate signatures
|
|
|
About | Advertise | Bad Ideas | Community | Contact Us | Copyright Policy | Drugs | Ego | Erotica
FAQ | Fringe | Link to totse.com | Search | Society | Submissions | Technology
|
|
|
|
|
|
