Public Key Cryptography

CN Tower from Wards Island
CN Tower from Wards Island

Bank online?

Most of us do.

Whenever you see HTTPS as the prefix of your bank’s Internet address, it indicates that the data exchanged between your device and the bank’s website is encrypted.

A technique called Public Key Encryption enables us to securely manage our financial affairs online.

Early cryptography depended primarily on code books which provided a key for transposing the letter “A” for example into “Z” and B to value of 9. Any string in the coded representation of the message containing “Z9” means the encoded text is “AB”. This is not a very secure way of keeping a secret.

The most frequent words in the English language are “the”, “be”, “and” and “of”. Without a technique to deal with frequent word patterns, the patterns provide a valuable clue as to how the message was encoded.   The second problem with this method is that encryption keys needed to be provided with every person the using the code book – a major chore but necessary since to eliminate the risk of compromise.

The problem facing the intelligence agencies since World War I was the secure exchange of cryptography code books where keys needed to be sent in advance of the secure communication transmission.

Changing the keys to thwart an interloper was an involved and timely process.  Until all code books were replaced, the communications system remained compromised.

The basis of public key encryption was invented in 1969 by James Ellis – a scientist working for Britain’s Government Communications Headquarters (GCHQ) Intelligence Service. The basis of the invention is:

  1. Two keys – the public key and private keys are generated at the same time.
  2. The transmission of the encrypted message contained both the message and public key
  3. Sending the key with the message would eliminate the need for code books. An interloper monitoring the encrypted traffic would only see gibberish.
  4. A second property of the system is that the sender’s encrypted message encrypted by a key known to all (the public key) may only be deciphered using the receiver’s key (the private key)

An algorithm removing the public key from the message would yield the public encryption key plus the encrypted message. Even if the interloper knew how the system worked, without the receiver’s private key, the message could not be deciphered, nor could the key be determined.

Ellis knew how the system entitled “non secret encryption” worked but lacked the encryption algorithm to handle symmetric private and public keys. This was the achievement of Clifford Crocks in 1972 – a Cambridge graduate, Oxford post grad and recently hired GCHQ scientist.

Both GCHQ and  the American NSA agency lacked applications for Public Key Encryption and secure key distribution.

The invention languished under the guise of National Security until an objecting GCHQ official retired. There was no proof available showing that PKE could not be compromised.

The final part of the puzzle is solving for a way the sender and receiver obtain a key that have the symmetric key property.

Malcolm Williamson invented the secure key distribution part of the problem in 1974.

Fast forward to 1976. The non secret encryption algorithm was independently “invented” in the US by Whitfield Diffie and Martin Hellman at Stanford. In 1977 at MIT, Ron Rivest, Adi Shamir, and Leonard Adleman developed an implementation of the RSA algorithm with an article published in August 1977 edition of Scientific American. RSA became a commercial success.

Twenty five years lapsed before GCHQ on December 18, 1997 acknowledged the achievement of Ellis, Williamson and Crocks.

With the rise of the Internet, PKE became the defacto method of securing communications between a client and server. The system an as well be used to create digital signatures which enables the identification of a specific individual.

Extra Reading

The Alternative History of Public-Key Cryptography