Public Key Cryptography

Explanation: Cryptography

Required Reading

Overview

Many things we do online today are made possible and secure using Public Key Cryptography. More generally, cryptography is the science of obscuring information from eavesdroppers or third parties. The process of “encryption” involves taking some data and applying an algorithm, resulting in a string of gibberish. This is commonly accomplished using a password. The process of “decryption” reverses the algorithm and recovers the original data from the gibberish. As a naïve example, you use the password “1234” to encrypt the message “hello” resulting in the text “DfkL3J1LN”. Anyone receiving the message sees only the encrypted gibberish, unless they know the password. Anyone who knows the password can decrypt the message and see that the original data read “hello”. Note that this example is called Symmetric Encryption since the same password is used for both encryption and decryption. Using a good algorithm and a strong enough password (please do not make your password “1234”), this effectively ensures that no one without the password can read the message.

The Problem with Symmetric Cryptography

This methodology is fine when sharing an encrypted document with a friend, since you can just write the password on a piece of paper. However, it is problematic in the age of the internet, since everyone is constantly connecting to remote servers like Amazon and Netflix. Sending the password over the internet itself would be silly, since anyone who happened to be listening in could then read the password and decrypt your messages. The answer to this problem is Asymmetric Encryption, where the encryption and decryption passwords are different (but related).

Assymetric Cryptography

Public Key Cryptography uses a special pair of “passwords” called a private key and a public key. Note that the algorithms are designed so that when messages are encrypted with the public key, they can only be decrypted with the private key (i.e. the public key will not work for decryption). Given a private key, it is very easy to figure out its corresponding public key. However, given a public key, it is nearly impossible to figure out the corresponding private key. It is similar to the mathematical operations of squaring and square rooting. Given the number 28 many people would be able to calculate the square as 784, some maybe even mentally. But given the number 784 and asked to find the square root, most people would take much longer or need a calculator. Given a much larger number, such as 1,483,294, the effect becomes even more pronounced. Furthermore, real-world encryption algorithms are based on much harder problems than taking the square root (for example, RSA is based on factoring very large numbers). This is an example of an asymmetric operation, in that it is much harder to find a number’s square root than it is to find its square (and this holds true for computers as well as people).

Example

Public Key Cryptography works as follows when Alice wants to send a message to Bob. First Bob must generate a public and private key pair. Then Alice requests Bob’s public key, and he sends it to her unencrypted over the internet. Now Alice uses Bob’s public key to encrypt the message, and sends it to him. Finally, Bob uses his private key to decrypt the message. As long as Bob never lets anyone find out his private key, then no one except him will be able to decrypt and read the message. Since a message encrypted with Bob’s public key can only be decrypted with his private key, making the public key available to everyone is fine. In the end, users can communicate securely using Public Key Cryptography as long as computers are unable to solve the underlying math problem. If you ever notice a lock symbol to the left the web address in your browser, it is because your connection to the website is being encrypted using Public Key Cryptography (specifically the TLS protocol using the RSA algorithm).

Digital Signatures

A useful extension of Public Key Cryptography is the ability to create “Digital Signatures.” Like a handwritten signature, these are designed to be unique to every individual and serve as proof that the true owner of a message has, in fact, authorized it. Since the public key and private key share the same format, they can be interchanged in encryption and decryption without any problem. So, if Bob wants to sign a message to Alice, he encrypts it using his private key. Anyone (including Alice) can then decrypt the message using his public key. Obviously, this method does not prevent others from reading the message. Rather, the advantage is that if the message were signed with someone else’s private key, “decrypting” it with Bob’s public key would yield garbage. Therefore, since Alice knows Bob’s public key, she can be confident that the message is from Bob, since Bob is the only one with Bob’s private key. Note that a message can be digitally signed and then normally encrypted as described previously, ensuring both the sender’s identity and that no one other than the intended recipient can read it.

Applications

Conclusion

In practice, when you connect over the internet you first generate a random password and encrypt it using Public Key Cryptography. All further communication is then encrypted using that password and symmetric cryptography due to implementation issues. In any case, this method allows for trusted, secure, and private communication with remote hosts on the Internet. There is some worry that Quantum Computers will render many Assymetric algorithms broken, but thankfully that hasn't happened yet. So in most cases you can be confident that "https://" in your browser's address bar means that your connection is private.