From Sixteenth-Century Cryptography to the New Millennium — The Last 500 Years - Codes: The Guide to Secrecy from Ancient to Modern Times - page 101

all of their correspondence rather than using it to set up a key exchange for use
with a symmetric-key cryptosystem. The reason has to do with eQciency, as we
will see in detail in Chapter 4. Public-key methods are extremely slow compared
to symmetric-key methods. In later discussions, we will see how both the public-
key and symmetric-key cryptosystems come to be used, in concert, to provide
the best of both worlds combining the e Q ciency of symmetric-key ciphers with
the increased security of public-key ciphers, called hybrid cryptosystems .
The DiQe-Hellman paper [69] was the “door-opener” to public-key cryptogra-
phy in that it was the landmark, since it had the first cryptographic protocol 2.24
with public-key properties including the idea of a trapdoor one-way function,
a partial solution to the public-key cryptosystem, and digital signatures (see
Chapter 4). At the end of their paper DiQe and Hellman state: “Skill in pro-
duction cryptanalysis has always been heavily on the side of the professionals,
but innovation, particularly in the design of new types of cryptographic systems,
has come primarily from amateurs.” They even go on to mention the “crypto-
graphic amateur”, Thomas Jefferson, and his wheel cypher and the fact that it
was used two centuries after its invention (see pages 66 and 67). Also, they talk
about the amateurs responsible for the rotor ciphers (see page 90).
In summary, the DiQe-Hellman key exchange allowed two entities to set
up a shared secret symmetric key, but they did not provide any method for
enciphering messages, or any way to extend to digital signatures, digital data
strings that associate a given message with its sender. As DiQe and Hellman
put it at the outset of their paper, “We propose new techniques for developing
public key cryptosystems, but the problem is still largely open.” This would
take a couple more years.
RSA and PKC
In 1978, a paper [230] was published by R. Rivest, A. Shamir, and L. Adle-
man. In this paper they describe a public-key cryptosystem, including key
generation and a public-key cipher, whose security rests upon the presumed
diQculty of factoring integers into their prime factors. 2.25 This cryptosystem,
which has come to be known by the acronym from the authors' names, the RSA
cryptosystem has stood the test of time to this day, where it is used in cryp-
tographic applications from banking, and e-mail security to e-commerce on the
Internet. We will be discussing all these applications as we progress through
the text, and we will provide the details of the RSA algorithm in Chapter 4.
The astonishing aspect of the RSA cipher is that it rests upon mathematical
developments from the eighteenth century, merely updated to our modern-day
information-based computer world. In the RSA paper [230], Alice and Bob
2.24 By a protocol , in general human terms, we will mean prearranged etiquette such as under-
stood behavior at a formal dinner party. On the other hand, a cryptographic protocol means
an algorithm, involving two or more entities, using cryptography to achieve a security goal,
which might involve issues of authentication, privacy, and secrecy, all of which we will discuss
in detail later in the text.
2.25 See theorem A.1 on page 469 in Appendix A.