Part II: Public Key

From Cryptography Decrypted

Part II Overview:

Public Key Cryptography

Public key cryptography is a mathematically innovative approach to secret key distribution and authentication. Not only does it let us digitally distribute secret keys securely over an unsecured line, it also provides us with non-repudiation, an assurance which we can’t get from secret key alone. And it uniquely authenticates the holder of the private part of the public key pair.

If public key cryptography is really so great, why don’t we all use it now? Though that lock you see at the beginning of your credit card purchase over the web is a piece of this system, we still don’t have all the pieces in place to allow ubiquitous authentication which could help prevent virus infection, illicit use of credit cards and terrorists attacks.

Perhaps we’d be closer to widespread application if more of us understood the technology and the issues involved in implementing it well. Certainly the cost of implementing new systems into everyone’s life is a factor inhibiting the sea change happening, but such resistances have been overcome before. After all, it hasn’t been so long since people used gas to light their houses. And it hasn’t been so long since DSL was only available at the office.

Age Old Problem: Who to Trust?

But even more than cost, there are some unresolved issues that it would behoove all of us to think about before we become enamoured of the more secure public utility the world wide web would become with state-of-the-art computer cryptographic authentication used by everyone.

Public key cryptography does not do away with the age-old problem that anyone wanting to protect secrets has always had. Who do you trust? Whoever you trust has the keys to your kingdom. Do you want Verisign to be the trusted issuer and manager of your public/private key pair? Do you want the federal government to play that role? Or do you want to trust people you know personally to verify other people they know personally? Or some combination of all three?

This problem of trust is one that has not gone away for thousands of years and is not likely to go away soon. Any cryptographic system is only as secure as who you trust at the root of the system. So no matter how technologically advanced we get, it’s good not to get too comfortable with any system. It is good to keep an eye on the guys protecting your back. Does this sound like the wild, wild west again?

That said, let’s look at the nuts and bolts of how such a system works.

The Public Key Delivery Man

In the 1970s a graduate student, Ralph Merkle, came up with an innovative way to distribute secret keys securely over an insecure line. Though Merkle’s professor was not impressed, others were. He joined with Martin Hellman and Whitfield Diffie to eventually turn this idea into Diffie-Hellman (DH) key exchange system which anyone with a credit card using SSL has benefited from.

Although it’s now accepted that British cryptographers developed public key cryptography before them, Diffie, Hellman and Merkle were the first to patent a public key system. The Diffie-Hellman public key system, implements the strategy of making a problem with at least two solution paths, an easy one and a very difficult one. Give your friends the easy, less time-consuming path and force your adversaries to solve the difficult more time-consuming version of the same problem. All public key cryptography uses this principle.

Diffie-Hellman key agreement method didn’t give us all the versatility and assurances we needed to fuel the digital age. Key exchange and authentication were still problems. With Diffie-Hellman you can’t be assured with whom you are sharing the shared secret key over that unsecured line. But in some situations that’s okay. In the case of SSL, we feel pretty comfortable that if we log onto Amazon.com, our credit card information is not going to an outfit in Russia unless Amazon authorized and outsourced their business to be handled that way.

Diffie-Hellman is used to derive secret keys in a real time situation where both parties are on the unsecured line together. That doesn’t work for us in all situations. Another public key system was needed to be more like UPS delivering secret keys whether or not we are there to receive them at that moment.

The idea of asymmetric ciphers solves key exchange and authentication problems. MIT mathematicians Ronald Rivest, Adi Shamir and Leonard Adleman built on Diffie, Hellman and Merkle’s public key foundation to create an asymmetric cipher known as RSA. In asymmetric ciphers one key is used to encrypt and another is used to decrypt, each key providing different assurances, as opposed to symmetric secret keys where both keys are the same and offer the same assurances.

RSA like AES is a published encryption method and considered very strong. At this stage in our history, if only you have access to your RSA private key, then only you can unlock what it secures.

So what is the difference between a private and a public key and how would you use them if you had such a key pair?

Using Public/Private Key Pairs

A public key is used to encrypt a message that can only be decrypted by the matching private key. Knowledge of the public key doesn’t help the nefarious BlackHat quickly decipher a public key encrypted message or figure out the private key. Since the public key doesn’t need to be concealed and is widely distributed, key distribution is much easier than in secret key cryptography.

In the following example, a stockbroker Alice uses public key cryptography to securely communicate with customer Bob. Anyone can use Alice’s public key to encrypt messages. Only Alice, the holder of the matching private key, can quickly decrypt messages encrypted with her public key.

If Alice wants to send confidential messages to her customers, she needs a separate public key for each of them.

Signing with the Private Key: Identity in Cyberspace

Public key confidentiality is one-way — from public key holder to private key holder. Bob, Casey, BlackHat — just anyone — can get copies of Alice’s public key and can send Alice confidential messages. Alice cannot send them confidential messages encrypted with her private key. As mentioned previously, she must obtain a customer’s public key to send that person a confidential message.

But Alice can provide her public key holders some assurances through the use of signing (encryption) with her private key. Alice can assure her public key holders her messages are from the authentic Alice and haven’t been altered in transit. She signs (encrypts) the messages with her private key. Private key encryption is called digitally signing. Digital signatures need a public key cryptographic system; each person has a (private) key, which is not shared.

Authentication, integrity and non-repudiation are from the private key holder to public key holders. (Note the ‘s’ on holder.)

In general, after Alice creates her RSA private/public key pair, she only uses her private key. Her customers only know Alice’s public key; that’s all they use in their confidential messages to Alice. In fact, if someone other than Alice ever learns her private key, her entire public key cryptographic system is insecure. All future messages lack any assurances.

Hashes: A Time-Saving Tool

Since public key encryption and decryption is very slow, cryptographer’s invented a condensed representation of a message called a message digest or cryptographic hash. Message digests are used as a short proxy for a usually much larger message and are designed to detect intentional modification to a message.

By signing the newsletter digest, Alice attaches her identity to the digest just like Alice signing her newsletter. But signing/verifying message digests is more efficient than signing/verifying the underlying message.

So to speed up the transmission of secure digital communications, stockbroker Alice sends and customer Bob verifies files using message digests as message proxies. The procedure is basically the same.

1. Alice makes a message digest from some plaintext message such as her stockbroker newsletter with particular stock picks.

2. Alice signs the message digest and sends the signed digest and plaintext message to Bob.

3. Bob independently recreates the message digest from the plaintext.

4. Bob verifies the file is authentic if the message digest he received from Alice is identical to the message digest he created.

Since the message digest is a redundant proxy for Alice’s newsletter, the private key signed (encrypted) message digest is only correctly verified (decrypted) by Alice’s public key. Signed hashes are also used when distributing public keys on digital certificates because they save time in verifying that the certificate is authentic.

Even though public and secret key cryptography solve a variety of problems with ushering in a more secure digital world, we still have the age-old problem of “who to trust.” How to distribute public keys is just not as mathematically comforting as strong cryptographic algorithms because of this issue.

Part III: PKI

Back to "Free Chapters"