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
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 .
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-
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
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
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
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
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
A few sample entries from the table below will give us what is needed
to convert the plaintext to ciphertext.
a 34714 10398 27225 36404
after school 72191
e 16628 72700 33525 73487 69419 15940
null 22604 24638 84879 71792 03858 11341
37135 11337 21715 92643 16989 67646
82998 07445 83430 10869 15653 17431
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
08565 topic is
72191 after school
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.
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.
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
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
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-