Cryptography isn't just for spies anymore - it's absolutely everywhere around us. Every time we use an ATM or buy something online we are sending data that we hope isn't intercepted on its way, because that would mean our finances were at risk. Additionally, corporations and the government have an interest in securing communications within their organizations and with other companies or governments so that information doesn't fall into the wrong hands.

How do these large organizations keep malicious people (commonly called "adversaries" in cryptology circles) from intercepting and reading their messages?

Ever since there have been leaders of the world, there have been ways of hiding communications between people. The Romans used primitive forms of encryption called alphabet substitutions (which can usually be found in a Sunday newspaper) where one letter was substituted with another based on a pre-defined key. Anybody in possession of the key could easily decipher the message - however, with a quick analysis of the letter frequency and a little ingenuity, an intercepting party could also decipher the message using some educated guesses: for instance, if the letter "X" appeared most frequently in the cipher (the encoded message), one could reasonably assume that "X" stood for "E" if the message was originally in English.

There are, of course, more complicated ways to do alphabet substitution, some involving techniques like using parts of the original message as the key, but overall they are fairly easily crackable with modern computing power and are therefore not used often.


Mystery Machine: The Nazi's Enigma Machine encoded messages that the Allies eventually decoded, thankfully. Photo Credit: University of Arizona

There is, however, a method of encryption that is genuinely bulletproof. Entitled the "one-time pad" method, it can completely garble a message so that only someone in possession of the key can decode it provided that the key matches certain criteria. Say you have a message encoded in binary, so that the only contents of the message are zeros and ones. Then you randomly generate a key (also in binary) that is exactly the length of the message you want to transmit. Using a 1-to-1 method, you then perform a bitwise XOR operation between the message and the key, generating the encoded message. If the key is truly random and at least as long as the message, then the encoded message will be truly unbreakable. Any person in possession of the key (which was commonly used one time, hence the name) would be able to decode it. Unfortunately, this method is not commonly used today because of the large amounts of key data that must be generated and shared between parties before any messages are even sent.

The one-time pad method of encryption displays a major problem with cryptography: symmetric cryptography, or what's commonly thought of when people imagine codes and ciphers, requires that both the sender and receiver of the message be in possession of the decoding key before the message is sent. Since any person in possession of the key and the encoded message can decode it, the two legitimate parties need to first have a secure channel over which to transmit the key before they can transmit the message - something of a catch-22. There's an additional problem: for each person in the organization to communicate securely with each other person, they each need a unique key for every person. This leads to a huge problem in key distribution that grows exponentially as the number of participants rises. One major standard, the Data Encryption Standard (DES), uses a symmetric encryption process. DES is used in ATM's as well as to encrypt data on hard drives and is well-vetted as a secure method for protecting data. Breaking DES requires searching the entire key space - 2⁵⁶ possible solutions - and using each to attempt to decode the message.

It wasn't until 1978 that the solution to the key-distribution problem was found. Ronald Rivest, Adi Shamir, and Leonard Adleman developed a system called the RSA method that uses public as well as private keys to protect data. The RSA method only requires twice as many keys as people, allowing for large-scale deployment. This is how the RSA method works: every person has a public key as well as a private key. When Person 1 wants to send a message to Person 2, Person 1 writes the message and uses Person 2's publicly available key to encode it. Now, only Person 2's private key will be able to decode it. After encoding, not even Person 1 can decode the message without Person 2's private key.

Each member's private key is dependent on his or her public key, but only through a certain type of mathematical function. Oyono, Esslinger, and Schneider describe this as a "trap-door" type function - one that's easy to compute going one direction but difficult in another. For instance, the multiplication of two large prime numbers is easy computationally but the factoring of a large number into two primes is exceedingly difficult. Although this isn't exactly how keys are generated in RSA, multiplication of primes does provide the basis for the algorithm. Another equally one-way function uses logarithms.

Keys generated using RSA are not completely unbreakable - given enough time, a computer will eventually be able to factor a large number into the appropriate primes to decode the message. However, the numbers involved are sufficiently large that the time required to perform the amount of computer cycles needed would far exceed the amount of time anybody actually has to decode the message. In the encryption industry, this is considered secure. Increases in computer power shouldn't harm RSA encryption either - according to the RSA Labs website, increases in computing power will make the encryption more secure: an equivalent increase in computing power will allow an adversary to factor a number two digits longer while the key generator will be able to create a key 12 digits longer.

On the horizon, of course, is the buzzword-leaden field of quantum cryptography, which poses such possibilities as being able to tell definitively whether a message has been intercepted (useful in key transmission - if you know your key is secure, you can use symmetric encryption and truly randomize your message). Without a true working quantum computer, however, such solutions still lie in the future.

Of course, security is only as good as the weakest link. The best encryption in the world won't stop people from giving their bank passwords to phishers. But at least the real integrity of our data is something we probably won't have to worry about any time soon.

---
RSA Labs - Check out the "Historical" section for more in-depth info
Ronald Rivest, Adi Shamir, and Leonard Adleman's Original Paper
CrypTool Script Section 5 - The Mathematical Ideas behind Modern Cryptography. Oyono R. / Esslinger B./ Schneider J., Sep. 2000; Updates Nov. 2000, Feb. 2003, Apr. 2007
Also, check out CrypTool for playing with different encryption and decryption schemes