# A new kind of cipher that would take millions of years to break

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/a-new-kind-of-cipher-that-would-take-millions-of-years-to-break

- **Authors:** Martin Gardner
- **Published:** 1977
- **Topic:** Computer Science
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1714343247109-pp5rwt5abt-35fbfed225ddcc239f1040ac290884e1%2Fnew_kind_of_cipher.pdf
- **Pages:** 5
- **Annotations:** 12 comments in 12 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/a-new-kind-of-cipher-that-would-take-millions-of-years-to-break

## Annotations

### Annotation 1 (page 1)

Beside the passage: “"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."”

**Annotation** by João Batalha (2024-04-28):

> Edgar Allan Poe, the renowned American poet and writer, was captivated by the art of secret writing. In 1841, he published an essay titled "A Few Words on Secret Writing" in Graham's Magazine, where he explored various methods of encryption. Poe was particularly interested in substitution ciphers, a technique in which each letter is replaced by a different one. He even challenged his readers to submit their own encrypted messages, offering to decipher them personally. Poe's fascination with cryptography stemmed from his passion for puzzles and codes, as well as his experience as a military officer and journalist, where secure communication was of utmost importance. He even incorporated cryptographic elements into some of his literary works, such as "The Gold-Bug”, which includes a detailed description of a cipher.
>
> ![](https://i.imgur.com/yVvhgnR.jpeg)
> *Edgar Allan Poe*

### Annotation 2 (page 1)

Beside the passage: “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-”

**Annotation** by João Batalha (2024-04-28):

> The price of sending a letter in the United States has steadily increased since the time of writing of this article (1977) as Martin Gardner predicted. In contrast, the volume of letters being sent peaked in the early 2000s, and today it is roughly at the same level as in the 70s.
> ![](https://i.imgur.com/5WByGv3.png)

### Annotation 3 (page 1)

Beside the passage: “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 …”

**Annotation** by João Batalha (2024-04-28):

> ### One-time pad
> The one-time pad (OTP) is a type of encryption that is unbreakable when used correctly. Here is how a simple implementation of a one time pad would work:
>
> Encryption
> - A random key, as long as the message, is generated.
> - The message is converted into a numerical format (e.g., ASCII code).
> - The key is added to the message, bit-by-bit or character-by-character, using modular addition (e.g., XOR).
> - The resulting ciphertext is sent to the recipient.
> Decryption
> - The recipient has a copy of the same random key.
> - The key is added to the ciphertext, bit-by-bit or character-by-character, using modular addition (e.g., XOR).
> - The resulting plaintext is the original message.

### Annotation 4 (page 1)

Beside the passage: “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 …”

**Annotation** by João Batalha (2024-04-28):

> According to historical accounts, such as Suetonius' "Lives of the Twelve Caesars", Caesar used a simple shift cipher to protect sensitive military and personal communications.
> > if there was occasion for secrecy, he wrote in cyphers; that is, he used the alphabet in such a manner, that not a single word could be made out. The way to decipher those epistles was to substitute the fourth for the first letter, as d for a, and so for the other letters respectively.
>
> This suggests that Caesar employed a uniform shift of three positions, meaning that each letter in the plaintext was replaced by the letter three positions down the alphabet.

### Annotation 5 (page 1)

Beside the passage: “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 …”

**Annotation** by João Batalha (2024-04-28):

> Rudolf Ivanovich Abel, whose real name was William August Fisher, was a notorious Soviet spy during the Cold War era. In 1948, Abel was sent to the United States as part of a Soviet espionage network tasked with gathering classified information about U.S. military and nuclear secrets. Operating under the alias "Emil Goldfus," Abel posed as a photographer and artist in Brooklyn, New York.
>
> He maintained contact with Moscow using a variety of covert communication methods, including the use of a miniature one-time pad disguised as a small booklet. In 1957, Abel was apprehended by the FBI in a New York hotel room, marking the end of his nine-year espionage career in the United States.
>
> The discovery of his one-time pad during the arrest was a significant piece of evidence in the case against him. Abel was eventually exchanged for Gary Powers, the U-2 pilot shot down over the Soviet Union in 1960.
> ![](https://i.imgur.com/HiQradF.png)
> *One-time pad booklet*

### Annotation 6 (page 1)

Beside the passage: “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 the spinner shown in the top illustration on the opposite page. …”

**Annotation** by João Batalha (2024-04-28):

> #### Caesar cipher
> A Caesar cipher, also known as a shift cipher, is one of the simplest and most widely known encryption techniques. While the Caesar cipher is simple to understand and implement, it is not secure by modern standards and can be easily broken.
> In a Caesar cipher, each letter of the alphabet is shifted along some number of places. For example, in a Caesar cipher of shift 3, A would become D, B would become E, Y would become B and so on.
> ![](https://i.imgur.com/L36uCQl.png)
> *Caesar cipher of shift 3*
>
> Here is an example:
> ```
> fermat
> ------
> ihupdw
> ```

### Annotation 7 (page 2)

Beside the passage: “The two men responsible for this remarkable breakthrough are Whitfield Difne 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 …”

**Annotation** by João Batalha (2024-04-30):

> Whitfield Diffie and Martin Hellman are two renowned American cryptographers who made groundbreaking contributions to the field of cryptography. In 1976, they published a seminal paper titled "New Directions in Cryptography," which introduced the concept of public-key cryptography. This revolutionary idea allowed for secure communication between parties without the need for a pre-shared secret key. Diffie and Hellman's work laid the foundation for the development of asymmetric encryption algorithms, such as RSA (Rivest-Shamir-Adleman), which are widely used today for secure online transactions, digital signatures, and encrypted communication.
> ![](https://i.imgur.com/F7935bZ.jpeg)
> *Martin Hellman, left, and Whitfield Diffie*

### Annotation 8 (page 2)

Beside the passage: “1477”

**Annotation** by João Batalha (2024-05-01):

> The message encoded in this ciphertext was deciphered in 1994. The message was:  `The Magic Words are Squeamish Ossifrage`

### Annotation 9 (page 3)

Beside the passage: “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 breakthrough. Ronald L. Rivest, Adi Shamir and Leonard Adleman, computer scientists at the Massachusetts Institute of Technology, …”

**Annotation** by João Batalha (2024-04-30):

> RSA is an asymmetric encryption algorithm that builds upon the groundbreaking work of Diffie and Hellman. Developed in 1977, just a year after the publication of Diffie and Hellman's "New Directions in Cryptography”, RSA is a practical implementation of the public-key cryptography concept introduced by Diffie and Hellman.
>
> While Diffie and Hellman's paper laid the theoretical foundation for asymmetric encryption, they did not provide a concrete implementation. RSA fills this gap by using the mathematical properties of prime numbers to create a pair of keys: a public key for encryption and a private key for decryption. The security of RSA relies on the difficulty of factoring large composite numbers, a problem closely related to the discrete logarithm problem that underlies the Diffie-Hellman key exchange.
>
> The development of RSA marked a significant milestone in the history of cryptography, as it turned the abstract concept of public-key cryptography into a practical and widely adopted encryption system that continues to be used extensively for secure digital communication and transactions.

### Annotation 10 (page 3)

Beside the passage: “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 p-\ = i …”

**Annotation** by João Batalha (2024-04-30):

> Fermat's little theorem is named after the 17th-century French mathematician Pierre de Fermat, who first stated the theorem in 1640. However, Fermat did not provide a proof for the theorem, as was common in his work. The first published proof was given by Leonhard Euler in 1736, almost a century after Fermat's claim.
>
> The theorem is particularly relevant for primality testing because it provides a quick and efficient way to determine whether a number is potentially prime or definitely composite. Primality tests based on Fermat's little theorem work as follows:
>
> To test if a number $n$ is prime, choose a random integer $a$ between 2 and $n-1$. Then, compute $a^{n-1} \bmod n$. If the result is not 1, then $n$ is definitely composite. If the result is 1, then $n$ might be prime, and the test is repeated with several different randomly chosen $a$ values. If the result is always 1, then there is a high probability that $n$ is prime.
>
> For example, let's test if $n = 17$ is prime.
> 1. Choose $a = 3$, then $3^{16} \bmod 17 = 1$.
> 2. Choose $a = 5$, then $5^{16} \bmod 17 = 1$.
> 3. Choose $a = 7$, then $7^{16} \bmod 17 = 1$.
>
> Since the test passed for multiple random $a$ values, there is a high probability that 17 is prime.
>
> This primality test is probabilistic, meaning that it can identify composite numbers with certainty but can only give a probability that a number is prime. If a number passes the test for many different random $a$ values, it is very likely to be prime.

### Annotation 11 (page 4)

Beside the passage: “quired 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 200 . (It is a 61- digit …”

**Annotation** by João Batalha (2024-05-01):

> Despite the original estimate, the prime factors were actually found just 17 years after the paper's publication. In 1994, a team led by Derek Atkins, Michael Graff, Arjen Lenstra, and Paul Leyland successfully factored the 129-digit number used in the RSA-129 challenge employing a combination of the quadratic sieve algorithm and a distributed computing approach involving about 1600 volunteers and their computers. This achievement highlighted the rapid advancements in both computational power and algorithmic efficiency that have occurred in recent decades.
>
> Today you can find the factors to RSA-129 for ~30$ using a public cloud like Google Cloud ([blogpost](https://natmchugh.blogspot.com/2015/03/the-magic-words-are-squeamish-ossifrage.html))
>
> 1994 announcement that a factorization of RSA-129 
> ```
> We are happy to announce that
>
> RSA-129 = 1143816257578888676692357799761466120102182967212423625625618429\
>           35706935245733897830597123563958705058989075147599290026879543541
>         = 3490529510847650949147849619903898133417764638493387843990820577 *
>           32769132993266709549961988190834461413177642967992942539798288533
>
>
> The encoded message published was
>
> 968696137546220614771409222543558829057599911245743198746951209308162\
> 98225145708356931476622883989628013391990551829945157815154
>
> This number came from an RSA encryption of the `secret' message using the
> public exponent 9007. When decrypted with he `secret' exponent
>
> 106698614368578024442868771328920154780709906633937862801226224496631\
> 063125911774470873340168597462306553968544513277109053606095
>
> this becomes
>
> 200805001301070903002315180419000118050019172105011309190800151919090\
> 618010705
>
> Using the decoding scheme 01=A, 02=B, ..., 26=Z, and 00 a space between
> words, the decoded message reads
>
> THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
>
>
>
> To find the factorization of RSA-129, we used the double large prime
> variation of the multiple polynomial quadratic sieve factoring method.
> The sieving step took approximately 5000 mips years, and was carried
> out in 8 months by about 600 volunteers from more than 20 countries,
> on all continents except Antarctica. Combining the partial relations
> produced a sparse matrix of 569466 rows and 524338 columns. This matrix
> was reduced to a dense matrix of 188614 rows and 188160 columns using
> structured Gaussian elimination. Ordinary Gaussian elimination on this
> matrix, consisting of 35489610240 bits (4.13 gigabyte), took 45 hours
> on a 16K MasPar MP-1 massively parallel computer. The first three
> dependencies all turned out to be `unlucky' and produced the trivial
> factor RSA-129. The fourth dependency produced the above factorization.
>
> We would like to thank everyone who contributed their time and effort
> to this project. Without your help this would not have been possible.
>
> Derek Atkins
> Michael Graff
> Arjen Lenstra
> Paul Leyland
> ```

### Annotation 12 (page 4)

Beside the passage: “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 …”

**Annotation** by João Batalha (2024-04-30):

> Two numbers are considered relatively prime (or coprime) if their greatest common divisor (GCD) is 1. In other words, they have no common factors other than 1.
>
> For example, 12 and 25 are relatively prime because their GCD is 1, even though neither number itself is prime. On the other hand, 12 and 18 are not relatively prime because they share a common factor of 6 (besides 1).
>
> In the RSA system, the number s must be carefully chosen so that it is relatively prime to both p - 1 and q - 1. This is a crucial condition for the encoding and decoding process to work correctly, allowing the efficient computation of modular exponentiation in the encryption and decryption steps.

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

I - f

MATHEMATICAL

GAMES

A new kind of cipher that would

take millions of years to break

by Martin Gardner

i v. ;

"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." [Annotation 1]

—EDGAR ALLAN POE

T

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 [Annotation 2] "[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 "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 de- . sirable 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 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 repeatedly without changing the key and

ABCDEFGHI JKLMNOPQR 01 23456789ABCDEFGH

STUVWXYZ0123456789 IJKLMNOPQRSTUVWXYZ

A Caesar cipher with a 10-shift

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. In- ' deed, 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 "onetime 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, as is shown in color in the illustration 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 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 the spinner shown in the top illustration on the opposite page. 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 in the illustration. T, therefore, is encoded as J. The same procedure is followed for every symbol in the plaintext. Before each symbol is [Annotation 6]

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 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 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. [Annotation 3] The sender uses page 1 for a cipher, then destroys the page. The receiver uses his [Annotation 4] page 1 for decoding, then destroys his page. [Annotation 5] 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 onetime 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

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

#### Page 2

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 [Annotation 7] Difne 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 Dime 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 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 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

9 A

w

u

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

9686

1477 [Annotation 8]

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

#### Page 3

1 1

J

1 1 j 1

I I I

I - r

\

10

The answers to last month's bisection problems

1 __ 1

I

1

|

i

r~ i

1

1

H

1 H

• i L.

1— .J 1 H

r .j i i j

1

r-

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 breakthrough. Ronald L. Rivest, Adi Shamir [Annotation 9] 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 [Annotation 10] is any positive number less than p. then a p-\ = i (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, 22i-i = 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 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 composites, all of which are infuriatingly slow. I content myself with the following facts, provided by Rivest. They dramatize the staggering gap in the re-

#### Page 4

quired 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 200 . (It is a 61- digit number equal to 2200 + 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 [Annotation 11] 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 09201900011212000718050511002015 001305.

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. [Annotation 12] 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 /, then reducing it to modulo r. As before, this takes less than a second of computer time. The number /, 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= 1143816257578888676692357 79976146612010218296721242362562

A ^_—-—

[

i*

)

C

Solutions to four equal-division problems

56184293570693524573389783059712 35639587050589890751475992900268 79543541.

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: 1999$ 513\149780510045 23171227402606474232040170583914 63103703717406259716089489275043 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 shown in the bottom illustration on page 121. 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: 1671786 v\ 5 031808442460152t713 89168$ 982^54369 01D32 J15 83 hi 21783 5O0'8446929j)626l55 £792£37llr4490S09}5786p865lS662y9 \^ 84dj)040$702P3 73. 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 060918192000191512220 51800230914190015140500082114041 805040004151212011819. 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. Dime and Hellman are applying for patents on cipher devices based on trapdoor functions they have not yet disclosed. Computers and complexity theory are pushing cryptog-

123

#### Page 5

A bilaterally symmetric tetrad with 18 sides

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

T

he top illustration on page 122 shows how the 12 shapes given last month can be divided into congruent halves. The bottom illustration on the same page shows how nine, of the 12 order-5 polyominoes can be dissected into the same four congruent parts. The three blank polyominoes cannot be cut into four congruent parts of any shape. The illustration on the preceding page answers the four problems at the end of last month's column. To bisect the nine squares draw the 10th square shown with broken lines. Rule AB to get point C, then join P to C. If the squares have

sides of length 1, then CD equals 1/4, and it is easy to see that PC bisects the original figure. To bisect the five circles add three additional circles as shown by the broken lines. The line through the centers of two circles obviously halves the total area. (Both problems are from A Problem a Day, by R. M. Lucey, Penguin Books, 1937.)

The hexagon at the bottom is trisected by joining /"to Cand D. the midpoints of two sides. Assume that the equilateral triangles have areas of 1. The area of PAB is 1, therefore the area of PBE is 2 and the rest follows. I was unable to find any comparably simple way to trisect a regular pentagon with a line through a corner.

The middle two hexagons show how Leo Moser proved that the minimumlength curve bisecting an equilateral triangle is the arc of a circle. Whatever the shape of the bisecting curve, it will form a closed curve if the triangle is reflected around one vertex as is shown. Such a curve cuts the hexagon in half, and it has a fixed area. The figure of minimum perimeter that encloses a given area is the circle, therefore the minimum-length bisecting curves inside each triangle are arcs of a circle. (This exercise is from Mathematical Quickies, by Charles W. Trigg, McGraw-Hill, 1967.)

C

omments on the mail response to April's short problems follow: The generalization of the pool-ball problem to triangles of order n, bearing consecutive numbers starting with 1, has been solved. Herbert Taylor found an ingenious way to prove that no TAD (triangle of absolute differences) could be made with triangular arrays of order 9 or higher. Computer programs eliminated TAD's of orders 6, 7 and 8, therefore the unique solution for the 15 pool balls is the largest TAD of this type.

A Cipher that Defeated Poe

"Ge Jeasgdxv,

Zij gl mw, laam. xzy zmlwhfzek ejlvdxw kwke tx lbr atgh lbmx aanu bai Vsmukkss pwn vlwk agh gnumk wdlnzweg jnbxw oaeg enwb zwmgy mo mlw wnbx mw al pnfdcfpkh wzkex hssf xkiyahul. Mk num yexdm wbxy sbc hv wyx Phwkgnamcuk?"

In 1839, in a regular column Edgar Allan Poe contributed to a Philadelphia •periodical, Alexander's Weekly Messenger, Poe challenged readers to send him {cryptograms (monoalphabetic substitution ciphers), asserting that he would solve them all "forthwith." One G. W. Kulp submitted a ciphertext in longhand. It was printed as shown above in the issue of February 26, 1840. Poe "proved " in a subsequent column that the cipher • was a hoax—"a jargon of random char-

acters having no meaning whatsoever." In 1975 Brian J.Winkel, a mathematician at Albion College, and Mark Lyster, a chemistry major in Winkel's cryptology class, cracked Kulp's cipher. It is not a simple substitution—Poe was right —but neither is it nonsense. Poe can hardly be blamed for his opinion. In addition to a major error by Kulp there are 15 minor errors, probably printer's mistakes in reading the longhand. Winkel is an editor of a new quarterly, Cryptologia, available from Albion College, Albion, Mich. 49224, at $16 per year. The magazine stresses the mathematical and computational aspects of cryptology. The first issue (January. 1977) tells the story of Kulp's cipher and gives it as a challenge to readers. So far only three readers have broken it. I shall give the solution next month.

Solomon W. Golomb proposed three candidates for further investigation: 1. If all numbers in a TAD of order greater than 5 are distinct but not consecutive, how big is the largest number forced to be? (Example: An order-6 TAD is possible with the largest number as low as 22.) 2. Using all numbers from 1 to k, but allowing repeats, how big can k b,e in a TAD of order n?(Example: An order-6 TAD is possible with k as high as 20.) 3. For what orders is it possible to form a TAD modulo m, where m is the number of elements in the triangle and the numbers are consecutive from 1 to m?Each difference is expressed modulo m. Such triangles can be rotated so that every element below the top row is the sum (modulo m) of the two numbers above it. Here, in rotated form, are the four order-4 solutions:

1694 2783 6149 7238

753 951 753 951

28 46 28 46

0 0 0 0

A backtrack program by Golomb and Taylor found no solution for order 5. Col. George Sicherman, who invented the original pool-ball problem, reports a computer proof of impossibility for order 6. Higher orders remain open. Robert Ammann, Greg Frederickson and Jean L. Loyer each found an 18-sided polygonal tetrad with bilateral symmetry [see illustration on this page], thus improving on the 22-sided solution I had published. Dan Eilers, Allen I. Janis, Scott Kim, P. H. Lyons, Robert Mathews (with Martin G. Wallser), James Newton and Mike Tempest each found a second solution (there are no more) for the lostking tour on the order-5 square. When I ended the column with limericks of decreasing length, I referred to the one-line limerick as the "last of four." Draper L. Kauffman, John Little, John McKay, Thomas D. Nehrer and James C. Vibber were the first of many who told me I should have called it the last-but-one of five. The fifth, of course, has no lines, which is why other readers failed to notice it. Tom Wright of Ganges, British Columbia, wrote: "I was interested in the limerick paradox, particularly in the decreasing two-line and one-line limericks. I wondered if you had, in fact, added the no-line limerick (about the man from Nepal), and I looked minutely to see if it wasn't there. On examination, my first impulse was to assume that it was indeed not there, since no space was provided, but further cogitation suggested that a no-line poem, requiring no space, might indeed be there. Unable to resolve this paradox by any logical proof, I am abjectly reduced to asking you whether or not a no-line limerick was not printed in the space not provided, or not."

CO

ap

ar

ta

L

I IS— i _

tf OF

<3

42205. A DI Edited by Sle, geology, geo paleontology, ogy, cartogra] 00470. VAN CLOPEDIA. prehensive o thoroughly re 1 photographs. Counts as 3 of 66570. AN C OGY. Bruce I Williams. Uptural geologylatest informal 55000. THE 1 ASTRONOV full range of a' tion, from anc 70170. PRIN Edition. Hou rigorous theoi tions. 44900. THE SCIENCE. £ Meek. A mom densed, accur; from theory tc the logical des lean algebra cross referenci tables. Counts 70190. PRIf SEARCH. Se 1039-page boc fundamental o 49340. FUND SYSTEM AN our assault on earliest sensoi tronomical tho «1530. MAT Edition. Edite enbach Revisi definitions of i

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/a-new-kind-of-cipher-that-would-take-millions-of-years-to-break. More annotated papers: https://fermatslibrary.com/llms.txt
