3

Symmetric-key Ciphers

1. Define a symmetric-key cipher.

Ans.: A cipher (a combination of encryption and decryption algorithms) that uses the same key for both encryption and decryption is referred to as a symmetric-key cipher.

2. Explain the symmetric cipher model.
            Or
            Explain the conventional encryption model.

Ans.: A symmetric cipher model (also referred to as a conventional encryption model) consists of various components (see Figure 3.1), which are described as follows:

Figure 3.1 Symmetric Cipher Model

(a) Plaintext: This refers to the original message that the sender wishes to send securely. It is an input to the encryption algorithm.

(b) Encryption algorithm: This algorithm applies various substitutions and transpositions on the plaintext, with the help of a secret key, to transform it into an unintelligible form. The encryption algorithm is used at the sender's end.

(c) Ciphertext: This refers to the coded (scrambled) message that is produced by the encryption algorithm. The ciphertext is sent to the receiver through a communication channel.

(d) Decryption algorithm: This is the opposite of an encryption algorithm. It is used at the receiver's end to convert ciphertext back into plaintext (original message). The encryption and decryption algorithms are together known as ciphers.

(e) Secret (shared) key: This usually refers to a number or a set of numbers on which the cipher operates. Both encryption and decryption algorithms use the same key (shared between the sender and receiver) to encrypt or decrypt the messages, respectively.

3. What are the issues in a conventional encryption model?

Ans.: Though conventional encryption is fast, efficient and excellent for large data transmissions such as file transfers, it suffers from certain limitations, which are as follows:

   As the sender and receiver share a single key, the key must be sent via a secure channel. However, if such a secure channel already exists, the question then arises as to why encryption was required in the first place.

   Exchanging the secret key using unsecure channels such as telephone lines, which are prone to eavesdropping, may violate the confidentiality of the key.

   There are some organizations that deal with thousands or million's of clients on a daily basis. In such organizations, it is extremely difficult to assign a unique key to each client.

4. What are the different categories of classical encryption techniques?

Ans.: The classical encryption techniques, also referred to as traditional symmetric-key ciphers, are divided into two categories: substitution ciphers and transposition ciphers.

   Substitution cipher: This cipher replaces a symbol (a single letter or a group of letters) of the plaintext with another symbol. For example, the letter A can be replaced with letter C, and letter P with letter Z. If the symbols are digits, then the digit 2 can be replaced by digit 5, and digit 3 with digit 6. Substitution ciphers are further categorized into monoalphabetic ciphers and polyalphabetic ciphers.

   Transposition cipher: In this cipher, there is no substitution of characters; rather, the location of characters in plaintext is changed to form the ciphertext. In other words, a transposition cipher reorders (transposes) the symbols in the plaintext, thereby creating the ciphertext. Thus, the order of characters in the plaintext is no longer preserved in the ciphertext. For example, a symbol at the third position in the plaintext may be placed at the eighth position in the ciphertext, or a symbol at the fifth position in the plaintext may appear at the fifteenth position in the ciphertext. Transposition ciphers are further categorized into keyless transposition ciphers and keyed transposition ciphers

5. What is a monoalphabetic cipher? Explain different techniques of monoalphabetic ciphers.

Ans.: A monoalphabetic cipher is a substitution cipher where a symbol in the plaintext has a one-to-one relationship with a symbol in the ciphertext. It means that a symbol in the plaintext is always replaced with the same symbol in the ciphertext, irrespective of its position in the plaintext. The different techniques based on monoalphabetic ciphers are as follows:

Additive cipher

This is the easiest and simplest monoalphabetic cipher, where each letter in plaintext is coded by shifting a certain number of spaces from it. For this, it uses a key that defines the number of spaces to be shifted. In this technique, each character in the plaintext is first assigned a numeric value according to its position in Z26, the set of alphabets. For example, a (or A) will be assigned 0, b (or B) will be assigned 1, c (or C) will be assigned 2, and so on. The key (say, K) used for encrypting the plaintext is also an integer in Z26.

At the sender's end, the key (K) is added to plaintext (say, P) and the result is mapped to Z26, using the modular arithmetic to form the ciphertext (say, C), as shown here.

C = (P + K) mod 26

At the receiver's end, the reverse process is followed for converting the ciphertext back to plaintext. That is, the additive inverse of key K in Z26, denoted as -K, is added to ciphertext (C) and the result is mapped to Z26 using the modular arithmetic to obtain plaintext (P), as shown here.

P = (C - K) mod 26

Figure 3.2 depicts the process of encryption and decryption in additive cipher. An example given in Question 17 illustrates the encryption and decryption processes using additive cipher.

Figure 3.2 Additive Cipher

Shift cipher

In this cipher, an encryption algorithm can be interpreted as ‘a shift by a key number of characters in the clockwise direction, that is, towards the end of the alphabet’ while a decryption algorithm can be interpreted as ‘a shift by a key number of characters in the anti-clockwise direction, that is, towards the beginning of the alphabet’. For example, for key = 5, the encryption algorithm moves five characters down in the set of alphabets (Z26), while the decryption algorithm moves five characters up the alphabet in the set of alphabets. Notice that during encryption and decryption, as the end or the beginning of the alphabet is reached, we wrap round. For the same value of the key K, both shift and additive ciphers produce the same ciphertext; thus, traditionally, additive ciphers have also been referred to as shift ciphers.

Caesar cipher

This cipher has been named after its inventor, Julius Caesar. It is simply an additive cipher with key = 3. That is, during encryption, each plaintext character is replaced with a character obtained by moving three places down in the alphabet and the reverse happens during decryption. Like shift cipher, on reaching the end or beginning of the alphabet, we wrap around. The simplicity of Caesar cipher becomes its weakness as anyone can determine the plaintext by just replacing each ciphertext character with a character obtained by moving three characters up in the alphabet.

To overcome this limitation of Caesar cipher, its enhanced version, named modified Caesar cipher, was proposed. In this cipher, a character can be replaced with any other character. However, as we know, the English alphabet has only 26 characters; hence, a character can be replaced only with one of the other 25 characters. Thus, the cipher is vulnerable to the brute-force attack, as an attacker just needs to choose one out of 25 possible characters.

Multiplicative cipher

In this cipher, the plaintext is encrypted by multiplying it with the key, while the ciphertext is decrypted by performing division on it with the key(K). Since the operations are in Z26, the result needs to mapped to Z26 using modular arithmetic. Moreover, division by key during decryption implies multiplication by the multiplicative inverse of the key in Z26 (denoted as K-1). The following are the formulae used to encrypt the plaintext (and) P decrypt the ciphertext(C), respectively.

C = (P * K) mod 26
    P = (C * K-1) mod 26.

Figure 3.3 depicts the process of encryption and decryption in a multiplicative cipher. The example given in Question 17 illustrates encryption and decryption using multiplicative cipher.

Figure 3.3 Multiplicative Cipher

Affine cipher

Affine cipher is the combination of additive and multiplicative ciphers with a pair of keys. Two ciphers are applied one after another, and a separate key is used for each. The first key of the key-pair is used for the first cipher (either additive or multiplicative), while the second key is used for the other. The process of encryption and decryption in affine cipher is shown in Figure 3.4.

Figure 3.4 Affine Cipher

At the sender's side, the plaintext (P) is first encrypted using the multiplicative cipher and key K1 to obtain the temporary ciphertext (C1), as shown here:

C1 = (P * K1) mod 26

Then, the ciphertext C1 is again encrypted using the additive cipher and key K2 to obtain the final ciphertext (C), as shown here:

C = (C1 + K2) mod 26.

At the receiver's side, the algorithm first decrypts the received ciphertext (C) using the additive cipher and additive inverse of the key K2 in Z26 (denoted as -K2) to obtain a temporary plaintext (P1), as shown here:

P1 = (C - K2) mod 26

Then, the plaintext P1 is again decrypted using the multiplicative cipher and multiplicative inverse of the key K1 in Z26 (denoted as K1-1) to obtain the original plaintext(P), as shown here:

P = (P1 * K1-1) mod 26.

It should be noted that, if the second cipher is the additive cipher in encryption, then the additive inverse should be the first cipher in decryption. In the same way, if the second cipher is the multiplicative cipher in encryption, then the multiplicative inverse should be the first cipher in decryption. An example given in Question 17 illustrates the encryption and decryption processes using the affine cipher.

6. What is polyalphabetic cipher? Also, explain the different techniques of using the polyalphabetic cipher.

Ans.: In polyalphabetic cipher, the characters in the plaintext may have a one-to-many relationship with the characters in the ciphertext. This means that the same character appearing in plaintext can be replaced with a different character in the ciphertext. For example, ‘hello’ can be encrypted to ARHIF using a polyalphabetic cipher. That is, the two occurrences of the letter ‘l’ in the plaintext are replaced with different characters. Due to the one-to-many relationship between the characters of plaintext and ciphertext, the key used must indicate which of the possible characters can be used for replacing a character in the plaintext. For this, the plaintext is divided into groups of characters, and a set of keys K =(K1, K2, K3,…)is used for encrypting the groups of plaintext, such that the ith key(Ki)is used to encrypt the ith character of a plaintext group. The different techniques based on polyalphabetic ciphers are as follows:

Autokey cipher

In this cipher, the key used is a group of subkeys (K1, K2, K3,…, Kn), where each subkey is used to encrypt the corresponding character in the plaintext. That is, the first subkey is used to encrypt the first plaintext character, the second subkey is used to encrypt the second plaintext character and so on. The cipher is named so because the subkeys are generated automatically during the encryption process. The first subkey is predetermined; its value is chosen by the sender and the receiver. The second subkey is the value of the first plaintext character, the third subkey is the value of the second plaintext character and so on.

At the sender's end, a plaintext character (say, Pi) is added with the respective subkey (Ki), and the result is mapped to Z26, using modular arithmetic to obtain the corresponding ciphertext character (Ci), as shown here:

Ci = (Pi + Ki) mod 26

At the receiver's end, the reverse process is followed to decrypt the ciphertext. That is, a ciphertext character (say, Ci) is added with the additive inverse of the respective subkey (denoted as, -Ki) and the result is mapped to Z26 using the modular arithmetic to obtain the corresponding plaintext character (Pi) as shown here:

Pi = (Ci - Ki) mod 26

An example given in Question 18 illustrates the encryption and decryption processes using the autokey cipher.

Playfair cipher

The Playfair cipher, also known as Playfair square, was used by the British army during World War I, and then by Australians during World War II. Despite its invention by Wheatstone in 1854, it is popularly known after the name of Lord Playfair, who heavily promoted its use. Here, the secret key is formed of 25 alphabets organized into a 5 × 5 matrix. (I and J are considered as same and inserted in the same cell in the matrix.) Different keys can be obtained from different possible arrangements of alphabets in the matrix.

The first step in the Playfair encryption technique is to create and populate the matrix. Initially, a keyword (or phrase) is chosen by the sender and receiver that may not necessarily contain all the 25 alphabets. To organize this keyword in the matrix, it is entered starting from the top left position to right (that is, row-wise), and from top to bottom. While entering, the duplicate letters in the keyword are dropped; that is, each letter of the keyword is entered only once. The remaining empty positions of the keyword matrix are filled with the alphabets (in order) that are not included in the keyword. Moreover, if either I or J appears in the keyword, both are ignored while filling the empty positions of the matrix. However, if neither I nor J appears in the keyword, both are placed at the same position in the matrix. This organization of 25 alphabets in the matrix becomes the secret key for encryption and decryption.

The next step is to encrypt the plaintext. However, before encryption, the plaintext message is broken into diagraphs (group of two characters). If both characters in a pair are the same, then we insert a bogus letter (say, X) between them to distinguish. In case the plaintext consists of an odd number of characters, then also a bogus character is inserted at the end of the plaintext to make the number of characters even. For example, if the plaintext is GREETING, then we have four groups of two letters each as GR, EE, TI, and NG. As the second pair of the message contains repeated letter E, the bogus letter X is inserted between two E's. Now, the pairs of the message become GR, EX, ET, IN and G. To make the number of characters even, the bogus character X is inserted at the end, making the last pair as GX.

At the sender's end, each pair of alphabets in the plaintext is encrypted using the following rules:

   If the two letters in a pair appear in the same row of the keyword matrix, they must be replaced with the letters at their immediate right positions. We must wrap around to the beginning of the row if the any of the letters appears at the end of the row.

   If the two letters in a pair appear in the same column of the keyword matrix, they must be replaced with the letters at their immediate below positions. We must wrap around to the beginning of the column if any of the letters is the last letter in the column.

   If the two letters in a pair do not appear in the same row or column of the keyword matrix, each of them must be replaced with the letter placed at the intersecting position of its own row and the column of another.

At the receiver's end, the ciphertext is decrypted using the same rules as for encryption, with some differences. If the two letters of a pair in the ciphertext satisfy the condition of rule 1, they are replaced with the letters at their immediate left positions. If the two letters of a pair in the ciphertext satisfy the condition of rule 2, they are replaced with the letters at their immediate above positions. The rule 3 is same for decryption. During decryption, the bogus letters are also removed. An example given in Question 19 illustrates the encryption and decryption processes using the Playfair cipher.

Vigenere cipher

The Vigenere cipher has been named after its designer Blaise de Vigenere. In this cipher, the group of subkeys used depends on the position of the characters in the plaintext, rather than the character itself. Thus, the group of subkeys can be created independent of the plaintext. The initial secret key of length n (where 1 ≤ n ≤ 26) is chosen by the sender and receiver. Then, the chosen key is repeated till the end of the plaintext. That is, if the initial secret key chosen is(K1, K2,…, Km), then the set of keys used for encryption and decryption will be K=[(K1, K2,…, Km), (K1, K2,…, Km),…]. Thus, this cipher helps to encrypt plaintext of any size.

At the sender's end, each plaintext character (Pi) is added with the respective key character (Ki) and the result is mapped to Z26 using the modular arithmetic to obtain the corresponding ciphertext character (Ci) as shown here:

Ci = (Pi + Ki) mod 26

At the receiver's end, the reverse process is followed to decrypt the ciphertext. That is, a ciphertext character (say, Ci) is added with the additive inverse of the respective key character (denoted as, -Ki) and the result is mapped to Z26 using the modular arithmetic to obtain the corresponding plaintext character (Pi) as shown here:

Pi = (Ci - Ki) mod 26

An example given in Question 20 illustrates the encryption and decryption processes using the Vigenere cipher.

Hill cipher

The Hill cipher was invented in 1929 by Lester S. Hill, and it is named after him. In the Hill cipher, the plaintext is first divided into equal-size blocks. Then, the blocks are encrypted in such a way that each block element (character) participates in the encryption of other block elements in the block. The key (K) used in the Hill cipher is in the form of an n×n square matrix, where n is the block size (see Figure 3.5). Each element of the key matrix is represented as Kij, where 1 ≤ i, j ≤ n.

Figure 3.5 Key Matrix

Consider a plaintext block (P) that contains n characters is to be encrypted. Let P1, P2,…, Pn represent the plaintext characters in this block and their corresponding ciphertext characters are represented as C1, C2,…, Cn. Then, we get the ciphertext as shown here:

C1 = (P1K11 + P2K21 + … + PnKn) mod 26
C2 = (P1K12 + P2K22 + … + PnKn2) mod 26
.
.
.
Cm = (P1K1n + P2K2n + … + PnKnn) mod 26

The preceding equations can be expressed as:

In general, the encryption in the Hill cipher can be expressed as shown here:

C = K P mod 26

To perform decryption at the receiver's end, the inverse of the key is first determined in Z26, and then the ciphertext is decrypted, as shown here:

P = K-1 C mod 26

An example given in Question 21 illustrates the encryption and decryption processes using the Hill cipher.

7. What are keyless and keyed transposition ciphers?

Ans.: Keyless and keyed ciphers are two categories of transposition ciphers that reorder (permute) the symbols of plaintext to form ciphertext. These are described as follows:

   Keyless transposition ciphers: These are the traditional ciphers, and are easy to use. They do not use any key to permute the characters in the plaintext and thus, are named as keyless ciphers. To permute the characters, the plaintext characters are written in a table either column-wise or row-wise. In the former case, ciphertext is formed by reading the characters from the table row-wise, while in the latter case, column-wise.

   Keyed transposition ciphers: These ciphers make use of a key to permute the characters in the plaintext and, thus, are named as keyed ciphers. These ciphers first divide the plaintext into blocks of predefined size, and then a key is used to permute the characters within each block individually.

8. Write a short note on columnar transposition ciphers.

Ans.: A columnar transposition cipher is the combination of keyless and keyed transposition ciphers. It performs encryption and decryption in three steps; the first and third steps are keyless, while the second step is performed on the basis of a key. The plaintext characters are first arranged in the table row-wise. Secondly, these characters are permuted by reordering the columns based on a key. And, finally, the characters are read from the new table column-wise.

To understand, consider the plaintext ‘hellohowareyou', and the key ‘BACKIN’. Initially, the plaintext characters are arranged in the table row-wise, as shown in the following. The rows are padded with extra characters to fill the table, if required.

After arranging the plaintext, the letters of the key BACKIN are numbered according to the alphabetical order. For example, A is assigned the number 1, B is 2, C is 3, I is 4, K is 5 and N is 6. Now, the columns of the table are reordered according to numbers assigned to the key letters. For example, the column 1 is interchanged with column 2, column 4 with column 5, while columns 3 and 6 remain intact. After reordering the columns, the new table is as shown in the following:

The characters are now read out column-wise from the new table to form the ciphertext. That is, the ciphertext is ‘ewuhoolaaoeclrbhyd’.

9. What is the difference between stream cipher and block cipher?

Ans.: Stream cipher and block cipher are two categories of symmetric ciphers.

   Stream cipher: This cipher operates on one symbol (character) of plaintext at a time and produces a corresponding symbol of ciphertext. As the name of the cipher implies, we have a plaintext stream P =(P1,P2,P3,…), a ciphertext stream C=(C1,C2,C3,…), and a key stream K=(K1, K2, K3,…). The plaintext characters are input into the encryption algorithm, one character at a time. The encryption algorithm uses the respective subkey to encrypt each plaintext character, which results in a corresponding ciphertext character. Each character is encrypted and decrypted using the same key, regardless of the fact that multiple keys are being used. For example, consider that the plaintext is ‘user’ and the key stream used is (K1, K2 and K3). Now, the plaintext is encrypted such that the characters ‘u’ and ‘r’ are encrypted using the key K1, the characters ‘s’ is encrypted using the key K2 and the character ‘e’ is encrypted using K3. During decryption also, the same set of keys (K1, K2 and K3) is used, such that the characters ‘u’ and ‘r’ are decrypted using the key K1, the character ‘s’ is decrypted using the key K2 and the character ‘e’ is decrypted using the key K3. The Additive cipher and Vigenere cipher can be categorized as stream ciphers.

   Block cipher: This cipher encrypts a group or block (with size > 1) of symbols in plaintext at one time, producing a block of ciphertext of the same size. Similarly, during decryption, a block of ciphertext symbols is converted back to a block of plaintext with one block at a time. A single key is used to encrypt or decrypt the entire block, even if the key contains multiple values. The Hill cipher and Playfair cipher can be categorized as block ciphers.

10. Explain the term one time pad.

Ans.: The one-time pad (also known as the Vernam cipher) was first implemented at AT&T using a device called the Vernam machine. It is actually a random set of non-repeating characters that is used as a key for generating the ciphertext message. As the name suggests, the set of characters can be used only once and, therefore, cannot be used for any other message. The algorithm used in generating a ciphertext message by the one-time pad scheme is as follows:

1.   The alphabets in the plaintext are assigned numbers in an increasing order. For example, A = 0, B = 1,…, and Z = 25.

2.   The one-time pad alphabets are randomly chosen, and numbers are assigned in the same manner as in the plaintext. For example, C = 2, D = 3 and so on.

3.   The numbers that correspond to the plaintext and the one-time pad input are added.

4.   Then the mod 26 operation is done with each generated character of the sum.

5.   The numbers obtained from the sum are translated back to the corresponding alphabet, which gives the output ciphertext.

The security of the one-time pad method is very high because of its randomness and one-time use. Thus, it can only be used for small plaintext messages. The ciphertext message generated using the one-time pad method is also random; that is, the same ciphertext message is not generated for two same plaintexts, thus making it less vulnerable to attacks. In spite of these benefits, it faces some difficulties in practical implementation. One problem is that it is difficult to generate a large set of random numbers each time for the same nodes to communicate with each other. Another problem is that of key distribution and protection, as a key of equal length is needed by both the sender and the receiver in every message exchange. An example illustrating the use of one-time pad is shown in Question 22.

11. What do you understand by bit-oriented ciphers? Why do we need them?

Ans.: The ciphers that perform encryption or decryption at the bit level rather than at the character level are referred to as bit-oriented ciphers. Earlier, most of the information to be encrypted was in textual form; thus, the use of character-oriented ciphers was justified. However, these days, the information to be encrypted is not just text, but may comprise graphics, audio and video. Thus, bit-oriented ciphers are needed, because such types of data can be conveniently transformed into streams of bits, which can then be encrypted and sent to the intended receiver. Moreover, as the text is treated at the bit level, each character of plaintext can be replaced with 8 bits or 16 bits. This increases the number of symbols in the plaintext by 8 or 16 times, thereby also increasing the security.

12. What do you mean by modern block cipher? What are its components?

Ans.: The modern block cipher is a bit-oriented symmetric-key cipher that encrypts an m-bit block of plaintext at a time to produce an m-bit block of ciphertext. Similarly, during decryption, an m-bit block of ciphertext is converted back to an m-bit block of plaintext, one block at a time. Each block of bits is encrypted or decrypted using the k-bit key (see Figure 3.6). The decryption algorithm used is the inverse of the encryption algorithm, and the same secret key is used for both encryption and decryption. Thus, the same block of plaintext is always encrypted to same block of ciphertext.

Figure 3.6 Modern Block Cipher

If the plaintext contains less than m bits, extra bits (padding) are added to make it an m-bit block. On the other hand, if the plaintext contains more than m bits, the plaintext is divided into blocks of m bits each and extra bits are added to the last block to make it an m-bit block if it contains less than m bits.

The modern block cipher consists of various components, described as follows:

   S-box: This is a substitution box having the same characteristics as that of the substitution cipher, except that the substitution of several bits is performed in parallel. It takes n bits of plaintext at a time as input and produces m bits of ciphertext as output, where the value of n and m may be the same or different. An S-box can be keyed or keyless. In a keyed S-box, the mapping of n inputs to m outputs is decided with the help of a key, whereas in a keyless S-box, the mapping from inputs to outputs is predetermined. Usually, keyless S-boxes are used in modern block ciphers.

   P-box: This is a permutation box having the same characteristics as that of the traditional transposition cipher, except that it performs transposition at the bit-level, and that transposition of several bits is performed at the same time. The input bits are permuted to produce the output bits. For example, the first input bit can be the second output bit, the second input bit can be the third output bit and so on. A P-box is sometimes also referred to as a D-box (diffusion box). It is normally a keyless cipher and can be classified into the following three types (see Figure 3.7), based on the length of input and output:

   Straight P-box: This P-box takes n bits as input, permutes them and produces n bits as output. As the number of inputs and outputs is the same, there are a total of n! ways to map n inputs to n outputs.

   Compression P-box: This P-box takes n bits as input and permutes them in such a way that an output of m bits is produced, where m < n. This implies that some of the inputs are blocked and do not reach the output. Compression P-boxes are used in those situations where we need to permute the bits and at the same time need lesser number of bits at each successive stage.

   Expansion P-box: This P-box takes n bits as input and permutes them in such a way that an output of m bits is produced, where m > n. This implies that a single input is mapped to more than one output. The expansion P-boxes are used in those situations where we want a higher number of bits at each successive stage.

   Circular shift: Another important component involved in modern block cipher is the circular shift operation, which tends to conceal the bit patterns in a transmitted word. The bits can be shifted either in the left or the right direction. In a circular left shift operation [see Figure 3.8 (a)], every bit of an m-bit word is shifted by a specific number of positions (say, n) in the left direction. In other words, the n leftmost bits of the word are removed and placed at the rightmost positions. The reverse happens in a circular right-shift operation [see Figure 3.8 (b)], where each bit of an m-bit word is shifted by n positions in the right direction. That is, the n rightmost bits of the word are removed and placed at the leftmost position. The circular shift operation can be either keyed or keyless. In the former case, the key defines the number of positions by which the bits are to be shifted. On the other hand, in the latter case, the number of positions to be shifted is usually fixed and predetermined. It is important to note that if a circular left shift operation is used in encryption, then a circular right shift operation is used in decryption, and vice-versa. Thus, both these operations are inverses of each other.

Figure 3.7 Types of P-Boxes

Figure 3.8 Circular Shift Operati

13. Explain Shannon's theory of diffusion and confusion.

Ans.: The theory of diffusion and confusion was proposed by Claude Shannon in attempt to thwart cryptanalysis based on statistical analysis. Both diffusion and confusion are the essential properties of block ciphers. Diffusion is based on the idea of hiding the relationship between the ciphertext and plaintext. This will frustrate a cryptanalyst who examines the ciphertext statistics in order to determine the plaintext. To achieve diffusion, a ciphertext symbol must depend on some or all symbols in the plaintext. That is, a change in a single symbol in the plaintext causes change in several or all symbols in the ciphertext.

On the other hand, confusion is based on the idea of hiding the relationship between the ciphertext and the key. This will frustrate a cryptanalyst who attempts to determine the key using the ciphertext. To prevent intruders from discovering the key, confusion attempts to make the relationship between the value of encryption key and the statistics of ciphertext as complex as possible. This can be achieved by making sure that a ciphertext symbol depends on some or all symbols of the key used. That is, a change in a single bit of the key causes changes in several or all symbols in the ciphertext.

14. What is a product cipher?

Ans.: The concept of product cipher was proposed by Shannon. The basic idea of a product cipher is to build a complex cipher by combining two or more ciphers (transformations) in such a manner that the resulting cipher is more secure than the individual components. That is, various transformations, including substitutions, permutations, circular shifts and transposition, are combined within a single unit to make a complex cipher, known as product cipher. The complexity of a product cipher makes it more secure and resistant to various attacks, thereby making it more difficult for a cryptanalyst to thwart the security. All modern ciphers are product ciphers, and are classified into two categories on the basis of the type of components used in them, namely, Feistel and non-Feistel ciphers.

15. Explain Feistel cipher and its structure.

Ans.: The Feistel cipher, proposed by Horst Fiestel, belongs to a class of product ciphers that permits the use of invertible as well as noninvertible components. The Feistel cipher uses three types of components (units), namely, self-invertible, invertible and noninvertible components. This cipher works by combining all noninvertible units into a single unit and then using the same unit in encryption and decryption algorithms. Now, the problem is that since both encryption and decryption algorithms use noninvertible units, how can they be the inverses of each other? To resolve this problem, we use the XOR operation, so that the effects of a noninvertible component in encryption can be cancelled out during decryption.

Initially, a basic model of the Fiestel cipher was proposed, which had certain shortcomings. To overcome these shortcomings, the basic model was improved, resulting in the final design. Here, we will discuss both the designs.

Basic model

In this structure, the plaintext is divided into two equal-length blocks: left and right. During encryption, a noninvertible function (f), which accepts key (K) as an input, is applied to the right block of the plaintext (denoted as Rp), and the resultant output is XOR-ed with the left block (denoted as Lp). The output of the XOR operation becomes the left block of the ciphertext (denoted as Lc), while the right block of ciphertext (denoted as Rc) is same as the right block of plaintext. The function f and the XOR operation together are referred to as the mixer, which is self-invertible in nature. During decryption, the reverse process is followed. However, the input to the function f remains the same in both the encryption and decryption processes, as shown in Figure 3.9.

Figure 3.9 Basic Model of Fiestel Cipher

To verify the correctness of the design, we need to ensure that the encryption and decryption algorithms are inverses of each other. That is, it must be proved that Lp = Lp' and Rp = Rp'. To prove this, let us assume that there is no change in the ciphertext during transmission, which means Lc = Lc' and Rc=Rc'. As Rc = Rp and Rc' = Rp', we have Rp' = Rp.

Now, we can write that

As we know that Lc = Lp f(Rp,K) and Rc = Rp, the equation (1) can be written as:

Hence, the decryption algorithm produces the same plaintext as used by the encryption algorithm. In other words, the encryption and decryption algorithms are the inverses of each other.

Final design of the Feistel cipher

In the basic model of the Feistel cipher, the right block of the plaintext never changes and remains the same in the ciphertext also. Due to this, the generated ciphertext becomes vulnerable to attacks and is more prone to interception by a hacker. Thus, the design was improved by including the following enhancements:

   The number of rounds was increased in the final design.

   A new element called swapper was added to each round. The role of the swapper is to swap the left and right blocks in each round. In addition, the effect of the swapper during encryption is cancelled out with the effect of the swapper during decryption.

   Two round keys (K1 and K2) are used during encryption and decryption. The encryption and decryption algorithms use the keys in reverse order.

Figure 3.10 shows the final design of the Feistel cipher with two rounds.

The mixers and swappers used in encryption and decryption are inverses of each other, respectively. This implies that the encryption and the decryption algorithms are also inverses of each other. To prove this fact, we need to show that Lp = Lp' and Rp = Rp'. To prove this, let us assume that there is no change in the ciphertext during transmission, which means Lc = Lc' and Rc = Rc'. First, we will prove the equality between the middle texts (L and L', R and R'), and then between the final text. As R' = Lc', Lc' = Lc and Lc = R, we have R' = R.

We can write that:

As we know that Rc= f(R,K2) and Lc=R, Equation (2) can be written as:

Now, we have Rp'=L', L'=L and L=Rp. Thus, it is proved that Rp' = Rp.

Figure 3.10 Final Design of Fiestel Cipher with two Rounds

We can also write that:

As R'=R and L'=L, Equation (3) can be written as:

As we know that L=Rp and R=Lpf(Rp,K1), Equation (4) can be written as:

Hence, the decryption algorithm produces the same plaintext as used by the encryption algorithm. In other words, encryption and decryption algorithms are the inverses of each other.

16. What is a non-Feistel cipher?

Ans.: A non-Feistel cipher uses only invertible components. Each element in the plaintext has a respective element in the cipher. For example, if an S-box is used, then it must have the same number of inputs and outputs. In addition, only the straight P-boxes can be used, because the compression and expansion P-boxes are non-invertible in nature. Unlike the Fiestel cipher, it is not required to break the plaintext into two halves in a non-Fiestel cipher.

17. Encrypt the message ‘this is an exercise’ using the following ciphers. Ignore the spaces between the words while encrypting. Also, decrypt the message to get the original plaintext.

(a) Additive cipher with key = 20

(b) Multiplicative cipher with key = 15

(c) Affine cipher with key = (15, 20)

Ans.: (a) Additive cipher with key = 20

Plaintext (P) = ‘this is an exercise’

Key (K) = 20

   Encryption: In additive cipher, the ciphertext (C) = (P + K) mod 26, which can be found as follows:

Hence, the corresponding ciphertext is ‘nbcmcmuhyrylwcmy’.

   Decryption: To decrypt the ciphertext (C), we first need to determine the additive inverse of 20 in Z26, which is equal to 6 (26–20). Now, the ciphertext (C) can be decrypted to obtain the plaintext (P) using the formula (C+6) mod 26, as shown here:

(b) Multiplicative cipher with key = 15

Plaintext (P) = ‘this is an exercise’

Key (K) = 15

   Encryption: In multiplicative cipher, the ciphertext (C) = (P * K) mod 26, which can be found as follows:

Hence, the corresponding ciphertext is ‘zbqkqkanihiveqki’.

   Decryption: To decrypt the ciphertext, first we need to determine the multiplicative inverse of 15 in Z26, which is equal to 7, as 15 * 7 ≡ 1 (mod 26). Now, the ciphertext (C) can be decrypted to obtain the plaintext (P) using the formula (C * 7) mod 26, as shown here:

(c) Affine cipher with key = (15, 20)

Plaintext (P) = ‘this is an exercise’

Key (K) = 15

   Encryption: In affine cipher, the plaintext (P) is first encrypted using the multiplicative cipher and the first key (that is, 15) to produce the temporary ciphertext (C1). Then, C1 is again encrypted using the additive cipher and the second key (that is, 20) to produce the final ciphertext(C), as shown here:

Hence, the corresponding ciphertext is ‘tvkekeuhcbcpykec’.

   Decryption: First, the ciphertext (C) is decrypted using the additive cipher and the additive inverse of key 20 to produce the temporary plaintext P1. Then, P1 is again decrypted using the multiplicative cipher and the multiplicative inverse of key 15. The additive inverse of key 20 in Z26 is 6, while the multiplicative inverse of key 15 in Z26 is 7. Now, the decryption is performed as shown here:

18. Encrypt the plaintext message ‘ATTACK SUCCESSFUL’ by using the initial key stream as 12 with the autokey cipher.

Ans.: The plaintext will be encrypted to form the ciphertext as shown here:

Hence, the corresponding ciphertext is ‘MTMTCMCMWEGWKXZF’.

19. Given the key ‘MONARCHY', apply the Playfair cipher to the plaintext ‘FACTIONALISM’. Decrypt the ciphertext also.

Ans.: The given keyword = ‘MONARCHY’

The corresponding keyword matrix is as follows:

Encryption

The given plaintext is ‘FACTIONALISM’. The different pairs of plaintext are FA, CT, IO, NA, LI and SM. These pairs are encrypted as follows:

   In the first pair, the letter F is at position (3, 2), and A is at position (1, 4) in the keyword matrix. That is, neither their rows nor their columns match. Thus, F is replaced with the letter at the intersecting position of the third row and fourth column, which is either I or J. Let us use I. Similarly, A is replaced with the letter at the intersecting position of the first row and second column, which is the letter O.

   For the next two pairs, CT and IO, neither the rows nor the columns match. Thus, using the same rule as earlier, they are replaced with DL and FA, respectively.

   In the fourth pair, NA, both letters appear in the same row. Thus, they are replaced with the letters at their immediate right positions, which are A and R.

   In the last two pairs, LI and SM, neither the rows nor the columns match. Thus, they are replaced with SE and LA, respectively.

Hence, the corresponding ciphertext is ‘IODLFAARSELA’.

Decryption

The different pairs of ciphertext are IO, DL, FA, AR, SE and LA. These pairs are decrypted as follows:

   In the first pair, the letter I is at position (3, 4) and O appears at position (1, 2) in the keyword matrix. That is, neither their rows nor their columns match. Thus, I is replaced with the letter at the intersecting position of third row and second column, which is F. Similarly, O is replaced with the letter at the intersecting position of first row and fourth column, which is the letter A.

   For the next two pairs, DL and FA, neither the rows nor the columns match. Thus, using the same rule as earlier, they are replaced with CT and IO, respectively.

   In the fourth pair, AR, both letters appear in the same row. Thus, they are replaced with letters at their immediate left positions, which are N and A.

   In the last two pairs, SE and LA, neither the rows nor the columns match. Thus, they are replaced with LI and SM, respectively.

Hence, the corresponding plaintext is ‘FACTIONALISM’.

20. Encrypt the plaintext message ‘honesty is the best’ by using a 6-character key ‘CENTRE’ with the Vigenere cipher.

Ans.: The encryption process using the Vigenere cipher is shown here:

Hence, the corresponding ciphertext is ‘jsaxjxamfmyidifm’.

21. Given the key ‘GYBNQKURP', apply the Hill cipher to the plaintext ‘ACT’ to show how encryption and decryption are performed and prove authenticity.

Ans.: The given plaintext (P) = ‘ACT’

Key (K) = ‘GYBNQKURP’

The key used can be written as:

Encryption

The plaintext ACT can be written as:

Thus, the ciphertext (is) C given as PK mod 26 as shown here.

Hence, the corresponding ciphertext is ‘POH’.

Decryption

In order to decrypt the ciphertext, we first need to calculate the inverse of the key matrix and then multiply it with the ciphertext, that is, P = K-1C mod 26. Now, the inverse of the key matrix is:

Thus, the plaintext can be obtained as shown here:

Since the receiver receives the same message as sent by the sender, the authenticity of the message is proved.

22. Generate the ciphertext message using the one-time pad algorithm for the plaintext message ‘higautam’.

Ans.:

Hence, the corresponding ciphertext is ‘ikfsptxf’.

Multiple-choice Questions

1.   Which of the following is a monoalphabetic cipher?

(a) Caesar cipher

(b) Autokey cipher

(c) Vigenere cipher

(d) All of these

2.   The __________ cipher is a combination of additive and multiplicative ciphers with a pair of keys.

(a) Affine

(b) Caesar

(c) Autokey

(d) Shift

3.   In the polyalphabetic cipher, the characters in plaintext have a __________ relationship with the characters in ciphertext.

(a) One-to-one

(b) One-to-many

(c) Many-to-one

(d) Many-to-many

4.   The Hill cipher belongs to the category of ciphers, named __________.

(a) Stream cipher

(b) Block cipher

(c) Both (a) and (b)

(d) None of these

5.   The __________ cipher can be categorized as a stream cipher.

(a) Additive

(b) Hill

(c) Playfair

(d) None of these

6.   Which of the following is/are components of a modern block cipher?

(a) Circular shift

(b) S-box

(c) P-box

(d) All of these

7.   __________ is based on the idea of hiding the relationship between the ciphertext and the key.

(a) Diffusion

(b) Confusion

(c) Both (a) and (b)

(d) None of these

8.   The concept of product cipher was proposed by __________.

(a) Verman

(b) Fiestel

(c) Lester S. Hill

(d) Shannon

9.   The Feistel cipher uses the __________ operation.

(a) AND

(b) NOR

(c) XOR

(d) OR

10. A non-Feistel cipher uses only the __________ P-box.

(a) Compression

(b) Expansion

(c) Straight

(d) None of these

Answers

  1. (a)

  2. (a)

  3. (b)

  4. (b)

  5. (a)

  6. (d)

  7. (b)

  8. (d)

  9. (c)

10. (c)