Asymmetric Cryptography

This section deals with asymmetric cryptography, cryptographic methods in which the encryption key is different from the decryption key. With this type of cryptography, the decryption process is not simply an inverse of the encryption process but a totally different mathematical transformation. Asymmetric cryptography is a very powerful technology because a key need not be shared between two communicating parties. This eliminates the concern of how a common key is shared.

Asymmetric Primitives

As with symmetric cryptography, asymmetric primitives are the building blocks for asymmetric cryptographic protocols and for secure asymmetric applications. Recall that although cryptographic primitives by themselves do not provide useful functionality, an understanding of these primitives is helpful in understanding the protocols

RSA

RSA is perhaps the most well-known asymmetric or public key technique. There are two families of RSA primitives: for encryption and for digital signatures. Although these two families are fundamentally the same (their underlying basic algorithms are identical), we distinguish between these two families because they accomplish different goals.

The details are not necessary for understanding the uses and importance of the RSA algorithms. Although you are encouraged to read this section, grasping the mathematics is not necessary. Many software libraries handle these details transparently, and most applications developers never have to work directly with the RSA primitives.

Before you can use the RSA primitives, you must generate public and private RSA keys. The process to generate these keys follows:

1. Select two large random prime numbers, and name them p and q.

2. Set the values n = pq and = (p 1)(q 1).

3. Pick a random integer e greater than 1 and less than so that the only common divisor between e and is 1.

4. Derive the integer d between 1 and so that ed _ 1 mod (that is, the remainder of ed divided by is 1).

5. The public key consists of the integers n and e, and the private key consists of the integers n and d.

When people refer to the size of an RSA key, they mean the length of the integer n in bits (that is, a 1,024-bit RSA key means an RSA key where n is 1,024 bits long). If you are astute, you may have noticed that the preceding procedures deal with integers. Likewise, the RSA encryption and signature primitives operate on integers. This, in and of itself, is not very useful. How often do you need to send or verify only integer data? Therefore, the higher-level protocols discussed in the next section handle the conversion between the data to be sent and an integer message, on which the RSA primitives operate.

To encrypt an integer m with the public key (n, e) resulting in the integer result c (where m and c are integers between 0 and n 1), you compute c = m^e mod n.

To decrypt an integer c retrieving the integer m with the corresponding private key (n, d), you compute m = c^d mod n.

The RSA signature and verification primitives are actually the encryption and decryption primitives in the reverse order. Therefore, to sign or produce a signature s of an integer m, both between 0 and n 1, encrypt m with the private key (n, d): s = m^d mod n.

To verify the signature s, decrypt s with the public key (n, e): m = s^e mod n.

Because encryption and signature schemes are designed to meet different goals, and to avoid confusion, it is best to think of the encryption and signature families of RSA primitives as distinct. Additionally, although these primitives serve as the foundations for secure encryption and signature algorithms, by themselves they are insecure. Consequently, applications should not directly invoke the preceding RSA primitives. Rather, applications should use the RSA-based encryption and signature protocols discussed in the next section.

Discrete Logarithms

Another class of asymmetric primitives is based on the discrete logarithm and the Diffie-Hellman problems. These primitives work because of the difficulty computing the logarithm of elements in certain groups. (A group, as referenced here, is a set of elements related to each other in a mathematical way.)

The discrete logarithm problem is this: Given a prime p, a generator g of the multiplicative group Z_p^* and an element x in Z_p^*, find the least positive integer a so that x=g^a mod p.

Now, if that made perfect sense to you, you can skip this explanation. If you responded with a "Huh?," read on. Okay, what does it mean in layman's terms? We will break down each portion:

1. A prime p in cryptographic terms is usually a very large number divisible by only 1 and p.

2. Recall that modulo, or mod, produces the remainder after an integer division operation (that is, 20 modulo 5 = 0, 17 modulo 5 = 2, and 2 modulo 5 = 2).

3. A generator g of the multiplicative group Z_p^* says that there is a generator (function) g^a modulo p, where a may be in the range 0, 1, . . . p 2, that produces all the elements in Z_p^*. The elements may not be produced in order, but all elements are produced when a takes on values through the entire range.

4. The multiplicative group Z_p^* is the set or group of positive numbers that is closed under multiplication with respect to the modulo of a prime p, or the set of positive numbers {1, 2, . . . p 1}. Any member, when multiplied by another member, produces a product. This product modulo p falls within the set. For every element x in {1,2, . . . p 1}, there is an inverse y in the set, so xy mod p = yx mod p = 1.

5. Find the least positive integer a so that x = g^a mod p.

The discrete logarithm problem can be stated as follows: Given an integer a, you can easily compute x = g^a, but no one knows how to efficiently compute a, given x and g. In fact, this is regarded as a very hard problem!

The Diffie-Hellman problem is this: Given a prime p, a generator g of Z_p^*, and elements g^a mod p and g^b mod p, find g^ab mod p.

Examining the problem from a different perspective, given only g^a and g^b (that is, you are not given a or b), it is very hard to compute g^ab. Of course, given g^a and b (or given g^b and a), it is easy to compute g^ab. The difficulty of computing g^ab given only g^a and g^b serves as the basis for many asymmetric cryptographic protocols.

For traditional discrete logarithms, the private key is an integer s between 1 and p 2, and the public key is g^s mod p. The prime p and generator g are not secret they are known to all parties. When people refer to the size of a traditional discrete logarithm key, they mean the length of the prime p in bits (for example, a 1,024-bit discrete logarithm key means a key where p is 1,024 bits long).

Numerous discrete logarithm-based primitives exist. There are primitives for secret value derivation (so that two parties can compute a shared secret symmetric key), for digital signatures (so that an individual can electronically sign a message), and for signature verification (so that a recipient can verify a signature on a message). Each of these primitives includes many exponentiations (raising g or another element in Z_p^* to some power).

Elliptic Curve Discrete Logarithms

Elliptic curve based cryptographic primitives are very similar to the discrete log primitives, except that the underlying mathematical group is an elliptic curve, instead of the positive integers modulo a prime number. Just as with the preceding group, you can define the discrete logarithm problem for elliptic curve groups: Given a cyclic subgroup G of an elliptic curve, a generator g of G, and an element x in G, find the least positive integer a so that x = g^a.

For elliptic curve cryptography, the generator g and the elliptic curve are publicly known. The private key consists of an integer s between 1 and |G| 1, and the public key consists of the curve point g^s. When people refer to the size of an elliptic curve key, they mean the number of bits necessary to represent the subgroup G. For example, if G has about 2¹⁶⁰ elements, the key size is 160 bits.

Generally speaking, computing the discrete logarithm for elliptic curve groups is more difficult than for Z_p^*. This means that you can use smaller elliptic curve groups and achieve the same effective level of security as with the larger Z_p^* groups. In practical terms, this translates into smaller key sizes and less network traffic. Elliptic curve implementations can also take up less space in dedicated hardware than traditional discrete logarithm or RSA cryptographic primitives. Therefore, the primary motivation for using elliptic curves is efficiency. Because efficiency is of greater concern with wireless systems than wired, this explains the interest in using elliptic curve algorithms with wireless systems.

Other Public Key Cryptographic Primitives

Other public key cryptographic primitives are in use or under development. Two that have drawn the interest of the wireless community are NTRU and XTR. Although relatively new, both have gained considerable attention throughout the cryptographic communities. The reason for bringing these to your attention is not to discuss further the details behind these two systems but to point out that the field is changing and which primitive will eventually become adopted as the standard for wireless systems remains to be seen. Further, as computing power and resources available on wireless devices increase, we are likely to see a progression to other, more secure algorithms in the future.

Asymmetric Protocols

Asymmetric protocols, like symmetric protocols, provide a method of utilizing asymmetric primitives to create cryptographic procedures to enable protected communications between participating parties. We shall explore four common asymmetric protocols that utilize the primitives as building blocks for useful functionality: Encryption, Digital Signatures, Key Establishment, and Certificates.

Encryption

To send a secret message, the sender encrypts the message with the recipient's public key, and the recipient decrypts the message with her private key. Simple, right? Not quite. The most common asymmetric encryption algorithm is RSA. However, recall that the RSA encryption primitive by itself is insecure. In particular, RSA works on integers. Most useful messages are noninteger, so conversion of the message to integer form must be done. The RSA encryption primitive must be "wrapped" in a more sophisticated and secure protocol. For RSA, such a protocol is the Optimal Asymmetric Encryption Padding (OAEP) mode.

To encrypt a message M with the OAEP mode, depicted in Figure 6.10, you do the following:

Figure 6.10. Encrypting with the RSA OAEP mode

1. Apply an OAEP-specific encoding to M to obtain an OAEP-encoded message (this step is critical).

2. Convert the encoded message to an integer m.

3. Apply the RSA encryption primitive to obtain the integer c.

4. Convert the integer c back to a noninteger ciphertext C.

To decrypt ciphertext C with the OAEP mode, depicted in Figure 6.11, you do the following:

Figure 6.11. Decrypting with the RSA OAEP mode

1. Convert C to an integer c.

2. Apply the RSA decryption primitive to obtain the integer m.

3. Convert m from an integer to an OAEP-encoded message.

4. Apply an OAEP-specific decoding operation to obtain the plaintext M.

We caution developers that many cryptographic libraries support older and insecure versions. Further, there is no guarantee that since the writing of this book another protocol has not superceded OAEP. Developers must ensure that they know which mode is being used in libraries they are using and that these libraries contain the latest and most secure protocols and modes.

Digital Signatures

Another big advantage of public key cryptosystems over private key cryptosystems is that public key cryptosystems enable parties to create digital signatures of electronic messages. A digital signature is analogous to a physical signature. Using the office complex case study, if Louis signs a message, NitroSoft (or anyone else) can examine the message and be reasonably assured that Louis actually signed it (and that the signature was not forged by Kathleen). The presence of the signature provides evidence that Louis saw and agreed to the contents of the message before it was signed. In this way, digital signatures can also provide nonrepudiation. (Recall that nonrepudiation means that, after signing a message, the signer cannot claim that he did not sign that message.)

As with the asymmetric encryption protocols, secure signature protocols build on top of the corresponding primitives. Digital signature schemes consist of two algorithms: a signature generation algorithm and a signature verification algorithm. Most applications that use digital signatures use digital signatures with an appendix. This means that the digital signature schemes attach a signature to the end of the signed message and require the signed message as input to the verification algorithm (some digital signature schemes reconstruct the original message from the signature). The most common digital signature algorithms are DSA (the U.S. Government's Digital Signature Algorithm), an elliptic curve version of DSA, and RSA-based signature schemes.

Key Establishment

Key establishment is the process of using asymmetric techniques to agree on a shared symmetric key that is then used to communicate securely. Although the previously discussed asymmetric encryption and digital signature protocols can be used to communicate securely over an untrusted network, asymmetric cryptosystems are typically much less efficient than symmetric cryptosystems. Consequently, almost all applications use a hybrid approach a combination of symmetric techniques (for speed) and asymmetric techniques (to establish secure communications without any a priori shared secret).

There are two general classes of key establishment techniques: key transport protocols and key agreement protocols. In a key transport protocol, a session key is created and sent to the recipient. For example, Louis could create a session key, sign it, and then encrypt the key and the signature with NitroSoft's public key. Upon receipt, NitroSoft would decrypt the session key and signature, verify the signature (to ensure that the key came from Louis), and use the session key to communicate securely via a symmetric protocol.

In a key agreement protocol, both parties partake in the derivation of a shared session key. Many popular key agreement protocols are based on the discrete logarithm and the elliptic curve discrete logarithm problems. Here is a simple example:

a. Louis and NitroSoft publicly agree on a prime p and a generator g of Zp*.

b. Louis picks a non-negative integer a less than p 1 and gives g^a to NitroSoft.

c. NitroSoft also picks a non-negative integer b less than p 1 and gives g^b to Louis.

d. Louis computes (g^b)^a = g^ab and NitroSoft computes (g^a)^b = g^ab. The result, g^ab, becomes the shared secret.

Although this scheme is not perfect, it does present the basic ideas behind discrete logarithm-based key agreement protocols.

There are many desirable properties for key establishment protocols. One such property is perfect forward secrecy. This means that if an attacker compromises the private key of one of the individuals involved in a communication, the attacker should not be able to learn any of the prior session keys. The preceding example does not have perfect forward secrecy. If an attacker learns Louis's private key (n, a), she can compute (g^b)^a and obtain the symmetric key. An authenticated key establishment protocol is a key establishment protocol in which the parties can be assured that they performed the key establishment protocol with each other (and not an attacker).

Certificates

A discussion of asymmetric protocols should not neglect one significant problem how do two parties know that they really have each other's public keys? The commonly accepted solution to this problem is to use certificates. A certificate is an attempt to correlate a user's public key with her real-world identity. At a minimum, a certificate contains a user's public key and identifying information about the user. The certificate is also signed by a trusted third party. This trusted third party is called a certificate authority (CA). By verifying the CA's signature on the user's certificate before communicating with her, you are somewhat assured that you are communicating with the user and not an impostor. A public key infrastructure (PKI) is a system with a certificate authority and a clearly defined way of obtaining, validating, and deleting certificates.