A History of Public Key Cryptography

Public key cryptography as we know it is actually the outcome of efforts to solve a major issue with symmetric encryption systems (such as the DES)-key distribution. Concepts such as private key and public key represent the final step in the solution to the problem of key distribution.

Simon Singh in his book titled The Code Book, which deals with the history of codes and code breaking , devotes an entire chapter to Public Key Cryptography. The following is my summary of the relevant chapter along with some concepts that will explain how public key cryptography works:

 

What is Key distribution

Suppose a bank wants to send some confidential data to a client. In order to encrypt the message the bank picks a key (which will need to be used by the client to decipher the message) and uses an encryption method (an algorithm), say DES, to encrypt the message.  In order to decrypt the message the client will need to have a copy of the DES software and more importantly it needs to have the key that was used to encrypt the message. Without the key it would be impossible for the client to decipher the message. To ensure that the key is not intercepted during transfer the bank needs to hand over the key physically to the client.  However physically distributing keys to clients costs money and could become a logistics nightmare.

 

Alice, Bob and Eve

While thinking of the problem of key distribution, it is helpful to consider Alice, Bob and Eve, three fictional characters who have become the industry standard for discussions about cryptography. In typical situation, Alice wants to send a message to Bob or vice-versa and Eve is trying to eavesdrop.

 

Asymmetric and Symmetric Encryption

In Symmetric encryption, the process of deciphering the message is the reverse of the process of encrypting the message i.e. the same key is used for both encrypting and deciphering the message. A simple analogy would be that of putting a padlock on a box and handing over the key.The recipient would use the same key to unlock the box.

On the other hand in Asymmetric encryption , the encryption and decryption keys are not identical. So in the context of asymmetric encryption Alice uses a key to encrypt a message and sends it to Bob. Bob uses another key to decrypt the message.

So if asymmetric encryption were possible , it would eliminate the need to distribute keys.

 

What are Public keys and Private Keys

We can explain what public key and private keys are using an example. Supposing Bob wants to send a message to Alice-Alice would have an encryption key which she would call her public key, because she makes this key known to everyone who wants to communicate with her. Bob would use this public key to encrypt any message sent to Alice. On the other hand she would also have a private key which remains her secret and which she would use to decrypt any message sent to her that was encrypted using her public key.

 

How does the Asymmetric Encryption Cipher work?

While the basic ideas of asymmetric encryption were put forward by Whittfield Diffe and Martin Hellman, the credit for developing the asymmetric cipher was won by another trio of researchers- Ronald Rivest, Adi Shamir and Leonard Adleman. It is from this trio that we get the very popular RSA encryption system.

In order to build an asymmetric encryption cipher, cryptographers researched several mathematical functions. Of particular interest were one way functions– functions that are easy to do but very difficult to undo, a very simple analogy of a one-way process would be the mixing of of yellow and blue paint to get green.  Once the paints are mixed it is impossible to separate the colors.

The one-way function that underlies the RSA system involved selecting 2 sufficiently large prime numbers and obtaining the product. The product is equivalent to the public key and the 2 sufficiently large prime numbers are the private keys. So to illustrate, lets say we multiply 2 prime numbers 17,159 and 10,247 , the resulting number is 175,828,273.

If we were given the number 175,828,273 and asked to derive the primes, it would require several iterations before we can arrive at the answer. In reality the choice of the prime numbers tend be of the magnitude of 10 raised to the powers of 100 and the resulting number  would be even larger. To crack such numbers would require millions of computers working in tandem over several years.

The actual algorithm for encrypting the message involves a few more steps involving the public key and private keys derived using the process described above. It also requires significant computing power and therfore RSA encryption is generally available only to large corporations/establishments.

 

A Final Word

While the RSA algorithm seems inherently secure,it is conceivable that some method for rapid prime number factoring will be discovered that will make the process a lot simpler than the iterative techniques that we currently use. It is also conceivable that sometime in the future with further increases in computing speed, the speeds at which prime numbers are factored will come down dramtically.