Asymmetric Ciphers

1 Conversation

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)1 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.

1The US Government has a similar organisation called the National Security Agency (NSA)

Bookmark on your Personal Space


Conversations About This Entry

Title
Latest Post

Entry

A612280

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry


Written and Edited by

Disclaimer

h2g2 is created by h2g2's users, who are members of the public. The views expressed are theirs and unless specifically stated are not those of the Not Panicking Ltd. Unlike Edited Entries, Entries have not been checked by an Editor. If you consider any Entry to be in breach of the site's House Rules, please register a complaint. For any other comments, please visit the Feedback page.

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more