Public Key Cryptography Overview

Introduction

For virtually as long as people have communicated with each other, there has been a desire to ensure the privacy of their communications. In times of war, for instance, messages dispatched to the field must be protected from interception. The ancient Greeks developed a system, called a scytale, which rendered messages unreadable by the enemy. The technique used two cylinders of equal diameters, a long ribbon to be wrapped around each cylinder and a message written lengthwise along the ribbon/cylinder. When unwrapped from the cylinder, the ribbon displayed a seemingly unreadable series of characters. When wrapped around the matching cylinder by the recipient, however, the message was revealed. This is an early example of a cipher.

Technically, a cipher is a methodological transformation by which characters are rearranged or transformed to scramble information. An extremely simple cipher replaces a character in a message by the character three positions later in the alphabet. For example, the message “Good Morning” would be enciphered to read “Jrrg Pruqlqj.” (Figure 1)

To read the original message, the recipient would simply replace each letter with the letter 3 positions before it in the alphabet. (Figure 2)

This transformation is simple to perform, and without specific knowledge of the transformation the message is effectively unreadable. (Unfortunately, this cipher is relatively easy to break by applying well-known rules and techniques regarding the composition of languages.)

A code, on the other hand, is a semantic or lexical substitution in which characters or groups of characters are replaced with other characters or symbols that represent them. Morse code, for example, where dots and dashes represent letters, is a code.

The common trait to both ciphers and codes is that they rely upon a shared secret; a method in the case of a cipher, or a codebook, in the case of a code. The secret must be known by both parties in order to be effective; the requirement to communicate the secret makes this a weak system.

As literacy increased, a need developed for ciphers or codes that could offer better security. The resulting solutions are known collectively as cryptographic systems, and the art and science of hiding information is called cryptography. To transform a message so as to hide or scramble its content is to encrypt it. The recipient must then decrypt the message before it can be read.

Symmetric Encryption Algorithms

The previous examples represent symmetric encryption algorithms. Symmetric algorithms use the same secret, or key, to both encrypt and decrypt the message. For instance, in the “Good Morning” cipher, the key is the knowledge that each character has been replaced by the character three positions later. In Morse code, the key is the codebook that tells what dots and dashes represent what letter.

Disseminating the key poses the primary threat to symmetric algorithms; it must somehow be communicated between the sender and the receiver in a secure fashion, and then it must be kept a secret. If the key is compromised it becomes worthless as a means of cryptographic security. This burden has rendered symmetric encryption technologies cumbersome and unpopular.

Asymmetric Encryption

A significantly more recent advancement in the field of cryptography was the development of asymmetric encryption algorithms; asymmetric algorithms use a pair of keys to encrypt and decrypt data. What is encrypted with one key can only be decrypted with the other.

Public / Private Key Pairs
In an asymmetric cryptographic system, one key of the pair is typically declared to be the public key. This key is shared as widely and as generally as possible and is not considered in any way to be a secret. The other key is the private key and is known only to the individual who possesses it.

Anyone who wants to communicate securely must possess a public/private key pair of his/her own. This key pair corresponds only to that individual and the private key is (or at least should be) kept absolutely secret. The private key is never shared, which eliminates the need to disseminate it and significantly reduces the potential for compromise. Eliminating the need for a shared secret is the key benefit of an asymmetric cryptographic algorithm, and is what makes systems of this sort significantly more accepted in actual use than traditional symmetric-algorithm based cryptographic systems.

Data Encryption
Encrypting a message in an asymmetric system requires the public key of the intended recipient. The message is algorithmically transformed using the recipient’s public key. The recipient decrypts the message with the corresponding private key. (The recipient doesn’t necessarily have to be another person – the recipient could be a web site, for instance.)

For instance, Alice wishes to communicate securely with Bob. She writes a message to Bob and encrypts it with Bob’s public key. She then sends this message to Bob, who decrypts it with his private key. If the message is intercepted while in transit, it cannot be read. (Figure 3)

The process is reversed when Bob responds to Alice. (Figure 4)

This model of data encryption ensures the privacy of communications while eliminating the need for shared keys.

Digital Signatures
Beyond just assuring the privacy of communications, it is also important to know with whom you are communicating, or to authenticate the source of the message. Additionally, it is important to know that the message content has not been altered in transmission, or that the integrity of the message has been maintained. In an asymmetric encryption model, the public/private keys are also used to provide absolute confirmation of both the source and integrity of a message. This two-fold purpose is accomplished through the use of digital signatures.

A digital signature is a digest, or hash, of the message encrypted with the sender’s private key. A hash is a unique, algorithmically derived representation of the message content. Every message will produce a (reasonably) unique hash that differs from the hash produced by another message. This little message represents the contents of the big message, but does not reveal the content of the big message, meaning you cannot recreate the message from the hash. The hash is calculated using a standard algorithm. Once produced, it is encrypted with the sender’s private key and appended to the message – this is the digital signature.

If Alice wishes to digitally sign a message that she sends to Bob, the program she is using first creates a hash of the message and encrypts it with her private key. This is the digital signature, which is then attached to the message itself; the message with signature attached is sent to Bob. (Figure 5)

When he gets the message, Bob decrypts the digital signature with the Alice’s public key, recalculates the hash of the message itself, and compares the two. If the results match, Bob is assured that the message is in fact from Alice and not from an imposter, and he is also assured that the message has not been tampered with in transit. (When you are shopping on the web, this authentication and the data encryption described previously is what the Secure-Socket-Layer (SSL) protocol uses to identify the seller to you and to protect your credit card information in transit.) (Figure 6)

If an imposter has sent the message or if as little as one character of the message has been changed in transit, the two hashes will not verify and the communication will be known to be unreliable.

Unlike traditional signatures, digital signatures cannot be forged. Once the identity of a key pair holder has been established, it can be stated with certainty that messages bearing that digital signature are from that individual – assuming that the private key has not been compromised.

Private, Authenticated and Tamper-Proof
To summarize the combined process: a message is signed with the sender’s private key and then encrypted with the recipient’s public key. Upon receipt, the message is decrypted with the recipient’s private key and then the signature verified using the sender’s public key. (Figure 7)

Public/private key pairs enable the use of data encryption and digital signatures to ensure private, authenticated, tamper-proof communications without the burden and volatility associated with shared secret models. In the next section we discuss matters associated with the distribution of public keys and the authentication of the identity of the holder of the corresponding private key.

Public Key Distribution and Digital IDs

While public/private key solutions provide the basis for secure communications, one additional problem must be addressed: How can public keys be trusted? While not secret, they must be distributed in a way that guarantees both the source and the integrity of the key – otherwise a sender wouldn’t know to whom they are encrypting messages or whose signature is on the messages they receive.

It is necessary in all cryptographic systems to establish a trust relationship of some kind before secure communication starts. In the simple symmetric examples given earlier, the trust relationship is the fact that two parties have trusted each other with a shared secret. In an asymmetric model, the trust relationship is the knowledge of the source and the integrity of the public key.

A digital signature applied to the public key will achieve this, but who will sign it? The purpose of the signature is to verify the public key’s association with a given private key holder in order to establish a trust relationship, so it is useless to have the private key holder sign the public key.

The solution: A third party to certify the integrity of the public key and package it for easy distribution.

Digital IDs and WildID
A digital ID, or digital certificate, is the package issued by a third party with a public key and information identifying the corresponding private key holder. A WildID is a digital ID that may be pseudonymous or anonymous in nature that contains the following information:
· the public key
· any identifying information that the holder of the corresponding private key wishes to provide
· WildID’s identity and information relating to WildID
· the validity period of the digital ID (digital IDs must be renewed)
· a digital signature of the above produced with WildID’s private key

A WildID provides the identifying connection between an individual and their public key. If, for instance, Alice has a copy of Bob’s WildID that she has independently verified to be his, she has his public key, which she may use to encrypt messages sent to Bob and to authenticate messages that she has received from him. (Figure 8)

One of the items contained in a WildID is a digital signature created by WildID’s private key. This signature may be cryptographically verified with WildID’s public key to validate both the integrity and the source of the digital ID. WildID’s public key is contained in WildID’s digital ID, which is a self-signed digital ID known as a root certificate. (Figure 9)

There is no secret information in a WildID. In fact it’s best to disseminate the WildID as widely as possible to facilitate secure communications with a number of people (and other entities.) The private key that is associated with the WildID however, is a secret that should never be shared.

Certificate Authorities
A third party that issues digital IDs is a certificate authority (CA). Obtaining a digital ID from a certificate authority enables the use of the secure communications technologies that already exist on tens or even hundreds of millions of desktops today.

Traditionally, certificate authorities have demanded personal information before issuing a digital ID to a user, such as credit card information, social security numbers, or driver’s licenses. WildID, however, is the certificate authority that issues digital IDs without invading one’s privacy. A user may provide as much or as little personal information as desired to be contained in a WildID.

For instance, Alice may obtain a WildID containing only her Hotmail address for use in secure communications with people she meets in a newsgroup, but with whom she does not wish to exchange personal information. Or, Bob and Alice obtain WildIDs containing their identities and exchange them. They then independently verify, by phone or other means, the exchange. These WildIDs may then be used for secure communications between them.

Certificate Validity
Good security practices require periodic revalidation of trust relationships. In order to facilitate this, digital IDs have a validity period before and after which they cannot be used. WildIDs have a validity period of 30 days after which they need to be renewed or replaced. This period has been selected due to the arbitrary nature of the identity that the digital ID is bound to. If a WildID user believes that the integrity of the identity and the security of the private key have been maintained, the WildID may very easily be renewed by simply revisiting the WildID website.

Conclusion

While cryptography itself has been around for centuries, the development of the asymmetric algorithms for public key cryptography is fairly recent. The benefits of public key cryptography are only beginning to be explored and new applications are developed every day. Public key cryptography provides an extremely convenient and widely available means of securing electronic communications.