Encryption
by Chris Woodford. Last updated: January 13, 2012.
You've seen a rare book you want to buy online and it costs—wait
for it—$500. It's on an online auction so you have to act fast.
Fortunately, you bid in time to win and the book is yours. Happy with
your success, you type in your credit card details to pay, without
even thinking about it. Thanks to the wonders of e-commerce, one of
the most valuable pieces of information you own (effectively the key
to your entire bank account) whistles across the ether through
merchants and banks and the seller receives your payment a few
seconds later. Would you dream of sending $500 in cash this way? Passing it
from person to person, through a long chain of people you've never
met, with a little note attached: "Give this to Joe in Duluth"?
Of course not! And yet you feel totally comfortable doing exactly the
same thing online. The difference is that, when you pay
electronically, your payment information is "scrambled" as it
travels so only you and the person who receives the money (or their
bank) ever get to see it. That's the brilliance of a mathematical
technology called encryption (sometimes also
referred to as cryptography). Let's take a closer look at how it works!
Photo: Military forces have always used encryption to ensure secret communications stay out of
enemy hands. This is some of the complex encryption and radio communication equipment used by US forces in the 1980s.
Today, all of us have encryption at our fingertips. Photo by Vincent Kitts courtesy of Defense Imagery.
What is encryption used for?
Encryption is another word for "coding," so when we talk about
encrypting something we really just mean turning it into an
indecipherable message using a secret code. We all like playing spies
when we're kids, but why would we want to do that as adults? These
days, the main reason is that we share so much information online. By
its very nature, the Internet is a public
medium. Every time you send an email or browse a Web page, the
information your computer sends
and receives has to pass through maybe a dozen or more other machines
on its way to and from its ultimate destination. At every stage, that
information could be intercepted by crooks or others of dubious
intent. Encrypting information keeps it safe just long enough to make
the journey. There's another reason you might want to use
encryption: proving information really comes from you. Anyone can
send an email pretending to be from someone else; you can use
encryption to digitally "sign" your messages and verify your
identity.
Photo: This cellphone is having an encryption chip installed in it to ensure secure communications. The chip uses a type of encryption called AES (Advanced Encryption Standard). Photo by Andrew Rodier courtesy of US Air Force and Defense Imagery.
How does secret-key cryptography work?
All codes are a bit like padlocks. You "lock" your message,
the message travels to its destination, and then the recipient
"unlocks" it and reads it. But not all codes work the same way.
Secret agents in spy movies use a
method called secret-key cryptography.
Suppose you're an agent working in Washington, DC and you need to send a message to another
agent in Rome, Italy. The best way to do it is for the two of you to
meet up in advance, in person, and agree on a method of locking and
unlocking all the messages you'll send and receive in future. This
method is called a secret key, because only
the two of you will have access to it. The secret key could be something like
"Replace every letter in the message with another letter three
further on in the alphabet." So, to send the message "HELLO" to
your contact in Rome, you simply move each letter three forward,
which gives you "KHOOR." When the person at the other end gets
the message, he simply has to move each letter back three positions
in the alphabet to find out what you're really saying. In this case, the key
isn't a piece of metal you poke in a lock: it's the method of
cracking the code by shifting the letters. Real secret
keys are obviously much more complex and sophisticated than this.
This way of securing information is also called PSK (pre-shared key) and in some circumstances it's very effective.
It's widely used to secure wireless
Internet networks, for example.
When you set up a secure wireless network, you're asked to choose a
secret key (effectively, a password) that's known to both your
wireless router (your main local access point to the Internet) and to
any portable computers that need to use it. When you're using
wireless Internet, you may notice that your connection is encrypted
with something called WPA-PSK (Wi-Fi Protected Access-Pre-Shared
Key). If you try to log onto a new wireless network and you're asked
for a password, what you're really supplying is a secret key that
will be used to encrypt and decrypt all the messages that pass back
and forth.
Photo: You don't need a padlock to secure information:
you can do it with encryption.
Although secret (pre-shared) keys are effective and secure for
things like this, they're not at all useful in other situations—like
sending secure messages to people you've never met. That's because
they rely on your knowing and meeting the person you're communicating
with in advance to exchange the secret key. What if you can't do
that? What if you want to exchange secure information with someone
you've never met—someone who could be on the opposite side of the
world? That's exactly the problem you have when you're paying for
things online.
How does public-key encryption work?
In that case, you can use a different system called public-key cryptography, which is how online encryption works. The basic
idea is simple. Each person has two keys, one called a public key
and one called a secret key. Each "key" is
actually a long, meaningless string of numbers—nothing like a metal key you'd
use to open and close a door lock. The
public key is something you can
share with anyone, while the secret key is something you must
keep private. Suppose you want to send a message to a friend using
public key cryptography. You use their public key (which they've
freely shared with the world) to encrypt the message and turn it into
gibberish. You email the scrambled message to them over the Internet
and when they receive it they use their secret key to decrypt
(unscramble) and read it. That then is the essence of public-key
cryptography: anyone can encrypt a message and send it to you (using
your public key), but only you can read it (using your secret key).
How to send a message with public-key encryption
Suppose Annie wants to send a secure message to Bob, whom she's never met.
Here's how they can do it with public-key encryption.
1. Generate keys
First, each of them has to generate public and secret (private) keys with their computer. They need to do this only once. After they've generated a public and secret key pair, they can use it to communicate with any number of different people.
2. Swap public keys
Next they swap their public keys. They keep their secret keys to themselves and never share them with anyone else. They can send their public keys to whoever they wish—it's okay even to publish your public key on your website or attach it to your emails.
3. Exchange messages
To send Bob a message, Annie uses Bob's public key to encrypt her words. The encrypted message is complete gibberish and it doesn't matter who sees it. When Bob receives the message, he uses his secret key to decrypt it (turn it back into a message he can read). If he wants to reply securely to Annie, he simply runs the process in reverse: he uses Annie's public key to encrypt his message and she uses her secret key to decrypt it.
4. Digitally signing messages
Bob and Annie can also use their keys to prove messages they send really come from them by adding what's called a digital signature. Bob can add a digital signature to his emails using his secret key. When Annie receives a signed message from someone claiming to be Bob, she can use his public key to prove that the message really did come from him.
What's the trick?
It sounds like a trick! How can anyone encrypt a message but only
you can decrypt it? Surely if one person can encrypt a message using
a publicly available key, other people can decrypt it too using the
same key? Not so! The answer lies in the two different keys and in
the fact that some mathematical processes are much harder to do one
way than the other.
Consider the two prime numbers 7901 and 7919
(prime numbers are ones that you can divide by no other numbers than
one and themselves). Suppose you multiply them together to get
62568019. That's a pretty simple operation anyone can do in two
seconds flat with a calculator. But what if I give you the number
62568019 and tell you to figure out the two numbers I multiplied
together to make that number. You'd be there all day!
What if encrypting a message were as easy as multiplying two prime numbers
but decrypting were as hard as figuring out what those numbers were?
That's the basic idea behind public-key cryptography. When you secure
a message with someone's public key, your computer performs an easy
mathematical operation anyone could do. But once the message is
encrypted, figuring out what information it contains is a very tough
mathematical operation that would take you days, weeks, or months to
complete (unless you happen to know the secret key).
You'll see from this that there is a basic flaw in public-key
encryption. Given enough time and computing power, you could always
figure out the secret key from the public key and decrypt the
message. That's why public-key encryption relies on keys that are
really big. The keys my computer uses, for example, are made
up of 1024 bits (binary digits): a string of 1024 zeros or ones in a
long line. The longer the keys you use (that is, the more bits they
have), the tougher the encryption and the more secure your message
will be. Secure Web pages typically use 128-bit or 256-bit encryption
when they travel to and from your browser carrying banking
information.
Types of public-key encryption
There are various different types of public-key encryption that
you'll come across. The original idea was invented in the mid-1970s
by two Stanford University mathematicians named Whitfield Diffie and
Martin Hellman and systems that use their particular mathematical
coding method (which is known as an algorithm)
are usually called DH (Diffie-Hellman). Others include RSA (named for Ron Rivest,
Adi Shamir, and Leonard Adleman), Elgamal (named for Taher Elgamal),
Data Encryption Standard (DES) and Triple-DES, and the successor to DES, known as Advanced Encryption Standard (AES) or Rijndael.
Web browsers and servers use encryption methods called SSL (Secure Sockets Layer) and
TLS (Transport Layer Security), themselves based on algorithms such
as RSA and DH, to protect information traveling back and forth over
the Net. Some email programs have built-in encryption to make it easy
to send and receive secure messages; there's also a popular web-based
email system called Hushmail that has encryption built-in as standard.
Many PCs use a widely available encryption program named PGP (Pretty Good Privacy) developed by American software engineer Philip Zimmermann in 1991 (Linux equivalents of PGP include KGPG and GnuPG).
Will quantum computers make encryption impossible?
There's a huge amount of interest in quantum computers that use
atoms (or subatomic particles such as electrons) to carry out similar tasks to conventional computers but at far higher speed, in parallel. As we've just seen, the effectiveness of public-key encryption rests on the difficulty of figuring out factors of large numbers; even by brute force trial-and-error, conventional computers take far too long to solve essentially "intractable" problems such as this. But a quantum computer using parallel processing could potentially decrypt information encrypted in this way in the blink of an eye, rendering conventional public-key encryption useless. Goodbye secure online transactions!
Fortunately, this frightening possibility has an equally tantalizing solution: using quantum-mechanical
methods to make codes that are theoretically uncrackable. The basic idea is that two people, Annie and Bob, use the inherent unpredictability of quantum states to generate and share a key securely (a technique known as
quantum key distribution (QKD), which they then use to securely encrypt and decrypt the messages they exchange. Unlike in public-key cryptography, where the key is public but essentially useless, this is an example of a pre-shared key (PSK) system where the actual key remains secret from third parties. With QKD, it's also possible to detect any attempt by a third party to eavesdrop and discover the key, which would change it in a noticeable way (because eavesdropping would be equivalent to "measuring" the key and, according to the laws of quantum mechanics, you can't measure something like this without altering it in some way).
Further reading
On this website
On other sites
- How PGP works: A good, clear introduction to cryptography and the widely available PGP public cryptography tool.
- Philip Zimmermann: Website of the PGP creator, with lots of useful background about PGP.
- OpenPGP Alliance: Responsible for OpenPGP, an open world standard based on PGP.
- GNU Privacy Guard (GnuPG): The GNU project's free implementation of OpenPGP, available for various operating systems.
Books
General
- Computer Security Basics by Rick Lehtinen, Deborah Russell, and G. T. Gangemi. O'Reilly, 2006. A good overview of computer security for people like IT managers (who need to know the general concepts rather than the extreme nitty gritty of implementation).
- Cryptography Demystified by John E. Hershey. McGraw-Hill Professional, 2003. A more thoughtful introduction that will appeal to math geeks who want to understand exactly how encryption works.
- Cryptography for Dummies by Chey Cobb. Dummies, 2004. A simple introduction focused on public key encryption and how to use it for things like protecting files, ecommerce, and VPN (virtual private network) encryption.
- A Shortcut Through Time: The Path to the Quantum Computer by George Johnson. Random House, 2004. A reasonably simple introduction to quantum computing. Chapter 6 covers how quantum computers might be used to decrypt codes, while chapter 9 looks at quantum key distribution.
PGP
- The Official PGP User's Guide by Philip R. Zimmermann. DIANE Publishing Company, 1999. An introduction to PGP by its inventor.
- PGP: Pretty Good Privacy by Simson Garfinkel. O'Reilly, 1995. A good introduction to PGP and its history, plus a lot of stuff about Internet privacy (a topic for which Garfinkel is best known), but somewhat dated now.
Articles
