Surveillance: How encryption works

Privacy advocates claim the government's plans to monitor email using real-time decryption are unrealistic and illustrate the government's backwardness in understanding the issue.

At the heart of the debate is encryption technology. How does encryption work and why is it so important for our personal privacy? Will Knight provides insight.

What it is...

"Encrypted" information, in its simplest terms, is data made unintelligible by garbling it using a mathematical mixing process controlled by a special "key". Decryption reverses this action and makes the information readable again. This is easy to achieve if the key is available.

Without the key, accessing the encrypted information is extremely difficult in principle, and often impossible in practice.

For the last 50 years encryption has been largely used by governments to hide military and diplomatic information but it is now increasingly being used commercially for things such as cash machines, pay TV and even wireless burglar alarms.

What controversy?

The controversy surrounding access to encrypted data is rooted in the way in which two American academics, Whitfield Diffie and Martin Hellman, revolutionised encrypted communication in 1976 by inventing the concept of "public" and "private" keys (it is now known that the same ideas were discovered even earlier by GCHQ scientists but for reasons of national security were kept secret).

Public and private keys

A "key" in this context is a piece of data used to either encrypt or decrypt a piece of data or message.

In conventional encryption the same "secret key" is used for both encryption and decryption and is kept secret between the sender and recipient of a message. For secret information to pass between the sender and the recipient these keys must be available to both. If they are not, the information cannot be accessed.

Diffie and Hellman discovered that it is possible to have a pair of keys rather than a single key, so that when one key of a pair is used to garble information the other is needed to recover it. This means that knowing the encryption, or "public", key does not necessarily allow messages to be decrypted, since this requires the second pair. As a result, anyone who wants to receive encrypted messages can publish their public key with their name attached and invite others to use it to send them encrypted messages. They then use the other key of the pair -- which is kept secret -- to decrypt the messages.

The trick here is to find mathematical problems of sufficient complexity to ensure it would take an inordinate amount of time -- not to mention effort -- to use the public key to figure out the private one.

The first method for doing this was developed by the inventors of the RSA standard for public key cryptography, Rivest, Shamir and Adleman in 1979. These bright sparks suggested it should be possible to obtain key pairs by multiplying two very large secret prime numbers -- an easy task. But the opposite task, finding the two secret prime numbers from the result, is enormously difficult and can be made impractical by choosing sufficiently large numbers to start with.

There have since been developed a number of different mathematical problems used to link the public and private key, but the essential factor is the length of time it takes for them to be solved.

What's a "bit"?

Keys are often described in terms of "bits", for example, "40 bit keys".

Here the number of bits measures how difficult it is to recover encrypted information without requiring the private key.

In "secret key" encryption every bit added doubles, on average, the time taken to break a piece of encrypted information ("breaking" is a term used to describe recovering encrypted information without having the decryption key). With public key encryption -- using key pairs -- the difficulty also grows as the length of keys increases but in a different way.

So, the length of keys in bits is a broad measure of the complexity of the mathematical problem to be solved in order to break an encrypted message. The public and private keys of key pairs, for example, have to be much longer than the keys in secret key encryption.

It is important to realise, however, that even with modern computers it takes considerable computing power and time to break even the "40-bit" encryption currently permitted for unrestricted export from the US for public use.

In Part 2, an explanation of the National Criminal Intelligence Service's decryption goals.

Take me to Surveillance.

What do you think? Tell the Mailroom.