The idea of using one-way functions, which can only be inverted if a certain secret (a so-called trapdoor) is known, has led to the invention of
public key cryptography
Today, public key cryptography is a battlefield for mathematicians and theoretical computer scientists. We are not going to delve into the mathematical details. Instead, we address public key cryptography from a practical point of view. From this point of view, a public key cryptosystem is simply a cryptosystem in which a
A public key that can be published without doing any harm to the system s overall security;
A private key that is assumed to never leave the possession of its owner.
For both the public and private keys, it must be
The use of a public key cryptosystem is overviewed in Figure 4.2. Again, A and B represent users, and the dark rectangles located in front of them represent the
If A wants to securely transfer a plaintext message P to B, she does the following things:
She gets the public key of B (i.e.,
) from an
She encrypts P with k B ;
She sends the resulting
Figure 4.2: The use of a public key cryptosystem.
On the other side, B uses his private key k B -1 B to successfully decrypt P = D kB -1 (C) = D kB -1 (E kB (P)) .
A public key cryptosystem can be used not only to protect the confidentiality of a message, but also to protect its authenticity and integrity. If A wants to protect the authenticity and integrity of a message
, she creates a digital signature
S = D
is abbreviated with
in Figure 4.2) for
and send it together with the message to B. Using the public key of A (i.e.,
), B can now verify the digital signature. Consequently, the value
in Figure 4.2 represents a boolean value (i.e., either the digital signature is correctly
Digital signatures provide an electronic analog of handwritten signatures for electronic documents, and ”similar to handwritten signatures ”digital signatures must not be forgeable, recipients must be able to verify them, and the signers must not be able to repudiate them later. However, a major difference between a
Arbitrated digital signature schemes are based on secret key cryptography. In such a scheme, a trusted third party (
A key-generation algorithm that
A signature algorithm that takes as input a message and a private key, and that generates as output a digital signature for the message;
A signature verification algorithm that takes as input a digital signature and a public key, and that generates as output a message and an information bit according to whether the signature is valid for the message. A comprehensive overview and discussion of public-key-based digital signature schemes are given in . According to the OSI security architecture, a digital signature refers to data appended to, or a cryptographic transformation of, a data unit that allows a recipient of the data unit to
A digital signature giving message recovery refers to the situation in which a cryptographic transformation is applied to a data unit. In this case, the data is automatically recovered if the recipient verifies the signature.
digital signature with appendix
refers to the situation in which some
The structure of a digital signature giving message recovery (a) and a digital signature with appendix (b) are
Figure 4.3: The structure of a digital signature giving (a) message recovery and (b) a digital signature with appendix.
In the case of digital signatures with appendix, the bandwidth limitation of public key cryptography is unimportant because of the use of one-way hash functions as auxiliaries. A can use her private key k A -1 to compute a digital signature S = D A (M) or S = D A (h(M)) for message M . In the second case, h refers to a cryptographic hash function that is applied to M before generating the digital signature. In summary, A does the following things when she computes and sends to B a digital signature with appendix for message M :
She uses a cryptographic hash function h to compute h(M) .
She encrypts h(M) with her private key k A -1 . The result represents the digital signature that is appended to the message.
She transmits M and the digital signature to B.
On the other side, B does the following things to verify the signature:
He hashes the message M with the same cryptographic hash function h .
He decrypts the digital signature with A s public key (i.e., k A ).
He verifies whether the two values match or not (the signature is verified only if the values match).
The use of public key cryptography considerably
A public key (or digital) certificate consists of three main elements:
1. A public key;
2. Certificate information that refers to the certificate owner s identity, such as his or her
3. One or more digital signatures.
The aim of the digital signature(s) on the certificate is to state that the other certificate information has been attested to by some other person or entity.
A digital certificate can be one of a number of different formats, including, for example, PGP and ITU-T X.509. Again, this point is further addressed in Chapter 7. In the following sections, we overview some public key cryptosystems that are in widespread use today.
The most widely used public key cryptosystem is RSA, invented by Ronald L. Rivest, Adi Shamir, and Len M. Adleman at MIT in 1977 . The RSA cryptosystem gets its security from the difficulty and intractability of the integer factorization problem. What this means is that it is
Mathematically spoken, the RSA public key cryptosystem requires two distinct large primes (
(n) = (p-1)(q-1)
Against this background, message encryption and decryption work as
To encrypt, one raises the plaintext block
to the power of
To decrypt, one raises the ciphertext block C to the power of d and reduces modulo n : P = C d (mod n ).
Digital signature generation and verification uses the same algorithms with different keys (the private key is used to digitally sign a message, whereas the public key is used to verify the signature).
The RSA public key cryptosystem was protected by U.S. Patent No. 4,405,829 ˜ ˜Cryptographic Communications System and Method, issued and granted to MIT on September 20, 1983. The patent
In 1977, Whitfield Diffie and Martin Hellman proposed a key agreement protocol that allows
The Diffie-Hellman key agreement protocol was protected by U.S. Patent No. 4,200,770, ˜ ˜Cryptographic Apparatus and Method, issued and granted to Stanford University on April 29, 1980. The patent expired in 1997. Similar to the RSA public key cryptosystem, the Diffie-Hellman key agreement protocol has never been protected by a patent outside the United States.
In the early 1980s, Taher ElGamal
Unlike many other public key cryptosystems, the ElGamal public key cryptosystem has not been patented in the U.S.
In the early 1990s, the U.S. NIST published the Digital Signature Standard (DSS) as a
More recently, the use of elliptic curve cryptography (ECC) has attracted a lot of interest. ECC-based public key cryptosystems obtain their security from the difficulty and intractability of the elliptic curve discrete logarithm problem (that uses groups of points on elliptic curves). As illustrated in Table 4.2, a number of different types of cryptography have been defined over elliptic curves. The resulting ECC-based public key cryptosystems seem to be advantageous with regard to their security properties (meaning that smaller keys are required for a similar level of security). As such, they are particularly useful in situations where small keys are required (e.g., mobile and wireless applications).
Elliptic curve Diffie-Hellman key agreement
Elliptic curve digital signature algorithm
Elliptic curve encryption scheme
Elliptic curve MQV key agreement
Elliptic curve Nyberg-Rueppel signature scheme with appendix
Unlike RSA, the general category of ECC is not patented. Individual companies, however, have filed patents for specific efficiency or security algorithms that are related to ECC. Most importantly, the Certicom Corporation  holds several patents in this field.
 In spite of the fact that  is commonly used to refer to the invention of public key cryptography, similar ideas were pursued by Ralph C. Merkle.