stand today on the brink of a revolution in cryptography.
The development of cheap digital hardware has freed it
from the design limitations of mechanical computing and
brought the cost of high grade cryptographic devices down
to where they ca be used in such commercial applications
as remote cash dispensers and computer terminals.
turn, such applications create a need for new types of
cryptographic systems which minimize the necessity of secure
key distribution channels and supply the equivalent of
a written signature. At the same time, theoretical developments
in information theory and computer science show promise
of providing provably secure cryptosystems, changing this
ancient art into a science.
Diffie and Martin Hellman; "New Directions in Cryptography";
IEEE Transactions on Information Theory; Nov. 1976.
Public Key Cryptography
(PKC) uses two keys, a "public key" and a "private key",
to implement an encryption algorithm that doesn't require two
parties to first
exchange a secret key in order to conduct secure communications.
In a nice mathematical twist, this conceptual breakthrough also
enables an elegant implementation of digital
For thousands of years, it was unanimously agreed in the cryptography
community that the only way for two parties to establish secure
communications was to first exchange a secret key of some kind.
This seemed to be simple common sense: if the recipient didn't
have a secret to give them some leverage, how could they be in
a better position to decrypt the message than an eavesdropper?
Practically speaking, this meant that one of the parties first
had to send a trusted person to the second party with a secret
key (which typically took a fair amount of time), or send the key
through an existing encryption channel that couldn't be completely
trusted (if it was broken, all of the keys transmitted over that
channel were also broken).
Nevertheless, there was increasing motivation to examine the problem
for both military and commercial use. The task of military encryption
key management had greatly expanded with the growth in electronic
communications networks, and the number of parties that needed
to communicate to organize a large-scale military operation such
as World War II had numbered in the thousands. Practical experience
with military communications showed that much of the conversations
had ended up unencrypted, simply because there wasn't time to establish
a secure connection. In the commercial domain the problem was quickly
growing to become even more challenging,
with increasing use of electronic networks to conduct sensitive
business communications and financial transactions, often between
parties from different organizations that had not previously communicated
or had the
chance to exchange encryption keys beforehand.
The subsections below describe the history of the development
of the seemingly magical solution to these problems, just in time
use on the
Internet -- Public Key Cryptography (PKC):
Diffie, Hellman, Merkle. The
first researchers to discover and publish the concepts of PKC
Diffie and Martin Hellman from Stanford University, and Ralph Merkle
from the University of California at Berkeley. As so often happens
in the scientific world, the two groups were working independently
on the same problem -- Diffie and Hellman on public key cryptography
and Merkle on public key distribution -- when they became aware
of each other's work and realized there was synergy in their approaches.
In Hellman's words: "We each had a key part of the puzzle
and while it's true one of us first said X, and another of us first
said Y, and so on, it was the combination and the back and forth
between us that allowed the discovery."
The first published work on PKC was in a groundbreaking paper
by Whitfield Diffie and Martin Hellman titled "New Directions
in Cryptography" in the November, 1976 edition of IEEE
Transactions on Information Theory, and which also referenced
Merkle's work. The paper described the key concepts of PKC, including
the production of digital signatures, and gave some example algorithms
for implementation. This paper revolutionized the world of cryptography
research, which had been somewhat restrained up to that point by
real and perceived Government restrictions, and galvanized dozens
of researchers around the world to work on practical implementations
of a public key cryptography algorithm.
Diffie, Hellman, and Merkle later obtained patent number 4200770 on
their method for secure public key exchange.
Rivest, Shamir, Adleman (RSA). The
Diffie-Hellman-Merkle key exchange algorithm provided an implementation
for secure public key
distribution, but didn't implement digital signatures. After
reading the Diffie-Hellman paper, three researchers at MIT named Ronald
Shamir, and Leonard
Adleman (RSA) began searching for a practical mathematical
function to implement a complete PKC approach. After working on
more than 40 candidates, they finally discovered an elegant algorithm
based on the product of two
prime numbers that exactly fit the requirement for a practical
public key cryptography implementation.
RSA's breakthrough was first publicized by Martin
Gardner in August, 1977, in his widely read column Mathematical
Games in the magazine Scientific
American, and included an offer from RSA to mail a complete
report on the PKC method to anyone that requested
it. Recognizing the power of the idea and fearing its use by
the US National Security Agency (NSA)
requested that RSA stop distributing the report. However, when
queried, they were unable to provide a legal basis for their
request, so the university bravely decided to continue distribution.
February, 1978, RSA published a more detailed paper on their
work in the
of the ACM,
and the PKC cat was out of the bag for good.
In a foreshadowing of the struggle over PGP,
the legal battle with the US Government over the RSA algorithm
went on for several years. In one of the most comical incidents,
RSA was written up by Adam Back as a 5 line PERL
program, for which Peter
Junger requested and received written instructions from the
US Government prohibiting export outside of the country. Many people
subsequently put the program in their email signatures or printed
it on t-shirts to protest the Government restrictions.
In 1982, RSA formed the company RSA to
market their PKC algorithm in electronic security
products. They obtained patent number 4405829 on
the RSA algorithm in the US, but could not obtain a patent internationally
because they had already published the idea and most other countries
bar retroactive patenting of open
Whether as a licensed product, as part of PGP, or implemented
by others, the RSA algorithm has become the foundation of an
entire generation of public key cryptography security products.
Because it provides secure communications over distances between
not previously met, RSA provides the ideal mechanism
required for private communications over electronic networks, and
forms the basis of almost all of the security products now in use
on the Internet for financial and other private communications,
including most organizational level Public Key Infrastructure
In September 2000, the US patent for the RSA algorithm expired,
for the first time enabling software developers everywhere to freely include
this PKC standard in their products.
Ellis, Cocks, Williamson. In December, 1997, it
was revealed that researchers at the GCHQ organization
did some work in the early 1970's in the field of "non-secret encryption",
which is related to public key cryptography, but without inclusion of the concept
of digital signatures. However, these
claims are not verifiable since the work was not published, and there are no
evidentiary artifacts available such as original copies of the papers (although
modern transcriptions are linked below). Therefore, in keeping with a long
tradition, credit for the development and publication of PKC must remain with
the researchers who first published their work in the open scientific literature,
as described above. The work of the GCHQ researchers is described below as
related by James Ellis in his paper The
History of Non-Secret Encryption.
Ellis began thinking about the shared secret key problem in the late 1960's
when he discovered an old Bell Labs paper from
October, 1944 titled "Final Report on Project C43", describing a clever method
of secure telephone conversation between two parties without any prearrangement.
If John calls Mary, then Mary can add a random amount of noise to the phone line
to drown out John's message in case any eavesdroppers are listening. However,
at the same time Mary can also record the telephone call, then later play it
back and subtract the noise she had added, thereby leaving John's original message
for only her to hear. While there were practical disadvantages to this method,
it suggested the intriguing logical possibility: there might be methods
establishing secure communications without first exchanging a
shared secret key.
Ellis thought about this seemingly paradoxical idea for awhile, and while
lying in bed one night developed an existence proof that the concept was possible
encryption, which he recorded in a secret CESG report
titled The Possibility
Encryption in January, 1970. This showed logically that there could be an
encryption method that could work without prior prearrangement, and the quest
in GCHQ then turned to find a practical example.
The first workable mathematical formula for non-secret encryption was discovered
by Clifford Cocks, which he recorded in 1973 in a secret CESG report titled A
Note on Non-Secret Encryption. This work describes a special case of the
RSA algorithm, differing in that the encryption and decryption algorithms are
not equivalent, and without mention of the application to digital signatures.
A few months later in 1974, Malcolm Williamson discovered a mathematical expression
based on the commutativity of exponentiation that he recorded in a secret report
Using A Finite Field, and which describes a key exchange method similar to
that discovered by Diffie, Hellman, and Merkle. It is not known to what uses,
if any, the GCHQ work was applied.