Modern Cryptography -- Methods and Uses
Created | Updated Jan 8, 2004
cryp·tog'·ra·phy n.
The process or skill of communicating in or deciphering secret writings or ciphers.1
So says the American Heritage Dictionary of the English Language. But cryptography, or crypto, goes beyond communicating in "secret writings or ciphers".
Most importantly, cryptography entails security. Crypto allows you to make sure your credit card numbers aren't stolen, no one knows your password and that the recipient of a message knows, indisputably, that you sent it. Cryptography is the encryption and decryption of information that you want to keep secure.
Who uses cryptography?
Governments. Spies. Banks. Credit card companies. You, if you've ever bought anything online.
But do you realise you're using cryptography? That little lock in the bottom corner of your web browser shows that you're browsing on a secure site -- you're using a form of cryptography called "single-key cryptography". Historically, it's the most common form.
Unfortunately, crypto suffers the stigma that only people with something to hide use crypto.
Why use cryptography?
Because you value your privacy; it's really that simple. Governments don't want classified information out. Banks and credit card companies are interested in your privacy, so they make sure your sensitive information is kept secret. You want to use e-mail like regular mail, not like shouting across a crowded room.
A Brief History Of Cryptography
Caeser's Alphabet
The most widely-known form of cryptography is Caeser's Alphabet. It's a very simple substitution cipher -- a letter shift. Every letter in the alphabet is shifted a certain number of letters to the left. The most common key is 3. Here is the alphabet as we know it, followed by Caeser's "encrypted" alphabet:
ABCDEFGHIJKLMNOPQRSTUVWXYZ
DEFGHIJKLMNOPQRSTUVWXYZABC
Pretty simple, no? As such, the "cleartext" of "THIS IS AN ENCRYPTED MESSAGE" would become the "ciphertext" of "WKLV LV DQ HQFUBSWHG PHVVDJH".
Can this be a secure cryptosystem? It depends on who you're trying to secure it from. Governments? Not at all. Other people? Not really. Caeser's Alphabet is a very basic substitution cipher, and many people break substitution ciphers as a hobby, in the form of "cryptograms".
Enigma2
Quite a jump -- from ancient Rome to World War II. Enigma was the revolutionary cryptosystem developed by the German navy in order to pass secret messages without the pesky Allies getting the messages and interfering with the plans. The system was primarily mechanical and was a stream cipher -- every point in the message affected every later point.
Enigma used a series of electrically connective wheels to exchange one letter into another multiple times. Most Enigma machines had spaces for three wheels, although later incarnations used four wheels to confound the Allied cryptanalysts. These wheels were chosen out of only a few possible wheels. The standard Enigma machine came with five possible wheels. The German Army and Air Force used a standard wheel set, while the Navy used a set of eight wheels.
When the user pressed a key on an Enigma machine's keyboard, the following changes occurred:
1. The rightmost wheel moved forward one position. This achieved Enigma's stream-based property.
2. The keypress went (if necessary) through the plugboard. Each letter could be exchanged with another letter with the plugboard. The plugboard itself was reciprocal -- If A changed to F, then F changed to A.
3. Next, the current entered the first wheel. Each wheel randomly connected each input letter to a different output letter. The wheels themselves were not reciprocal, adding a decent degree of security to the system.
4. The current then passed through the next two wheels in the same fashion as the first wheel.
5. The current then entered the "reflector" This wheel returned the current back through the path it originally took (through each wheel and the plugboard in reverse order), but through a different input letter. The reflector added multiple layers of difficulty to cryptanalysis (if, of course, the cryptanalyst did not have an Enigma machine).
6. The current then lit up the appropriate light on the machine's display. This displayed the letter to be written down and transmitted.
Enigma itself was a reciprocal cryptosystem -- provided that the machine had been reset, all one needed to do to decrypt a message was to enter the ciphertext into the keyboard, and the cleartext would be output on the display.
DES -- The Data Encryption Standard3
DES' history is long and convoluted, but successfully brought cryptography out of strictly governmental use and into the commercial market. Originally known as Lucifer and developed at IBM, DES was IBM's attempt to form a virtual monopoly in the digital world. If IBM could introduce cryptography to the consumer, then everyone would use their solution. IBM's first customer would be the various banks, with the revised, all-hardware version of Lucifer known as DSD-1.
Unfortunately, the National Security Agency (otherwise known as No Such Agency -- the NSA) decided that commercial cryptography could be detrimental to national security and informed IBM that DSD-1 would require the NSA's stamp of approval before it could be shipped worldwide. IBM consented and submitted DSD-1 for approval.
Cracking DSD-1 proved to be a harder task for the NSA than originally expected. An attack upon ciphertext known as a "T attack", which would attempt to force open the ciphertext and reveal the key by attempting various mathematical formulae, proved useless -- IBM had somehow discovered this previously-classified method and redesigned Lucifer, taking this particular attack into account. The NSA forced IBM to classify all information regarding DSD-1 and Lucifer.
The NSA did have one idea for DSD-1 that would make IBM balk -- the key length itself. The original specification for Lucifer involved a 128-bit key. That might seem paltry, but consider this -- 128 bits means that for each of those 128 positions, there are two choices. A two-bit key has a "keyspace" of four possible keys. A three-bit key has eight. A key of this length has a monstrously large keyspace -- approximately 3.4x1038 (a mind-bendingly large number) possible keys. Assuming a computer could try a billion different keys in a single second, it would still take over ten quintillion millennia to try the entire keyspace. A key length of 128 bits, assuming the cryptosystem is only vulnerable to such an attack (known as a "brute force" attack) would be virtually unbreakable using modern computers. NSA insisted that the key length be reduced to only 56 bits. A 56-bit key may be just under half as long, but it is orders of magnitude simpler to force open (A key requiring half the time to brute force would be 127 bits long). This recommended key would take the same computer just over only two years to break. The NSA, of course, even at the time that DSD-1 was under development (circa 1974), must have had supercomputers significantly more powerful than this, in order to be comfortable with a keyspace of 56 bits.
IBM relented on the key length, and DSD-1 became DES. The NSA controlled the export of DES beyond the US borders, but it became enormously popular with the country. DES did just what IBM had hoped -- it introduced cryptography to the consumer.
Modern Cryptosystems
Since the development and publication of DES, cryptography has become enormously popular. Numerous cryptosystems (or algorithms, as they are better known today) have been developed for various purposes. Generally, they all benefit cryptography and privacy in one way or another.
Types of ciphers
Substitution Ciphers
Substitution ciphers are the most simple, because they switch one letter for another, throughout the length of a message. They are easily broken by analysing the frequency of letters in the ciphertext and applying the most commonly-used letters in the appropriate places.
Reciprocal Ciphers
Reciprocal ciphers encompass more cryptosystems, and can make a system either less secure or more usable. A reciprocal cipher means, just as one enters the cleartext into the cryptosystem to get the ciphertext, one could enter the ciphertext into the same place in the system to get the cleartext. Using a reciprocal substitution is a form of cryptographic suicide -- it makes the cipher half as difficult to break. However, if Enigma weren't reciprocal, it would have been significantly more difficult to implement.
Symmetric Ciphers
For a long time, symmetric ciphers were the only form of cryptography available. A symmetric cipher uses the same key for encryption and decryption. Generally, symmetric ciphers are no less secure than asymmetric ciphers, since, in most modern cryptosystems, securing the key is more important than securing the cryptosystem itself.
Asymmetric Ciphers4
An asymmetric cipher is another name for a "split-key" algorithm. Very few split-key algorithms exist in the world of cryptography. The concept of split-key cryptography emerged in 1975. It revolutionised cryptography, as not only could the recipient of a message know that only he could read the contents, but that the message also could have come only from the sender. Each key, however has a dual purpose.
The Keys
The public and private keys have a very special property -- they are complementary of each other. In order the reverse the effects of one key, the other must be applied to the ciphertext.
The Public Key - The public key is, well, public. It is distributed to anyone and everyone. Anyone is allowed to see a person's public key.
The Private Key - The private key, similar to the public key, is private. It is not distributed at all.
How They're Used
Securing message data - The sender (Alice) of the message has the recipient's (Bob) public key. Alice then applies that public key to the message and sends it on its way. Whoever receives the message will get only garble. Bob, however, has his own private key. He applies this private key to the ciphertext and voila! the cleartext appears.
Signing a message - Suppose that isn't enough. Suppose Alice wants the Bob to be absolutely sure that the message was sent by her. Merely writing "Love, Alice" at the bottom of the message isn't good enough; anyone could write that. How will she guarantee that Bob will know that she wrote it? By applying her own private key to the message. Anyone that has her public key will be able to verify that Alice wrote the message. Now, Bob can rest assured that Alice wrote the message, because it's been encrypted with her private key. He also knows that only he can read the message, because it's also been encrypted with his own public key.
Popular Titles in Cryptography
SSL5
SSL isn't a revolutionary cryptosystem. It's actually a means of implementing cryptography into a web browser. SSL stands for Secure Sockets Layer and it's absolutely crucial for e-commerce.
The operation of SSL lies somewhere between simple and complicated. It relies on an asymmetric cipher to assure that the server computer in question belongs to the company it claims it does and a symmetric cipher to proceed with encrypted communication.
1. The client (your) computer sends a bunch of data to the server. This includes the version of SSL your browser uses (we're up to version 3.0), some cipher settings (what algorithms the browser understand), some random data and various other tidbits of information necessary for the session.
2. The server (their) computer sends back a bunch of data. It's pretty much the same kind of stuff, but it also includes the server's Authentication Certificate. If the people running the server have decided that they'd like the client's certificate, the server asks for that.
3. The client makes sure that the server's certificate is valid. This is a weird, complicated process, but it basically involves making sure that the client trusts the company who has said that the server is what it says it is. If this can't be done, the browser warns the user and abandons all hope of establishing secure communication.
4. The client creates a "premaster secret" based on everything that has been transmitted so far. It then encrypts the premaster with the server's public key (it came with the certificate) and sends it off. If the server wants the client's certificate, it signs this data first and sends its own certificate along for the ride.
5. If the server wanted the client's certificate, it authenticates the client. If this can't be done, the server stops trying to secure the transmission. If it works, the server generates the "master secret" from the premaster (after having applied its private key to the premaster). The client has performed the same operation. Now both computers have the same master secret.
6. That master secret is used to generate the "session keys". These keys are only good once, because they're based on information decided at the beginning of the session. They're symmetric and used not only to encrypt and decrypt data, but also to verify that the data hasn't been changed during transmission.
7. The client sends a message to the server saying that all future transmissions will use the session key and that it's done with this "handshake". The server sends a similar message.
At this point, all the information sent between the client and the server can only be read by those two machines. Credit card numbers, passwords, you name it -- it can't be read by eavesdroppers.
PGP
PGP (otherwise known as "Pretty Good Privacy"), like SSL, isn't a cryptographic algorithm in and of itself, but a wrapper around cryptography. Phil Zimmermann began developing the PGP software in the mid-eighties in a political attack against the anti-crypto movements of the government.6
PGP implements a number of asymmetric and symmetric algorithms in order to safely and securely encrypt and decrypt your email, depending on the contents of your certificate. This certificate includes your public key and your preferred symmetric algorithm. PGP uses any one of CAST, IDEA and TripleDES (DES applied three times) to encrypt the message (Recent versions seem to prefer CAST and TripleDES over IDEA as the former two are patent-free). The software encrypts using the following steps:
1. The message is compressed. This is done as a safeguard against potential flaws in the encryption algorithm.
2. A session key is randomly generated, using keystrokes and mouse movements as its basis.
3. The compressed message is then encrypted using the recipient's choice of the three previously-mentioned algorithms. All three are symmetric algorithms.
4. The session key is encrypted using the recipient's public key. Now, only the recipient can decrypt the message.
PGP is quite simple in theory. The actual algorithms used are what made this software package difficult to write. Decryption operates in the opposite direction -- the session key is decrypted with the recipient's private key, then the compressed message is decrypted using the appropriate algorithm, then PGP decompresses the message.7
Conclusion
The benefits of using cryptography should be relatively obvious -- your private messages are kept private and you can be quite sure that your mail has been sent by the person who claims to have sent it. Privacy and peace of mind, plain and simple.
Of course, communication isn't the only thing crypto can be used for. A controversial concept called "digital rights management" can benefit from digital signatures -- record companies could digitally sign songs that they don't mind being distributed and if a piece of music without the appropriate signature arrives on a person's hard drive, their music software could refuse to play it. As well, these digital signatures could be used to sign important documents in Adobe's Portable Document Format (also known as PDF). This could greatly speed up various legal or bureaucratic situations.
Cryptography, therefore, it could be argued, is a necessity in today's "digital age". Governments may complain that, with widespread use of cryptography, national security will be threatened. On the other hand, what good is national security if the population has to give up their personal security? The Bush administration has taken pains to promote national security at the expense of personal privacy. This defeats the efforts that numerous mathematicians and programmers have taken to promote peace of mind in the coming era -- and could make e-commerce, among many other behaviours on the internet, just as dangerous as it was only five years ago.
Explore cryptography today!
Glossary
algorithm – a plan for the manipulation of data within a computerasymmetric cipher – a cipher that requires one key to encrypt and another to decrypt
bit – a single unit of data storage in a computer. Has an "on" or "off" state.
brute force attack – an attack on a cryptosystem that attempts to determine the key used for encryption by attempting to decrypt the message using every possible key
cipher – a particular cryptosystem
ciphertext – the output generated by encryption
cleartext – a readable message. Also called plaintext.
cryptanalysis – the analysis of ciphertext in an attempt to determine the cleartext
cryptanalyst – one who performs cryptanalysis
cryptogram – a puzzle wherein a hidden message is encoded using a basic substitution cipher
cryptography – the process or skill of communicating in or deciphering secret writings or ciphers
decipher – see decrypt
decrypt – to apply a known key to ciphertext in order to retrieve the cleartext
DES – The Data Encryption Standard. Developed by IBM with the NSA in the mid-seventies.
e-commerce – commerce done over the internet
encrypt – to apply a known key to a message in order to turn the message into ciphertext
Enigma – a type of electromechanical cryptographic machine developed and used by the German military in the Second World War
keyspace – all possible keys for a particular cryptosystem. Typically measured in bit length.
Lucifer – the original, internal name of DES
National Security Agency (NSA) – the U.S. governmental body involving cryptanalysis and cryptography
PDF – Portable Document Format. Adobe Systems, Inc.’s multi-platform, versatile file format.
PGP – Pretty Good Privacy. Software program for using cryptography within e-mail.
reciprocal cipher – a substitution cipher wherein each ciphertext letter’s cleartext letter reverses – if a ciphertext "A" becomes a cleartext "F", a ciphertext "F" becomes a cleartext "A"
substitution cipher – a simple cipher that replaces each instance of a particular cleartext letter with a matching ciphertext letter – all cleartext "A"s would become ciphertext "F"s
symmetric cipher – a cipher that uses the same key for encryption and decryption
1"Cryptography". The American Heritage Dictionary of the English Language. Fourth Edition. 16 May 2001. Reference.com. 23 January 2003. <http://dictionary.reference.com/search?q=cryptography>2Hamer, David. "Enigma". 20 January 2003. <http://www.eclipse.net/~dhamer/Enigma1.htm>3Levy, Steven. "The Standard". Crypto -- How the Code Rebels Beat the Government--Saving Privacy in the Digital Age. Penguin: Toronto, 2001.4Levy, Steven. "Public Key". Crypto -- How the Code Rebels Beat the Government--Saving Privacy in the Digital Age. Penguin: Toronto, 2001.5Netscape Communications Corporation. "Introduction to SSL". 23 January 2003. <http://developer.netscape.com/docs/manuals/security/sslin/contents.htm>6Levy, Steven. "Crypto Anarchy". Crypto -- How the Code Rebels Beat the Government - Saving Privacy in the Digital Age. Penguin: Toronto, 2001.7An Introduction to Cryptography. The PGPi Project. 23 January 2003. <ftp://ftp.pgpi.org/pub/pgp/6.5/docs/english/IntroToCrypto.pdf>
