Fermat's Library | A new kind of cipher that would take millions of years to break annotated/explained version.

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 -

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

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

«ot

;

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

ABCDEFGHI JKLMNOPQR

01 23456789ABCDEFGH

STUVWXYZ0123456789

IJKLMNOPQRSTUVWXYZ

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

once,

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

units,

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

code.

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

THE.

We spin the arrow and it stops on

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 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

them.

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

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 Codebreak-

ers,

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

staffs.

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

messaj

cation

shippii

equiva

volum

Let i

ing it i

peated

Until r

kind v

breaka

has en<

Then i

propos

ation \

"unbre

from t

known

cipher;

in the

practic

strong!

ly desi;

ciple tl

but on]

for mi]

The

marka

Dime

electric

sity. T

by the

in 197

per "N

(IEEE

ory, Ni

Hellm;

able ci

sendin;

the mi

can be

they c;

and th

provid

unlike

forged

from y

A actu

As sig

eavesd

The;

made ]

man c;

Such a

erties:

teger x

it has a

back ti

for col

tion an

tion a

known

to disc

The

that gi'

a trapi

hard H

possibJ

less on

is hide

"trapd'

cannot

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"

(IEEE

Transactions

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,

A's

signature cannot be forged by an

eavesdropper or even by Z

himself!

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-

erties:

(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

S R

Randomizer for encoding a "one-time pad"

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. 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

9686

1477

8829

7431

0816

3569

8962

1829

9613

1409

0575

9874

2982

3147

8013

9451

7546

2225

9991

6951

2514

6622

3919

5781

2206

4355

1245

2093

5708

8839

9055

5154

A ciphertext challenge worth $100

121

The answers to last month's bisection problems

__ 1

•

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

p-\

= 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

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 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-

Comments