What is an Asymmetric Cipher?

As ciphers became more secure and more widespread a simple problem started to manifest itself. How do two people who rarely or never meet set up a secure encryption system? The problem is known as the Key Distribution Problem, a term that describes the difficulty perfectly. How can a person get a secret key to another person without the risk of the key being intercepted and used to decrypt any fuure messages between them?

As is sometimes the case, the answer was known before a method of implementing it appeared. The solution was something called an asymmetric cipher. An asymmetric cipher is a simple thing, it is a cipher where two different keys are used, one to encrypt, the other to decrypt. In fact there is another important requirement, one of the keys must be distributable without compromising the other.

So the design of the algorithm looks like this:

• Key A is used to encrypt
• Key B is used to decrypt
• Key B is very difficult to determine if you only know Key A

This is an asymmetric cipher, or to use the common business term, Public Key. The public key is key A and can be distributed freely, key B is kept secret, sometimes called the Private Key.

This solves the key distribution problem because someone can send another person his public key and doesn't care who may intercept it. Any message subsequently encrypted with that public key can only be read by someone who holds the private key.

The only problem is that no known mathematical algorithm existed that would carry out this function, the search was on.

RSA

The first attempts used all sorts of complicated rules, sending multiple keys and permitting one to be broken or encrypting multiple times and specifying complex orders for the decryption. All these were somewhat unsatisfactory, but one man did have a scheme that would work, it worked using some very complex mathematics, and it was elegant.

Clifford Cocks worked at the Government Communications Headquarters (GCHQ)¹ in Cheltenham, England. GCHQ's role is to protect the communications of Britain and her allies and to attempt to undermine the communications security of her enemies. Cocks was fascinated by the problem and he found a way to solve it using modular arithmetic and huge prime numbers, fairly advanced concepts in mathematics. In 1973 he announced to his superiors that he had the solution and yet there was no rejoicing from the cryptographers around the world. Asymmetric encryption existed but it was a closely guarded secret.

In 1977 three mathematicians, Rivest, Shamir and Adleman, published the same algoithm in a mathematics journal, this time it caused a stir because this time everyone could use the technique. From the initials of the authors, the algorithm was patented under the name RSA and immediately people started to find uses for it.

The security of the algorithm lies in quite a simple idea. Any two prime numbers multiplied together will produce a number with only itself, either of the primes and one as factors. The public key contains this large product number and in order to cryptanalyse the message an attacker needs to factor that number, to find the two prime numbers that were multiplied together to produce it. Sounds simple enough, but factoring large numbers is one of the 'difficult' problems in mathematics. The numbers that are used are huge and factoring them would take a very long time indeed.