Encryption - Part1

A Brief History of Encryption Encryption is a way of protecting data against unauthorized use. Several techniques have been used throughout the years to protect data against enemies who would misuse the information. Thousands of years ago, the main use of using encryption was to protect data during war. David Kahn, in his impressive work, The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet, has traced the history of cryptography as far back as ancient Egypt, progressing through India, Mesopotamia, Babylon, World War I, World War II, and into modern times, where encryption has taken on new meaning. The extensive use of telegraph and radio waves in modern times has increased the need to encrypt information because sophisticated techniques are available to intercept the information that flows in today’s global environment. Military communication without the use of encryption is worthless. The biggest achievements in cryptography can be attributed to the work done by Alan Turing during World War II. Using the help of Alan Turing in Britain, the allies were able to use computers to break the Enigma code used by Germany during the war. Since World War II, the National Security Agency (a branch of the Department of Defense) has become the center for cryptographic research and activity. The existence of this highly secret organization within the government was denied until recently and is jokingly referred to as “No Such Agency.” The budget and activities of this agency are highly classified. It has been rumored that the NSA employs the largest number of mathematicians in the world and actively eavesdrops on phone conversations. For years, the use of codes and ciphers was reserved to the NSA and military operations. Civilians had to be content with using envelopes and couriers to protect data. With the computer revolution and the explosion of the information age—and especially the Internet—the need for encryption in civilian use was recognized. The manner in which data was disseminated through electronic mail and the Internet, and the financial value attached to the information, fueled enough research for civilians to use encryption. In the late 1960s, IBM chairman Thomas Watson, Jr set up a cryptographic research group. This group, led by Horst Feistel, developed a private key encryption method called Lucifer, which was used by Lloyd’s of London to protect a cash-dispensing system. The success of Lucifer prompted IBM to make it available for commercial use. The team formed for this purpose was headed by Dr. Walter Tuchman and Dr. Carl Meyer, who tested the cipher and fixed the flaws they found in the method. By 1974, the cipher was ready and available on a silicon chip. However, IBM was not the only company to make ciphers available commercially. Other companies made other codes available, but there were some problems associated with all these ciphers:

• They could not communicate with each other
  
• There was no way to determine their strength
  

Private Key Cryptography
The kind of cryptography used in earlier days and in the code and cipher techniques such as the Caesar Cipher and Vernam Cipher is called private key or secret key cryptography. The term private key is used because this technique implies that both the sender and the receiver of the message have a key that must be kept private. Private key cryptography makes use of the same key on both the sending and the receiving end and is therefore also referred to as symmetric cryptography. Whenever you want to communicate with someone using these methods, you must give the cryptographic key to the person with whom you want to communicate. The process of exchanging the cryptographic key is referred to as key distribution and can be very difficult: The key is the secret to breaking the cipher text; if there exists a really secure method of communicating the key, why isn’t that method used to communicate the message in the first place? For many years, the key distribution method used by the United States government was to place the keys in a locked briefcase, which was handcuffed to a courier. The courier would board an airplane and would be met at the destination country by an official from the U.S. embassy and taken to the embassy. The cuffs would be removed at the embassy, and the keys were then available to decipher diplomatic messages. The courier did not have a way to remove the cuffs or open the briefcase. If the bad guys caught the courier, the diplomats in the United States would know about it and would not use those particular keys to encrypt messages.
Private Key Algorithms
There are several popular private key algorithms. We will briefly describe just a few of them:

• DES: The Data Encryption Standard was adopted by the U.S. government in 1977 and as an ANSI standard in 1981. It makes use of 56-bit keys to encrypt the information.
  
• Triple-DES: This algorithm is a variation of DES; it uses the DES encryption algorithm three times with two different keys. Financial institutions currently use this technique.
  
• RC codes: Rivest codes are named after MIT professor Ronald Rivest who is also the coinventor of the RSA public key encryption algorithm. These methods are proprietary algorithms that are distributed by RSA Data Security. The two most popular codes are RC2 (which is a block cipher method like DES) and RC4 (which is a stream cipher that produces a stream of pseudo-random numbers that are XORed with the information). These codes can be used with keys from 1 to 1,024 bits in length. There is no estimate of how secure these codes really are because they are proprietary.
  
• IDEA: In 1990, James L. Massey and Xuejia Lai developed and published the International Data Encryption Algorithm in Zurich, Switzerland. This technique uses a 128-bit key and seems to be very strong (although the exact nature of the security it provides is not known).
  
• Skipjack: This secret algorithm was developed by the National Security Agency for civilian purposes. It uses an 80-bit key. It is at the heart of the Clipper chip used by law enforcement agencies to perform legal wiretaps. The Clipper chip is not as secure as Skipjack.
  

There are several problems associated with private key encryption:

• As mentioned earlier, the biggest problem with private key encryption is the method of key distribution.
  
• The second problem with private key encryption is the security involved in distributing the key itself.
  

Mechanics of Secret Key Encryption
Most successful secret key encryption techniques use a simple set of functions and procedures to convert the plaintext into cipher text. The concept of block encryption is very commonly used for this purpose; it involves the use of a block or a group of bytes for encryption purposes instead of a single byte or character. Each block can be operated on by any combination of several processes. The final cipher text can be generated by applying the following processes during several iterations or rounds of encryption:

• Substitution techniques: Substitution techniques are very commonly used in encryption algorithms. As we have seen earlier, knowledge of the language and the context of the message give a hacker a lot of information about how to decipher the code. Therefore, block encryption is used instead of bit or character substitution. Security is obtained by having a one-to-one mapping between blocks of characters of plaintext and blocks of cipher text of the same size—but the relationship between them is not easy to figure out. Substitution techniques usually use some simple strategy such as a lookup table or the XOR function.
  
• Permutation: You can rearrange the characters of a plaintext message to convert the message into an anagram that looks like a message with random characters. For example, most messages consist of 7-bit ASCII characters. By scrambling the bits to create a random set of bits, you can get the desired encryption. Permutation techniques are usually used in conjunction with other techniques such as substitution.
  
• Encryption functions: Exclusive OR is an example of an encryption function (as described in the following section). Other functions such as binary addition, multiplication, and modular arithmetic functions are also common.
  

Using Exclusive OR (XOR) to Perform Block Encryption
A very popular method for performing simple encryption is the XOR function. The Exclusive OR function is used to indicate that if there are two conditions (say conditionA and conditionB), then either conditionA is true or conditionB is true—but not both. The complete set of possibilities for two values being XORed and their result is as follows:
Using Substitution Boxes
A popular method of implementing a substitution function is to use a construct referred to as a substitution box, or an S-box. The S-box function takes some bit or set of bits as input and provides some other bit or set of bits as output. It makes use of a replacement table to perform the conversion. These reference tables can map more than one input to the same output. As a result of this truth, a hacker cannot take the output from an S-box and figure out which of the many inputs may have been used to generate the output.
Using Expansion Permutation
The expansion permutation takes a block of data and expands it into a set of overlapping groups; each group may be small compared to the original block. Suppose that we have a block of 24 bits; we can perform expansion permutation to convert it into a block of 36 bits as follows:

1. Break the 24 bits into six groups of four bits each.
   
2. To each group, add the bit that precedes it and the bit that follows it.
   

Now we have six groups with six bits each for a total of 36 bits. The techniques in this and the preceding sections are just some of the commonly used methods in encryption algorithms. You can mix and match them to obtain an encryption algorithm. However, the security of encryption algorithms is not related to the usage of specific techniques or at least a certain number of these methods.
Using Encryption Rounds
Encryption algorithms become more complex and secure at the same time by using different encryption techniques one after the other. However, it is important to use different techniques in different rounds. For example, if you use substitution (or iteration) during the first round of encrypting plaintext, and use substitution again on the cipher text in the second round (even if the substitution characters are different in the two rounds), the resultant cipher text is no more secure than using just one round of substitution. In fact, even if you use a thousand rounds of substitution, the security is the same as using one round because there is always a one-to-one mapping between the plaintext and the final cipher text. A much more secure encryption can be obtained by using one round of substitution followed by a second round of permutation. Popular encryption algorithms make use of 8 or 16 different rounds of encryption techniques.
Public Key Cryptography
Public key cryptography is also referred to as asymmetric cryptography and is the result of a mathematical breakthrough that occurred in 1970. Unlike symmetric key methods that use a single key for encryption and decryption, asymmetric methods make use of two keys: a secret key and a public key. The public key is used to encrypt the message and the secret key is used to decrypt the message. The receiver has the secret key that should be protected. A mathematical process can be used to generate the two keys that are mathematically related. The goal of public key cryptography was to eliminate the biggest problem of private key cryptography of key distribution. Several techniques have been identified in the domain of public key cryptography over the years. These techniques are described in the following sections.
Ralph Merle’s Puzzle Technique
Ralph Merkle has published his work in Communications of the ACM, a premier computer science journal. He said that his work was “secure communication over insecure channels.” The basis of his communication approach involves the use of puzzles. To understand this method, assume that John and Jane want to communicate with each other over a channel that is known to be insecure. John first creates a large number of encryption keys—say a million keys. John then places the keys in puzzles—one key per puzzle. Each puzzle takes a couple minutes to solve. John sends the puzzles to Jane, who chooses any one of the puzzles and its associated key. Using this key, Jane encrypts a message and sends it to John. John now figures out the key Jane chose based on his list of keys. Future communications between John and Jane occur using this key. An eavesdropper will be aware of the puzzles going back and forth but will take an extremely long time to figure out the exact key. In simple words, John creates a very large number of keys and “envelopes” or hides the keys in some “cover”—one key in one envelope—and sends these envelopes to Jane. Jane randomly picks any envelope and therefore one key, encrypts a message using that key, and sends the message to John. John can figure out which key was chosen because John has all the keys. This key then becomes the key for future conversations.
Diffie-Hellman Multiuser Cryptographic Techniques
A paper called “Multiuser Cryptographic Techniques” was published in 1975 by Whitfield Diffie and Martin Hellman. Their cryptographic techniques used the concept commonly used now in public key cryptography. The basic idea of this strategy was that it should be possible to encrypt a message using one key and decrypt the message using another key. Several suggestions were made to Diffie and Hellman about how this could be achieved, including the following:

• Multiplying prime numbers, which can be done easily; but it is difficult to factor the corresponding result.
  
• Using a discrete exponentiation of numbers; the corresponding task of discrete logarithms is difficult.
  

Diffie and Hellman chose the second approach to conduct further research. The Diffie-Hellman exponential key exchange approach was published in their paper “New Directions in Cryptography” in IEEE Transactions on Information Theory. The Diffie-Hellman approach is based on the following suggestion by John Gill, another Stanford colleague: Take the exponents of numbers and calculate the results modulo some prime number. The method works as follows:

1. Both the active participants must first agree on two numbers, p and q. Numbers p and q can be publicly known.
   
2. Each participant must now choose a number, perform a mathematical operation that involves p, q, and the chosen number, and transmit the result to the other participant. Suppose that the first participant chooses M1 and the other participant chooses M2. The result of their separate mathematical operations are N1 and N2.
   
3. Using a second mathematical formula, both participants can now compute another number, K, such that K can be computed as a function of the numbers M1 and N2 or the numbers M2 and N1—but not the numbers N1 and N2. Future communications occur using the session key K. The eavesdropper can have access to p, q, N1, and N2 but neither M1 nor M2. As a result, the eavesdropper cannot calculate K. Thus K can be used as a session key for a private key encryption algorithm such as DES. This method is used for communication between two people and makes use of three keys: two secret keys (one for each person) and a session key determined by the two people during the course of the conversation. In other words, the conversation starts with the two people using their own keys; they exchange information to determine a session key which is then used for all future messages.
   

The RSA Technique
The RSA technique is one of the most powerful encryption methods known. It is used as the public key system in PGP (Pretty Good Privacy). RSA makes use of any publicly available key to encrypt the information, but the decryption can be done only by the person who holds the matching secret key. RSA can also be used as a digital signature system. The biggest problem with the Diffie-Hellman method is that the two participants must communicate actively. This may not be possible in email communication between two people who are not necessarily actively conversing. In 1976, three professors in the computer science lab at MIT—Ronald Rivest, Adi Shamir, and Len Adelman—started working on the proposition made in the Diffie-
Hellman paper, “New Directions in Cryptography,” to find a practical multiuser cryptography system. After several months of research, they were about to conclude that such a public system was not possible. Then, in 1977, they realized a basic fact: It is very easy to multiply two prime numbers to get a large composite number, but it is difficult to take that composite number and find its prime number components. The outcome of this research is the technique simply referred to by the initials of its three inventors: RSA. This method is better than the Diffie-Hellman key exchange method because it does not rely on active participation between the person performing the encryption and the person performing the decryption. To understand how RSA works, here’s an example described in Bruce Schneier’s book, Applied Cryptography. The steps to effectively use RSA are as follows:

1. Choose two very large prime numbers at random, say M and N.
   
2. Obtain Z (the encryption modulo) by multiplying M and N. In other words, Z = M*N.
   
3. Choose E (the encryption key), which is relatively prime to (M-1)*(N-1).
   
4. Publish Z and E as the RSA keys that others can use to encrypt the information.
   

Suppose that you choose M = 47 and N = 71. Therefore, Z = 47*71 = 3337. Now you have to choose E such that it is relatively prime to (M-1)*(N-1) = 46*70 = 3220. Suppose that you pick E = 79. The decryption key is now calculated using the extended Euclid algorithm and the prime numbers as follows: D = 79-1 (mod 3220) = 1019
Now a user who wants to encrypt and send some information to us can use Z and E to encrypt the data. Suppose that someone wants to send us the number 688. To do so, they’d perform the following calculation: 68879 mod 3337 = 1570
We would receive the number 1570 and decrypt it as follows: 15701019 mod 3337 = 688
The security of RSA depends on the following:

• The numbers M and N must be kept secret. This is obvious: If Z and E are already public and you also know M and N, it is not very difficult to figure out the decryption key D.
  
• It should be extremely difficult to factor Z. If Z can be easily factored, you can derive M and N from it, and then you can easily find out the decryption key.
  
• here should be no other mathematical techniques to derive the decryption key using Z and E.
  

Sieve Algorithm
The following code segment shows a simple implementation of the sieve algorithm that can be used to check whether or not a particular number r is a prime number:

Awesome tutorial!