October 1, 1996

Process Software Corporation, Framingham, Massachusetts

By late 1996, DES had been a standard for nineteen years. Several

designs for machines to crack DES keys had been around for years.

From time to time, someone would assert”without supporting any

evidence, of course”that the government already had machines like

the ones described early on by Hellman and Di¬e and later by Wiener.

Whether the rumors about government intelligence agencies actually

having DES-cracking hardware at their disposal were true mattered less

Key Length 35

than the simple availability of designs that would crack DES-encrypted

messages quickly and the fact that, like all computers, such machines

were getting cheaper and easier to build.

Some attempts had been made to address the short key size in DES.

In particular, several modes of operation were de¬ned where a message

would be encrypted more than once, with multiple keys. Two major

standardized versions followed, both known informally as “Triple-DES”

(or “3DES”), because a cryptographic operation was performed thrice.

In the usual two-key variant, plaintext is encrypted with one key, run

through the decryption operation with a second key, and encrypted

again with the ¬rst key, giving an e¬ective strength of 112 bits. In

a three-key variant, plaintext is encrypted three times, each with a

di¬erent key, giving an e¬ective strength of 168 bits.

Despite cryptographers™ lack of con¬dence in DES against deter-

mined attackers and the availability of stronger systems, DES contin-

ued to stand in o¬cial standards and was used very heavily. As long

as the government stood by its standard, DES would remain in heavy

use.

Cryptographer Peter Trei posted an article to Cypherpunks mailing

list entitled, “Can we kill single DES?” “Single DES” was a reference to

the original 56-bit standard for data encryption, to prevent readers from

confusing it with Triple-DES. In his message, he determined that with

the technology of the day, it was quite likely that DES keys could be

broken at no cost in roughly six months. This would take into account

the speed of computers in general use, the likelihood of how many

participants would be willing to work on such a project, and just how

much computing power would be needed to ¬nd one key out of 256 .

5

Discovery

Summer 1985

Bexley Public Library, Bexley, Ohio

Like most cryptographers-to-be, I spent many of my summers o¬ from

school studying mathematical topics that I otherwise would not learn

about until years later. I wanted to learn everything about how to ma-

nipulate numbers and symbols to determine the value of the mysterious

x. Such studies necessitated frequent trips to the library.

At twelve years old, I discovered David Kahn™s 1967 book, The

Codebreakers, sitting on the shelf of the library I frequented. Being

interested in history, mathematics, and computers, the book looked

promising. With over 1000 pages documenting the role of cryptogra-

phy in one decisive point in history after another, I found myself drawn

into a world where secrets could be written and transmitted, incompre-

hensible to unintended readers. Just as intriguing were the unintended

readers whose savvy and persistence allowed them to turn the jumble

of ciphertext into valuable plaintext.

Before long, I became fascinated with the making and breaking of

ciphers. Not content just to read about ciphers, I started to read more

about how ciphers worked, and started to write my own enciphered

messages”starting with the Caesar Cipher. Reckoning that a 2000-

year-old cipher must be universally known, I began to develop my own

systems for encrypting messages.

My ¬rst ciphers were intended to be manual systems”allowing for

messages to be enciphered and deciphered with no more advanced tech-

nology than a pencil and paper. Having practiced my own skill at break-

37

38 CHAPTER 5

ing messages enciphered with simple substitution systems (such as in

the daily newspaper™s “cryptoquote”), I started to look for ways to

make substitution ciphers more resistant to attack.

In an e¬ort to resist frequency analysis, I found that I could normal-

ize frequency of letters and numbers appearing in ciphertext if instead

of creating a simple one-to-one relationship between plaintext and ci-

phertext (e.g., where A is always written as M), a plaintext character

could be mapped to a group (e.g., where A could be written as M or

1). Letters with higher plaintext frequency would be assigned larger

groups.

That led to a new problem: creating a mapping where some plain-

text letters had more than one ciphertext equivalent meant that I

needed more than twenty-six ciphertext characters to represent twenty-

six plaintext letters. This problem was initially solved by adding num-

bers to the mix. By requiring that all plaintext messages have numbers

spelled out, I could gain an extra ten ciphertext characters, thus al-

lowing more ciphertext letters to represent common letters like E and

T.

I kept a notebook of my ciphers, giving each a name, along with

some comments on the system™s strength and likely scenarios where

each would be appropriate to choose. At the same time, I established

a means to identify which cipher was in use.

Some of the more sophisticated systems were further resistant to

analysis, using a single ciphertext digit for plaintext letters that com-

monly appear together, such as TH, CH, and SH. As I continued to de-

velop these, I moved further away from simple substitution ciphers

that change ciphertext to plaintext one letter at a time and into codes,

where a symbol could mean a whole word or phrase. Such systems de-

manded more and more symbols to represent ciphertext, so I adopted

the use of “codegroups” (groups of numbers or letters) for ciphertext.

Once I had access to a computer, where I could create and manage

such systems more easily, I settled on a system of ¬ve-digit numbers

for my codegroups. Instead of being limited to thirty-six characters to

represent ciphertext, I suddenly had 100,000. I could make the groups

for common letters as large as I liked, add a large set of “nulls.” Nulls

were codegroups that had no plaintext equivalent: they existed only to

confuse attempts analyze the ciphertext.

Encrypting a message with such a system was tedious because such

a large table was needed. In fact, it would work very much like a foreign

Discovery 39

language dictionary that goes from one language to another in the front

part, and then back again in the second half.

To encrypt a message like:

Meet at the library after school today. The topic is

algebra.

the plaintext-to-ciphertext table would be consulted to ¬nd words or

phrases that would be de¬ned. Most of the words in a message like

this would be de¬ned in their entirety, such as “meet,” “at,” “library,”

and “today.” The phrases “after school” and “the topic is” would be

de¬ned in their entirety as well. De¬nite articles in this case can be

safely dropped without any loss in meaning, leaving us to spell out

only “algebra.”

A few sample entries from the table below will give us what is needed

to convert the plaintext to ciphertext.

. 34134

a 34714 10398 27225 36404

after school 72191

at 47008

b 88420

library 02979

e 16628 72700 33525 73487 69419 15940

g 30148

l 46399

meet 40746

null 22604 24638 84879 71792 03858 11341

37135 11337 21715 92643 16989 67646

82998 07445 83430 10869 15653 17431

r 66911

today 65573

topic is 08565

Working through our cleartext message, constructing the ciphertext

from the codebook would create ciphertext that obfuscates not only the

letters and words used to create the message, but its general structure.

The resulting ciphertext would look like the following.

40746 47008 02979 72191 65573 34134 08565 22604

34714 46399 30148 16628 88420 66911 10398 24638

40 CHAPTER 5

Decryption would use the corresponding table that was sorted by

number, e.g.,

02979 library

08565 topic is

10398 a

16628 e

22604 null

24638 null

30148 g

34134 .

34714 a

40746 meet

46399 l

47008 at

65573 today

66911 r

72191 after school

88420 b

Using that table, the ciphertext could be converted back to plain-

text, one codegroup at a time. After I began to use computers to con-

struct these elaborate codebooks and to use them more e¬ciently, I

learned how data are represented in computers and how they could be

manipulated in much more powerful ways, opening a whole new world

of cryptographic capabilities. It was then, in high school, that I learned

about cryptosystems like DES and the mathematical methods used to

try to break them.

I had not realized the complexity of the ¬eld until I learned enough

that my pursuit of cryptography was no longer an absurdity.

My early cryptosystems”the most sophisticated of which I thought

to be ¬endishly devious”were all a joke in the grand scheme of things.

On the other hand, they were secure for their purpose. My friends and

I were able to use my systems to keep our secret plans to rendezvous

at the library safe from the prying eyes of our “adversaries.” But the

experience was valuable and ultimately helped me to develop expertise

in cryptography that would allow me to protect information from sig-

ni¬cantly more sophisticated cryptanalysts than teachers and parents.

6

RSA Crypto Challenges

August 12, 1982

MIT, Boston, Massachusetts

With signatures applied to a handful of documents, RSA Data Security,

Inc. came to life, a company formed to bring the work of three MIT

mathematicians”Ron Rivest, Adi Shamir, and Len Adleman”to mar-

ket. The trio invented a public key cryptosystem in 1977 and named it

“RSA” after themselves. Looking for a means to bring their algorithm

into use, Rivest, Shamir, and Adleman formed the company and, with

some ¬nancial backing from an experienced businessman, acquired the

exclusive rights from MIT to commercialize their invention, U.S. Patent

4,405,829, “Cryptographic Communications System and Method.”14

By 1996, RSA Data Security grew to be a company whose technology

was used to protect all manner of information, especially on the Inter-

net. Securing e-mail messages and Web transactions became everyday

events thanks to products incorporating RSA Data Security™s crypto-

graphic algorithms. Such systems needed not only the ¬‚agship RSA

public-key algorithm, but symmetric cryptosystems as well. To answer

this need, RSA Data Security o¬ered symmetric algorithms, including

a system devised by MIT mathematician and RSA founder Ron Rivest.

41

42 CHAPTER 6

The RSA algorithm itself depends on a di¬cult mathematical prob-

lem: factoring of large numbers (i.e., ¬nding all of the smaller numbers

that will divide evenly into a given large number). RSA key pairs are

generated mathematically, and need to be made with big numbers”

numbers so big that factoring them would take so long that by the time

an attacker factored the number, the encrypted message contents would

be worthless. Knowing how big those numbers had to be would require

staying abreast of just how quickly large numbers could be factored.

As part of its ongoing research e¬orts, RSA Data Security spon-

sored a series of contests, known as the RSA Factoring Challenges.

Those contests were designed to encourage researchers to factor large

numbers”over 100 digits long”and to compete against each other to

see who could factor the largest numbers in the least time. These e¬orts,

in turn, helped RSA researchers keep an eye on how quickly the code-

breaking technology was progressing, so that the code-implementors

would be sure to use keys large enough to keep the real attackers at

bay.

Scientists had factored large numbers on computers before. In 1988,

an e¬ort to factor a large number was undertaken by Arjen K. Lenstra

and Mark S. Manasse. While large numbers had been factored before,

the Lenstra-Manasse e¬ort was unique in that it used the Internet to

coordinate its participants™ e¬orts. Rather than having the computa-

tions performed by one large computer or by many computers from

the same lab, volunteers in the project ran special software on their

computers that would have them work with all of the other computers

running the Lenstra-Manasse software.

RSA Data Security Inc. issued its Factoring Challenge contests to

ensure that the factoring work would continue to be done. The strat-

egy worked. In 1993, RSA-129 (a 129-digit number) was successfully

factored by 600 volunteers. Since that time, many other RSA num-

bers have been factored, including RSA-160. (RSA paid cash prizes to

contest winners.)

In each of these challenges, the contestants would be given some

encrypted data, along with some information like which cryptosystem

was used for the encryption and a little bit of the text that would match

properly-decrypted plaintext. In short, this provided enough informa-