Public-Key Cryptography

Motivation for public-key cryptography

Public-key cryptography was initially invented to overcome some of the problems with symmetric cryptography. We must begin our discussion by clearly understanding what these are.

Problems with symmetric cryptography

The same key is used to encrypt and decrypt in a symmetric cryptosystem. There’s nothing conceptually problematic with this requirement, but it has implications that may not always be desirable. The idea behind public-key cryptography arose from an attempt to overcome these two most restrictive implications of symmetric cryptography:

• Symmetric trust: Since the sender and receiver have to share the same symmetric key, there’s an implication that, to an extent, the sender and receiver ‘trust’ one another. This ‘trust’ arises since anything cryptographic that the sender can do (by deploying the symmetric key), the receiver can also do (by deploying the same key). Therefore, it would be impossible to ensure non-repudiation. We’ll see how problematic this requirement is for at least one cryptographic service.

• Key establishment: The sender and the receiver need to agree on a symmetric key before using a symmetric cryptosystem. So the sender and receiver need a secure key establishment mechanism.

Both of these implications are quite constraining. Consider as an example an application such as an online store. A potential customer browsing the store for the first time has no reason to trust the store or any preexisting relationship. Yet, they may wish to purchase from this store and benefit from cryptography to protect any data communicated to and from the store during the transaction.

Symmetric cryptography, on its own, is unsuitable for use in this situation. Since the key is shared, non-repudiation can’t be ensured and one of the participants can claim that they didn’t forward the encrypted message. Also, since the key is transmitted on an insecure channel, an eavesdropper could potentially steal the encryption key and hijack the communication.

We’ll see shortly that public-key cryptography can be used in an attempt to overcome these problems. We apply the caveats because, as always, there are issues that need to be resolved before we can comfortably claim that public-key cryptography does overcome these problems. This shows that public-key cryptography still requires an indirect trust relationship between entities employing it. We’ll see that one of the most effective public-key cryptography uses is to support the establishment of symmetric keys.

History of public-key cryptography

There was no public-key cryptography until the final quarter of the last century. Because of this, public-key cryptography is a relatively new idea in cryptographic history. The timing of its invention is, however, more than coincidental. That’s because the problematic issues we have just associated with symmetric cryptography are relatively simple to overcome in the types of application environments in which cryptography was used before the 1970s. These were typically large, closed organizations such as governments, the military, and big financial corporations. Symmetric cryptography was perfectly suitable for use in such organizations and indeed still is for these two reasons:

• Trust relationships exist between users of cryptography since they are typically part of either the same or allied organizations.

• Symmetric key establishment can be facilitated and managed by an organization’s internal procedures and policies.

With the spread of more open computer networks, a genuine need arose for deploying cryptography in environments where the problems with using symmetric cryptography present a significant challenge.

The invention of public-key cryptography is an interesting tale in itself. The intrigue lies in the fact that years after the ‘public’ mid-1970s invention of public-key cryptography in the US, it emerged that the idea had also been discovered several years earlier by UK government researchers. Interestingly enough, the UK government researchers had set aside the idea, primarily due to practical implementation concerns.

Properties of public-key cryptosystems

We now work towards a blueprint for a public-key cryptosystem that identifies the properties we might want from such a system.

The briefcase protocol

We have observed that symmetric encryption to protect a communication channel requires a trust relationship between the two communicating entities and the initial establishment of a symmetric key. As we will see in the following example, this is not strictly true. We term this particular example the briefcase protocol.

Let’s begin with a physical analogy. Suppose Alice wishes to send a secure message physically to Bob, whom she has not met before and has no previous trust relationship with. Since it’s a physical message, Alice will secure it by locking it in a briefcase. By ‘secure,’ we mean that Alice wants to make sure that nobody can see this message during its transportation (in other words, we want confidentiality over the communication channel). Since Alice has not had any prior trust relationship with Bob, we assume Bob does not already share a key with Alice. The illustration below shows that, perhaps surprisingly, establishing some secure channel is possible.