8 bits only: Public and Private Key Encryption
In my last post, I gave a brief taste of what exactly modern cryptography entails, starting first with some historical cryptography, and how it contrasts with what we could consider useful cryptography, in the age of high-performance, distributed and networked computing. I left you with a few questions:
- Is the same key used for encrypting and decrypting a message?
- How do we initially share the keys that we use to encrypt the messages on a channel, over that very same channel? Is this even possible?
- Do we use the same keys for encryption of channels with many different parties?
These questions in many ways drive the differences between the two well-formed schools of thought in modern cryptography, known as public and private key encryption.
Before we get to these two approaches to encryption, we first need to cement our understanding of one other constraints when designing encryption schemes, known as key space.
Key Space
When we design a key-based encryption scheme, a key constraint is that an adversary cannot simply brute force the correct key, by exhausting all possible keys. The key space is the set of all possible keys, and we need to ensure this is sufficiently large such that it would be too computationally intensive to exhaust all options, and verify the correct one. For example, if the key for a particular scheme were to be a number between 1 and 100, it would be trivial to try all possible key values to decrypt some cipher text, then manually verify the correct resulting plain text, and thus, crack the scheme. On the other hand, if we have at least the minimum key space, given the constraints of modern computing, which is approximately 2⁸⁰ possible keys, then we cannot succumb to brute force attacks, without some additional optimizations to reduce the number of keys to try.
Private Key Encryption
Private key encryption is the first of the two mechanisms of encryption. Unlike public key encryption, it is used both in modern, and historical cryptographic techniques. It is based on the use of a single key, both for encoding plaintext, and decoding cipher text, and is in many ways the more intuitive mode of encryption.
Take, for example, the world’s most simple private key encryption scheme, known as the shift cipher. Using this scheme, the key is some integer value in the range of the set of characters (e.g. for encrypting some English plain text, the key is between 0 and 25). We can then encrypt plaintext for a given key K, by shifting each letter in the plaintext forward by K characters (e.g. for the letter A, and the key 3, A becomes D). We can then clearly decrypt cipher text when we know the key, by shifting letters backwards by the key value.
Obviously, the shift cipher falls significantly below the key space constraint we defined earlier, but another simple, yet powerful private key encryption scheme which has existed for quite some time is mono-alphabetic substitution. This scheme can be imagined as a 1:1 mapping of some plain text character to some cipher text character, where we appropriately swap letters to encrypt or decrypt text based on this 1:1 mapping. This ups the possible key space to 26!, or 2⁸⁸ possible 1:1 mappings as the key.
Much time can be spent on additional private key encryption schemes and their feasibility, but instead let’s revisit our driving questions from earlier.
Firstly, we’ve addressed that for private key encryption, the same key is used for both encrypting and decrypting messages. This is why private key encryption is also referred to as symmetric key encryption.
Secondly, for sharing the private key, it’s not exactly clear yet how this would be done using private key encryption. One example of how this could be accomplished would be by physically sharing this key between two communicators e.g. using a hard drive. Another option would be using a short-lived, costlier encrypted channel for sharing the private key, and later using a new channel encrypted by this key.
For whether or not we use the same key between different channels, its easy to see why this is not the case. Consider three different individuals, A, B, and C, which all have the same private key K. Now if A and B try to establish a secure channel using K, C will be able to eavesdrop on their messages over this channel, and decrypt them. It’s clear that for private key encryption, each key can only be used on a single channel, and only shared among those who were intended to be able to use that channel.
Some downsides of private key encryption include that there is a linear growth in the number of private keys each communicator must store, relative the number of channels they use. For example, a web app using private key encryption would need to store a private key for each user of the service, which is not scalable. Secondly, there is the constraint of requiring some additional step to share the private key initially, to avoid some third party from being able to eavesdrop on an encrypted channel.
Public Key Encryption
Public key encryption is the second of the two mechanisms of encryption. It is largely a product of modern cryptographic research, and is based on the use of a pair of keys, which are used to decrypt messages encoded by the other key, and are not both shared between the communicating parties.
Public key cryptography is a modern innovation largely due to the major idealogical shift it is predicated on. It seems quite odd that we would not share a key to encrypt and decrypt some data, but the reason for its creation is largely due to the fact that it allows for not sharing all the keys necessary to eavesdrop on a channel. For example, a server can generate pair of keys, where one is shared with a client, known as the public key, and the other is not, known as the private key. Since the private key only can decrypt messages by the public key, even if the public key is initially shared with the client over an unsecured channel, any messages encrypted and sent to the server by the client can still only be decrypted by the server (since it has never shared the public key).
To answer the first of the three questions posed, public key encryption does not use the same key for encrypting and decrypting messages, which is why it is also known as asymmetric key encryption
Secondly, sharing the public key is now easily done over an unsecured channel, since only the server can decrypt messages encoded by this key, even if the public key is known by some adversary.
Thirdly, we now have the ability to safely use the same keys for many channels. Consider again a web service with millions of users. We can now give the public key for this service to every user, and rest assured that they can send messages to us that cannot be decrypted by some adversary, provided that the private key is still secured.
Public key encryption is a significant paradigm shift from private key encryption, and largely solves the scalability issue of managing private keys, as well as part of the safety issue that reusing keys would cause.
Wait, something is off…
If you’ve been following closely, you may have noticed that public key encryption hasn’t just magically made our problems go away
With public key encryption, we can now use the same public key for all channels, and clients with this public key can send encrypted messages to the server, which cannot be decrypted by an adversary. Unfortunately, this is only a 1-way encrypted channel, as a message encrypted by the server’s private key could be decrypted by anyone with the public key.
Another Issue?!
Beyond how to establish a 2-way encrypted channel, we also now introduce a new problem which has to do with how we share the public key. Given that we may share this over an unsecured channel, it is entirely possible that an adversary could intercept this message, and replace the public key with their own public key, unbeknownst to the client.
Now, at this point, we may think we are communicating over an encrypted channel with gmail.com, but really, our channel has been intercepted by definitelynotascammail.com, and since we believe the public key we have received is for gmail, but in fact is not, any future messages we send can be decrypted by this dubious adversary.
The struggle continues
We’ve been able to get a more clear idea of the two different forms of encryption, and how they differently handle the questions we were left with last time. Going forward, we will largely be discussing cryptography based on the usage of public key encryption, as this concept is the backbone of the modern, secured internet. There are still many issues though with public key encryption as we know it so far. The questions I’ll leave you with to ponder before my next post are as follows:
- How can we ensure that a public key shared over an unsecured channel is actually the public key of the party we expected to be communicating with?
- How can we establish a two-way encrypted channel, while still sharing the key(s) used for encryption, over an unsecured channel?
We’ll get to work on these issues next time, by discussing public-key infrastructure, and the Diffie-Hellman key exchange protocol.
