0% found this document useful (0 votes)

7 views

Chapter 3 Symmetric Key Algorithms and AES

Uploaded by

anushkasaundane5

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

7 views

Chapter 3 Symmetric Key Algorithms and AES

Uploaded by

anushkasaundane5

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 66

+0)26-4 !

Symmetric Key
Algorithms and AES

3.1 Introduction
We have discussed the basic concepts of cryptography, encryption and decryption. Computers perform
encryption quite easily and fast. Symmetric key cryptography has been quite popular over a number of
years. Of late, asymmetric key cryptography is equally popular. However, as we shall study later, most
practical implementations use a combination of symmetric and asymmetric key cryptography.
In this chapter, we shall look at the various aspects of symmetric key cryptography. We shall discuss
the various types and modes of symmetric key algorithms. We shall also examine uses of chaining.
This chapter also discusses a number of symmetric key algorithms in great detail. We go to the last bit
of explanation, which should make the reader understand how these algorithms work. The algorithms
discussed here are: DES (and its variations), IDEA, RC4, RC5 and Blowfish. We also touch upon the
Rijndael algorithm, which is approved by the US Government as the Advanced Encryption Standard
(AES).
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

After reading this chapter, the reader will have a complete understanding of how symmetric key
encryption works. However, if the reader is not very keen in understanding the minute details of the
algorithms, the relevant sections can be skipped without any loss of continuity.

3.2 Algorithm Types and Modes

Before we discuss real-life computer-based cryptography algorithms, let us discuss two key aspects of
such algorithms: algorithm types and algorithm modes. An algorithm type defines what size of plain
text should be encrypted in each step of the algorithm. The algorithm mode defines the details of the
cryptographic algorithm, once the type is decided.

3.2.1 Algorithm Types

We have been talking about the transformation of plain text messages into cipher text messages. We have
also seen the various methods for performing these transformations earlier. Regardless of the techniques

Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
88 Cryptography and Network Security

used, at a broad level, the generation of cipher text

from plain text itself can be done in two basic ways, Algorithm Types
stream ciphers and block ciphers. This is shown in
Fig. 3.1.

Stream Ciphers In Stream Ciphers, the plain

text is encrypted one byte at a time. Suppose the Stream Ciphers Block Ciphers

original message (plain text) is Pay 100 in ASCII

(i.e. text format). When we convert these ASCII Fig. 3.1 Types of cipher
characters to their binary values, let us assume that it
translate to 01011100 (hypothetically, just for Input 1 Input 2 Output
simplicity, in reality, the binary text would be much 0 0 0
larger as each text character takes seven bits). 0 1 1
Suppose the key to be applied is 10010101 in binary. 1 0 1
Let us also assume that we apply the XOR logic as 1 1 0
the encryption algorithm. XOR is quite simple to Fig. 3.2 Functioning of XOR logic
understand as shown in Fig. 3.2. In simple terms,
XOR produces an output of 1 only if one input is 0 and the other is 1. The output is 0 if both the inputs are
0 or if both the inputs are 1 (hence the name exclusive).
We can see the effect of XOR in Fig. 3.3.

In text format In binary format

Pay 100 010111001 Plain text

+ 100101011 XOR operation with the key

ZTU91 ^%D 11001001 Cipher text

Fig. 3.3 Stream ciphers

As a result of applying one bit of key for every respective bit of the original message, suppose the
cipher text is generated as 11001001 in binary (ZTU91 ^% in text). Note that each byte of the plain text
is encrypted one after the other. Thus, what is transmitted is 11001001 in binary, which even when
translated back to ASCII would mean ZTU91 ^%. This makes no sense to an attacker and thus protects
the information.

Stream Cipher technique involves the encryption of one plain text byte at a time. The
decryption also happens one byte at a time.

Another interesting property of XOR is that when used twice, it produces the original data. For
example, suppose we have two binary numbers A = 101 and B = 110. We now want to perform an XOR
operation on A and B to produce a third number C, i.e.:

C = A XOR B
Thus, we will have:
C = 101 XOR 110
= 011
Now, if we perform C XOR A, we will get B. That is:
B = 011 XOR 101
= 110
Similarly, if we perform C XOR B, we will get A. That is:
A = 011 XOR 110
= 101
This reversibility of XOR operations has many implications in cryptographic algorithms, as we shall
notice.

XOR is reversible – when used twice, it produces the original values. This is useful in
cryptography.

Block Ciphers In Block Ciphers, rather than encrypting one byte at a time, a block of bytes is
encrypted at one go. Suppose we have a plain text FOUR_AND_FOUR that needs to be encrypted.
Using block cipher, FOUR could be encrypted first, followed by _AND_ and finally FOUR. Thus, one
block of characters gets encrypted at a time.
During decryption, each block would be translated back to the original form. In actual practice, the
communication takes place only in bits. Therefore, FOUR actually means binary equivalent of the
ASCII characters FOUR. After any algorithm encrypts these, the resultant bits are converted back into
their ASCII equivalents. Therefore, we get funny symbols such as Vfa%, etc. In actual practice, their
binary equivalents are received, which are decrypted back into binary equivalent of ASCII FOUR. This
is shown in Fig. 3.4.
An obvious problem with block ciphers is repeating text. For repeating text patterns, the same cipher
is generated. Therefore, it could give a clue to the cryptanalyst regarding the original plain text. The
cryptanalyst can look for repeating strings and try to break them. If she succeeds in doing so, there is a
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

danger that a relatively large portion of the original message is broken into and therefore, the entire
message can then be revealed with more effort. Even if the cryptanalyst cannot guess the remaining
words, suppose she changes all debit to credit and vice versa in a funds transfer message, it could cause
havoc! To deal with this problem, block ciphers are used in chaining mode, as we shall study later. In
this approach, the previous block of cipher text is mixed with the current block, so as to obscure the
cipher text, thus avoiding repeated patterns of blocks with the same content.

Block Cipher technique involves encryption of one block of text at a time. Decryption also
takes one block of encrypted text at a time.

Practically, the blocks used in block cipher generally contain 64 bits or more. As we have seen, stream
ciphers encrypt one byte at a time. This can be very time consuming and actually unnecessary in real life.
That is why block ciphers are used more often in computer-based cryptographic algorithms as compared
to stream ciphers. Consequently, we will focus our attention on block ciphers with reference to algorithm
modes. However, as we shall see, two of the block cipher algorithm modes can also be implemented as
stream cipher modes.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
90 Cryptography and Network Security

FOUR _AND_ FOUR Plain text

Encrypt Encrypt Encrypt

VFa% *yT1x VFa% Cipher text

(a) The encryption process at the sender’s end

VFa% *yT1x VFa% Cipher text

Decrypt Decrypt Decrypt

FOUR _AND_ FOUR Plain text

(b) The decryption process at the receiver’s end

Fig. 3.4 Block ciphers

Group Structures When discussing an algorithm, many times a question arises, as to whether it is a
group. The elements of the group are the cipher text blocks with each possible key. Grouping, thus,
means how many times the plain text is scrambled in various ways to generate the cipher text.

Concepts of Confusion and Diffusion Claude Shannon introduced the concepts of confusion and
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

diffusion, which are significant from the perspective of the computer-based cryptographic techniques.
Confusion is a technique of ensuring that a cipher text gives no clue about the original plain text. This
is to try and thwart the attempts of a cryptanalyst to look for patterns in the cipher text, so as to deduce
the corresponding plain text. We already know how to achieve confusion: it is achieved by means of the
substitution techniques discussed earlier.
Diffusion increases the redundancy of the plain text by spreading it across rows and columns. We
have already seen that this can be achieved by using the transposition techniques (also called as
permutation techniques).
Stream cipher relies only on confusion. Block cipher uses both confusion and diffusion. We leave the
question of why this is the case, to the reader.

3.2.2 Algorithm Modes

An algorithm mode is a combination of a series of the basic algorithm steps on block cipher and some
kind of feedback from the previous step. We shall discuss it now, as it forms the basis for the computer-

based security algorithms. There are four important algorithm modes, namely, Electronic Code Book
(ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB) and Output Feedback (OFB). This
is shown in Fig. 3.5. The first two modes operate on block cipher, whereas the latter two modes are block
cipher modes, which can be used as if they are working on stream cipher.
Apart from this, we also discuss a variation of the OFB mode, called as Counter (CTR).

Algorithm Modes

Electronic Code Cipher Block Cipher Feedback Output

Book (ECB) Chaining (CBC) (CFB) Feedback (OFB)

These two modes work on

These two modes work on
block ciphers acting as
block ciphers.
stream ciphers.

Fig. 3.5 Algorithm modes

We shall discuss the algorithm modes in brief in the following sections.

Electronic Code Book (ECB) Mode Electronic Code Book (ECB) is the simplest mode of
operation. Here, the incoming plain text message is divided into blocks of 64 bits each. Each such block
is then encrypted independently of the other blocks. For all blocks in a message, the same key is used for
encryption. This process is shown in Fig. 3.6.

Plain text block 1 Plain text block 2 Plain text block n

Key Encrypt Key Encrypt ••• Key Encrypt

Cipher text block 1 Cipher text block 2 Cipher text block n

Step 1 Step 2 Step n

Fig. 3.6 ECB mode – The encryption process

At the receiver’s end, the incoming data is divided into 64-bit blocks and by using the same key as
was used for encryption, each block is decrypted to produce the corresponding plain text block. This
process is shown in Fig. 3.7.

Cipher text block 1 Cipher text block 2 Cipher text block n

Key Decrypt Key Decrypt ••• Key Decrypt

Plain text block 1 Plain text block 2 Plain text block n

Step 1 Step 2 Step n

Fig. 3.7 ECB mode – The decryption process

In ECB, since a single key is used for encrypting all the blocks of a message, if a plain text block
repeats in the original message, the corresponding cipher text block will also repeat in the encrypted
message. Therefore, ECB is suitable only for encrypting small messages, where the scope for repeating
the same plain text block is quite less.

Cipher Block Chaining (CBC) Mode We saw that in the case of ECB, within a given message (i.e.
for a given key), a plain text block always produces the same cipher text block. Thus, if a block of plain
text occurs more than once in the input, the corresponding cipher text block will also occur more than
once in the output, thus providing some clues to a cryptanalyst. To overcome this problem, the Cipher
Block Chaining (CBC) mode ensures that even if a block of plain text repeats in the input, these two (or
more) identical plain text blocks yield totally different cipher text blocks in the output. For this, a
feedback mechanism is used, as we shall learn in the following paragraphs.
Chaining adds a feedback mechanism to a block cipher. In Cipher Block Chaining (CBC), the results
of the encryption of the previous block are fed back into the encryption of the current block. That is, each
block is used to modify the encryption of the next block. Thus, each block of cipher text is dependent on
the corresponding current input plain text block, as well as all the previous plain text blocks.
The encryption process of CBC is depicted in Fig. 3.8 and described thereafter.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

IV Plain text block 1 Plain text block 2 Plain text block n

XOR XOR XOR

•••
Key Encrypt Key Encrypt Key Encrypt

Cipher text block 1 Cipher text block 2 Cipher text block n

Step 1 Step 2 Step n

Fig. 3.8 CBC mode – The encryption process

1. As shown in the figure, the first step receives two inputs: the first block of plain text and a random
block of text, called as Initialization Vector (IV).
(a) The IV has no special meaning: it is simply used to make each message unique. Since the
value of IV is randomly generated, the likelihood of it repeating in two different messages
is quite rare. Consequently, IV helps in making the cipher text somewhat unique or at least
quite different from all the other cipher texts in a different message. Interestingly, it is not
mandatory to keep IV secret – it can be known to everybody. This seems slightly
concerning and confusing. However, if we re-look at the operation of CBC, we will realize
that IV is simply one of the two inputs to the first encryption step. The output of Step 1 is
Cipher text block 1, which is also one of the two inputs to the second encryption step. In
other words, Cipher text block 1 is also an IV for Step 2! Similarly, Cipher text block 2 is
also an IV for Step 3 and so on. Since all these cipher text blocks will be sent to the
receiver, we are actually anyway sending all IVs for Step 2 onwards! Thus, there is no
special reason why the IV for Step 1 should be kept secret. It is the key used for encryption
is what needs to be kept secret. However, in practice, for maximum security, both the key
and the IV are kept secret.
(b) The first block of cipher text and IV are combined using XOR and then encrypted using a
key to produce the first cipher text block. The first cipher text block is then provided as a
feedback to the next plain text block, as explained below.
2. In the second step, the second plain text block is XORed with the output of Step 1, i.e. the first
cipher text block. It is then encrypted with the same key, as used in Step 1. This produces cipher
text block 2.
3. In the third step, the third plain text block is XORed with the output of Step 2, i.e. the second cipher
text block. It is then encrypted with the same key, as used in Step 1.
4. This process continues for all the remaining plain text blocks of the original message.
Remember that the IV is used only in the first plain text block. However, the same key is used for
encryption of all plain text blocks.
The decryption process works as follows.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

1. The Cipher text block 1 is passed through the decryption algorithm using the same key, which was
used during the encryption process for all the plain text blocks. The output of this step is then
XORed with the IV. This process yields Plain text block 1.
2. In Step 2, the Cipher text block 2 is decrypted and its output is XORed with Cipher text block 1,
which yields Plain text block 2.
3. This process continues for all the Cipher text blocks in the encrypted message.
The decryption process is shown in Fig. 3.9.

Appendix A provides some more mathematical details about the CBC mode.

Cipher Feedback (CFB) Mode Not all applications can work with blocks of data. Security is also
required in applications that are character-oriented. For instance, an operator can be typing keystrokes at
a terminal, which need to be immediately transmitted across the communications link in a secure
manner, i.e. by using encryption. In such situations, stream cipher must be used. The Cipher Feedback
(CFB) mode is useful in such cases. In this mode, data is encrypted in units that are smaller (e.g. they
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
94 Cryptography and Network Security

Cipher text block 1 Cipher text block 2 Cipher text block n

•••
Key Decrypt Key Decrypt Key Decrypt

XOR XOR XOR

Plain text block 1 Plain text block 2 Plain text block n

Step 1 Step 2 Step n

Fig. 3.9 CBC mode – The decryption process

could be of size 8 bits, i.e. the size of a character typed by an operator) than a defined block size (which
is usually 64 bits).
Let us understand how CFB mode works, assuming that we are dealing with j bits at a time (as we
have seen, usually, but not always, j = 8). Since CFB is slightly more complicated as compared to the
first two cryptography modes, we shall study CFB in a step-by-step fashion.
Step 1: Like CBC, a 64-bit Initialization Vector (IV) is used in the case of CFB mode. The IV is kept
in a shift register. It is encrypted in the first step to produce a corresponding 64-bit IV cipher text. This is
shown in Fig. 3.10.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

IV Encrypt Encrypted IV

Key

Fig. 3.10 CFB – Step 1

Step 2: Now, the leftmost (i.e. the most significant) j bits of the encrypted IV are XORed with the first
j bits of the plain text. This produces the first portion of cipher text (say C) as shown in Fig. 3.11. C is
then transmitted to the receiver.
Step 3: Now, the bits of IV (i.e. the contents of the shift register containing IV) are shifted left by j
positions. Thus the rightmost j positions of the shift register now contain unpredictable data. These
rightmost j positions are now filled with C. This is shown in Fig. 3.12.

First j bits of the First j bits of the

Encrypted IV plain text

XOR

Cipher text 1
(C)

Fig. 3.11 CFB – Step 2

Left shift IV by j
positions IV

Move j bits of C into the

rightmost side of IV IV C

Fig. 3.12 CFB – Step 3

Step 4: Now, Steps 1 through 3 continue until all the plain text units are encrypted. That is, the
following Steps repeat:
• IV is encrypted.
• The leftmost j bits resulting from this encryption process are XORed with the next j bits of the
plain text.
• The resulting cipher text portion (i.e. the next j bits of cipher text) is sent to the receiver.
• The shift register containing the IV is left-shifted by j bits.
• The j bits of the cipher text are inserted from right into the shift register containing the IV.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Figure 3.13 shows the overall conceptual view of the CFB mode.
At the receiver’s end, the decryption process is pretty similar, with minor changes. We shall not
discuss it.

Output Feedback (OFB) Mode The Output Feedback (OFB) mode is extremely similar to the
CFB. The only difference is that in the case of CFB, the cipher text is fed into the next stage of
encryption process. But in the case of OFB, the output of the IV encryption process is fed into the next
stage of encryption process. Therefore, we shall not describe the details of OFB and instead, shall simply
draw the block diagram of the OFB process, as shown in Fig. 3.14. The same details as discussed in CFB
apply here, excepting the change, as pointed out above.
Let us summarize the key advantage of the OFB mode. In simple terms, we can state that in this mode,
if there are errors in individual bits, they remain errors in individual bits and do not corrupt the whole
message. That is, bit errors do not get propagated. If a cipher text bit Ci is in error, only the decrypted
value corresponding to this bit, i.e. Pi is wrong. Other bits are not affected. Remember that in contrast to
this, in the CFB mode, the cipher text bit Ci is fed back as input to the shift register and would corrupt the
other bits in the message!
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
96 Cryptography and Network Security

IV IV IV
(Shift register) (Shift register) (Shift register)

•••

Key Encrypt Key Encrypt Key Encrypt

Take just the Take just the Take just the

leftmost 8 bits leftmost 8 bits leftmost 8 bits

XOR XOR XOR

Plain text j Plain text j Plain text j

bits bits bits

Cipher text Cipher text Cipher text

j bits j bits j bits

Fig. 3.13 CFB – The overall encryption process

IV IV IV
(Shift register) (Shift register) (Shift register)

•••

Key Encrypt Key Encrypt Key Encrypt

Take just the Take just the Take just the

leftmost 8 bits leftmost 8 bits leftmost 8 bits
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

XOR XOR XOR

Plain text j Plain text j Plain text j

bits bits bits

Cipher text Cipher text Cipher text

j bits j bits j bits

Fig. 3.14 OFB – The overall encryption process

The possible drawback with OFB is that an attacker can make necessary changes to the cipher text
and the checksum of the message in a controlled fashion. These causes change the cipher text without it
getting detected. In other words, the attacker changes both the cipher text and the checksum at the same
time, hence there is no way to detect this change.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
Symmetric Key Algorithms and AES 97

Counter (CTR) Mode The Counter (CTR) mode is quite similar to the OFB mode, with one
variation. It uses sequence numbers called as counters as the inputs to the algorithm. After each block is
encrypted, to fill the register, the next counter value is used. Usually, a constant is used as the initial
counter value and is incremented (usually by 1) for every iteration. The size of the counter block is the
same as that of the plain text block.
For encryption, the counter is encrypted and then XORed with the plain text block to get the cipher
text. No chaining process is used. On the other hand, for decryption, the same sequence of counters is
used. Here, each encrypted counter is XORed with the corresponding cipher text block to obtain the
original plain text block.
The overall operation of the Counter mode is shown in Fig. 3.15 and Fig. 3.16.

Counter Counter + 1 Counter + n – 1

Key Encrypt Key Encrypt ••• Key Encrypt

XOR XOR XOR

Plain text Plain text Plain text

(P1) (P2) (Pn)

Cipher text block 1 Cipher text block 2 Cipher text block n

Step 1 Step 2 Step n

Fig. 3.15 Counter (CTR) mode: The encryption process

Counter Counter + 1 Counter + n – 1

Key Encrypt Key Encrypt ••• Key Encrypt

XOR XOR XOR

Cipher text Cipher text Cipher text

(C1) (C2) (Cn)

Plain text block 1 Plain text block 2 Plain text block n

Step 1 Step 2 Step n

Fig. 3.16 Counter (CTR) mode: The decryption process

The encryption or decryption process in Counter can be done in parallel on multiple text blocks, since
no chaining is involved. This can make the execution speed of Counter faster. Multiprocessing systems
can take advantage of this feature to introduce features that help reduce the overall processing time. Pre-
processing can be achieved to prepare the output of the encryption boxes that input to the XOR
operations. The Counter mode mandates implementation of the encryption process only and not of the
decryption process.
Table 3.1 summarizes the key features of the various algorithm modes.

Table 3.1 Algorithm Modes: Details and Usage

Algorithm mode Details Usage

Electronic Code Book (ECB) The same key independently Transmitting a single value in a
encrypts blocks of text, 64 bits secure fashion (e.g. password or key
at a time. used for encryption)
Cipher Block Chaining (CBC) 64 bits cipher text from the Encrypting blocks of text
previous step and 64 bits plain
text of the next step are XORed Authentication
together.
Cipher Feedback (CFB) K bits of randomized cipher text Transmitting encrypted stream of data
from the previous step and K bits
plain text of the next step are Authentication
XORed together.
Output Feedback (OFB) Similar to CFB, except that the Transmitting encrypted stream of data
input to the encryption step is the
preceding DES output.
Counter (CTR) A counter and plain text block are Block-oriented transmissions
encrypted together, after which the
counter is incremented. Applications needing high speed

Table 3.2 summarizes the key advantages and disadvantages of the various modes.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

3.3 An Overview of Symmetric Key

Cryptography
Let us briefly review Symmetric Key Cryptography. Symmetric Key Cryptography is referred to by
various other terms, such as Secret Key Cryptography or Private Key Cryptography. In this scheme,
only one key is used and the same key is used for both encryption and decryption of messages.
Obviously, both the parties must agree upon the key before any transmission begins and nobody else
should know about it. Figure 3.17 shows how symmetric key cryptography works. Basically at the
sender’s end (A), the key transforms the plain text message into a cipher text form. At the receiver’s end
(B), the same key is used to decrypt the encrypted message, thus deriving the original message out of it.
As we have discussed, in practical situations, symmetric key cryptography has a few problems. We
shall now revise them quickly.

Table 3.2 Advantages and Disadvantages of the various modes

Feature ECB CBC CFB OFB/Counter

Security-related Plain text patterns Plain text blocks Plain text blocks Plain text is easy to
problems are not hidden. can be removed can be removed manipulate.
from the beginning from the beginning Altering cipher text
Input to the block and end of the and end of the alters plain text
cipher is the same message and bits message and bits directly.
as the plain text and of the first block of the first block
is not randomized. can be altered. can be altered.

Plain text is easy

to manipulate,
blocks of text
can be removed,
repeated or
exchanged.

Security-related The same key can be XOR of plain text Plain text patterns Plain text patterns
advantages used for encrypting with previous are hidden. are hidden.
multiple messages. cipher text block
hides the plain text. The same key can The same key can
be used for encryp- be used for
The same key can ting multiple encrypting multiple
be used for encryp- messages, by using messages, by using
ting multiple a different IV. a different IV.
messages.
Input to the block Input to the block
cipher is randomized. cipher is
randomized.
Problems related Size of cipher text Size of cipher text Size of cipher text Size of cipher text
to effectiveness is more than the is more than the is the same as that is the same as that
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

plain text size by plain text size by of the plain text of the plain text
one padding block. one block. size. size.

Pre-processing is Pre-processing is Parallelism cannot Parallelism cannot

not possible. not possible. be introduced in be introduced
encryption. (OFB only).
Parallelism cannot
be introduced in
encryption.

The first problem here is that of key agreement or key distribution. The problem is: in the first place,
how do two parties agree on a key? One solution is that somebody from the sender’s end physically
visits the receiver and hand over the key. Another way is to courier a paper on which the key is written.
Both are not exactly very convenient. A third way is to send the key over the network to B and ask for the
confirmation. But then, if an intruder gets the message, he can interpret all the subsequent ones!

Sender Receiver
(A) (B)

Network
Plain Cipher Cipher Plain
text text text text

Encrypt Decrypt
with with
symmetric symmetric
key key

Fig. 3.17 Symmetric key cryptography

The second problem is equally serious. Since the same key is used for encryption and decryption, one
key per communicating parties is required. Suppose A wants to securely communicate with B and also
with C. Clearly, there must be one key for all communications between A and B; and there must be
another, distinct key for all communications between A and C. The same key as used by A and B cannot
be used for communications between A and C. Otherwise, there is a chance that C can interpret
messages going between A and B or B can do the same for messages going between A and C! Since the
Internet has thousands of merchants selling products to hundreds of thousands of buyers, using this
scheme would be impractical because every buyer-seller combination would need a separate key!
Regardless, because these drawbacks can be overcome using intelligent solutions as we shall see and
also because symmetric key cryptography has several advantages as well, it is widely used in practice.
However, we shall first discuss the most popular computed-based symmetric key cryptographic
algorithms and think about solving the problems associated when we discuss asymmetric key
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

cryptography subsequently.

3.4 Data Encryption Standard (DES)

3.4.1 Background and History
The Data Encryption Standard (DES), also called as the Data Encryption Algorithm (DEA) by ANSI
and DEA-1 by ISO, has been a cryptographic algorithm used for over three decades. Of late, DES has
been found vulnerable against very powerful attacks and therefore, the popularity of DES has been
slightly on the decline. However, no book on security is complete without DES, as it has been a
landmark in cryptographic algorithms. We shall also discuss DES at length to achieve two objectives:
Firstly to learn about DES, but secondly and more importantly, to dissect and understand a real-life
cryptographic algorithm. Using this philosophy, we shall then discuss some other cryptographic
algorithms, but only at a conceptual level; because the in-depth discussion of DES would have already
helped us understand in depth, how computer-based cryptographic algorithms work. DES is generally
used in the ECB, CBC or the CFB mode.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
Symmetric Key Algorithms and AES 101

The origins of DES go back to 1972, when in the US, the National Bureau of Standards (NBS), now
known as the National Institute of Standards and Technology (NIST) embarked upon a project for
protecting the data in computers and computer communications. They wanted to develop a single
cryptographic algorithm. After two years, NBS realized that IBM’s Lucifer could be considered as a
serious candidate, rather than developing a fresh algorithm from scratch. After a few discussions, in
1975, the NBS published the details of the algorithm. Towards the end of 1976, the US Federal
Government decided to adopt this algorithm and soon, it was renamed as Data Encryption Standard
(DES). Soon, other bodies also recognized and adopted DES as a cryptographic algorithm.

3.4.2 How DES Works

Basic Principles DES is a block cipher. It encrypts data in blocks of size 64 bits each. That is, 64 bits
of plain text goes as the input to DES, which produces 64 bits of cipher text. The same algorithm and key
are used for encryption and decryption, with minor differences. The key length is 56 bits. The basic idea
is shown in Fig. 3.18.

64-bit 64-bit 64-bit

Plain text Plain text Plain text
...

56-bit Key 56-bit Key 56-bit Key

DES DES DES

64-bit 64-bit 64-bit

Cipher text Cipher text Cipher text

Block 1 Block 2 Block n

Fig. 3.18 The conceptual working of DES

We have mentioned that DES uses a 56-bit key. Actually, the initial key consists of 64 bits. However,
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

before the DES process even starts, every eighth bit of the key is discarded to produce a 56-bit key. That
is, bit positions 8, 16, 24, 32, 40, 48, 56 and 64 are discarded. This is shown in Fig. 3.19 with shaded bit
positions indicating discarded bits. (Before discarding, these bits can be used for parity checking to
ensure that the key does not contain any errors.)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
th
Fig. 3.19 Discarding of every 8 bit of the original key (Shaded bit positions are discarded)
Thus, the discarding of every 8th bit of the key produces a 56-bit key from the original 64-bit key, as
shown in Fig. 3.20.

Simplistically, DES is based on the two fundamental

attributes of cryptography: substitution (also called as Original 64-bit Key
confusion) and transposition (also called as diffusion). DES
consists of 16 steps, each of which is called as a round. Each
round performs the steps of substitution and transposition. Let Key discarding process
us now discuss the broad-level steps in DES.
1. In the first step, the 64-bit plain text block is handed over Resulting 56-bit Key
to an Initial Permutation (IP) function.
2. The Initial Permutation is performed on plain text.
Fig. 3.20 Key discarding process
3. Next, the Initial Permutation (IP) produces two halves of
the permuted block; say Left Plain Text (LPT) and Right Plain Text (RPT).
4. Now, each of LPT and RPT go through 16 rounds of encryption process.
5. In the end, LPT and RPT are rejoined and a Final Permutation (FP) is performed on the
combined block.
6. The result of this process produces 64-bit cipher text.
This process is shown diagrammatically in Fig. 3.21.

Step 1 Plain text (64 bits)

Initial Permutation
Step 2
(IP)

Step 3 LPT RPT

Step 4 Key 16 16 Key

rounds rounds
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Final Permutation
Step 5
(FP)

Step 6 Cipher text (64 bits)

Fig. 3.21 Broad level steps in DES

Let us now understand each of these processes in detail.

Initial Permutation (IP) As we have noted, the Initial Permutation (IP) happens only once and it
happens before the first round. It suggests how the transposition in IP should proceed, as shown in
Fig. 3.22. For example, it says that the IP replaces the first bit of the original plain text block with the 58th

Bit position in the plain text block To be overwritten with the contents of this bit position
1 58
2 60
3 42
.. ..
64 7

Fig. 3.22 Idea of IP

bit of the original plain text block, the second bit with the 50th bit of the original plain text block and so
on. This is nothing but jugglery of bit positions of the original plain text block.
The complete transposition table used by IP is shown in Fig. 3.23. This table (and all others in this
chapter) should be read from left to right, top to bottom. For instance, we have noted that 58 in the first
position indicates that the contents of the 58th bit in the original plain text block will overwrite the
contents of the 1st bit position, during IP. Similarly, 1 is shown at the 40th position in the table, which
means that the first bit will overwrite the 40th bit in the original plain text block. The same rule applies
for all the other bit positions.

58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6 64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1 59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

Fig. 3.23 Initial Permutation (IP) table

As we have noted, after IP is done, the resulting 64-bit permuted text block is divided into two half
blocks. Each half block consists of 32 bits. We have called the left block as LPT and the right block as
RPT. Now, 16 rounds are performed on these two blocks. This process is described as follows.

Rounds Each of the 16 rounds, in turn, consists of the broad level steps outlined in Fig. 3.24.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Key Transformation

Expansion Permutation

S-Box Substitution

P-Box Permutation

XOR and Swap

Fig. 3.24 Details of one round in DES

Let us discuss these details step-by-step.

Step 1: Key transformation We have noted that the initial 64-bit key is transformed into a 56-bit key
by discarding every 8th bit of the initial key. Thus, for each round, a 56-bit key is available. From this 56-
bit key, a different 48-bit sub-key is generated during each round using a process called as key
transformation. For this, the 56-bit key is divided into two halves, each of 28 bits. These halves are
circularly shifted left by one or two positions, depending on the round. For example, if the round number
is 1, 2, 9 or 16, the shift is done by only position. For other rounds, the circular shift is done by two
positions. The number of key bits shifted per round is shown in Fig. 3.25.

Round 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Number of key
1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
bits shifted

Fig. 3.25 Number of key bits shifted per round

After an appropriate shift, 48 of the 56 bits are selected. For selecting 48 of the 56 bits, the table
shown in Fig. 3.26 is used. For instance, after the shift, bit number 14 moves into the first position, bit
number 17 moves into the second position and so on. If we observe the table carefully, we will realize
that it contains only 48 bit positions. Bit number 18 is discarded (we will not find it in the table), like 7
others, to reduce the 56-bit key to a 48-bit key. Since the key transformation process involves
permutation as well as selection of a 48-bit sub-set of the original 56-bit key, it is called as compression
permutation.

14 17 11 24 1 5 3 28 15 6 21 10
23 19 12 4 26 8 16 7 27 20 13 2
41 52 31 37 47 55 30 40 51 45 33 48
44 49 39 56 34 53 46 42 50 36 29 32

Fig. 3.26 Compression permutation

Because of this compression permutation technique, a different subset of key bits is used in each
round. That makes DES not so easy to crack.
Step 2: Expansion permutation Recall that after Initial Permutation, we had two 32-bit plain text
areas, called as Left Plain Text (LPT) and Right Plain Text (RPT). During expansion permutation, the
RPT is expanded from 32 bits to 48 bits. Besides increasing the bit size from 32 to 48, the bits are
permuted as well, hence the name expansion permutation. This happens as follows:
1. The 32-bit RPT is divided into 8 blocks, with each block consisting of 4 bits. This is shown in
Fig. 3.27.
2. Next, each 4-bit block of the previous step is then expanded to a corresponding 6-bit block. That is,
per 4-bit block, 2 more bits are added. What are these two bits? They are actually the repeated first
and the fourth bits of the 4-bit block. The second and the third bits are written down as they were in
the input. This is shown in Fig. 3.28. Note that the first bit inputted is outputted to the second
output position and also repeats in output position 48. Similarly, the 32nd input bit is found in the
47th output position as well as in the first output position.

Original Right Plain Text (RPT) of 32 bits

···

Block 1 (4 bits) Block 2 (4 bits) Block 8 (4 bits)

Fig. 3.27 Division of 32-bit RPT into eight 4-bit blocks

Input Block 1 (4 bits) Input Block 2 (4 bits) Input Block 3 (4 bits)

1 2 3 4 5 6 7 8 ... 29 30 31 32

1 2 3 4 5 6 7 8 9 10 11 12 43 44 45 46 47 48

Output Block 1 (6 bits) Output Block 2 (6 bits) Output Block 8 (6 bits)

Fig. 3.28 RPT expansion permutation process

Clearly, this process results into expansion as well as permutation of the input bits while creating the
output.
As we can see, the first input bit goes into the second and the 48th output positions. The second input
bit goes into the third output position and so on. Consequently, we will observe that the expansion
permutation has actually used the table shown in Fig. 3.29.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

32 1 2 3 4 5 4 5 6 7 8 9
8 9 10 11 12 13 12 13 14 15 16 17
16 17 18 19 20 21 20 21 22 23 24 25
24 25 26 27 28 29 28 29 30 31 32 1

Fig. 3.29 RPT expansion permutation table

As we have seen, firstly, the Key transformation process compresses the 56-bit key to 48 bits. Then,
the Expansion permutation process expands the 32-bit RPT to 48 bits. Now, the 48-bit key is XORed
with the 48-bit RPT and the resulting output is given to the next step, which is the S-box Substitution
(which we shall discuss in the next section) as shown in Fig. 3.30.
Step 3: S-box substitution S-box substitution is a process that accepts the 48-bit input from the
XOR operation involving the compressed key and expanded RPT and produces a 32-bit output using the

Key Transformation Expansion Permutation

(Compress key from 56 bits to (Expand RPT from 32 bits to
48 bits) 48 bits)

48-bit Key XOR 48-bit RPT

S-box Substitution

Fig. 3.30 Way to S-box substitution

substitution technique. The substitution is performed by eight substitution boxes (also called as S-
boxes). Each of the eight S-boxes has a 6-bit input and a 4-bit output. The 48-bit input block is divided
into 8 sub-blocks (each containing 6 bits) and each such sub-block is given to an S-box. The S-box
transforms the 6-bit input into a 4-bit output, as shown in Fig. 3.31.

48-bit input block

6-bit sub-block 6-bit sub-block ··· 6-bit sub-block

S-box 1 S-box 2 S-box 8

4-bit output 4-bit output 4-bit output

32-bit output block

Fig. 3.31 S-box substitution

What is the logic used by S-box substitution for selecting only four of the six bits? We can
conceptually think of every S-box as a table that has 4 rows (numbered 0 to 3) and 16 columns
(numbered 0 to 15). Thus, we have 8 such tables, one for each S-box. At the intersection of every row
and column, a 4-bit number (which will be the 4-bit output for that S-box) is present. This is shown in
Fig. 3.32.

14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

Fig. 3.32 (a) S-box 1

15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10
3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5
0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15
13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9

Fig. 3.32 (b) S-box 2

10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8
13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1
13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7
1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

Fig. 3.32 (c) S-box 3

7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15
13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9
10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4
3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

Fig. 3.32 (d) S-box 4

2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9
14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6
4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14
11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

Fig. 3.32 (e) S-box 5

12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11
10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8
9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

Fig. 3.32 (f ) S-box 6

4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1
13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6
1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2
6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

Fig. 3.32 (g) S-box 7

13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7
1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2
7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8
2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11

Fig. 3.32 (h) S-box 8

The 6-bit input indicates which row and column and therefore, which intersection is to be selected
thus, determining the 4-bit output. How is it done? Let us assume that the six bits of a S-box are indicated
by b1, b2, b3, b4, b5 and b6. Now, bits b1 and b6 are combined to form a two-bit number. Two bits can
store any decimal number between 0 (binary 00) and 3 (binary 11). This specifies the row number. The
remaining four bits b2, b3, b4, b5 make up a four-bit number, which specifies the column number
between decimal 0 (binary 0000) and 15 (binary 1111). Thus, the 6-bit input automatically selects the
row number and column number for the selection of the output. This is shown in Fig. 3.33.

b1 b2 b3 b4 b5 b6

4-bit column number

2-bit row number

Fig. 3.33 Selecting an entry in a S-box based on the 6-bit input

Let us take an example now. Suppose the bits 5 to 8 of the 48-bit input (i.e. the input to the second S-
box) contain a value 101101 in binary. Therefore, using our earlier diagram, we have (b1, b6) = 11 in
binary (i.e. 3 in decimal) and (b2, b3, b4, b5) = 0110 in binary (i.e. 6 in decimal). Thus, the output of S-
box 2 at the intersection of row number 3 and column number 6 will be selected, which is 4. (Remember
to count rows and columns from 0, not 1). This is shown in Fig. 3.34.

1 0 1 1 0 1

1 0 1 1 0 1
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Column: 0110 in binary, 6 in decimal

Row: 11 in binary, 3 in decimal

Fig. 3.34 Example of selection of S-box output based on the input

The output of each S-box is then combined to form a 32-bit block, which is given to the last stage of
a round, the P-box Permutation, as discussed next.
Step 4: P-box permutation The output of S-box consists of 32 bits. These 32 bits are permuted using
a P-box. This straightforward permutation mechanism involves simple permutation (i.e. replacement of
each bit with another bit, as specified in the P-box table, without any expansion or compression). This is

called as P-box Permutation. The P-box is shown in Fig. 3.35. For example, a 16 in the first block
indicates that the bit at position 16 of the original input moves to bit at position 1 in the output and a 10
in the block number 16 indicates that the bit at the position 10 of the original input moves to bit at the
position 16 in the output.

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 10
2 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

Fig. 3.35 P-box permutation

Step 5: XOR and Swap Note that we have been performing all these operations only on the 32-bit
right half portion of the 64-bit original plain text (i.e. on the RPT). The left half portion (i.e. LPT) was
untouched so far. At this juncture, the left half portion of the initial 64-bit plain text block (i.e. LPT) is
XORed with the output produced by P-box permutation. The result of this XOR operation becomes the
new right half (i.e. RPT). The old right half (i.e. RPT) becomes the new left half, in a process of
swapping. This is shown in Fig. 3.36.

Original 64-bit Plain Text Block

32-bit Left Plain Text (LPT) Block 32-bit Right Plain Text (RPT) Block

1. Key Transformation
(not involved directly)
2. Expansion Permutation
3. S-box Substitution
4. P-box Permutation
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

XOR

32-bit Left Plain Text (LPT) Block 32-bit Right Plain Text (RPT) Block

Next round

Fig. 3.36 XOR and swap

Final Permutation At the end of the 16 rounds, the Final Permutation is performed (only once).
This is a simple transposition, based on Fig. 3.37. For instance, the 40th input bit takes the position of the
1st output bit and so on.

40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30 37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28 35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25

Fig. 3.37 Final permutation

The output of the Final Permutation is the 64-bit encrypted block.
DES decryption From the above discussion of DES, we might get a feeling that it is an extremely
complicated encryption scheme, therefore, the decryption using DES would employ a completely
different approach. To most people’s surprise, the same algorithm used for encryption in DES also works
for decryption! The values of the various tables and the operations as well as their sequence are so
carefully chosen that the algorithm is reversible. The only difference between the encryption and the
decryption process is the reversal of key portions. If the original key K was divided into K1, K2, K3, …,
K16 for the 16 encryption rounds, then for decryption, the key should be used as K16, K15, K14, …, K1.

Analyzing DES
Use of S-boxes The tables used for substitution, i.e. the S-boxes, in DES are kept secret by IBM. IBM
maintains that it took them over 17 person years to come up with the internal design of the S-boxes. Over
the years, suspicion has grown that there is some vulnerability in this aspect of DES, intentional (so that
the government agencies could secretly open encrypted messages) or otherwise. Several studies keep
appearing, which suggest that there is some scope for attacks on DES via the S-boxes. However, no
concrete example has emerged till date.
Key length We have mentioned earlier that any cryptographic system has two important aspects: the
cryptographic algorithm and the key. The inner workings of the DES algorithm (which we have
discussed earlier) are completely known to the general public. Therefore, the strength of DES lies only in
the other aspect - its key, which must be secret.
As we know, DES uses 56-bit keys. (Interestingly, the original proposal was to make use of 112-bit
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

keys.) Thus, there are 256 possible keys (which is roughly equal to 7.2 x 1016 keys). Thus, it seems that a
brute-force attack on DES is impractical. Even if we assume that to obtain the correct key, only half of
the possible keys (i.e. the half of the key space) needs to be examined and tried out, a single computer
performing one DES encryption per microsecond would require more than 1,000 years to break DES.
Differential and Linear cryptanalysis In 1990, Eli Biham and Adi Shamir introduced the concept
of differential cryptanalysis. This method looks at pairs of cipher text whose plain texts have particular
differences. The technique analyses the progress of these differences as the plain texts travel through the
various rounds of DES. The idea is to choose pairs of plain text with fixed differences. The two plain
texts can be chosen at random, as long as they satisfy specific difference conditions (which can be as
simple as XOR). Then, using the differences in the resulting cipher texts, assign different likelihood to
different keys. As more and more cipher text pairs are analysed, the correct key emerges.
Invented by Mitsuru Matsui, the linear cryptanalysis attack is based on linear approximations. If we
XOR some plain text bits together, XOR some cipher text bits together and then XOR the result, we will
get a single bit, which is the XOR of some of the key bits.
The descriptions of these attacks are quite complex and we will not discuss them here.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
Symmetric Key Algorithms and AES 111

Timing attacks Timing attacks refer more to asymmetric key cryptography. However, they can also
apply to symmetric key cryptography. The idea is simple: observe how long it takes for the
cryptographic algorithm to decrypt different blocks of cipher text. The idea is to try and obtain either the
plain text or the key used for encryption by observing these timings. In general, it would take different
amounts of time to decrypt different sized cipher text blocks.

3.4.3 Variations of DES

In spite of its strengths, it is generally felt that with the tremendous advances in computer hardware
(processing speeds of Gigahertz and more, high memory availability at cheap prices, parallel processing
capabilities, etc.), DES is susceptible to possible attacks. However, because DES is already proven to be
a very competent algorithm, it would be nice to reuse DES by making it stronger by some means, rather
than writing a new cryptographic algorithm. Writing a new algorithm is not easy, more so because it has
to be tested sufficiently so as to be proved as a strong algorithm. Consequently, two main variations of
DES have emerged, which are Double DES and Triple DES. Let us discuss them now.

Double DES Double DES is quite simple to understand. Essentially, it does twice what DES
normally does only once. Double DES uses two keys, say K1 and K2. It first performs DES on the
original plain text using K1 to get the encrypted text. It again performs DES on the encrypted text, but
this time with the other key, i.e. K2. The final output is the encryption of encrypted text (i.e. the original
plain text encrypted twice with two different keys). This is shown in Fig. 3.38.

Original Cipher Cipher

Encrypt Encrypt
Plain Text Text Text

K1 K2

Fig. 3.38 Double DES encryption

Of course, there is no reason why double encryption cannot be applied to other cryptographic
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

algorithms as well. However, in the case of DES, it is already quite popular, therefore, we have discussed
this in the context of DES. It should also be quite simple to imagine that the decryption process would
work in exactly the reverse order, as shown in Fig. 3.39.

Cipher Decrypt Cipher Decrypt Original

Text Text Plain Text

K2 K1

Fig. 3.39 Double DES decryption

The doubly encrypted cipher text block is first decrypted using the key K2 to produce the singly
encrypted cipher text. This cipher text block is then decrypted using the key K1 to obtain the original
plain text block.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
112 Cryptography and Network Security

If we use a key of just 1 bit, there are two possible keys (0 and 1). If we use a 2-bit key, there are four
possible key values (00, 01, 10 and 11). In general, if we use an n-bit key, the cryptanalyst has to perform
2n operations to try out all the possible keys. If we use two different keys, each consisting of n bits, the
cryptanalyst would need 22n attempts to crack the key. Therefore, on the face of it, we may think that
since the cryptanalysis for the basic version of DES requires a search of 256 keys, Double DES would
require a key search of (22*56) i.e. 2128 keys. However, it is not quite true. Merkle and Hellman
introduced the concept of the meet-in-the-middle attack. This attack involves encryption from one end,
decryption from the other and matching the results in the middle, hence the name meet-in-the-middle
attack. Let us understand how it works.
Suppose that the cryptanalyst knows two basic pieces of information: P (a plain text block) and C (the
corresponding final cipher text block) for a message. We know that the relations shown in Fig. 3.40 are
true for P and C, if we are using Double DES. The mathematical equivalents of these are also shown. The
result of the first encryption is called as T and is denoted as T = EK1 (P) [i.e. encrypt the block P with key
K1]. After this encrypted block is encrypted with another key K2, we denote the result as C =
EK2(EK1(P)) [i.e. encrypt the already encrypted block T, with a different key K2 and call the final cipher
text as C].

EK1(P) T = EK1(P) EK2(EK1(P)) C = EK2(EK1(P))

Temporary
P Encrypt Encrypt C
result (T)

K1 K2

Fig. 3.40 Double DES mathematically expressed

Now, the aim of the cryptanalyst, who is armed with the knowledge of P and C, is to obtain the values
of K1 and K2. What would the cryptanalyst do?
Step 1 For all possible values (256) of key K1, the cryptanalyst would use a large table in the memory
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

of the computer and perform the following two steps:

1. The cryptanalyst would encrypt the plain text block P by performing the first encryption operation,
i.e. EK1(P). That is, it will calculate T.
2. The cryptanalyst would store the output of the operation EK1(P), i.e. the temporary cipher text (T),
in the next available row of the table in the memory.
We show this process for the ease of understanding using a 2-bit key (actually, the cryptanalyst has to
do this using a 64-bit key, which makes the task a lot harder). Refer to Fig. 3.41.
Step 2 Thus, at the end of the above process, the cryptanalyst will have the table of cipher texts as
shown in the figure. Next, the cryptanalyst will perform the reverse operation. That is, she will now
decrypt the known cipher text C with all the possible values of K2 [i.e. perform DK2(C) for all possible
values of K2]. In each case, the cryptanalyst will compare the resulting value with all the values in the
table of cipher texts, which were computed earlier. This process (as before, for 2-bit key) is shown in
Fig. 3.42.

P
Table of
cipher
Possible Keys text (T)
(Key = K1)
00 Result = T

01 Result = T
Encrypt
10 Result = T
11 Result = T

Fig. 3.41 Conceptual view of the cryptanalyst’s encrypt operation

C For each Table of

result, do a cipher
Possible Keys table look up text (T)
(Key = K2)
00 Result = T
01 Result = T
Decrypt
10 Result = T
11 Result = T

Fig. 3.42 Conceptual view of the cryptanalyst’s decrypt operation

To summarize:
• In the first step, the cryptanalyst was calculating the value of T from the left hand side (i.e. encrypt
P with K1 to find T). Thus, here T = EK1(P).
• In the second step, the cryptanalyst was finding the value of T from the right hand side (i.e. decrypt
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

C with K2 to find T). Thus, here T = DK2(C).

From the above two steps, we can actually conclude that the temporary result (T) can be obtained in
two ways, either by encrypting P with K1 or by decrypting C with K2. This is because, we can write the
following equations:
T = EK1(P) = DK2(C)
Now, if the cryptanalyst creates a table of EK1(P) (i.e. table of T) for all the possible values of K1 and
then performs DK2(C) for all possible values of K2 (i.e. computes T), there is a chance that she gets the
same T in both the operations. If the cryptanalyst is able to find the same T for both encrypt with K1 and
decrypt with K2 operations, it means that the cryptanalyst knows not only P and C, but she has now also
been able to find out the possible values of K1 and K2!
She can now try this K1 and K2 pair on another known pair of P and C and if she is able to get the
same T by performing the EK1(P) and DK2(C) operations, she can then try to use K1 and K2 for the
remaining blocks of the message.

Clearly, this attack is possible, but requires a lot of memory. For an algorithm that uses 64-bit plain
text blocks and 56-bit keys, we would need 256 64-bit blocks to store the table of T in memory (there is
no point in storing it on the disk, as it would be too slow and defeat the very purpose of the attack). This
is equivalent to 1017 bytes, which is too high for the next few generations of computers!

Triple DES Although the meet-in-the-middle attack on Double DES is not quite practical yet, in
cryptography, it is always better to take the minimum possible chances. Consequently, Double DES
seemed inadequate, paving the way for Triple DES. As we can imagine, Triple DES is DES – three
times. It comes in two flavours: one that uses three keys and the other that uses two keys. We will study
both, one-by-one.
• Triple DES with three keys The idea of Triple DES with three keys is illustrated in Fig. 3.43. As
we can see, the plain text block P is first encrypted with a key K1, then encrypted with a second key K2
and finally with a third key, K3, where K1, K2 and K3 are all different from each other.

Original Cipher Final

Encrypt
Plain Text Text 1 Cipher Text

K1 Encrypt Cipher Encrypt

Text 2

K2 K3

Fig. 3.43 Triple DES with three keys

Triple DES with three keys is used quite extensively in many products, including PGP and S/MIME.
To decrypt the cipher text C and obtain the plain text P, we need to perform the operation P =
DK3(DK2(DK1(C))).
• Triple DES with two keys Triple DES with three keys is highly secure. It can be denoted in the
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

form of equation as C = EK3(EK2(EK1(P))). However, Triple DES with three keys also has the drawback
of requiring 56 x 3 = 168 bits for the key, which can be slightly difficult to have in practical situations. A
workaround suggested by Tuchman uses just two keys for Triple DES. Here, the algorithm works as
follows:
1. Encrypt the plain text with key K1. Thus, we have EK1(P).
2. Decrypt the output of Step 1 above with key K2. Thus, we have DK2(EK1(P)).
3. Finally, encrypt the output of Step 2 again with key K1. Thus, we have EK1(DK2(EK1(P))).
This is shown in Fig. 3.44.
To decrypt the cipher text C and obtain the original plain text P, we need to perform the operation P =
DK1(EK2(DK1(C))).
There is no special meaning attached to the second step of decryption. Its only significance is that it
allows Triple DES to work with two, rather than three keys. This is also called as Encrypt-Decrypt-
Encrypt (EDE) mode. Triple DES with two keys is not susceptible to the meet in the middle attack,
unlike Double DES as K1 and K2 alternate here.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
Symmetric Key Algorithms and AES 115

Original Cipher Final

Encrypt
Plain Text Text 1 Cipher Text

K1 Decrypt Cipher Encrypt

Text 2

K2 K1

Fig. 3.44 Triple DES with two keys

3.5 International Data Encryption

Algorithm (IDEA)
3.5.1 Background and History
The International Data Encryption Algorithm (IDEA) is perceived as one of the strongest
cryptographic algorithms. It was launched in 1990 and underwent certain changes in names and
capabilities as shown in Table 3.3.

Table 3. 3 Progress of IDEA

Year Name Description

1990 Proposed Encryption Standard (PES) Developed by Xuejia Lai and James Massey
at the Swiss Federal Institute of Technology
1991 Improved Proposed Encryption Standard (IPES) Improvements in the algorithm as a result of
cryptanalysts finding some areas of weakness
1992 International Data Encryption Algorithm (IDEA) No major changes, simply renamed
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Although it is quite strong, IDEA is not as popular as DES for two primary reasons. Firstly, it is
patented unlike DES and therefore, must be licensed before it can be used in commercial applications
Secondly DES has a long history and track record as compared to IDEA. However one popular email
privacy technology known as Pretty Good Privacy (PGP) is based on IDEA.

3.5.2 How IDEA Works

Basic Principles Technically, IDEA is a block cipher. Like DES, it also works on 64-bit plain text
blocks. The key is longer and consists of 128 bits. IDEA is reversible like DES, that is, the same
algorithm is used for encryption and decryption. Also, IDEA uses both diffusion and confusion for
encryption.
The working of IDEA can be visualized at a broad level as shown in Fig. 3.45. The 64-bit input plain
text block is divided into four portions of plain text (each of size 16 bits), say P1 to P4. Thus, P1 to P4 are
the inputs to the first round of the algorithm. There are eight such rounds. As we mentioned, the key

consists of 128 bits. In each round, six sub-keys are generated from the original key. Each of the sub-
keys consists of 16 bits. (Do not worry if you do not understand this. We shall discuss this in great detail
soon). These six sub-keys are applied to the four input blocks P1 to P4. Thus, for the first round, we will
have the six keys K1 to K6. For the second round, we will have keys K7 to K12. Finally, for the eighth
round, we will have keys K43 to K48. The final step consists of an Output Transformation, which uses
just four sub-keys (K49 to K52). The final output produced is the output produced by the Output
Transformation step, which is four blocks of cipher text named C1 to C4 (each consisting of 16 bits).
These are combined to form the final 64-bit cipher text block.

Input Plain Text (64 bits)

P1 (16 bits) P2 (16 bits) P3 (16 bits) P4 (16 bits)

K1
.
Round 1 .
K6

K7
.
Round 2 .
K12

···

K43
.
Round 8 .
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

K48

K49
.
Output Transformation .
K52

C1 (16 bits) C2 (16 bits) C3 (16 bits) C4 (16 bits)

Output Cipher Text (64 bits)

Fig. 3.45 Broad level steps in IDEA

Rounds We have mentioned that there are 8 rounds in IDEA. Each round involves a series of
operations on the four data blocks using six keys. At a broad level, these steps can be described as shown
in Fig. 3.46. As we can see, these steps perform a lot of mathematical actions. There are multiplications,
additions and XOR operations.

Step 1: Multiply* P1 and K1.

Step 2: Add* P2 and K2.

Step 3: Add* P3 and K3.

Step 4: Multiply* P4 and K4.

Step 5: XOR the results of Step 1 and Step 3.

Step 6: XOR the results of Step 2 and Step 4.

Step 7: Multiply* the results of Step 5 with K5.

Step 8: Add* the results of Step 6 and Step 7.

Step 9: Multiply* the results of Step 8 with K6.

Step 10: Add* the results of Step 7 and Step 9.

Step 11: XOR the results of Step 1 and Step 9.

Step 12: XOR the results of Step 3 and Step 9.

Step 13: XOR the results of Step 2 and Step 10.

Step 14: XOR the results of Step 4 and Step 10.

Fig. 3.46 Details of one round in IDEA

Note that we have put an asterisk in front of the words Add and Multiply, causing them to be shown as
Add* and Multiply*, respectively. The reason behind this is that these are not mere additions and
multiplications. Instead, these are addition modulo 216 (i.e. addition modulo 65536) and multiplication
modulo 216 + 1 (i.e. multiplication modulo 65537), respectively. [For those who are not conversant with
modulo arithmetic, if a and b are two integers, then a mod b is the remainder of the division a/b. Thus, for
example, 5 mod 2 is 1 (because the remainder of 5/2 is 1) and 5 mod 3 is 2 (because the remainder of 5/
3 is 2)].
Why is this required in IDEA and what does this mean? 1111111100000000
Let us examine the case of the normal binary addition with
an example. Suppose that we are in round 2 of IDEA.
Further, let us assume that P2 = 1111111100000000 and 1111111111000001
K2 = 1111111111000001. First, simply add them (and not
add* them!) and see what happens. The operation would
look like as shown in Fig. 3.47. 11111111011000001
As we can see, the normal addition will produce a
number that consists of 17 bits (i.e.11111111011000001). Fig. 3.47 Binary addition of two 16-bit
However, remember that we have only 16 bit positions numbers
available for the output of Round 2. Therefore, we must reduce this number (which is 130753 in
decimal) to a 16-bit number. For this, we take modulo 65536 of this. 130753 modulo 65536
yields 65217, which is 1111111011000001 in binary and is a 16-bit number, which fits well in our
scheme.
This should explain why modulo arithmetic is required in IDEA. It simply ensures that even if the
result of an addition or multiplication of two 16-bit numbers contains more than 16 bits, we bring it back
to 16 bits.
Let us now re-look at the details of one round in a more symbolic fashion, as shown in Fig. 3.48. It
conveys the same meaning as the earlier diagram, but is more symbolic than verbose in nature. We have
depicted the same steps as earlier. The input blocks are shown as P1 to P4, the sub-keys are denoted by
K1 to K6 and the output of this step is denoted by R1 to R4 (and not C1 to C4, because this is not the final
cipher text – it is an intermediate output, which will be processed in further rounds as well as in the
Output Transformation Step).
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Sub-key Generation for a Round We have been talking about sub-keys in our discussion quite
frequently. As we mentioned, each of the eight rounds makes use of six sub-keys (so, 8 ¥ 6 = 48 sub-keys
are required for the rounds) and the final Output Transformation uses four sub-keys (making a total of 48
+ 4 = 52 sub-keys overall). From an input key of 128 bits, how are these 52 sub-keys generated? Let us
understand this with the explanation for the first two rounds. Based on the understanding of the sub-key
generation process for the first two rounds, we will later tabulate the sub-key generation for all the
rounds.
• First round We know that the initial key consists of 128 bits, from which 6 sub-keys K1 to K6 are
generated for the first round. Since K1 to K6 consist of 16 bits each, out of the original 128 bits, the first
96 bits (6 sub-keys ¥ 16 bits per sub-key) are used for the first round. Thus, at the end of the first round,
bits 97-128 of the original key are unused. This is shown in Fig. 3.49.

P1 P2 P3 P4

K1 Multiply* Add* K3

K2 Add* Multiply* K4

XOR

K5 Multiply*

Add*

Multiply* K6

Add* XOR

XOR

XOR XOR
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

R1 R2 R3 R4

Fig. 3.48 One round of IDEA

• Second round In the second round, firstly, the 32 unused bits (i.e. bits 97-128) of the first round are
used. We know that each round requires 6 sub-keys K1 to K6, each of 16 bits, making a total of 96 bits.
Thus, for the second round, we still require (96 – 32 = 64) more bits. However, we have already
exhausted all the 128 bits of the original key. How do we now get the remaining 64 bits? For this, IDEA
employs the technique of key shifting. At this stage, the original key is shifted left circularly by 25 bits.
That is, the 26th bit of the original key moves to the first position and becomes the first bit after the shift
and the 25th bit of the original key moves to the last position and becomes the 128th bit after the shift. The
whole process is shown in Fig. 3.50.

Original Key (128 bits)

K1 (Bits 1-16) K2 (Bits 17-32) ·· K6 (Bits 81-96) Unused (Bits 97-128)

Fig. 3.49 Sub-key generation for round 1

These 32 bits are used now. Bits 97-112 become K1. bits
Unused (Bits 97-128)
113-128 become K2. The key is exhausted now.

K1 (Bits 97-112) K2 (Bits 113-128)

Sub-keys K1 and K2 are ready for round 2. Now, the original key is
exhausted. It is circular-left shifted by 25 bits.

Position 1 Position 128

Original Key (128 bits)

Circular-left shift by 25 bits

We now start allocating fresh sub-keys from K3 to K6. As we can see,

the first 64 bytes would give us these four sub-keys (K3 to K6), each one
consisting of 16 bits.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Position 1 (after shift) Position 128 (after shift)

New Key (128 bits)

K3 (Bits 1-16) ·· K6 (Bits 49-64) Unused

(Bits 65-128)

Fig. 3.50 Circular-left key shift and its use in sub-key generation for round 2

We can now see that the second round uses the bits 97-128 of the first round, and after a 25-bit shift
bits 1-64. For the third round, we then use the remaining bits, i.e. bits 65-128 (i.e. a total of 64 bits).
Again a shift on 25 bits occurs, and post this shifting, bits 1-32 are used in the third round, and so on.

Thus, is every round, 96 bits are obtained in the same manner, and this is how a 128-bit Key is divided
into 96-bit subkeys.

Table 3.4 Sub-key Generation Process for Each Round

Round Details of the sub-key generation and use

1 Bit positions 1-96 of the initial 128-bit key would be used. This would give us 6 sub-keys K1 to K6
for Round 1. Key bits 97 to 128 are available for the next round.

2 Key bits 97 to 128 make up sub-keys K1 and K2 for this round. A 25-bit shift on the original key
happens, as explained. Post this shifting; the first 64 bits are used as sub-keys K3 to K6 for this
round. This leaves bits 65 to 128 unused for the next round.

3 Unused key bits 65 to 128 are used as sub-keys K1 to K4 of this round. Upon key exhaustion,
another 25-bit shift happens, and bits 1 to 32 of the shifted key are used as sub-keys K5 and K6.
This leaves bits 33 to 128 unused for the next round.

4 Bits 33 to 128 are used for this round, which is perfectly adequate. No bits are unused at this stage.
After this, the current key is again shifted.

5 This is similar to Round 1. Bit positions 1-96 of the current 128-bit key would be used. This would
give us 6 sub-keys K1 to K6 for Round 1. Key bits 97 to 128 are available for the next round.

6 Key bits 97 to 128 make up sub-keys K1 and K2 for this round. A 25-bit shift on the original key
happens, as explained. Post this shifting; the first 64 bits are used as sub-keys K3 to K6 for this
round. This leaves bits 65 to 128 unused for the next round.

7 Unused key bits 65 to 128 are used as sub-keys K1 to K4 of this round. Upon key exhaustion,
another 25-bit shift happens, and bits 1 to 32 of the shifted key are used as sub-keys K5 and K6.
This leaves bits 33 to 128 unused for the next round.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

8 Bits 33 to 128 are used for this round, which is perfectly adequate. No bits are unused at this stage.
After this, the current key is again shifted for the Output Transformation round.

At the end of the last round, we have no unused bits. They are used in the Output Transformation.

Output Transformation The Output Transformation is a one-time operation. It takes place at the
end of the 8th round. The input to the Output Transformation is, of course, the output of the 8th round.
This is, as usual, a 64-bit value divided into four sub-blocks (say R1 to R4, each consisting of 16 bits).
Also, four sub-keys are applied here and not six. We will describe the key generation process for the
Output Transformation later. For now, we shall assume that four 16-bit sub-keys K1 to K4 are available
to the Output Transformation. The process of the Output Transformation is described in Fig. 3.51.

Step 1: Multiply* R1 and K1.

Step 2: Add* R 2 and K2.

Step 3: Add* R 3 and K3.

Step 4: Multiply* R4 and K4.

Fig. 3.51 Details of the output transformation

This process can be shown diagrammatically as illustrated by Fig. 3.52. The output of this process is
the final 64-bit cipher text, which is the combination of the four cipher text sub-blocks C1 to C4.

R1 R2 R3 R4

K1 Multiply* Add* K3

K2 Add* Multiply* K4

C1 C2 C3 C4

Output Cipher Text (64 bits)

Fig. 3.52 Output transformation process

Sub-key Generation for the Output Transformation The process for the sub-key generation for
the Output Transformation is exactly similar to the sub-key generation process for the eight rounds.
Recall that at the end of the eighth and the final round, the key was exhausted. Hence, the key is again
shifted by 25 bits. Post this shift operation, the first 64 bits of the key are taken, and are called as sub-
keys K1 to K4 for the final output Transformation round.

IDEA Decryption The decryption process is exactly the same as the encryption process. There are
some alterations in the generation and pattern of sub-keys. The decryption sub-keys are actually
inverses of the encryption sub-keys. We shall not discuss this any further, as the basic concepts remain
the same.

The Strength of IDEA IDEA uses a 128-bit key, which is double than the key size of DES. Thus, to
break into IDEA, 2128 (i.e. 1038) encryption operations would be required. As before, even if we assume
that to obtain the correct key, only half of the possible keys (i.e. the half of the key space) needs to be
examined and tried out, a single computer performing one IDEA encryption per microsecond would
require more than 5400000000000000000000000 years to break IDEA!

3.6 RC4
3.6.1 Background
RC4 was designed by Ron Rivest of RSA Security in 1987. The official name for this algorithm is
“Rivest Cipher 4”. However, because of its ease of reference, the acronym RC4 has stuck.
RC4 is a stream cipher. This means that the encryption happens byte-by-byte. However, this can be
changed to bit-by-bit encryption (or to a size other than a byte/bit).
RC4 was initially kept secret. However, in September 1994, a description of the algorithm was
anonymously posted to the Cypherpunks mailing list. Thereafter, it was posted on the sci.crypt
newsgroup and from there to many other Internet sites. Because the algorithm is now well known, it is no
longer a secret. However, we should note that there is a trademark associated with the name “RC4”.
An interesting remark says that “The current status seems to be that unofficial implementations are
legal, but cannot use the RC4 name.”
RC4 has become part of some widely used encryption techniques and standards, including Wireless
Equivalent Privacy (WEP) and WPA for wireless cards and TLS. What has made its wide deployment
possible is its speed and simplicity of design. Implementations in both software and hardware are
possible. RC4 does not consume many resources.

3.6.2 Description
RC4 generates a pseudorandom stream of bits called as keystream. This is combined with the plain text
using XOR for encryption. Even decryption is performed in a similar manner.
Let us understand this in more detail in the following paragraphs..
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

There is a variable length key consisting of 1 to 256 bytes (or 8 to 2048 bits). This key is used to
initialize a 256-byte state vector with elements identified as S[0].S[1]. ...., S[255]. To perform
encryption or decryption operation, one of these 256 bytes of S is selected and processed. We will call
the resulting output as k. After this, the entries in S are permuted once again.
Overall, there are two processes involved: (a) Initialization of S and (b) Stream generation. We
describe these as follows:

Initialization of S This process consists of the following steps.

1. Choose a key (K) of length between 1 and 256 bytes.
2. Set the values in the state vector S equal to the values from 0 to 255 in an ascending order. In other
words, we should have S[0] = 0, S[1] = 1, …, S[255] = 255.
3. Create another temporary array T. If the length of the key K (termed as keylen) is 256 bytes, copy
K into T as is. Otherwise, after copying K to T, whatever are the remaining positions in T are filled
with the values of K again. At the end, T should be completely filled.

Thus, following steps are executed:

for i = 0 to 255
// Copy the current value of i into the current position in the S array
S [i] = i;

// Now copy the contents of the current position of the K array into T. If K is exhausted, loop back
// to get the values of the K array from the un-exhausted portion of K.
T [i] = K [i mod keylen];

A small Java program shown in Fig. 3.53 implements this logic. Here, we have considered that the K
array contains 10 elements, i.e. keylen is 10.

public class InitRC4 {

public static void main (String [] args) {

int[] S, T, K;
S = new int [255];
T = new int [255];
K = new int [255];

int i;
int keylen = 10;

for (i=0; i<200; i++)

K [i] = i * 2;

for (i=0; i<255; i++) {

S [i] = i;
T [i] = K [i % keylen];
}
}
}

Fig. 3.53 Java code for implementing initialization of S Step

After this, the T array is used to produce initial permutation of S. For this purpose, a loop executes,
iterating i from 0 to 255. In each case, the byte at the position S[i] is swapped with another byte in the S
array, as per an arrangement decided by T[i]. For this purpose, the following logic is used:
j = 0;

for i = 0 to 255
j = (j + S [i] + T [i]) mod 256;
swap (S [i], S [j]);

Note that this is just a permutation. The values of S are simply being rearranged, not changed. The
corresponding Java portion is shown in Fig. 3.54.

Stream Generation Now that the S array is ready with the above initializations and permutations,
the initial key array K is discarded. Now, we need to again loop for i = 0 to 255. In each step, we swap S

// Initial permutation of S

int j = 0, temp;

for (i=0; i<255; i++) {

j = (j + S [i] + T [i]) % 256;
temp = S [i];
S [i] = T [i];
T [i] = temp;
}

for (i=0; i<255; i++) {

System.out.println ("S [i] = " + S [i]);
}

Fig. 3.54 Java code for implementing permutation of S Step

[i] with another byte in S, as per the mechanism decided by the implementation of S. Once we exhaust
the 255 positions, we need to restart at S[0].
The logic is as follows:
i = 0;
j = 0;

while (true)
i = (i + 1) mod 256;
j = (j + S [i]) mod 256;
swap (S [i], S [j]);
t = (S [i] + S [j]) mod 256;
k = S [t];

After this, for encryption, k is XORed with the next byte of the plain text. For decryption, k is XORed
with the next byte of the cipher text.
Some vulnerability has been found in RC4, hence it is not recommended for new applications.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

3.7 RC5
3.7.1 Background and History
RC5 is a symmetric key block encryption algorithm developed by Ron Rivest. The main features of RC5
are that it is quite fast as it uses only the primitive computer operations (such as addition, XOR, shift,
etc). It allows for a variable number of rounds and a variable bit-size key to add to the flexibility.
Different applications that demand varying security needs can set these values accordingly. Another
important aspect is that RC5 requires less memory for execution and is, therefore, suitable not only for
desktop computers, but also for smart cards and other devices that have a small memory capacity. It has
been incorporated into the RSA Data Security Incorporation’s products such as BSAFE, JSAFE and S/
MAIL.

3.7.2 How RC5 Works

Basic Principles In RC5, the word size (i.e. input plain text block size), number of rounds and
number of 8-bit bytes (octets) of the key, all can be of variable length. These values can consist of the
sizes as shown in Table 3.5. Of course, once decided, these values remain the same for a particular
execution of the cryptographic algorithm. These are variable in the sense that before the execution of a
particular instance of RC5, these values can be chosen from those allowed. This is unlike DES, for
instance, where the block size must be of 64 bits and the key size must always be of 56 bits; or unlike
IDEA, which uses 64-bit blocks and 128-bit keys.

Table 3.5 RC5 Block, Round and Key Details

Parameter Allowed values

Word size in bits (RC5 encrypts 2-word blocks at a time) 16, 32, 64
Number of rounds 0-255
Number of 8-bit bytes (octets) in the key 0-255

The following conclusions emerge from the table:

• The plain text block size can be of 32, 64 or 128 bits (since 2-word blocks are used).
• The key length can be 0 to 2040 bits (since we have specified the allowed values for 8-bit keys).
The output resulting from RC5 is the cipher text, which has the same size as the input plain text. Since
RC5 allows for variable values in the three parameters, as specified, a particular instance of the RC5
algorithm is denoted as RC5-w/r/b, where w = word size in bits, r = number of rounds, b = number of 8-
bit bytes in the key. Thus, if we have RC5-32/16/16, it means that we are using RC5 with a block size of
64 bits (remember that RC5 uses 2-word blocks), 16 rounds of encryption and 16 bytes (i.e. 128 bits) in
the key. Rivest has suggested RC5-32/12/16 as the minimum safety version.

Principles of Operation At first, RC5 appears to be complicated because of the notations used.
However, it is actually quite simple to understand. Rather than getting into notations, we shall first
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

illustrate the working of RC5 using Fig. 3.55. As shown in the figure, there is one initial operation
consisting of two steps (shown shaded), then a number of rounds. As we have noted, the number of
rounds (r) can vary from 0 to 255.
For simplicity, we shall assume that we are working on an input plain block with size 64 bits. The
same principles operation will apply to other block sizes, in general.
In the first two steps of the one-time initial operation, the input plain text is divided into two 32-bit
blocks A and B. The first two sub-keys (we shall later see how they are generated) S[0] and S[1] are
added to A and B, respectively. This produces C and D respectively and marks the end of the one-time
operation.
Then, the rounds begin. In each round, there are following operations:
• Bit-wise XOR
• Left circular-shift
• Addition with the next sub-key, for both C and D – This is the addition operation first and then the
result of the addition mod 2w (since w = 32 here, we have 232) is performed.

First, divide the original plain text into two blocks of

equal sizes. Call them as A and B.

Add A and S[0] to produce C.

Add B and S[1] to produce D.
Start with a counter i = 1.

Note: First perform all the left-hand side steps,

and then come to the right hand side steps, as
indicated by the step numbers.

1. XOR C and D to produce E. 4. XOR D and F to produce G.

2. Circular-left shift E by D bits. 5. Circular-left shift G by F bits.

3. Add E and S[2i] to produce F. 6. Add G and S[2i + 1] to produce H.

Increment i by 1.

Call F as C
(i.e. C = F) No Check:
Call H as D Is i > r?
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

(i.e. D = H)

Yes

Stop

Fig. 3.55 Encryption using RC5

If we observe the operations shown in the figure carefully, we will note that the output of one block is
fed back as the input to another block, making the whole logic quite complicated to decipher.
Let us now look at the algorithm details in step-by-step fashion in the next few sections.

One-time Initial Operation We will first take a look at the one-time initial operation, as shown in
Fig. 3.56. This consists of two simple steps: first, the input plain text is divided into two equal-sized
blocks, A and B. Then the first sub-key, i.e. S[0] is added to A and the second sub-key, i.e. S[1] is added
to B. These operations are mod 232, as we have noted and produce C and D, respectively.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
128 Cryptography and Network Security

Original Plain text message

A B

S[0] + + S[1]

C D

Fig. 3.56 One-time initial operation in RC5

Details of One Round Now, we observe the results for the first round. The process for the first
round will apply for further rounds. Therefore, we shall not discuss those rounds separately.
Step 1: XOR C and D In the first step of each round, C and D are XORed together to form E, as
shown in Fig. 3.57.

C D

XOR
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

Fig. 3.57 Step 1 in a round

Step 2: Circular-left shift E Now, E is circular-left shifted by D positions, as shown in Fig. 3.58.

Perform a circular left

shift by D bits

Fig. 3.58 Step 2 in a round

Step 3: Add E and next sub-key In this step, E is added to

the next sub-key (which is S[2] for the first round and S[2i] in Shifted E
general, for any round, where i starts with 1. The output of this
process is F. This is shown in Fig. 3.59.
We would now note that the operations (XOR, circular-left S[2] +
shift and add) in Steps 4 to 6 that follow are the same as the
operations in Steps 1 to 3. The only difference, of course, is that Note that this is
S[2i] in general
the inputs to the Steps 4-6 are different from those to Steps 1-3. F

Step 4: XOR D and F This step is similar to Step 1. Here, D

and F are XORed to produce G. This is shown in Fig. 3.60. Fig. 3.59 Step 3 in a round

D F

XOR

Fig. 3.60 Step 4 in a round

Step 5: Circular-left shift G This step is similar to Step 2. Here, G is circular-left shifted by F
positions, as shown in Figure 3.61.

Perform a circular left

shift by F bits

Fig. 3.61 Step 5 in a round

Step 6: Add G and next sub-key In this step (which is
identical to Step 3), G is added to the next sub-key (which is S[3] Shifted G
for the first round and S[2i + 1] in general, for any round, where i
starts with 1. The output of this process is H. This is shown in
Fig. 3.62. S[3] +

Step 7: Miscellaneous tasks In this step, we check to see if

Note that this is
all the rounds are over or no. For this, perform the following S[2i] in general H
steps:
• Increment i by 1 Fig. 3.62 Step 6 in a round
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
130 Cryptography and Network Security

• Check to see if i < r

Assuming that i is still less than r, we rename F as C and H as D and return back to Step 1. This is
shown in Fig. 3.63.

i = i + 1

If i < r
Call F as C again
Call H as D again
Go back to step 1
Else
Stop
End-if

Fig. 3.63 Step 7 in a round

Mathematical Representation Interestingly, all these operations (one-time initial operation and all
the rounds) in RC5 can be signified mathematically in a very cryptic fashion, as shown in Fig. 3.64. Note
that <<< means circular-left shift.

A = A + S[0]
B = B + S[1]

For i = 1 to r
A = ((A XOR B) <<< B) + S[2i]
B = ((B XOR A) <<< A) + S[2i + 1]
Next i

Fig. 3.64 Mathematical representation of RC5 encryption

Furthermore, we will also write the mathematical representation of RC5 decryption process as shown
in Fig. 3.65 and leave its verification as an exercise. Note that >>> means circular right-shift.

For i = r to 1 step–1 (i.e. decrement i each time by 1)

A = ((B – S[2i + 1]) >>> A) XOR A
B = ((A – S[2i]) >>>B) XOR B
Next i
B = B – S[1]
A = A – S[0]

Fig. 3.65 Mathematical representation of RC5 decryption

Sub-key Creation Let us now examine the sub-key creation process in RC5. This is a two-step
process.
1. In the first step, the sub-keys (denoted by S[0], S[1], …) are generated.
2. The original key is called as L. In the second step, the sub-keys (S[0], S[1], …) are mixed with the
corresponding sub-portions of the original key (i.e. L[0], L[1], …).
This is shown in Fig. 3.66.

Sub-key generation Generate S[0], S[1], …

Sub-key mixing Mix with L[0], L[1], …

Fig. 3.66 Sub-key generation process

Let us understand these two steps.
Step 1: Sub-key generation In this step, two constants P and Q are used. The array of sub-keys to be
generated is called as S. The first sub-key S[0] is initialised with the value of P.
Each next sub-key (i.e. S[1], S[2], …) is calculated on the basis of the previous sub-key and the
constant value Q, using the addition mod 232 operations. The process is done 2 (r + 1) – 1 times, where
r is the number of rounds, as before. Thus, if we have 12 rounds, this process will be done 2 (12 + 1) – 1
times, i.e. 2 (13) – 1 times, i.e. 25 times. Thus, we will generate sub-keys S[0], S[1], … S[25].
This process is illustrated in Fig. 3.67.
The mathematical form of this sub-key generation is shown in Fig. 3.68.
Step 2: Sub-key mixing In the sub-key mixing stage, the sub-keys S[0], S[1], … are mixed with the
sub-portions of the original key, i.e. L[0], L[1], … L[c]. Note that c is the last sub-key position in the
original key. This process is shown mathematically in Fig. 3.69.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

3.7.3 RC5 Modes

The overall performance of RC5 can be made better by implementing it in one of the algorithm modes,
as shown in Table 3.6. This is defined in RFC 2040.

3.8 Blowfish
3.8.1 Introduction
Blowfish was developed by Bruce Schneier and has the reputation of being a very strong symmetric key
cryptographic algorithm. According to Schneier, Blowfish was designed with the following objectives
in mind.
• Fast – Blowfish encryption rate on 32-bit microprocessors is 26 clock cycles per byte.
• Compact – Blowfish can execute in less than 5 kb memory.

P = B7E15163 in Hexadecimal Q = 9E3779B9 in Hexadecimal

Set S[0] = P

Start with a counter i = 1

Calculate A = S[i – 1] + Q

Calculate B = A mod 232

S[i] = B

Increment i by 1

Yes Check:
Is i < 2(r + 1) - 1?

Stop

Fig. 3.67 Sub-key generation

S[0] = P

For i = 1 to 2 (r + 1) – 1
S[i] = (S[i – 1] + Q) mod 232
Next i

Fig. 3.68 Mathematical representation of sub-key generation

i = j = 0
A = B = 0

Do 3n times (where n is the maximum of 2 (r + 1) and c)

A = S[i] = (S[i] + A + B) <<< 3

B = L [i] = (L[i] + A + B) <<< (A + B)

i = (i + 1) mod 2 (r + 1)
j = (j + 1) mod c

End-do

Fig. 3.69 Mathematical representation of Sub-key mixing

Table 3.6 RC5 Modes

Mode Description
RC5 block cipher This is also called as Electronic Codebook (ECB) mode. It involves encryption
of fixed-size input blocks consisting of 2w bits into cipher text block of the same
length.
RC5-CBC This is the Cipher Chaining Block for RC5. In this, plain text messages whose
length is equal to a multiple of the RC5 block size (i.e. multiple of 2w bits) are
encrypted. This mode offers better security, as the same plain text blocks in the
input produce different cipher text blocks in the output.
RC5-CBC-Pad This is a modified version of CBC. Here, the input can be of any length. The
cipher text is longer than the plain text by at the most the size of a single RC5
block. To handle length mismatches, padding is used. This makes the length of a
message equal to a multiple of 2w bits. The length of the original message is
considered to be a specific number of integer number of bytes. Padding of length
1 to bb bytes is added to the end of the message. How many such padding bytes
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

are added is decided by a simple formula bb = 2w / 8. Thus, b equals the block

size for RC5 in bytes. The value of all padding bytes is the same and is set to a
byte that represents the number of bytes used in padding. For instance, if there
are 6 padding bytes, each padding byte contains a value of 6 in binary, i.e.
00000110.
RC5-CTS This is called as Cipher text Stealing mode. This mode is similar to RC5-CBC-
Pad. Here, the plain text input can be of any length. The output cipher text is also
of equal length.

• Simple – Blowfish uses only primitive operations, such as addition, XOR and table lookup,
making its design and implementation simple.
• Secure – Blowfish has a variable key length up to a maximum of 448 bits long, making it both
flexible and secure.
Blowfish suits applications where the key remains constant for a long time (e.g. communications link
encryption), but not where the key changes frequently (e.g. packet switching).
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
134 Cryptography and Network Security

3.8.2 Operation
Blowfish encrypts 64-bit blocks with a variable-length key. It contains two parts, as follows.
• Subkey generation: This process converts the key up to 448 bits long to sub-keys totaling
4168 bits.
• Data encryption: This process involves the iteration of a simple function 16 times. Each round
contains a key-dependent permutation and key- and data-dependent substitution.
We shall now discuss these two parts.

Subkey Generation Let us understand the important aspects of the subkey generation process step-
by-step.
(i) Blowfish makes use of a very large number of subkeys. These keys have to be ready before
encryption and decryption happen. The key size ranges from 32 bits to 448 bits. In other words, the
key size ranges from 1 to 14 words, each comprising word of 32 bits. These keys are stored in an
array, as follows:
K1, K2, …, Kn where each block contains 32 bits
(ii) We then have the concept of a P-array, consisting of 18 32-bit subkeys:
P1, P2… P18
Creation of the P-array is described subsequently.
(iii) Four S-boxes, each containing 256 32-bit entries:
S1,0, S1,1 …, S1,255
S2,0, S2,1 …, S2,255
S3,0, S3,1 …, S3,255
S4,0, S4,1 …, S4,255
Creation of the S-boxes is described subsequently.
Now let us examine how all this information is used to generate subkeys.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

(i) Initialize the P-array first, followed by the four S-boxes, with a fixed string. Schneier recommends
the usage of the bits of the fractional part (in hexadecimal form) of the constant pi (p) for this
purpose. Thus, we will have:
P1 = 243F6A88
P2 = 85A308D3
….
S4,254 = 578FDFE3
S4,255 = 3AC372E6
(ii) Do a bitwise XOR of P1 with K1, P2 with K2, etc, until P18. This works fine till P14 and K14. At
this stage, the key array (K) is exhausted. Hence, for P15 to P18, reuse K1 to K4. In other words,
do the following:
P1 = P1 XOR K1

P2 = P2 XOR K2
….
P14 = P14 XOR K14
P15 = P15 XOR K1
P16 = P16 XOR K2
P17 = P17 XOR K3
P18 = P18 XOR K4
(iii) Now take a 64-bit block, with all the 64 bits initialized to value of 0. Use the above P-arrays and S-
boxes above (the P-arrays and S-boxes are called as subkeys) to run the Blowfish encryption
process (described in the next section) on the 64-bit all-zero block. In other words, to generate the
subkeys themselves, the Blowfish algorithm is used. It is needless to say that once the final
subkeys are ready, the Blowfish algorithm would be used to encrypt the actual plain text.
This step would produce 64-bit cipher text. Divide this into two 32-bit blocks and replace the
original values of P1 and P2 with these 32-bit block values, respectively.
(iv) Encrypt the output of Step (iii) above using Blowfish with the modified subkeys. The resulting
output would again consist of 64 bits. As before, divide this into two blocks of 32 bits each. Now,
replace P3 and P4 with the contents of these two cipher text blocks.
(v) In the same manner, replace all the remaining P-arrays (i.e. P5 through P18) and then all the
elements of the four S-boxes, in order. In each step, the output of the previous step is fed to the
Blowfish algorithm to generate the next two 32-bit blocks of the subkey (i.e. P5 and P6, followed
by P7 and P8, etc).
In all, 521 iterations of the Blowfish algorithm are required to generate all P-arrays and S-boxes.

Data Encryption and Decryption The encryption of a 64-bit block plain text input X is shown in an
algorithmic fashion in Fig. 3.70. We use the P-arrays and S-boxes during the encryption and decryption
processes.

and XR will consist of 32 bits each.

2. For i = 1 to 16

XL = XL XOR Pi
XR = F (XL) XOR XR
Swap XL, XR
Next i

3. Swap XL, XR (i.e. undo last swap).

4. XL = XL XOR P18.

5. Combine XL and XR back into X.

Fig. 3.70 Blowfish algorithm

This process is depicted in Fig. 3.71.

Plain text (64 bits)

XL (32 bits) XR (32 bits)

P1 (32 bits)
XOR F XOR

P2 (32 bits)
XOR F XOR

13 more rounds

P16 (32 bits)

XOR F XOR

P18 (32 bits) P17 (32 bits)

32 bits 32 bits

Cipher text (64 bits)

Fig. 3.71 Blowfish encryption

The function F is as follows:
(i) Divide the 32-bit XL block into four 8-bit sub-blocks, named a, b, c and d.
(ii) Compute F [a, b, c, d] = ((S1,a + S2,b) XOR S3,c) + S4,d. For example, if a = 10, b = 95, c = 37 and
d = 191, then the computation of F would be:
F [a, b, c, d] = ((S1,10 + S2,95) XOR S3,37) + S4,191
The diagrammatic view of the function F is shown in Fig. 3.72.

8 bits 32 bits
S-box 1

XOR
32 bits
8 bits
32-bit S-box 2 XOR
XL block

8 bits 32 bits 32-bit

S-box 3 XOR output

8 bits 32 bits
S-box 4

Fig. 3.72 Function F in Blowfish

The decryption process is shown in Fig. 3.73. As we can see, it is quite similar to the encryption
process, with reversal of P-array values.

3.9 Advanced Encryption Standard (AES)

3.9.1 Introduction
In the 1990s, the US Government wanted to standardize a cryptographic algorithm, which was to be used
universally by them. It was to be called as the Advanced Encryption Standard (AES). Many proposals
were submitted and after a lot of debate, an algorithm called as Rijndael was accepted. Rijndael was
developed by Joan Daemen and Vincent Rijmen (both from Belgium). The name Rijndael was also
based on their surnames (Rijmen and Daemen).
The need for coming up with a new algorithm was actually because of the perceived weakness in
DES. The 56-bit keys of DES were no longer considered safe against attacks based on exhaustive key
searches and the 64-bit blocks were also considered as weak. AES was to be based on 128-bit blocks,
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

with 128-bit keys.

In June 1998, the Rijndael proposal was submitted to NIST as one of the candidates for AES. Out of
the initial 15 candidates, only 5 were short listed in August 1999, which were as follows:
(i) Rijndael (From Joan Daemen and Vincent Rijmen; 86 votes)
(ii) Serpent (From Ross Anderson, Eli Biham and Lars Knudsen; 59 votes)
(iii) Twofish (From Bruce Schneier and others, 31 votes)
(iv) RC6 (From RSA Laboratories, 23 votes)
(v) MARS (From IBM, 13 votes)
In October 2000, Rijndael was announced as the final selection for AES. In November 2001, Rijndael
became a US Government standard published as Federal Information Processing Standard 197
(FIPS 197).
According to its designers, the main features of AES are as follows.

Cipher text Y (64 bits)

YL (32 bits) YR (32 bits)

P18 (32 bits)

XOR F XOR

P17 (32 bits)

XOR F XOR

13 more rounds

P3 (32 bits)
XOR F XOR

P1 (32 bits) P2 (32 bits)

XOR XOR

Plain text (64 bits)

Fig. 3.73 Blowfish decryption

(i) Symmetric and parallel structure – This gives the implementers of the algorithm a lot of flexibility.
It also stands up well against cryptanalysis attacks.
(ii) Adapted to modern processors – The algorithm works well with modern processors (Pentium,
RISC, parallel).
(iii) Suited to smart cards – The algorithm can work well with smart cards.
Rijndael supports key lengths and plain text block sizes from 128 bits to 256 bits, in the steps of
32 bits. The key length and the length of the plain text blocks need to be selected independently. AES
mandates that the plain text block size must be 182 bits and key size should be 128, 192 or 256 bits. In

general, two versions of AES are used: 128-bit plain text block combined with 128-bit key block and
128-bit plain text block with 256-bit key block.
Since the 128-bit plain text block and 128-bit key length are likely to pair as a commercial standard,
we will examine that case only. Other principles remain the same. Since 128 bits give a possible key
range of 2128 or 3 x 1038 keys, Andrew Tanenbaum outlines the strength of this key range in his un-
imitable style:

Even if NSA manages to build a machine with 1 billion parallel procesors, each being able to
evaluate one key per picosecond, it would take such a machine about 1010 years to search the
key space. By then the sun would have burned out, so the folks then present will have to read
the results by candlelight.

3.9.2 Operation
The basics of Rijndael are in a mathematical concept called as Galois field theory. For the current
discussion, we will keep those concepts out and try and figure out how the algorithm itself works at a
conceptual level.
Similar to the way DES functions, Rijndael also uses the basic techniques of substitution and
transposition (i.e. permutation). The key size and the plain text block size decide how many rounds need
to be executed. The minimum number of rounds is 10 (when key-size and the plain text block size are
each 128 bits) and the maximum number of rounds is 14. One key differentiator between DES and
Rijndael is that all the Rijndael operations involve entire byte and not individual bits of a byte. This
provides for more optimized hardware and software implementation of the algorithm.
Figure 3.74 describes the steps in Rijndael at a high level.

(i) Do the following one-time initialization processes:

(a) Expand the 16-byte key to get the actual Key block to be used.

(b) Do one time initialization of the 16-byte plain text block (called as State).

(c) XOR the state with the key block.

(ii) For each round, do the following:

(a) Apply S-box to each of the plain text bytes.

(b) Rotate row k of the plain text block (i.e. state) by k bytes.

(c) Perform a mix columns operation.

(d) XOR the state with the key block

Fig. 3.74 The description of Rijndael

Let us now understand how this algorithm works, step-by-step.

3.9.3 One-time Initialization Process

We will describe each of the algorithm steps in detail now.

(a) Expand the 16-byte Key to get the Actual Key Block to be Used The inputs to the algorithm
are the key and the plain text, as usual. The key size is 16 bytes, in this case. This Step expands this 16-
byte key into 11 arrays, each array contains 4 rows and 4 columns. Conceptually, the key expansion
process can be depicted as shown in Fig. 3.75.

16-byte key

Expanded into 11 arrays, each of size 4 ¥ 4

Fig. 3.75 Key expansion: conceptual view

In other words, the original 16-byte key array is expanded into a key containing 11 ¥ 4 ¥ 4 = 176
bytes. One of these 11 arrays is used in the initialization process and the other 10 arrays are used in the
10 rounds, one array per round.
The key expansion process is quite complex and can be safely ignored. We nevertheless describe it
below for the sake of completeness. Now, let us start using the terminology of word, in the context of
AES. A word means 4 bytes. Therefore, in the current context, our 16-byte initial key (i.e. 16 / 4 = 4-
word key) will be expanded into 176-byte key (i.e.176 / 4 words, i.e. 44 words).
1. Firstly, the original 16-byte key is copied into the first 4 words of the expanded key (i.e. the first
4 ¥ 4 array of our diagram), as is. This is shown in Fig. 3.76.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

16-byte key

Copied, as is

To be expanded into 11 arrays, each of size 4 ¥ 4

Fig. 3.76 Key expansion: Step 1

Another representation of the same concept is shown in Fig. 3.77.

2. After filling the first array (for words numbered W0 to

W3) of the expanded key block as explained above, the K0 K1 K2 K3
remaining 10 arrays (for words numbered W4 to W43) K4 K5 K6 K7
are filled one-by-one. Every time, one such 4 ¥ 4 array
K8 K9 K10 K11
(i.e. four words) gets filled. Every added key array block
depends on the immediately preceding block and the K12 K13 K14 K15

block 4 positions earlier to it. That is, every added word

w [i] depends on w [i – 1] and w [i – 4]. We have said that
W0 W1 W2 W3
this fills four words at a time. For filling these four words
at a time, the following logic is used:
(a) If the word in the W array is a multiple of four, Fig. 3.77 Key expansion: First Step
some complex logic is used, explained later. That is, for words W [4], W [8], W [12]… W
[40], this complex logic would come into picture.
(b) For others, a simple XOR is used.
This logic is described in an algorithm shown in Fig. 3.78.

ExpandKey (byte K [16], word W [44]) {

word tmp;

// First copy all the 16 input key blocks into first four words of output key
for (i = 0; i < 4; i++) {
W [i] = K [4*i], K [4*i + 1], K [4*i + 2], K [4*i + 3];
}

// Now populate the remaining output key words (i.e. W5 to W43)

for (i = 4; i < 44; i++) {
tmp = W [i–1];

w [i] = w [i–4] XOR tmp;

}
}

Fig. 3.78 Key expansion described as an algorithm

We have already discussed the portion of copying all the 16 input key blocks (i.e. 16 bytes) into the
first four words of the output key block. Therefore, we will not discuss this again. This is described by
the first for loop.
In the second for loop, we check if the current word being populated in the output key block is a
multiple of 4. If it is, we perform three functions, titled Substitute, Rotate and Constant. We will describe
them shortly. However, if the current word in the output key block is not a multiple of four, we simply
perform an XOR operation of the previous word and the word four places earlier and store it as the
output word. That is, for word W [5], we would XOR W [4] and W [1] and store their output as W [5].
This should be clear from the algorithm. Note that a temporary variable called as tmp is created, which
stores W [i – 1], which is then XORed with W [i – 4].
Let us now understand the three functions, titled Substitute, Rotate and Constant.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
142 Cryptography and Network Security

(i) Function Rotate performs a circular left shift on the contents of the word by one byte. Thus, if an
input word contains four bytes numbered [B1, B2, B3, B4]; then the output word would contain
[B2, B3, B4, B1].
(ii) Function Substitute performs a byte substitution on each byte of the input word. For this purpose,
it uses an S-box, shown in Fig. 3.79.

Y
0 1 2 3 4 5 6 7 8 9 a b c d e f
0 63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
1 ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
2 b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
3 04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
4 09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
5 53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
6 d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
7 51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
X
8 cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
9 60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d 70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f 8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

Fig. 3.79 AES S-box

(iii) In the function Constant, the output of the above steps is XORed with a constant. This constant is
a word, consisting of 4 bytes. The value of the constant depends on the round number. The last
three bytes of a constant word always contain 0. Thus, XORing any input word with such a
constant is as good as XORing only with the first byte of the input word. These constant values per
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

round are listed in Fig. 3.80.

Round number 1 2 3 4 5 6 7 8 9 10
Value of constant to be used in Hex 01 02 04 08 10 20 40 80 1B 36

Fig. 3.80 Values of constants per round, to be used in the Constant function
Let us understand how the whole thing works, with an example.
1. Suppose that our original unexpanded 4-word (i.e. 16-byte) key is as shown in Fig. 3.81.

Byte position 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
(Decimal)
Value (Hex) 00 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F

Fig. 3.81 Key expansion example – Step 1 – Original 4-word key

2. In the first four rounds, the original 4-word input key would be copied into the first 4-word output
key, as per our algorithm step as follows:
// First copy all the 16 input key blocks into first four words of output key
f o r (i = 0; i < 4; i++) {
W [ i ] = K [4*i], K [4*i + 1], K [4*i + 2], K [4*i + 3];
}

Thus, the first 4 words of the output key (i.e. from W [0] to W [3]) would contain values as shown
in Fig. 3.82. This is constructed from the input 4-word (i.e. 16-byte) key as follows:
(a) Firstly, the first four bytes, i.e. one word, of the input key, namely 00 01 02 03 is copied
into the first word of the output key W [0].
(b) Now, the next four bytes of the input key, i.e. 04 05 06 07 would be copied into the second
word of the output key, i.e. W [1].
Needless to say, W [2] and W [3] would get populated with the remaining contents of the input key
bytes, as shown in the figure.

W [0] W [1] W [2] W [3] W [4] W [5] ... W [44]

00 01 02 03 04 05 06 07 08 00 0A 0B 0C 0D 0E 0F ? ? ? ?

Fig. 3.82 Key expansion example – Step 2 – Filling of first 4 output key words
3. Now let us understand how the next word of the output key block, i.e. W [4] is populated. For this
purpose, the following algorithm would be executed:
// Now populate the remaining output key words (i.e. W5 to W43)
f o r (i = 4; i < 44; i++) {
tmp = W [i 1];

i f (i mod 4 == 0)
tmp = Substitute (Rotate (temp)) XOR Constant [i/4];

w [i] = w [i 4] XOR tmp;

Based on this, we will have the following:

tmp = W [i – 1] = W [4 – 1] = W [3] = 0C 0D 0E 0F
Since i = 4, i mod 4 is 0. Therefore, we will now have the following Step:
tmp = Substitute (Rotate (temp)) XOR Constant [i/4];
• We know that Rotate (temp) will produce Rotate (0C 0D 0E 0F), which equals 0D 0E 0F 0C.
• Now, we need to do Substitute (Rotate (temp)). For this purpose, we need to take one byte at a time
and look up in the S-box for substitution. For example, our first byte is 0D. Looking it up in the S-
box with x = 0 and y = D produces D7. Similarly, 0E produces AB, 0F produces 76 and 0C
produces FE. Thus, at the end of the Substitute (Rotate (temp)) step, our input of 0D 0E 0F 0C is
transformed into the output of D7 AB 76 FE.
• We now need to XOR this value with Constant [i/4]. Since i = 4, we need to obtain the value of
Constant [4/4], i.e. Constant [1], which is 01, as per our earlier table of constants. As we know, we

need to pad this with three more bytes, all set to 00. Therefore, our constant value is 01 00 00 00.
So, we have:
D7 AB 76 FE
XOR
10 00 00 00
= D6 AB 76 FE
Thus, our new tmp value is D6 AB 76 FE.
• Finally, we need to XOR this tmp value with W [i – 4], i.e. with W [4 – 4], i.e. with W [0]. Thus, we
have:
D6 AB 76 FE
XOR
00 01 02 03
= D6 AA 74 FD
Thus, W [4] = D6 AA 74 FD.
We can use the same logic to derive the remaining expanded key blocks (W [5] to W [44]).

(b) Do One Time Initialization of the 16-byte Plain Text Block (Called as State) This step is
relatively simple. Here, the 16-byte plain text block is copied into a two-dimensional 4 ¥ 4 array called
as state. The order of copying is in the column order. That is, the first four bytes of the plain text block
get copied into the first column of the state array, the next four bytes of the plain text block get copied
into the second column of the state array and so on. This is shown in Fig. 3.83 for every byte (numbered
from B1 to B16).

16-byte plain text block

B1 B2 B3 B4 B5 B6 B7 B8 B9 B10 B11 B12 B13 B14 B15 B16

B1 B5 B9 B13
B2 B6 B10 B14
B3 B7 B11 B15
B4 B8 B12 B16

State array

Fig. 3.83 Copying of the input text block into state array

(c) XOR the State with the Key block Now, the first 16 bytes (i.e. four words W [0], W [1], W [2]
and W [3]) of the expanded key are XORed into the 16-byte state array (B1 to B16 shown above). Thus,
every byte in the state array is replaced by the XOR of itself and the corresponding byte in the expanded
key.
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.
Symmetric Key Algorithms and AES 145

At this stage, the initialization is complete and we are ready for rounds.

3.9.4 Processes in Each Round

The following steps are executed 10 times, one per round.

(a) Apply S-box to Each of the Plain Text Bytes. This step is very straightforward. The contents
of the state array are looked up into the S-box. Byte by byte substitution is done to replace the contents
of the state array with the respective entries in the S-box. Note that only one S-box is used, unlike DES,
which has multiple S-boxes.
(b) Rotate Row k of the Plain Text Block (i.e. state) by k Bytes. Here, each of the four rows of
the state array are rotated to the left. Row 0 is rotated 0 bytes (i.e. not rotated at all), row 1 is rotated by
1 byte, row 2 is rotated 2 bytes and row 2 is rotated 3 bytes. This helps in diffusion of data. Thus, if the
original 16 bytes of the state array contain values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 then the
rotate operation would change the values as follows:
Original array Modified array

1 5 9 13 1 5 9 13
2 6 10 14 6 10 14 2
3 7 11 15 11 15 3 7
4 8 12 16 16 4 8 12

(c) Perform a Mix Columns Operation Now, each column is mixed independent of the other.
Matrix multiplication is used. The output of this step is the matrix multiplication of the old values and a
constant matrix.
This is perhaps the most complex step to understand and also to explain. Nevertheless, we will make
an attempt! This is based on a nice article by Adam Berent.
There are two aspects of this step. The first explains which parts of the state are multiplied against
which parts of the matrix. The second explains how this multiplication is implemented over what’s
called as a Galois Field.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

(c.1) Matrix Multiplication We know that the state is arranged into a 4 ¥ 4 matrix.
The multiplication is performed one column at a time (i.e. on 4 bytes at a time). Each value in the
column is eventually multiplied against every value of the matrix (i.e. 16 total multiplications are
performed). The results of these multiplications are XORed together to produce only 4 resulting bytes
for the next state. We together have 4 bytes input, 16 multiplications, 12 XORs and 4 bytes output. The
multiplication is performed one matrix row at a time against each value of a state column.
For example, consider that our matrix is as shown in Fig. 3.84.

2 3 1 1
1 2 3 1
1 1 2 3
3 1 1 2

Fig. 3.84 Multiplication matrix

Next, let us imagine that the 16-byte state array is as shown in Fig. 3.85.

b1 b5 b9 b13
b2 b6 b10 b14
b3 b7 b11 b15
b4 b8 b12 b16

Fig. 3.85 16-byte state array

The first result byte is calculated by multiplying four values of the state column with the four values
of the first row of the matrix. The result of each multiplication is then XORed to produce one byte. For
this, the following calculation is used:
b1 = (b1 * 2) XOR (b2 * 3) XOR (b3 * 1) XOR (b4 * 1)
Next, the second result byte is calculated by multiplying the same four values of the state column
against four values of the second row of the matrix. The result of each multiplication is then XORed to
produce one byte.
b2 = (b1 * 1) XOR (b2 * 2) XOR (b3 * 3) XOR (b4 * 1)
The third result byte is calculated by multiplying the same four values of the state column against four
values of the third row of the matrix. The result of each multiplication is then XORed to produce one
byte.
b3 = (b1 * 1) XOR (b2 * 1) XOR (b3 * 2) XOR (b4 * 3)
The fourth result byte is calculated by multiplying the same four values of the state column against
four values of the fourth row of the matrix. The result of each multiplication is then XORed to produce
one byte.
b4 = (b1 * 3) XOR (b2 * 1) XOR (b3 * 1) XOR (b4 * 2)
This procedure is repeated again with the next column of the state, until there are no more state
columns.
To summarize:
The first column will include state bytes 1-4 and will be multiplied against the matrix in the following
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

manner:
b1 = (b1 * 2) XOR (b2*3) XOR (b3*1) XOR (b4*1)
b2 = (b1 * 1) XOR (b2*2) XOR (b3*3) XOR (b4*1)
b3 = (b1 * 1) XOR (b2*1) XOR (b3*2) XOR (b4*3)
b4 = (b1 * 3) XOR (b2*1) XOR (b3*1) XOR (b4*2)
(b1= specifies the first byte of the state)
The second column will be multiplied against the second row of the matrix in the following manner.
b5 = (b5 * 2) XOR (b6*3) XOR (b7*1) XOR (b8*1)
b6 = (b5 * 1) XOR (b6*2) XOR (b7*3) XOR (b8*1)
b7 = (b5 * 1) XOR (b6*1) XOR (b7*2) XOR (b8*3)
b8 = (b5 * 3) XOR (b6*1) XOR (b7*1) XOR (b8*2)
And so on until all columns of the state are exhausted.

(c.2) Galois Field Multiplication The multiplication mentioned above is performed over a Galois
Field. The mathematics behind this is quite complex and beyond the scope of the current text. However,
we will discuss the implementation of the multiplication, which can be done quite easily with the use of
the following two tables, shown in hexadecimal formats. Refer to Fig. 3.86 and Fig. 3.87.

0 1 2 3 4 5 6 7 8 9 A B C D E F
0 01 03 05 0F 11 33 55 FF 1A 2E 72 96 A1 F8 13 35
1 5F E1 38 48 D8 73 95 A4 F7 02 06 0A 1E 22 66 AA
2 E5 34 5C E4 37 59 EB 26 6A BE D9 70 90 AB E6 31
3 53 F5 04 0C 14 3C 44 CC 4F D1 68 B8 D3 6E B2 CD
4 4C D4 67 A9 E0 3B 4D D7 62 A6 F1 08 18 28 78 88
5 83 9E B9 D0 6B BD DC 7F 81 98 B3 CE 49 DB 76 9A
6 B5 C4 57 F9 10 30 50 F0 0B 1D 27 69 BB D6 61 A3
7 FE 19 2B 7D 87 92 AD EC 2F 71 93 AE E9 20 60 A0
8 FB 16 3A 4E D2 6D B7 C2 5D E7 32 56 FA 15 3F 41
9 C3 5E E2 3D 47 C9 40 C0 5B ED 2C 74 9C BF DA 75
A 9F BA D5 64 AC EF 2A 7E 82 9D BC DF 7A 8E 89 80
B 9B B6 C1 58 E8 23 65 AF EA 25 6F B1 C8 43 C5 54
C FC 1F 21 63 A5 F4 07 09 1B 2D 77 99 B0 CB 46 CA
D 45 CF 4A DE 79 8B 86 91 A8 E3 3E 42 C6 51 F3 0E
E 12 36 5A EE 29 7B 8D 8C 8F 8A 85 94 A7 F2 0D 17
F 39 4B DD 7C 84 97 A2 FD 1C 24 6C B4 C7 52 F6 01

Fig. 3.86 E table

0 1 2 3 4 5 6 7 8 9 A B C D E F
0 00 19 01 32 02 1A C6 4B C7 1B 68 33 EE DF 03
1 64 04 E0 0E 34 8D 81 EF 4C 71 08 C8 F8 69 1C C1
2 7D C2 1D B5 F9 B9 27 6A 4D E4 A6 72 9A C9 09 78
3 65 2F 8A 05 21 0F E1 24 12 F0 82 45 35 93 DA 8E
4 96 8F DB BD 36 D0 CE 94 13 5C D2 F1 40 46 83 38
5 66 DD FD 30 BF 06 8B 62 B3 25 E2 98 22 88 91 10
6 7E 6E 48 C3 A3 B6 1E 42 3A 6B 28 54 FA 85 3D BA
7 2B 79 0A 15 9B 9F 5E CA 4E D4 AC E5 F3 73 A7 57
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

8 AF 58 A8 50 F4 EA D6 74 4F AE E9 D5 E7 E6 AD E8
9 2C D7 75 7A EB 16 0B F5 59 CB 5F B0 9C A9 51 A0
A 7F 0C F6 6F 17 C4 49 EC D8 43 1F 2D A4 76 7B B7
B CC BB 3E 5A FB 60 B1 86 3B 52 A1 6C AA 55 29 9D
C 97 B2 87 90 61 BE DC FC BC 95 CF CD 37 3F 5B D1
D 53 39 84 3C 41 A2 6D 47 14 2A 9E 5D 56 F2 D3 AB
E 44 11 92 D9 23 20 2E 89 B4 7C B8 26 77 99 E3 A5
F 67 4A ED DE C5 31 FE 18 0D 63 8C 80 C0 F7 70 07

Fig. 3.87 L Table

The result of the multiplication is actually the output of a lookup of the L table, followed by the
addition of the results, followed by a lookup of the E table. Note that the term addition means a
traditional mathematical addition and not a bit-wise AND operation.
All numbers being multiplied using the Mix Column function converted to Hex will form a maximum
of 2 digit Hex number. We use the first digit in the number on the vertical index and the second number
on the horizontal index. If the value being multiplied is composed of only one digit we use 0 on the

vertical index. For example if the two Hex values being multiplied are AF * 8 we first lookup L (AF)
index which returns B7 and then lookup L (08) which returns 4B. Once the L table lookup is complete
we can then simply add the numbers together. The only trick being that if the addition result is greater
than FF, we subtract FF from the addition result. For example B7+4B= 102. Because 102 > FF, we
perform: 102-FF which gives us 03.
The last step is to look up the addition result on the E table. Again we take the first digit to look up the
vertical index and the second digit to look up the horizontal index.
For example E(03)=0F. Therefore, the result of multiplying AF * 8 over a Galois Field is 0F.

(d) XOR the State with the Key Block. This Step XORs the key for this round into the state array.
For decryption, the process can be executed in the reverse order. There is another option, though. The
same encryption process, run with some different table values, can also perform decryption.

SUMMARY

G In symmetric key cryptography, the sender and the receiver share a single key and the same key is
used for both encryption and decryption.
G Some of the important symmetric key cryptographic algorithms are DES (and its variations),
IDEA, RC4, RC5 and Blowfish.
G An algorithm type defines what size of plain text should be encrypted in each step of the algorithm.
G There are two main types of algorithms: stream cipher and block cipher.
G In stream cipher, each bit/byte of text is encrypted/decrypted individually.
G In block cipher, a block of text is encrypted/decrypted at a time.
G An algorithm mode defines the details of the cryptographic algorithm, once the type is decided.
G Confusion is a technique of ensuring that a cipher text gives no clue about the original plain text.
G Diffusion increases the redundancy of the plain text by spreading it across rows and columns.
G There are four important algorithm modes: Electronic Code Book (ECB), Cipher Block Chaining
(CBC), Cipher Feedback (CFB) and Output Feedback (OFB).
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

G There is a variation of the OFB mode, called as Counter (CTR).

G Electronic Code Book (ECB) is the simplest mode of operation. Here, the incoming plain text
message is divided into blocks of 64 bits each. Each such block is then encrypted independently of
the other blocks. For all blocks in a message, the same key is used for encryption.
G The Cipher Block Chaining (CBC) mode ensures that even if a block of plain text repeats in the
input, these two (or more) identical plain text blocks yield totally different cipher text blocks in the
output. For this, a feedback mechanism is used.
G The Cipher Feedback (CFB) mode encrypts data in units that are smaller (e.g. they could be of size
8 bits, i.e. the size of a character typed by an operator) than a defined block size (which is usually
64 bits).
G The Output Feedback (OFB) mode is extremely similar to the CFB. The only difference is that in
the case of CFB, the cipher text is fed into the next stage of encryption process. But in the case of
OFB, the output of the Initial Vector (IV) encryption process is fed into the next stage of encryption
process.

G The Counter (CTR) mode is quite similar to the OFB mode, with one variation. It uses sequence
numbers called as counters as the inputs to the algorithm. After each block is encrypted, to fill the
register, the next counter value is used.
G There are two problems in symmetric key encryption: problem of key exchange and one key is
required per communication pair.
G The Data Encryption Standard (DES), also called as the Data Encryption Algorithm (DEA) by
ANSI and DEA-1 by ISO, has been a cryptographic algorithm used for over two decades. Of late,
DES has been found vulnerable against very powerful attacks, therefore, the popularity of DES has
been slightly on the decline.
G DES is a block cipher. It encrypts data in blocks of size 64 bits each. That is, 64 bits of plain text
goes as the input to DES, which produces 64 bits of cipher text. The same algorithm and key are
used for encryption and decryption, with minor differences. The key length is 56 bits.
G In 1990, Eli Biham and Adi Shamir introduced the concept of differential cryptanalysis. This
method looks at pairs of cipher text whose plain texts have particular differences. The technique
analyses the progress of these differences as the plain texts travel through the various rounds of
DES.
G Invented by Mitsuru Matsui, the linear cryptanalysis attack is based on linear approximations. If
we XOR some plain text bits together, XOR some cipher text bits together and then XOR the
result, we will get a single bit, which is the XOR of some of the key bits.
G Timing attacks refer more to asymmetric key cryptography. However, they can also apply to
symmetric key cryptography. The idea is simple: observe how long it takes for the cryptographic
algorithm to decrypt different blocks of cipher text. The idea is to try and obtain either the plain
text or the key used for encryption by observing these timings.
G Two main variations of DES have emerged, which are Double DES and Triple DES.
G Double DES is quite simple to understand. Essentially, it does twice what DES normally does only
once. Double DES uses two keys.
G Merkle and Hellman introduced the concept of the meet-in-the-middle attack. This attack involves
encryption from one end, decryption from the other and matching the results in the middle, hence
the name meet-in-the-middle attack.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

G Triple DES is DES – three times. It comes in two flavours: one that uses three keys and the other
that uses two keys.
G The International Data Encryption Algorithm (IDEA) is perceived as one of the strongest
cryptographic algorithms.
G IDEA is a block cipher. Like DES, it also works on 64-bit plain text blocks. The key is longer, and
consists of 128 bits. IDEA is reversible like DES, that is, the same algorithm is used for encryption
and decryption. Also, IDEA uses both diffusion and confusion for encryption.
G RC4 was designed by Ron Rivest of RSA Security in 1987. The official name for this algorithm is
“Rivest Cipher 4”. However, because of its ease of reference, the acronym RC4 has stuck.
G RC4 is a stream cipher. This means that the encryption happens byte-by-byte. However, this can be
changed to bit-by-bit encryption (or to a size other than a byte/bit).
G RC5 is a symmetric key block encryption algorithm developed by Ron Rivest. The main features
of RC5 are that it is quite fast as it uses only the primitive computer operations (such as addition,
XOR, shift, etc). It allows for a variable number of rounds and a variable bit-size key to add to the
flexibility.

G Blowfish was developed by Bruce Schneier and has the reputation of being a very strong
symmetric key cryptographic algorithm.
G Blowfish encrypts 64-bit blocks with a variable-length key.
G In the 1990s, the US Government wanted to standardize a cryptographic algorithm, which was to
be used universally by them. It was to be called as the Advanced Encryption Standard (AES).
Many proposals were submitted and after a lot of debate, an algorithm called as Rijndael was
accepted.
G Rijndael supports key lengths and plain text block sizes from 128 bits to 256 bits, in the Steps of
32 bits. The key length and the length of the plain text blocks need to be selected independently.
AES mandates that the plain text block size must be 182 bits and key size should be 128, 192 or
256 bits. In general, two versions of AES are used: 128-bit plain text block combined with 128-bit
key block and 128-bit plain text block with 256-bit key block.

KEY TERMS AND CONCEPTS

L Advanced Encryption Standard (AES) L Group
L Algorithm mode L Initialization Vector (IV)
L Algorithm type L International Data Encryption Algorithm
L Block cipher (IDEA)
L Chaining mode L Keystream
L Cipher Block Chaining (CBC) L Linear cryptanalysis
L Cipher Feedback (CFB) L Lucifer
L Confusion L Meet-in-the-middle attack
L Counter mode L Output Feedback (OFB)
L Data Encryption Standard (DES) L RC4
L Differential cryptanalysis L RC5
L Diffusion L Rijndael
L Double DES L Stream cipher
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

L Electronic Code Book (ECB) L Timing attacks

L Galois field L Triple DES

PRACTICE SET

MULTIPLE-CHOICE QUESTIONS
1. In , one bit of plain text is encrypted at a time.
(a) stream cipher (b) block cipher
(c) both stream and block cipher (d) none of the above
2. In , one block of plain text is encrypted at a time.
(a) stream cipher (b) block cipher

(c) both stream and block cipher (d) none of the above
3. increases the redundancy of plain text.
(a) Confusion (b) Diffusion
(c) Both confusion and diffusion (d) Neither confusion nor diffusion
4. works on block mode.
(a) CFB (b) OFB
(c) CCB (d) CBC
5. DES encrypts blocks of bits.
(a) 32 (b) 56
(c) 64 (d) 128
6. There are rounds in DES.
(a) 8 (b) 10
(c) 14 (d) 16
7. is based on the IDEA algorithm.
(a) S/MIME (b) PGP
(c) SET (d) SSL
8. The actual algorithm in the AES encryption scheme is .
(a) Blowfish (b) IDEA
(c) Rijndael (d) RC4
9. The Blowfish algorithm executes the algorithm for subkey generation.
(a) Blowfish (b) IDEA
(c) Rijndael (d) RC4
10. In AES, the 16-byte key is expanded into .
(a) 200 bytes (b) 78 bytes
(c) 176 bytes (d) 184 bytes
11. In IDEA, the key size is .
(a) 128 bytes (b) 128 bits
(c) 256 bytes (d) 256 bits
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

12. In the algorithm, once the initial key of 1-256 bytes is used to create a transformed
key, the original key is discarded.
(a) Blowfish (b) IDEA
(c) Rijndael (d) RC4
13. There are encryption rounds in RC5.
(a) 8 (b) 12
(c) 16 (d) 20
14. The RC5 block cipher mode is also called as .
(a) RC5 block cipher (b) RC5-CBC
(c) RC5-CBC-Pad (d) RC5-CTS
15. The step ensures that plain text is not vulnerable in block cipher mode.
(a) encryption (b) round
(c) initial (d) chaining

EXERCISES
1. Distinguish between stream and block ciphers.
2. Discuss the idea of algorithm modes with detailed explanation of at least two of them.
3. Write a note on the security and possible vulnerabilities of the various algorithm modes.
4. What is an Initialization Vector (IV)? What is its significance?
5. What are the problems with symmetric key encryption?
6. What is the idea behind meet-in-the-middle attack?
7. Explain the main concepts in DES.
8. How can the same key be reused in triple DES?
9. Explain the principles of the IDEA algorithm.
10. Distinguish between differential and linear cryptanalysis.
11. Explain the subkey generation in the Blowfish algorithm.
12. Explain the usage of the S array in the case of the RC4 algorithm.
13. Discuss how encryption happen in RC5.
14. How does the one-time initialization step work in AES?
15. Explain the steps in the various rounds of AES.

DESIGN/PROGRAMMING EXERCISES
1. Write a C program to implement the DES algorithm logic.
2. Write the same program as in Step 1, in Java.
3. Write a Java program that contains functions, which accept a key and input text to be encrypted/
decrypted. This program should use the key to encrypt/decrypt the input by using the triple DES
algorithm. Make use of Java cryptography package.
4. Write a C program to implement the Blowfish algorithm.
5. Write the same program in VB.NET.
Copyright © 2007. Tata McGraw-Hill. All rights reserved.

6. Investigate Rijndael further and write a C program to implement the same.

7. Find out more about the vulnerabilities of DES from the Internet.
8. Write the RC4 logic in Java.
9. Try to implement the logic of the various algorithm modes in a programming language of your choice.
10. Create a visual tool that should take as input some plain text and a key and then execute an
algorithm of the user’s choice (e.g. DES). It should provide a visual display of the output at each
stage of the encryption process.
11. Using Java cryptography, encrypt the text “Hello world” using Blowfish. Create your own key
using Java keytool.
12. Perform the same task by using the cryptography API in .NET.
13. Examine which software products in real life use which cryptographic algorithms. Try to find out
the reasons behind the choice of these algorithms.
14. Implement DES-2 and DES-3 (with two keys) using Java cryptography and try to encrypt a large
block of text. Find out if there is any significant performance difference.
15. Compare the results of the above with DES-3 (with three keys).
Kahate, Atul. Cryptography and Network Security, Tata McGraw-Hill, 2007. ProQuest Ebook Central,
http://ebookcentral.proquest.com/lib/inflibnet-ebooks/detail.action?docID=5121458.
Created from inflibnet-ebooks on 2021-09-21 06:14:45.

Caesar Cipher Report
100% (1)
Caesar Cipher Report
5 pages
Unit-2
No ratings yet
Unit-2
68 pages
Network Security Unit-2
No ratings yet
Network Security Unit-2
17 pages
ALGORITHM Types and Modes
No ratings yet
ALGORITHM Types and Modes
190 pages
S 1
No ratings yet
S 1
12 pages
Modern Symmetric Key Cipher
No ratings yet
Modern Symmetric Key Cipher
28 pages
ACS Material 1
No ratings yet
ACS Material 1
21 pages
Cryptography Additional Study Guide
No ratings yet
Cryptography Additional Study Guide
37 pages
Week 7
No ratings yet
Week 7
59 pages
04-crypto
No ratings yet
04-crypto
74 pages
ISS L2 SymmetricCrypto
No ratings yet
ISS L2 SymmetricCrypto
41 pages
Stream Ciphers07 - GeeksforGeeks
No ratings yet
Stream Ciphers07 - GeeksforGeeks
13 pages
The Most Common Security Threats Are An
No ratings yet
The Most Common Security Threats Are An
13 pages
Symmetric Cryptography: Block Ciphers and Stream Ciphers
No ratings yet
Symmetric Cryptography: Block Ciphers and Stream Ciphers
18 pages
Cryptography
No ratings yet
Cryptography
43 pages
IS Unit 2 IMP Bat Notes
No ratings yet
IS Unit 2 IMP Bat Notes
7 pages
Part 1
No ratings yet
Part 1
36 pages
Unit 2
No ratings yet
Unit 2
8 pages
Cryptography Lecture 1 and 2- IAA-20-04-2020
No ratings yet
Cryptography Lecture 1 and 2- IAA-20-04-2020
61 pages
Chapter-3.2 Cryptography and Encryption Techniques
No ratings yet
Chapter-3.2 Cryptography and Encryption Techniques
58 pages
Symmetric Key Aditya VAIO
No ratings yet
Symmetric Key Aditya VAIO
19 pages
Chapter - 8 - Crypto
No ratings yet
Chapter - 8 - Crypto
163 pages
02 - Cryptography (1)
No ratings yet
02 - Cryptography (1)
35 pages
Lecture 2 - Classical Cryptography
No ratings yet
Lecture 2 - Classical Cryptography
53 pages
Explain Keyed and Keyless Transposition Ciphers 1.: CSS Page 1
No ratings yet
Explain Keyed and Keyless Transposition Ciphers 1.: CSS Page 1
9 pages
Cryptography: by Mrs. Ankita Joshi
No ratings yet
Cryptography: by Mrs. Ankita Joshi
21 pages
SW_Security_CH3_CH6
No ratings yet
SW_Security_CH3_CH6
231 pages
Iis Mod 1 Part 3
No ratings yet
Iis Mod 1 Part 3
16 pages
Model of Conventional Encryption
No ratings yet
Model of Conventional Encryption
10 pages
May 2015 EE Exemplar A
No ratings yet
May 2015 EE Exemplar A
23 pages
Unit-2 Cns Imp Topics
No ratings yet
Unit-2 Cns Imp Topics
14 pages
Unit-2(modes)
No ratings yet
Unit-2(modes)
37 pages
Cryptography and Network Security
No ratings yet
Cryptography and Network Security
6 pages
Is - PS2 - Ciphers
No ratings yet
Is - PS2 - Ciphers
21 pages
ECEG-6530 Computer (And Network) Security: Private-Key Encryption Schemes, Modes of Encryption
No ratings yet
ECEG-6530 Computer (And Network) Security: Private-Key Encryption Schemes, Modes of Encryption
30 pages
Cryptography - Notes For CISSP: by Keith Turpin - June 2005
No ratings yet
Cryptography - Notes For CISSP: by Keith Turpin - June 2005
7 pages
Ciphers and Its Types
No ratings yet
Ciphers and Its Types
25 pages
Unit 2.1
No ratings yet
Unit 2.1
28 pages
Lab01 - Classical Cryptography
No ratings yet
Lab01 - Classical Cryptography
13 pages
Computer security ch3.
No ratings yet
Computer security ch3.
65 pages
CISSP-Domain 3-Cryptography Ver 2021
100% (1)
CISSP-Domain 3-Cryptography Ver 2021
14 pages
Lecture 7 Multiple Encryption + Modes of Operation
No ratings yet
Lecture 7 Multiple Encryption + Modes of Operation
41 pages
Chapter - 3 Cryptography and Encryption Techniques
No ratings yet
Chapter - 3 Cryptography and Encryption Techniques
62 pages
Chapter - 3 Cryptography and Encryption Techniques
No ratings yet
Chapter - 3 Cryptography and Encryption Techniques
62 pages
Is CH2
No ratings yet
Is CH2
11 pages
Security Engineering - Cryptography
No ratings yet
Security Engineering - Cryptography
81 pages
crypto_basics
No ratings yet
crypto_basics
94 pages
Session 2 - Lecture Notes Crypto Part 1
No ratings yet
Session 2 - Lecture Notes Crypto Part 1
29 pages
Chapter -3 Cryptography and Encryption Techniques
No ratings yet
Chapter -3 Cryptography and Encryption Techniques
62 pages
Cryptography
No ratings yet
Cryptography
12 pages
Cryptography & Protocols: Presented By: Dr. S. S. Bedi Department of CSIT, MJP Rohilkhsnd University, Bareilly
No ratings yet
Cryptography & Protocols: Presented By: Dr. S. S. Bedi Department of CSIT, MJP Rohilkhsnd University, Bareilly
59 pages
02A IntroToCryptography
No ratings yet
02A IntroToCryptography
41 pages
Unit - II: Traditional Symmetric - Key Ciphers: Advanced Encryption Standard
No ratings yet
Unit - II: Traditional Symmetric - Key Ciphers: Advanced Encryption Standard
47 pages
Week 1
No ratings yet
Week 1
5 pages
Information Security_Ch08 (1)
No ratings yet
Information Security_Ch08 (1)
141 pages
Cryptography: BY, Ayesha Farhin
No ratings yet
Cryptography: BY, Ayesha Farhin
41 pages
Lab01 - Symmetric Cryptography
No ratings yet
Lab01 - Symmetric Cryptography
13 pages
Modes of Operation
No ratings yet
Modes of Operation
30 pages
CSS Assignment 1 Q and A
No ratings yet
CSS Assignment 1 Q and A
9 pages
Application and Implementation of DES Algorithm Based on FPGA
From Everand
Application and Implementation of DES Algorithm Based on FPGA
madhav
No ratings yet
Cryptography Basics for New Coders: A Practical Guide with Examples
From Everand
Cryptography Basics for New Coders: A Practical Guide with Examples
William E. Clark
No ratings yet
CNS Unit 2
No ratings yet
CNS Unit 2
32 pages
Lecture 5 - DeS and Its Variants
No ratings yet
Lecture 5 - DeS and Its Variants
30 pages
Types of Cipher
100% (1)
Types of Cipher
21 pages
Cryptography_Recent_Advances_and_Research_Perspect
No ratings yet
Cryptography_Recent_Advances_and_Research_Perspect
31 pages
8896ad74 1645604786190
No ratings yet
8896ad74 1645604786190
81 pages
Vigenère Cipher
No ratings yet
Vigenère Cipher
12 pages
Phasec Phaseb Phasea: MCLR PGD PGC Can - H Ocs1
No ratings yet
Phasec Phaseb Phasea: MCLR PGD PGC Can - H Ocs1
2 pages
Feistel Network
No ratings yet
Feistel Network
4 pages
Katalog Blue Eagle
0% (1)
Katalog Blue Eagle
18 pages
CS Chapter 3-1 2016
No ratings yet
CS Chapter 3-1 2016
58 pages
Network Security
No ratings yet
Network Security
104 pages
PMIT-6204:: Cryptography & Steganography
No ratings yet
PMIT-6204:: Cryptography & Steganography
21 pages
Delta Doc Center D D: Description
No ratings yet
Delta Doc Center D D: Description
2 pages
Block and Stream Ciphers
No ratings yet
Block and Stream Ciphers
8 pages
Playfair Cipher The Algorithm
No ratings yet
Playfair Cipher The Algorithm
2 pages
Cryptography and Network Security: Third Edition by William Stallings
No ratings yet
Cryptography and Network Security: Third Edition by William Stallings
39 pages
Aes PPT Sem V
No ratings yet
Aes PPT Sem V
16 pages
Symmetric Crypto
100% (1)
Symmetric Crypto
12 pages
Motor Controller PIC2550 Schematics
100% (3)
Motor Controller PIC2550 Schematics
1 page
Pfranger Masonic Ciphers
No ratings yet
Pfranger Masonic Ciphers
7 pages
Network Security Essentials: Fourth Edition by William Stallings Lecture Slides by Lawrie Brown
No ratings yet
Network Security Essentials: Fourth Edition by William Stallings Lecture Slides by Lawrie Brown
46 pages
2.2-Symmetric and Asymmetric Ciphers
No ratings yet
2.2-Symmetric and Asymmetric Ciphers
103 pages
Unit 2 - Symmetric Key Cryptography
No ratings yet
Unit 2 - Symmetric Key Cryptography
30 pages
LSPWM (5) 29 03 06
No ratings yet
LSPWM (5) 29 03 06
1 page
Ciphers
0% (1)
Ciphers
3 pages
L3 Symmetric Ciphers
No ratings yet
L3 Symmetric Ciphers
64 pages
The DES Algorithm Illustrated
No ratings yet
The DES Algorithm Illustrated
12 pages
General Solution For The ADFGVX Cipher System - NSA Declassified
No ratings yet
General Solution For The ADFGVX Cipher System - NSA Declassified
23 pages
Pesos de Materiales
No ratings yet
Pesos de Materiales
17 pages