THE 2015 ACM A.M. Turing Award recognized work I did
40 years ago, so it is understandable that my interests
have changed significantly, with my most recent project
being a book, A New Map for Relationships: Creating
True Love at Home & Peace on the Planet, co-authored
with my wife Dorothie. While, at first glance, the book
might seem to have nothing in common with my work
on cryptography, my Turing Lecture drew a number of
parallels I will bring out in what follows.
The story starts in March 1975, when the U.S.
National Bureau of Standards (NBS), now known as
the National Institute of Standards and
Technology (NIST), proposed a Data
Encryption Standard (DES) to protect
unclassified but sensitive data. Whit-
field Diffie, with whom I shared the
Award, and I quickly realized that DES’s
56-bit key size was inadequate and
needed to be increased.
DES had 256, or approximately 1017,
keys. We estimated that the 1975 technology would allow a single-chip search
engine to check 106 keys per second, so
106 such chips could search the entire
key space in 105 seconds. That is approximately one day, and we estimated
the equivalent cost to be on the order of
$5,000 per recovered key. We also noted
that the decreasing cost of computation—roughly a factor of 10 every five
years—would rapidly reduce this cost.
Even an order-of-magnitude error in
our estimate would thus be erased in a
short time. 3
We initially thought the inadequate
key size was a mistake that would be
corrected once we pointed it out, but
NBS resisted, claiming our estimates
were off by four orders of magnitude.
Our initial estimate had been a rough
that was adequate to show the need for
an increased key size. But NBS’s estimate was clearly wrong, and we came to
realize we were indirectly battling the
National Security Agency (NSA), in addition to NBS.
A larger key size would allow foreign
governments, criminals, and terrorists
to hide their communications from
NSA, while 56 bits would not. What we
had thought was a technical problem
Cyber deterrence, like nuclear deterrence,
depends on our adversaries being rational
enough to be deterred by our threats but us
not by theirs.
BY MARTIN E. HELLMAN
˽ While revolutionary, public key
cryptography can also be viewed as
a natural step in the evolution
of the field of cryptography.
˽ There is greater risk than is generally
recognized that a major advance in
factoring and discrete logarithms might
break existing public key systems.
˽ In making ethical decisions, we need to
zealously guard against fooling ourselves
about our real motivations.