Cryptology by Discovery: An Introduction to Conjecture and Proof

Section 5.1 Introduction

Quirky Question: What was ARPANET? Answer

The development of computers and the internet produces two major changes in the world of cryptography.

• Brute force attacks are much more viable.

• Security is not just for military anymore; everyone wants to be able to securely send information over the internet.

As a consequence cryptography moves in two major directions:

• Private (or Symmetric) Key Cryptography. In private key cryptography, the keys for encryption and decryption are the same and must be kept private. In order to use a symmetric key system, both parties must agree on and use the same shared key. All of the systems that we have discussed so far have been of this type. Modern symmetric key systems usually operate at the bit level and are designed to be very fast when implemented on computers. These systems either encrypt blocks of letters (or really, blocks of bits) of a fixed size, called Block Ciphers or they encrypt on a single bit (or byte) at a time and are called Stream Ciphers.

• Public Key Cryptography. A disadvantage of private key cryptography is that everyone who wishes to communicate with each must securely exchange a key. This is difficult and sometimes impossible. In public key cryptography the encrypting and decrypting keys are not the same. The encrypting key can be given to anyone, but the decrypting key is kept secret. Thus anyone can encrypt a message but only one person can decrypt it. These systems generally rely on a special type of mathematical functions called one-way functions.

We will focus on public key cryptography in this chapter. The ideas for public key cryptography first emerged in the 1970s. The history of public key cryptography has two different stories, a classified (until 1997) story and a public story. The classified story takes us back to the Government Code and Cypher School of Bletchley Park (and the previous chapter on Enigma). Since World War II, its name and location have changed, but not its interest in communications security. In 1946, the name was changed to Government Communications Headquarters (GCHQ). In 1970, a GCHQ researcher, James Ellis, developed the startling idea of non-secret encryption (his term for public key cryptography). In 1987, Ellis writes about how impossible this idea seemed initially, in “The History of Non-Secret Encryption”. (This article was not available to the public until it was declassified in 1997.)

It was obvious to everyone, including me, that no secure communication was possible without a secret key, some other secret knowledge, or at least some way in which the recipient was in a different position from an interceptor. After all, if they were in identical situations, how could one possibly be able to receive what the other could not? Thus there was no incentive to look for something so clearly impossible.

―James Ellis, “The History of Non-Secret Encryption”

But inspired by an article about adding noise to an audio message to encrypt speech, he nonetheless developed the 'impossible' idea of public key cryptography.

Clifford Cocks in the preface to Ellis' “The History of Non-Secret Encryption” article writes

James Ellis was a most original thinker who, when given a problem would always challenge the fundamental assumptions. Nowadays public key cryptography is so well established that it is hard to realise how improbable the concept originally seemed. The idea that in order for two parties to communicate securely, they had to have previously established a shared secret had been regarded as obvious - right back to the Caesar cipher of the Roman Empire. James shattered this long held assumption in 1969 with the notion that the recipient could play a part in the encipherment process - a revolutionary idea. He then persevered, despite some initial wariness which followed his proof of concept, to work with others to try to find a realisation of his idea, and later continued to work on the practical issues of implementing a public key system.

―Clifford Cocks, preface to “The History of Non-Secret Encryption”

Public key cryptography is currently used so widely that it is interesting to think about how strange it must have seemed at the beginning. Clifford Cocks, along with Malcolm Williamson, were the main GCHQ mathematicians who helped develop Ellis' idea into specific algorithms for implementation. In 1973, Clifford Cocks discovered ideas similar to what is now known as the RSA algorithm, and in 1974, Malcolm Williamson developed ideas similar to what is now known as the Diffie-Hellman key exchange. Of course, none of this was known in the 1970s, and it was only much later, in 1997, when these original papers were declassified and released to the public.

We will focus primarily on the public history of public key cryptography in the rest of this chapter. The public story begins with a ground breaking article by Whitfield Diffie and Martin Hellman, called “New Directions in Cryptography” and published in 1976. In this article, they propose the basic premises for public key cryptography.

In a public key cryptosystem enciphering and deciphering are governed by distinct keys, E and D, such that computing D from E is computationally infeasible (e.g., requiring \(10^{100}\) instructions). The enciphering key E can thus be publicly disclosed without compromising the deciphering key D. Each user of the network can, therefore, place his enciphering key in a public directory. This enables any user of the system to send a message to any other user enciphered in such a way that only the intended receiver is able to decipher it.

Public key distribution systems offer a different approach to eliminating the need for a secure key distribution channel. In such a system, two users who wish to exchange a key communicate back and forth until they arrive at a key in common. A third party eavesdropping on this exchange must find it computationally infeasible to compute the key from the information overheard.

―Whitfield Diffie and Martin Hellman, "New directions in Cryptography"

Photo from Stanford News Service

The idea of public key cryptography can be illustrated non-technically by considering a lockable box and a padlock. The lockable box and the open padlock can be put in a public place. Anyone can put a message in the box and shut and lock the box. But only the person with the key to the padlock can open it. In practice, we want to do this with mathematical functions instead of boxes and padlocks. In particular, public key systems generally depend on special types of mathematical functions called one-way functions. A one-way function is a function \(f(x)\) where given \(x\) it is easy to compute \(f(x)\text{,}\) but given \(y=f(x)\) then it is computationally difficult to compute \(x\text{.}\) Note that computationally difficult doesn't mean impossible, it just means that it would take too long to be useful. We return to modular arithmetic for several important examples of one-way functions.