After the warm reception of the free SQL Encryption Toolkit, a few folks e-mailed me asking for more information on cryptography in general. I skipped a lot of the background information in the previous article in order to focus on the use of the tools. In this article, I intend to follow up with the basics of cryptography for those who want to know more about the subject.
What Is Cryptography?
Cryptography is the science of "obscuring information to make it unreadable without special knowledge." The "special knowledge" is the key and the algorithm used to decrypt information. The main objective of cryptography is to make your information as obscure as possible so that the only parties who can read the encrypted information are the sender and receiver of said information.
Cryptanalysis is the science of analyzing and defeating cryptographic methods, algorithms and techniques; i.e., "codebreaking."
An "algorithm" is a process used to encrypt of decrypt our data.
An "encryption key" is a special value that the sender uses to encrypt plain text, and that the receiver uses to decrypt the encrypted text. In digital cryptography, the key length (in bits) is a good indicator of the security of the algorithm.
Codes differ from ciphers in that codes are achieved by replacing entire words or sentences with symbols or words. As an example:
Figure 1. Sample of a Code.
Ciphers, on the other hand, involve substituting individual letters with other letters or groups of letters.
Figure 2. Substitution Cipher Example.
Generally when we speak of digital encryption, we are dealing with ciphers as opposed to codes.
A Slightly Longer History of Cryptography
We'll begin with the history of cryptography, going even further back than the previous article (have to get your money's worth, right?) Back in the day, around the 7th Century B.C.E. to be exact, the Greeks used a system of enciphering messages during military campaigns using a wooden rod and a piece of leather, known together as a scytale. Enciphering a message involved wrapping the leather strap around a wooden pole, writing a message on the leather strap, and unwrapping the leather from the pole. Once the message was delivered, deciphering it involved wrapping the leather strap around a pole of the same size as the one used to encipher the message, and viola!
Caesar was known to have used an encryption method now known as the "Caesar Shift." In this method of encryption, you choose a number and shift all the letters in your plain text by that amount. Owing to the fact that most of Caesar's enemies were largely illiterate with regard to the Latin alphabet, the "Caesar Shift" method of encryption served him well. Due to the simplicity of the method and the high rate of literacy today, it is no longer effective (although it is still used in puzzles and games). The most common method is known as "ROT13" (short for "Rotate 13").
Due to the fact that there are 26 letters in the Modern Latin alphabet, performing a ROT13 encryption on a previously ROT13-encrypted message gives you back your original plain text. An example of an ROT13-encrypted message is the following:
Figure 3. ROT13 Cipher Sample
If you downloaded and installed the SQL Encryption Toolkit, you can run the xp_rot13 extended stored procedure to decipher these messages:
- VS LBH NER BHG GB QRFPEVOR GEHGU, YRNIR RYRTNAPR GB GUR GNVYBE. - N. RVAFGRVA
- ORJNER BS GUR LBHAT QBPGBE NAQ GUR BYQ ONEORE. - O. SENAXYVA
- OR PNERSHY NOBHG ERNQVAT URNYGU OBBXF. LBH ZNL QVR BS N ZVFCEVAG. - Z. GJNVA
- N SNANGVP VF BAR JUB PNA ABG PUNATR UVF ZVAQ NAQ JVYY ABG PUNATR GUR FHOWRPG. - J. PUHEPUVYY
To summarize, here's my quick and dirty list of Cryptography Milestones. Note that this is not an exhaustive list by any means, but it does give a good indicator of some of the major events that added to our current understanding of cryptography.
Figure 4. Cryptography Milestones
The First Codebreaker
Cryptanalysis is the art of codebreaking. The Arab philosopher/scholar al-Kindi is credited with writing the first book on cryptanalysis in the 9th Century C.E. Al-Kindi determined that in Arabic, certain letters appeared in writing more frequently than other letters. Thus a simple substitution cipher (in which letters are simply replaced with other letters) could be broken by determining the frequency of occurrence of the enciphered letters. This works for English as well, where letters occur with different frequency in written communications.
Figure 5. Frequency of Letters in Written English
As Figure 5 shows, the letter "E" occurs far more frequently than any other letter in written English. The letter "Z" occurs least. Not only is this handy for codebreaking simple ciphers, it will also help you develop a winning strategy if you are ever a contestant on Wheel of Fortune.
With this knowledge in hand, it becomes obvious that simply rotating letters around and/or using simple substitution ciphers was no longer secure. Modern cryptographic techniques focus not only on substituting characters for other characters, but also eliminating patterns from the encrypted data. Many cryptanalytical techniques rely on these patterns in encrypted data in order to reverse engineer encryption keys.
You might notice that the milestone list (Figure 4) contains events that involve encoding (i.e., invention of Morse Code, introduction of ASCII, etc.) You might also recall from the last article that encoding involves representing data in a different format without changing the data itself. As an example, 11110000 binary = 240 decimal = 0xF0 hexadecimal. The representation changes, but the underlying data stays the same.
So what do all these encoding milestones have to do with cryptography? Encoding methods can help to obscure our data slightly; but more importantly the events listed were chosen because they demonstrate advancements toward modern digital computer encryption.
Nothing advances cryptographic methods quite like war, and with good reason: People's lives depend on the security of our cryptographic algorithms. During wartime, top secret military orders and diplomatic messages must be transferred securely to Commanders and agents in the field. The enemy is constantly trying to break our codes, and we must constantly try to defeat enemy cryptanalysis. It’s a 'vicious circle' that advances the science by leaps and bounds.
One of the most oft-cited cryptanalysis stories was the cracking of the German "Enigma" code during World War II. During WW II, literally thousands of mathematicians were recruited, first by the Polish resistance and later by the Allies, to crack the German Enigma code. It has been estimated by historians that cracking the Enigma code shortened the war by at least a year.
It was also during WW II that electronic codebreaking computers were first devised and put to use. Since almost the entire body of cryptographic knowledge consisted mostly of highly classified military secrets, the civilian world did not have access to most of this knowledge until the late 1970's and early 1980's.
The introduction of personal computers into homes and businesses in the 1980's and the advent of the Internet and World Wide Web provided the push needed to bring cryptography to the general public. The proliferation of computers and online transactions has fueled demand for advancement in personal privacy.
Modern cryptography depends largely on mathematical functions, binary bit-shifting, bit-level logical operations, and their inverse operations. As an example, the inverse operator of "addition" is "subtraction", "multiplication" is the inverse of "division", etc.
One of the guiding principles of modern cryptography is that everyone has access to your algorithm; so security can never rest in obscuring or hiding the algorithm or the mathematical/logical functions used to manipulate the plain text. Security resides in the key. Generally speaking, the larger the key, the more secure your encryption.
In modern cryptography, an algorithm is considered secure if the only way to defeat it is to use a "brute-force" attack, which involves trying every possible combination of keys to decrypt a message. An "insecure" algorithm is one for which a short-cut to defeat the algorithm is found.
In 1976, the United States adopted IBM's Data Encryption Standard (DES) algorithm to secure government communications. DES uses a 56-bit key, and it was not until the late 1990’s that methods were found that could defeat DES. DES is no longer considered "secure," with some demonstrations of DES codebreaking taking less than 24 hours.
In 2001, the U.S. discontinued use of DES and adopted the Advanced Encryption Standard (AES) as a Federal Information Processing Standard (FIPS). AES is based on the Rijndael (pronounced "Rine-Dale") algorithm submitted by Daemen and Rijmen. AES utilizes a 128-, 192-, or 256-bit key. The AES algorithm has been approved for securing information up to the Top Secret level (192-bit or 256-bit key versions only). AES encryption is included in the SQL Encryption Toolkit.
These two algorithms are known as "symmetric key algorithms," since both the sender and the receiver must know the same key to encrypt and decrypt the message.
Asymmetric Key Algorithm
One of the greatest advances in modern cryptography was the creation of the "asymmetric key algorithm." Asymmetric key algorithms were developed for situations in which transmitting a symmetric key between parties would defeat the security provided by a symmetric encryption algorithm.
Asymmetric key encryption has been applied with great success to online transaction security. The most commonly used algorithm, RSA encryption, utilizes a public-key/private-key pair. You encrypt a message with your public key, and it can be decrypted by the receiver using their private key. Asymmetric key algorithms are based on mathematical problems that are considered extremely difficult, such as factoring the product of very large prime numbers.
Today cryptography is more important and relevant than ever. Legislation has been passed, or is being considered, that requires various levels of encryption in order to maintain compliance (FACTA, FCRA, etc.) Newspaper reports are coming out weekly that personal consumer data maintained by large corporations have been compromised in some form. Cryptography is one of the most important fields in computer science today, and we can expect it to get even more important in the future.
If you are interested in pursuing the subject further, there are several books and websites on the subject. Here are a few used in the creation of this article:
- Schneier, B. Applied Cryptography: Protocols, Algorithms and Souce Code in C
- Pratt, F. Secret and Urgent: The Story of Codes and Ciphers