<<

. 7
( 41 .)



>>



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-

<<

. 7
( 41 .)



>>