Crypto 101: Public-Key Cryptography

Unlike symmetric cryptography, public key cryptography uses two different keys - one public and one private. The keys are mathematically related, yet it is computationally infeasible to deduce one from the other. Anyone with the public key can encrypt a message but not decrypt it. Only the person with the private key can decrypt the message.

Bruce Schneier compares public-key cryptography with a mailbox. He writes:

Using public-key cryptography, Alice and Bob can communicate securely using the following simple protocol:

• Alice and Bob agree on a public key algorithm.
• Bob sends Alice his public key.
• Alice encrypts her message with Bob's public key and sends it to Bob.
• Bob decrypts Alice's message with his private key.

Notice that this protocol does not require any prior arrangements (such as agreeing on a key) for Alice and Bob to communicate securely.

In real-world implementations, public keys are rarely used to encrypt actual messages as public-key cryptography is very slow, about 1000 times slower that conventional cryptography [1]. Instead, public-key cryptography is used to distribute symmetric keys which are then used to encrypt and decrypt actual messages, as follows:

• Bob sends Alice his public key.
• Alice generates a random symmetric key (usually called a session key), encrypts it with Bob's public key and sends it to Bob.
• Bob decrypts the session key with his private key.
• Alice and Bob exchange messages using the session key.

Systems that use both symmetric and public-key cryptography in this manner are called hybrid.

Certain public-key algorithms such as RSA allow both the public and private key to be used for encryption. If a message is encrypted with someone's private key it can only be decrypted with the corresponding public key. This feature can be used to create digital signatures, as follows:

• Alice encrypts the document with her private key. The encrypted document becomes her digital signature.
• Alice sends the signature to Bob.
• Bob decrypts the document with Alice's public key thereby verifying the signature.

Once again, encrypting an actual message with a private key is very inefficient. Instead of signing the entire document, the document's hash can be signed, as follows:

• Alice computes a one-way hash of a document.
• Alice encrypts the hash with her private key. The encrypted hash becomes the document's signature.
• Alice sends the document along with the signature to Bob.
• Bob produces a one-way hash function of the document received from Alice, decrypts the signature with Alice's public key and compares the two values. If they match, Bob knows that: (1) the document really came from Alice and (2) the document was not tampered with during transmission.

RSA is by far the most popular public-key cryptography algorithm. It supports both encryption and digital signatures. It is also the easiest one to describe and implement. RSA has withstood years of extensive cryptoanalysis and is a de facto standard in much of the World [1]. RSA is named after the three inventors - Ron Rivest, Adi Shamir and Leonard Adleman.

In RSA, a public key is based on the product of two large prime numbers. These two numbers must be kept secret as they are used to compute the private key. The product of the two prime numbers is referred to as modulus. The security of RSA lies in the difficulty of factoring large numbers.

The Microsoft Base Cryptographic Provider implements RSA with a 512-bit modulus. With the Microsoft Enhanced and Strong Providers, the default modulus is 1024 bits, and valid moduli can be in the range of 384 bits to 16,384 bits in 8 bit increments.

The hybrid communication protocol described above is vulnerable to a man-in-the-middle attack. Let's assume that Mallory, an enemy hacker, not only can listen to the traffic between Alice and Bob, but also can modify, delete, and substitute Alice's and Bob's messages, as well as introduce new ones.

Mallory can impersonate Alice when talking to Bob and impersonate Bob when talking to Alice. Here is how the attack goes:

• Bob sends Alice his public key. Mallory intercepts the key and sends his own public key to Alice.
• Alice generates a random session key, encrypts it with "Bob"'s public key (which is really Mallory's) and sends it to Bob.
• Mallory intercepts the message. He decrypts the session key with his private key, encrypts it with Bob's public key and sends it to Bob.
• Bob receives the message thinking it came from Alice. He decrypts it with his private key and obtains the session key.
• Alice and Bob start exchanging messages using the session key. Mallory, who also has that key, can now read the entire conversation.

A man-in-the-middle attack works because Alice and Bob have no way to verify they are talking to each other. An independent third party that everyone trusts is needed to foil the attack. This third party could bundle the name "Bob" with Bob's public key and sign the package with its own private key. When Alice receives the signed public key from Bob, she can verify the third party's signature. This way she knows that the public key really belongs to Bob, and not Mallory.

A signed package containing a person's name (and possibly some other information such as an email address and company name) and his/her public key is called a digital certificate (or digital ID). An independent third party that everyone trusts whose responsibility is to issue certificates is called a Certification Authority (CA). Digital certificates are the topic of the next chapter.