Public-key cryptosystems

In a public-key cryptosystem, each participant has both a public key and a secret key. Each key is a piece of information. For example, in the RSA cryptosystem,each key consists of a pair of integers. The participants "Alice" and "Bob" are traditionally used in cryptography examples; we denote their public and secret keys as P_A, S_A for Alice and P_B, S_B for Bob.

Each participant creates his own public and secret keys. Each keeps his secret key secret, but he can reveal his public key to anyone or even publish it. In fact, it is often convenient to assume that everyone's public key is available in a public directory, so that any participant can easily obtain the public key of any other participant.

The public and secret keys specify functions that can be applied to any message. Let denote the set of permissible messages. For example, might be the set of all finite-length bit sequences. In the simplest, and original, formulation of public-key cryptography, we require that the public and secret keys specify one-to-one functions from to itself. The function corresponding to Alice's public key P_A is denoted P_A(), and the function corresponding to her secret key S_A is denoted S_A(). The functions P_A() and S_A() are thus permutations of . We assume that the functions P_A() and S_A() are efficiently computable given the corresponding key P_A or S_A.

The public and secret keys for any participant are a "matched pair" in that they specify functions that are inverses of each other. That is,

for any message . Transforming M with the two keys P_A and S_A successively, in either order, yields the message M back.

In a public-key cryptosystem, it is essential that no one but Alice be able to compute the function S_A() in any practical amount of time. The privacy of mail that is encrypted and sent to Alice and the authenticity of Alice's digital signatures rely on the assumption that only Alice is able to compute S_A(). This requirement is why Alice keeps S_A secret; if she does not, she loses her uniqueness and the cryptosystem cannot provide her with unique capabilities. The assumption that only Alice can compute S_A() must hold even though everyone knows P_A and can compute P_A(), the inverse function to S_A(), efficiently. The major difficulty in designing a workable public-key cryptosystem is in figuring out how to create a system in which we can reveal a transformation P_A() without thereby revealing how to compute the corresponding inverse transformation S_A().

In a public-key cryptosystem, encryption works as shown in Figure 31.5. Suppose Bob wishes to send Alice a message M encrypted so that it will look like unintelligible gibberish to an eavesdropper. The scenario for sending the message goes as follows.

• Bob obtains Alice's public key P_A (from a public directory or directly from Alice).

• Bob computes the ciphertext C = P_A(M) corresponding to the message M and sends C to Alice.

• When Alice receives the ciphertext C, she applies her secret key S_A to retrieve the original message: M = S_A(C).

Because S_A() and P_A() are inverse functions, Alice can compute M from C. Because only Alice is able to compute S_A(), Alice is the only one who can compute M from C. The encryption of M using P_A() has protected M from disclosure to anyone except Alice.

Digital signatures are similarly easy to implement within our formulation of a public-key cryptosystem. (We note that there are other ways of approaching the problem of constructing digital signatures, which we shall not go into here.) Suppose now that Alice wishes to send Bob a digitally signed response M′. The digital-signature scenario proceeds as shown in Figure 31.6.

• Alice computes her digital signature Σ for the message M′ using her secret key S_A and the equation Σ = S_A(M′).

• Alice sends the message/signature pair (M′, Σ) to Bob.

• When Bob receives (M′, Σ), he can verify that it originated from Alice by using Alice's public key to verify the equation M′ = P_A(Σ). (Presumably, M′ contains Alice's name, so Bob knows whose public key to use.) If the equation holds, then Bob concludes that the message M′ was actually signed by Alice. If the equation doesn't hold, Bob concludes either that the message M′ or the digital signature Σ was corrupted by transmission errors or that the pair (M′, Σ) is an attempted forgery.

Because a digital signature provides both authentication of the signer's identity and authentication of the contents of the signed message, it is analogous to a handwritten signature at the end of a written document.

An important property of a digital signature is that it is verifiable by anyone who has access to the signer's public key. A signed message can be verified by one party and then passed on to other parties who can also verify the signature. For example, the message might be an electronic check from Alice to Bob. After Bob verifies Alice's signature on the check, he can give the check to his bank, who can then also verify the signature and effect the appropriate funds transfer.

We note that a signed message is not encrypted; the message is "in the clear" and is not protected from disclosure. By composing the above protocols for encryption and for signatures, we can create messages that are both signed and encrypted. The signer first appends his digital signature to the message and then encrypts the resulting message/signature pair with the public key of the intended recipient. The recipient decrypts the received message with his secret key to obtain both the original message and its digital signature. He can then verify the signature using the public key of the signer. The corresponding combined process using paper-based systems is to sign the paper document and then seal the document inside a paper envelope that is opened only by the intended recipient.

The RSA cryptosystem

In the RSA public-key cryptosystem, a participant creates his public and secret keys with the following procedure.

1. Select at random two large prime numbers p and q such that p ≠ q. The primes p and q might be, say, 512 bits each.

2. Compute n by the equation n = pq.

3. Select a small odd integer e that is relatively prime to φ(n), which, by equation (31.19), equals (p - 1)(q - 1).

4. Compute d as the multiplicative inverse of e, modulo φ(n). (Corollary 31.26 guarantees that d exists and is uniquely defined. We can use the technique of Section 31.4 to compute d, given e and φ(n).)

5. Publish the pair P = (e, n) as his RSA public key.

6. Keep secret the pair S = (d, n) as his RSA secret key.

For this scheme, the domain is the set Z_n. The transformation of a message M associated with a public key P = (e, n) is

The transformation of a ciphertext C associated with a secret key S = (d, n) is

These equations apply to both encryption and signatures. To create a signature, the signer applies his secret key to the message to be signed, rather than to a ciphertext. To verify a signature, the public key of the signer is applied to it, rather than to a message to be encrypted.

The public-key and secret-key operations can be implemented using the procedure MODULAR-EXPONENTIATION described in Section 31.6. To analyze the running time of these operations, assume that the public key (e, n) and secret key (d, n) satisfy lg e = O(1), lg d ≤ β, and lg n ≤ β. Then, applying a public key requires O(1) modular multiplications and uses O(β²) bit operations. Applying a secret key requires O(β) modular multiplications, using O(β³) bit operations.

The security of the RSA cryptosystem rests in large part on the difficulty of factoring large integers. If an adversary can factor the modulus n in a public key, then he can derive the secret key from the public key, using the knowledge of the factors p and q in the same way that the creator of the public key used them. So if factoring large integers is easy, then breaking the RSA cryptosystem is easy. The converse statement, that if factoring large integers is hard, then breaking RSA is hard, is unproven. After two decades of research, however, no easier method has been found to break the RSA public-key cryptosystem than to factor the modulus n. And as we shall see in Section 31.9, the factoring of large integers is surprisingly difficult. By randomly selecting and multiplying together two 512-bit primes, one can create a public key that cannot be "broken" in any feasible amount of time with current technology. In the absence of a fundamental breakthrough in the design of number-theoretic algorithms, and when implemented with care following recommended standards, the RSA cryptosystem is capable of providing a high degree of security in applications.

In order to achieve security with the RSA cryptosystem, however, it is advisable to work with integers that are several hundred bits long, to resist possible advances in the art of factoring. At the time of this writing (2001), RSA moduli were commonly in the range of 768 to 2048 bits. To create moduli of such sizes, we must be able to find large primes efficiently. Section 31.8 addresses this problem.

For efficiency, RSA is often used in a "hybrid" or "key-management" mode with fast non-public-key cryptosystems. With such a system, the encryption and decryption keys are identical. If Alice wishes to send a long message M to Bob privately, she selects a random key K for the fast non-public-key cryptosystem and encrypts M using K , obtaining ciphertext C. Here, C is as long as M, but K is quite short. Then, she encrypts K using Bob's public RSA key. Since K is short, computing P_B(K) is fast (much faster than computing P_B(M)). She then transmits (C, P_B(K)) to Bob, who decrypts P_B(K) to obtain K and then uses K to decrypt C, obtaining M.

A similar hybrid approach is often used to make digital signatures efficiently. In this approach, RSA is combined with a public one-way hash function h-a function that is easy to compute but for which it is computationally infeasible to find two messages M and M′ such that h(M) = h(M′). The value h(M) is a short (say, 160-bit) "fingerprint" of the message M. If Alice wishes to sign a message M, she first applies h to M to obtain the fingerprint h(M), which she then encrypts with her secret key. She sends (M, S_A(h(M))) to Bob as her signed version of M. Bob can verify the signature by computing h(M) and verifying that P_A applied to S_A(h(M)) as received equals h(M). Because no one can create two messages with the same fingerprint, it is computationally infeasible to alter a signed message and preserve the validity of the signature.

Finally, we note that the use of certificates makes distributing public keys much easier. For example, assume there is a "trusted authority" T whose public key is known by everyone. Alice can obtain from T a signed message (her certificate) stating that "Alice's public key is P_A." This certificate is "self-authenticating" since everyone knows P_T. Alice can include her certificate with her signed messages, so that the recipient has Alice's public key immediately available in order to verify her signature. Because her key was signed by T, the recipient knows that Alice's key is really Alice's.