Understanding Public Key Cryptography

Understanding Public Key Cryptograp...

Collapse All

Topic Last Modified: 2005-05-19

This topic is a high-level introduction to public key cryptography elements that specifically relate to message security. There are other sources available, which you can consult for a more in-depth understanding of the topic.

Cryptography is the study of protecting information through the use of codes and ciphers. Cryptography forms a fundamental part of message security.

At its simplest, a code is a process of methodically changing information to make it unreadable without knowing how that information was changed. One of the earliest and simplest codes (called a Caesar cipher) worked by taking the alphabet and shifting all the letters by a fixed number. The sender and recipient would both know how many letters to shift and thus could use this code to change information so that each would be able to understand, but no one else could understand. This process of changing information into a code is encryption and the process of changing code back is decryption. The original message is referred to as "plaintext." The changed message is referred to as "ciphertext." The information that is used to change the plain text into ciphertext is referred to as the key. The particular way in which a key changes information is referred to as the algorithm.

Note:
Plaintext (or cleartext) in this context should not be confused with plain text when referring to the format of an e-mail message. In that context, plain text is used to differentiate a message's format from HTML format or Rich Text Format (RTF). In the context of message security, plaintext is used to differentiate from ciphertext to indicate that the text is not encrypted.

For example, if a sender wants to encrypt a message using this method, the sender knows that every instance of the letter A in plaintext would be changed by the key to the letter D in ciphertext; every instance of the letter B in plaintext would be changed to the letter E in the ciphertext, and so on. Using this key, which has an algorithm of "shift the letters forward by three," the word "help" in plaintext would be encrypted to be "khos" as ciphertext.

When the recipient receives the ciphertext message, the recipient would transform it back into plaintext by using the key to decrypt the information, in this case by shifting the letters backward by three, reversing the change.

In this example, both the sender and the recipient must keep the key secret because anyone who knows the key can use it to decrypt and read the message. A lost key renders the encryption useless. In addition, the strength of the algorithm is important. An unauthorized party can take encrypted ciphertext and attempt to break the encryption by determining the key based on the ciphertext.

Note that both the sender and the recipient use the same key. This type of encryption is referred to as "symmetric key" encryption, because both parties use the same key.

Although this is a simple example, it illustrates the core concepts and functionality of cryptography. Recent improvements and advancements in cryptography are ones of degree.

How Public Key Cryptography Works

In 1976, Whitfield Diffe and Martin Hellman created public key cryptography. Public key cryptography represents a major innovation because it fundamentally alters the process of encryption and decryption.

Instead of a single shared, secret key, Diffe and Hellman proposed the use of two keys. One key, called the "private key" remains a secret. Instead of being shared between parties, it is held by only one party. The second key, called the "public key," is not a secret and can be shared widely. These two keys, or "key pair" as they are called, are used together in encryption and decryption operations. The key pair has a special, reciprocal relationship so that each key can only be used in conjunction with the other key in the pair. This relationship ties the keys in the pair exclusively to one another: a public key and its corresponding private key are paired together and are related to no other keys.

This pairing is possible because of a special mathematical relationship between the algorithms for the public keys and private keys. The key pairs are mathematically related to one another such that using the key pair together achieves the same result as using a symmetrical key twice. The keys must be used together: each individual key cannot be used to undo its own operation. This means that the operation of each individual key is a one-way operation: a key cannot be used to reverse its operation. In addition, the algorithms used by both keys are designed so that a key cannot be used to determine the opposite key in the pair. Thus, the private key cannot be determined from the public key. The mathematics that makes key pairs possible, however, contributes to one disadvantage of key pairs as opposed to symmetric keys. The algorithms used must be strong enough to make it impossible for people to use the known public key to decrypt information that has been encrypted with it through brute force. A public key uses mathematical complexity and its one-way nature to compensate for the fact that it is publicly known to help prevent people from successfully breaking information encoded with it.

Applying this concept to the preceding example, the sender would use the public key to encrypt the plaintext into ciphertext. The recipient would then use the private key to decrypt the ciphertext back into plaintext.

Because of the special relationship between the private key and public key in the key pair, it is possible for one person to use the same key pair with many people rather than having to use a different key with each individual person. As long as the private key remains secret, the public key can be given to any number of people and used securely. The ability to use a single key pair with many people represents a major breakthrough in cryptography because it makes cryptography substantially more usable by significantly lowering the key management requirements. A user can share one key pair with any number of people rather than having to establish a single secret key with each person.

Putting Public Key Cryptography Together with Message Security

Public key cryptography is a fundamental element of message security. Without public key cryptography, it is doubtful that there would be practical message security solutions, due to the fact that key management before public key cryptography was cumbersome. With an understanding of the basic concepts of public key cryptography, the next step is to learn how those concepts work to make message security possible.

Public Key Cryptography and Digital Signatures

As discussed in the previous section, at the core of digital signatures is the ability to uniquely identify the sender of a message. The reciprocal nature of the relationship of the key pair makes this unique identification possible through public key cryptography.

Because the private key in a key pair belongs to only one party, any time that it is shown that the private key has been used, it can be concluded that only the owner of that key has used it. In this way, the use of the private key is like a signature on a paper because only the owner of a signature can actually make it. The signature confirms its owner's presence just as the use of the private key confirms its owner's presence.

If a key pair is successfully used in an encryption and decryption operation, the pair's private key must have been used for one part of the operation. Because a public key is tied to only one private key, the corresponding public key can be used to identify its related private key and only its related private key. If a particular public key is used successfully in an encryption and decryption operation, it can be inferred that the corresponding private key was used for one part of the operation. Because only the key owner can use the private key, this means that the key owner and only the key owner could have performed part of the encryption and decryption operation.

Using a private key to establish identity shows that the full encryption and decryption operation was accomplished successfully. Showing a full operation means that plaintext would have to be encrypted to ciphertext using a private key and then decrypted back to plaintext using the corresponding public key. If this operation is successfully shown, the use of the private key, and only the private key, is demonstrated.

To show a successful encryption and decryption operation, the plaintext before the encryption and decryption operations must match the plaintext after the encryption and decryption operation. Both sets of plaintext must be compared directly and shown to match absolutely. There must be a control that is used for comparison and validation.

In e-mail, this control is the actual message. Because the message is available to both the sender and the recipient, it is a convenient control element.

To be used in this comparison operation, the message is converted into a "hash," which is a numerical representation of the complete text. Identical message text will yield identical hash values.

By taking the hash value of the message and combining it with the private key at the time of sending, the owner of the private key proves that he or she, and only he or she, sent the message.

Combining the message with the private key is accomplished by encrypting the hash value with the sender's private key, which creates the actual digital signature. Depending on how the sender's e-mail system has been configured, the digital signature is appended either to the bottom of the message, creating a "clear signed" message, or the result is combined with the original message into a binary attachment, creating an "opaque signed" message.

Because the digital signature is added to the original message as an attachment, clear signed messages can be read by e-mail clients that do not support S/MIME. The signature is discarded and the original message is displayed by non-S/MIME clients. However, there is no way the message can be verified; it is essentially the same as an unsigned message. The disadvantage of clear signed messages is that there is an increased chance for intervening mail gateways to alter the message, and thus invalidate the signature.

Conversely, because the message and the digital signature are treated as a single binary attachment in opaque signed messages, they are much less likely to be altered in transit. However, only an S/MIME client can read the attachment. If a non-S/MIME client receives an opaque signed message, the message is unreadable.

Opaque-signed messages were, in part, created to solve the problem of e-mail systems that altered message bodies while e-mail was in transit. It should be noted here that current e-mail solutions that comply with S/MIME standards do not alter the message body. However, there are many clients that cannot read opaque-signed e-mail messages. Therefore, sending clear-signed messages is recommended.

When the message is received, the digital signature can be retrieved and the sender's public key applied in a decryption operation, which yields the original hash value of the message. A comparison of this hash value with the hash value of the received message can then be performed. Because only one private key can correspond to a public key, and only the owner of the public key could use it to encrypt the hash value successfully, decrypting the hash with the public key shows that the private key owner encrypted the hash value. Because the hash value is a numerical representation of the message text, if the encrypted hash value matches the hash value of the message received, it indicates that the message text that was sent matches the text that was received. When coupled with the fact that only the private key owner could have sent the message, the result is that the recipient is assured that only the key owner sent the message, which provides authentication and, consequently, nonrepudiation. It also shows that the message has not been changed, which provides data integrity. If the hash values did not match, the recipient would know that the message had either been altered in transit or that the public key used does not match the private key used. In both cases, the recipient knows that the message is not valid and should not be trusted.

Thus, the way that public key cryptography provides the security services that make up digital signatures can be seen.

The following figure shows the sequence of signing with the addition of the supporting elements of public key cryptography.

Public key cryptography and digital signing of an e-mail message
Aa998077.35451fb8-5e11-4d67-ba6e-e5d4da6febca(en-us,EXCHG.65).gif

Message is captured.
Hash value of the message is calculated.
Sender's private key is retrieved.
Hash value is encrypted with the sender's private key.
Encrypted hash value is appended to the message as a digital signature.
Message is sent.

The following figure shows the sequence of verifying with the addition of the supporting elements of public key cryptography.

Public key cryptography and verifying a digital signature of an e-mail message
Aa998077.d1b14a27-5cfb-4df2-89f7-990219378716(en-us,EXCHG.65).gif

Message is received.
Digital signature containing encrypted hash value is retrieved from the message.
Message is retrieved.
Hash value of the message is calculated.
Sender's public key is retrieved.
Encrypted hash value is decrypted with the sender's public key.
Decrypted hash value is compared against the hash value produced on receipt.
If the values match, the message is valid.

The sequence shows how public key cryptography provides the capabilities that give a digital signature its core security services: authentication, nonrepudiation, and data integrity.

Public Key Cryptography and Message Encryption

Unlike digital signatures, the relationship between public key cryptography and message encryption is generally more straightforward, because encryption is a core function of public key cryptography. However, message encryption is not accomplished by only encrypting and decrypting the message using the key pair. The key pair is used in message encryption, but not for the entire message.

Because the goal of message encryption is to ensure that only authorized recipients can view the message, the private key of each recipient is suited to provide that service. Because the private key can only be successfully used by its owner, the use of the key during the reading of a message ensures that the owner of that key, and only the owner of that key, can read the message. This capability provides the confidentiality that underlies message encryption. Further, because the public key can be distributed widely, it allows any number of people to send information to a single private key holder.

However, the key pair is not used on the entire message. This is because the encryption and decryption operation using a key pair is an expensive process, due to the necessary complexity of the keys' algorithms. Although a key pair needs to be used, it does not necessarily have to be used on the entire message. It needs to be part of the process that "locks" and "unlocks" the information. As long as the message is unreadable until the private key is presented, the goal of message encryption is met.

As noted in "How Public Key Cryptography Works" earlier in this topic, public keys use strong algorithms to compensate for being publicly known. These strong algorithms mean that they are larger, and thus computations that use them are slower, than the older symmetric keys. Because a private key is only used to unlock information before it is viewed, and not on the entire message, it is more economical to use a key pair on as little information as possible and use a faster, symmetric key on as much information as possible while ensuring that the information cannot be used until the private key is presented.

Symmetric keys use a secret key, which both parties must know. This process is sometimes called "key negotiation." With key pairs, there is no key negotiation because one public key can be used by many people. Key pairs can also be used in conjunction with symmetric keys to handle key negotiation. A symmetric key can be chosen and that key can be encrypted, using the public key of a key pair, and sent to the owner of the private key. When sending to multiple recipients, the same symmetric key can be used for all recipients, and then encrypted using the public key of each specific recipient. Because only the private key owner can decrypt the symmetric key, the symmetric key remains a secret shared among authorized people. You can generate symmetric keys for a one-time use during a particular operation or session. These are referred to as "session keys". Public key encryption can enhance rather than replace symmetric key encryption.

The goal of message encryption is to ensure that a message is unreadable until the private key is presented. The private key can be used in symmetric key negotiation to securely transmit a symmetric key. Because a symmetric key can be securely transmitted to a recipient, you can use a symmetric key to encrypt a message and then encrypt that symmetric key using the public key in a key pair. Only the private key holder can unlock the symmetric key, which is then used to decrypt the message. This operation functions as if the entire message had been encrypted and decrypted using the key pair. However, because it uses a faster, symmetric key on most of the information, the operation is faster than it would otherwise be. Throughout this process, the message remains protected until the presentation of the private key, thus providing confidentiality, which is the fundamental service of message encryption. Because of the encryption and decryption process, any alteration of a message after it has been encrypted will cause the decryption operation to fail, providing for data integrity.

Although the use of a symmetric key may be unexpected and its benefit not immediately obvious, it enhances message security by making the process of message encryption faster without sacrificing the security of the message. The following figure shows the sequence of encrypting with the supporting elements of public key cryptography.

Public key cryptography and encryption of an e-mail message
Aa998077.21058391-2d70-42f9-bf25-8ead79705b27(en-us,EXCHG.65).gif

Message is captured.
Recipient's public key is retrieved.
One-time symmetric session key is generated.
Encryption operation is performed on the message using the session key.
Session key is encrypted using the recipient's public key.
Encrypted session key is included with the encrypted message.
Message is sent.

The following figure shows the sequence of decrypting with the addition of the supporting elements of public key cryptography.

Public key cryptography and decrypting an e-mail message
Aa998077.50f0afca-e520-46b5-8e12-6e295dfe86d9(en-us,EXCHG.65).gif

Message is received.
Encrypted message and encrypted session key are retrieved from the message.
Recipient's private key is retrieved.
Session key is decrypted with the recipient's private key.
Message is decrypted with decrypted session key.
Unencrypted message is returned to the recipient.

The sequence shows how public key cryptography provides support for the core services of message encryption: confidentiality and data integrity.

Understanding How Public Key Cryptography in Digital Signatures and Message Encryption Work Together

Digital signatures and message encryption are complimentary services. After considering how public key cryptography integrates with each service individually, it is helpful to consider how these services are used together.

The following figure shows the sequence of signing and encrypting with the addition of the supporting elements of public key cryptography.

Public key cryptography and digitally signing and encrypting of an e-mail message
Aa998077.e81cca9b-c780-49d9-a3f9-69cc3c442183(en-us,EXCHG.65).gif

Aa998077.e81cca9b-c780-49d9-a3f9-69cc3c442183(en-us,EXCHG.65).gif

Message is captured.
Hash value of the message is calculated.
Sender's private key is retrieved.
Recipient's public key is retrieved.
Hash value is encrypted with the sender's private key.
Encrypted hash value is appended to the message as a digital signature.
One-time symmetric session key is generated.
Encryption operation is performed on a message using the session key.
Session key is encrypted using the recipient's public key.
Encrypted session key is included with the encrypted message.
Message is sent.

The following figure shows the sequence of decrypting and verifying the digital signature with the addition of the supporting elements of public key cryptography.

Public key cryptography and decrypting an e-mail message and verifying a digital signature
Aa998077.97705e57-0a94-4197-99c3-40bb58a9eaa0(en-us,EXCHG.65).gif

Aa998077.97705e57-0a94-4197-99c3-40bb58a9eaa0(en-us,EXCHG.65).gif

Message is received.
Encrypted message and encrypted session key are retrieved from the message.
Recipient's private key is retrieved.
Session key is decrypted with the recipient's private key.
Message is decrypted with the decrypted session key.
Digital signature containing encrypted hash value is retrieved from the message.
Hash value of the message is calculated.
Sender's public key is retrieved.
Encrypted hash value is decrypted with the sender's public key.
Decrypted hash value is compared against the hash value produced on receipt.
If the values match, the message is valid.
Unencrypted message is returned to the recipient.

The sequence shows how public key cryptography makes digital signatures and message encryption possible.

Note how the public key or the private key of one party is required by the other party based on the specific operation. For example, the sender must have his or her private key to digitally sign e-mail, but must have the recipient's public key to send encrypted e-mail. Because this can be confusing, a chart showing which keys are needed by which parties for which operation is shown in the following figure.

Key requirements based on role and operation
Aa998077.ef4e76b6-4799-45a9-90f8-ec7af508152a(en-us,EXCHG.65).gif

The next element to understand is digital certificates. Digital certificates make using digital signatures and encryption possible by distributing key pairs.