Part of my series explaining the RSA Algorithm

Asymmetric encryption, also known as public-key encryption, is a popular method for exchanging private information between individuals, which has become more and more important in the world of digital cryptography.

To begin, we’ll discuss the problems that asymmetric encryption solve.

Later, we’ll get into the weeds of how it works.

In the past few months I’ve written a lot about Number Theory. I thought it about time that we put all of this knowledge to some use. So today we’re going to tackle one of Number Theory’s most relevant application domains: cryptography.

What is encryption?

Encryption is a mechanism for hiding the meaning of information by expressing it in a non-readable way. In order to read it, the information must be decrypted. The process of encryption usually takes the form of mutating data in some way. Decryption can only be achieved with an awareness of the encryption process used.

The purpose of these cryptographic steps is to ensure that only intended parties can read the enclosed information. Since the invention of secrecy people have found ways to convey their meanings without others being able to intercept, however the dawn of the computer age has made these issues more acute.

The Caesar’s Cypher is two millennia old. It was used so that the Emperor could communicate without the messenger reading the message. The model of a message being transmitted from sender to recipient, on horseback or along fibre-optic cables, remains the same. The medium of transmission cannot be trusted. Interception is a real risk. This is why we need encryption.

Symmetric Encryption

Symmetric encryption is the better known method of encryption. The same key that encrypts the data decrypts the data. Analogous to a door, which is locked an unlocked by different copies of the same key.

The Caesar’s Cypher is symmetric encryption. The encryptor shifts ever letter in the message K letters to the right, in alphabetical terms. K could be any integer, and is the secret key known only by the sender and recipient. If K = 3 then a -> d, b -> e and so on. The message “ABC” becomes “DEF”. The recipient would also know that K = 3. They shift each letter back by 3. d -> a etc. This allows them to decrypt the message “DEF” as “ABC”.

The Caesar’s Cypher is a trivial example. There are only 25 possible keys, and can easily be brute-forced. This issue aside, there is another. The sender and recipient both need to know the key value, K. They cannot send this to each other in a message, or else it could be intercepted, and all following encryption would be compromised.

They would need to meet and physically exchange keys, to be sure that the key isn’t intercepted by someone else. In the past this may not have been a problem. Two spies wishing to use a symmetric encryption method could exchange keys in person before sharing encrypted letters with one another.

In the digital age though, it is not feasible to physically meet and exchange keys each time you need to encrypt data. When you came to this website, TLS encryption took place to keep your use of this site private. You did not need to physically meet me in order for that to work. If you had to do so, your use of the internet would be heavily limited. The purpose of the internet is to enable communication which is location-agnostic.

Asymmetric Encryption

Asymmetric encryption is a method which renders raw key exchange unnecessary. Instead, two corresponding keys are formed, with complimentary mathematical properties. As such, a message encrypted by one key can only be decrypted by the other, and vice versa. Importantly, no key can decrypt its own messages.

The intended recipient creates two such keys. One is chosen as the public key. This can be sent freely across the network to someone that wishes to communicate with this recipient. Using the public key, they encrypt their message and then send it. This message can only be decrypted with the other key, the private key, which the recipient kept for themself. The sender can be sure that only the desired recipient can read their messages.

The enormous benefit here is that the private, decrypting key is never sent or shared. It is kept locally and remains private.

Public Key Interception

An issue that remains though, is that the recipient cannot guarantee who sent this message.

Alice generates a public and private key pair. She sends the public key to Bob. Bob can use the key to encrypt messages and send to Alice. Alice receives those messages and decrypts them. Bob knows that only Alice can read them.

Charlie intercepted Alice’s public key when it was shared across the network. He can now write messages pretending to be Bob. He can encrypt them and send them to Alice. Alice can decrypt those messages and believe Bob is the sender.

Signing Messages

To prevent abuse of public keys, both Alice and Bob can generate a set of key pairs. They each share their public key with one another. When Bob wants to send a message to Alice he will encrypt the message with Alice’s public key as before. He will also add a signature. He might write “Signed by Bob”, and encrypt this with his own private key. This is appended to the end of his message.

When Alice receives this, she can decrypt the message using her private key as before. To verify Bob sent it to her, she can take the signature from the end of the message and decrypt using Bob’s public key. She is able to decrypt this and therefore be sure that the message is definitely from Bob. The same process works when Alice sends Bob a message.

Even if Charlie intercepts both shared public keys, he does not have the private keys necessary to encrypt a signature. Any messages he sends to Alice or Bob can be easily determined as imposters.

How Does It Work?

Now we have a good grasp of the purpose of asymmetric encryption. We need to know how it works next. How can two keys have complimentary properties so that only the other can decrypt its messages?

To understand exactly how RSA works, see the complete guide here.