38.4 CRYPTOGRAPHY

< Day Day Up >

In any communication system, the three important security services to be provided are:

Privacy
Authentication
Message integrity

These are achieved by cryptography.

Suppose you want to send a message to a friend. The message is let us meet at sundowner

Instead of sending this message directly, you can send the following message:

mfu vt nffu bu tvoepxfs

You have encrypted the message. The encryption algorithm is to replace each letter with the next letter in the alphabet (replace a with b, b with c, c with d… and z with a). You have to tell your friend in advance that this is the algorithm and, whenever you send a message, your friend will be able to decode it. You can perhaps write a program to take the normal text message and convert it into the encrypted message. If your friend also uses this software, he can easily decode the message. Conceptually this is the mechanism used in cryptography. But then, if this message is seen by your foe, he may not find it difficult to decode the message—it is not very difficult to find out the algorithm used. Many experts, called cryptoanalysts, can easily decode messages even if very complicated algorithms are used.

In cryptography, the message bit stream is modified using an encryption key. Only the person who has the encryption key can decode the message. Cryptographic algorithms are divided into two categories: secret key algorithms and public key algorithms.

We can modify the above algorithm slightly. The new algorithm will shift each letter by two letters (replace a with c, b with d, etc.) or three letters (replace a with d, b with e, etc.), and so on. Now you have two things: an algorithm to shift the letters and a key that tells the number by which each letter is shifted (two, three, and so on). The algorithm can be known to anybody, but only you and your friend know the key, and you can use this mechanism to exchange secret information.

Cryptographic algorithms are broadly divided into two categories:

Secret key algorithms
Public key algorithms

38.4.1 Secret Key Algorithms

In a secret key algorithm, the sender and receiver (called participants) share the same algorithm and key. At the sending side, the original message (called plain text) is encrypted using the secret key. This encrypted message (called ciphertext) is transmitted to the receiver, and the receiver uses the same key to decrypt the message. The sender has to reveal the secret key beforehand to the intended recipient. If the secret key is leaked to someone else, he will be able to decode the message. The Data Encryption Standard (DES) developed by the U.S. Department of Defense, is the most widely known secret key algorithm.

click to expand
Figure 38.6: Encryption using secret key.

In secret key algorithms, both the sender and receiver share the same algorithm and the encryption key. The encrypted message is called ciphertext. Note that in this type of encryption, the algorithm can be made public, but the key should be kept confidential.

In DES, 64 bits of information is manipulated using 56 bits of encryption key. The process of encryption using DES is shown in Figure 38.7. In the first step, the 64 bits of information are shuffled. Then the modified bit stream is modified using a 56-bit key in 16 iterations. The next step is to exchange the rightmost 32 bits with the leftmost 32 bits. The last step is to carry out the reverse operation of the first step. The output is a 64 bit encrypted data. At the receiving end, the operations are carried out in reverse order to get back the original plain text, of course using the same key.

click to expand
Figure 38.7: Data Encryption Standard.

Data Encryption Standard (DES) developed by the U.S. Department of Defense, has been used extensively as a secret key algorithm. In DES, each block of 64 bits of information is modified using a 56-bit encryption key to obtain 64-bit ciphertext.

DES is not based on any mathematical foundation. If the data is received by an unauthorized person, it is very difficult to decode the information because of the heavy computation involved—he has to try all possible combinations of ones and zeros of the 56-bit key to get the plain text. Through jugglery of bits, DES is a complicated algorithm.

To make it more secure, triple DES has been developed, which encrypts the data three times. For each iteration, a separate key can be used, so three keys are used for the encryption.

The intended recipient should know the key to decrypt the data. The key can be exchanged in person, or sent through the mail or separate secure communication links can be used.

38.4.2 Public Key Algorithms

In public key encryption, everyone will have two keys. One is called the public key, and the other is called the private key. The public key is known to everyone. You can keep the public keys in a database and make it accessible to everyone. The private key is kept confidential by everyone. As shown in Figure 38.8, if A wants to send a secret message to B, A encrypts the message using B's public key. B decrypts the message using his private key.

click to expand
Figure 38.8: Public key encryption.

In public key encryption, there will be two keys—public key and private key. To send a secret message, the message is encrypted using the recipient's public key, and the recipient decodes the message using his private key.

RSA algorithm is the most widely used public key algorithm. RSA gets its name from the initials of the three inventors: Rivest, Shamir, and Adleman. RSA algorithm is based on number theory. To understand this algorithm, you need to recall the following definitions:

The RSA algorithm is the most widely used public key algorithm. It is based on the fact that factoring large numbers is computationally intensive. Two large prime numbers are used to generate the public key and private key.

A number that has no factors except 1 and itself is known as a prime number. Examples of prime numbers are 2, 3, 5, 7, 11, 13 and 17.

If two numbers do not have any common factors other than 1, they are called relatively prime numbers or co-primes. Examples are 7 and 60, 8 and 15, 24 and 77, 105 and 143, and 108 and 77.

In the RSA algorithm, we need to generate a public key and a private key. For this, choose two large prime numbers p and q such that both are at least 256 bits.

Let n = a * b
Choose a number e such that e and (p–1) * (q−1) are relatively prime.
Calculate the value of d using the formula d = e⁻¹ mod((p−1)(q−1)).
The public key is the pair (e, n) and the private key the pair (d, n).
Encryption is done using the formula
Ciphertext = (message)^e mod n
Decryption is done using the formula
Message = (ciphertext)^d mod n

The RSA algorithm is based on number theory and on the fact that factoring large numbers is computationally intensive.

< Day Day Up >