UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Symmetric Key Cryptography: Data Encryption Standard (DES), Advanced Encryption

Standard (AES), Blowfish, IDEA, Block Cipher Modes of Operations.
Number Theory: Prime and Relatively Prime Numbers, Modular Arithmetic, Fermat’s and
Euler’s Theorems, the Chinese Remainder Theorem, Discrete Logarithms.

Symmetric Key Cryptography:

DATA ENCRYPTION STANDARD (DES):
DES is a Symmetric-key algorithm for the encryption of electronic data.
Data Encryption Standard (DES) is a widely-used method of data encryption using a private
(secret) key
DES applies a 56-bit key to each 64-bit block of data. The process can run in several modes
and involves 16 rounds or operations.

Overall Structure

DES (and most of the other major symmetric ciphers) is based on a cipher known as the
Feistel block cipher.
Looking at the left-hand side of the figure, we can see that the processing of the plaintext
proceeds in three phases.
1. First, the 64-bit plaintext passes through an initial permutation (IP) that rearranges the bits
to produce the permuted input.

2. This is followed by a phase consisting of sixteen rounds of the same function, which
involves both permutation and substitution functions. The output of the last (sixteenth)
round consists of 64 bits that are a function of the input plaintext and the key. The left and
right halves of the output are swapped to produce the pre output.

3. Finally, the pre output is passed through a permutation that is the inverse of the initial
permutation function, to produce the 64-bit cipher text. With the exception of the initial
and final permutations, DES has the exact structure of a Feistel cipher,

The right-hand portion of below figure shows the way in which the 56-bit key is used.
Initially, the key is passed through a permutation function. Then, for each of the sixteen
rounds, a subkey (Ki) is produced by the combination of a left circular shift and a permutation.

1
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

The permutation function is the same for each round, but a different subkey is produced
because of the repeated shifts of the key bits.

Details of Single Round

Below figure shows the internal structure of a single round. Again, begin by focusing on the
lefthand side of the diagram.

2
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

The left and right halves of each 64-bit intermediate value are treated as separate 32-bit
quantities, labeled L (left) and R (right).

• As in any classic Feistel cipher, the overall processing at each round can be summarized in
the following formulas:

• The round key Ki is 48 bits. The R input is 32 bits. This R input is first expanded to 48 bits
by using a table that defines a permutation plus an expansion that involves duplication of
16 of the R bits .

• The resulting 48 bits are XORed with Ki. This 48-bit result passes through a substitution
function that produces a 32-bit output, which is permuted.

3
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

S-Box Design in DES:

The role of the S-boxes in the function F is illustrated in Figure 3.7. The substitution consists
of a set of eight S-boxes, each of which accepts 6 bits as input and produces 4 bits as output

Key Generation

• Returning to above figure 3.4, we see that a 64-bit key is used as input to the algorithm.

• The bits of the key are numbered from 1 through 64; every eighth bit is ignored and The
key is first subjected to a permutation.

• The resulting 56-bit key is then treated as two 28-bit quantities, labelled C0 and D 0. At
each round, Ci-1 and Di-1 are separately subjected to a circular left shift.

• These shifted values serve as input to the next round. They also serve as input to the part
labeled Permuted Choice. which produces a 48-bit output that serves as input to the
Function F(Ri-1, Ki).

Des Decryption:

4
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Whatever process we following in the encryption that process is used for decryption also but
the order of key is changed on input message (cipher text).

Reverse order of keys are K16, K15 ……, K1.

Strengths of DES:

• The DES is a symmetric key block cipher which takes 64bits cipher text and 56 bit key as
an input and produce 64 bits cipher text as output.

• The DES function is made up of P & S boxes

• P-boxes transpose bits

• S-boxes Substitution bits to generating the cipher text.

The use of 56bits keys: 56 bit key is used in encryption, there are 256 possible keys,which is
approximately 256=7.2×1016 keys, by this a brute force attack on such number of keys is
impractical. A machine performing one DES encryption per microsecond would take more
than a thousand years to break the cipher.
The nature of algorithm: Cryptanalyst can perform cryptanalysis by exploiting the
characteristic of DES algorithm but no one has succeeded in finding out the weakness. This is
possible because, in DES, they using 8-substitution tables or S-boxes in each iteration & one
P-box transition for every individual iteration.
Avalanche Effect:

key desirable property of an encryption algorithm

a small change in either the plain text or the key should produce a significant change in the
cipher text (this property is called Avalanche Effect)
DES exhibits strong avalanche Effect
Timing Attacks:

Timing attack is one in which information about the key or the plaintext is obtained by
observing how long it takes a given implementation to perform decryptions on various
ciphertexts.

The authors conclude that DES appears to be fairly resistant to a successful timing attack.

5
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

ADVANCED ENCRYPTION STANDARD:

• The Advanced Encryption Standard (AES) was published by the National Institute of
Standards and Technology (NIST) in 2001.

• AES is a block cipher intended to replace DES for commercial applications.

• It uses a 128-bit block size and a key size of 128, 192, or 256 bits. The algorithm is
referred as AES-128, AES-192 OR AES-256

• AES does not use a Feistel structure. Instead, each full round consists of four separate
functions: byte substitution, permutation, arithmetic operations over a finite field, and
XOR with a key.
AES parameters:
Key size(words/bytes/bits) 4/16/128 6/24/192 8/32/256

Plaintext block Size (words/bytes/bits) 4/16/128 4/16/128 4/16/128

Number of rounds 10 12 14

Round Key size (words/bytes/bits) 4/16/128 4/16/128 4/16/128

Expanded key size (words/bytes) 44/176 52/208 60/240

AES STRUCTURE

General structure

• The input to the encryption and decryption algorithms is a single 128-bit block. , this
block is depicted as a 4 * 4 square matrix of bytes.

• This block is copied into the State array, which is modified at each stage of encryption
or decryption.

• After the final stage, State is copied to an output matrix. These operations are depicted
in Figure 5.2a. Similarly, the key is depicted as a square matrix of bytes.

• This key is then expanded into an array of key schedule words. Figure 5.2b shows the
expansion for the 128-bit key. Each word is four bytes, and the total key schedule is 44
words for the 128-bit key

6
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

The cipher consists of N rounds, where the number of rounds depends on the key length: 10
rounds for a 16-byte key, 12 rounds for a 24-byte key, and 14 rounds for a 32-byte key (Table
5.1).
The first N-1 rounds consist of four distinct transformation functions: SubBytes, ShiftRows,
MixColumns, and AddRoundKey, which are described subsequently. The final round contains
only Three Transformations, and there is a initial single transformation (AddRoundKey)
before the first round,

7
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Detailed Structure

Figure 5.3 shows the AES cipher in more detail, indicating the sequence of
transformations in each round and showing the corresponding decryption function Four
different stages are used, one of permutation and three of substitution:
• Substitute bytes: Uses an S-box to perform a byte-by-byte substitution of the block

• ShiftRows: A simple permutation

• MixColumns: A substitution that makes use of arithmetic

• AddRoundKey: A simple bitwise XOR of the current block with a portion of the expanded
key

8
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

AES TRANSORMATION FUNCTIONS

The four transformation functions are

• Substitute bytes

• ShiftRows

• MixColumns

• AddRoundKey

Substitute Bytes Transformation

• The forward substitute byte transformation, called SubBytes, is a simple table lookup
(Figure 5.5a).

9
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

• AES defines a16 *16 matrix of byte values, called an S-box (Table 5.2a), that contains
a permutation of all possible 256 8-bit values.

• Each individual byte of State is mapped into a new byte in the following way: The
leftmost 4 bits of the byte are used as a row value and the rightmost 4 bits are used as a
column value. These row and column values serve as indexes into the S-box to select a
unique 8-bit output value. For example, the hexadecimal value3 {95} references row
9, column 5 of the S-box, which contain the value {2A}

10
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Shift Rows Transformation

• The first row of State is not altered.

• For the second row, a 1-byte circular left shift is performed. 
For the third row, a 2-byte circular left shift is performed.
• For the fourth row, a 3-byte circular left shift is performed The

following is an example of ShiftRows:

11
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Mix columns Transformation

• The forward mix column transformation, called MixColumns, operates on each

column individually.
• Each byte of a column is mapped into a new value that is a function of all four bytes in
that column.

12
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

AddRoundKey Transformation

• In the AddRoundKey transformation, the 128 bits of State are bitwise XORed with the
128 bits of the round key.
• The operation is viewed as a column wise operation between the 4 bytes of a State
column and one word of the round key; it can also be viewed as a byte-level operation.
The following is an example of AddRoundKey:

13
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

AES KEY EXPANSION

• The AES key expansion algorithm takes as input a 4-word (16-byte) key and produces
a linear array of 44 words (176 bytes).
• This is sufficient to provide a 4-word round key for the initial AddRoundKey stage and
each of the 10 rounds of the cipher.
• The key is copied into the first four words of the expanded key. The remainder of the
expanded key is filled in four words at a time.
• Each added word w[i] depends on the immediately preceding word, w [i 1], and the
word four positions back,w[i 4].

14
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

In three out of four cases, a simple XOR is used. For a word whose position in the w array is a
multiple of 4, a more complex function is used. The function ‘g’ consists of the following
subfunctions:

1. RootWord performs a one-byte circular left shift on a word. This means that an input word
[b0, b1, b2, b3] is transformed into [b1, b2, b3, b0].
2. SubWord performs a byte substitution on each byte of its input word, using the S-box.
3. The result of steps 1 and 2 is XORed with a round constant, Rcon[j].

BLOW FISH ALGORITHM:

Blow fish is a symmetric block cipher developed by Bruce Schneir in year 1993.
Blow fish is designed to have following characteristics
Speed: Blowfish encrypts data on 32-bit microprocessor at a rate of 18 clock cycles per byte.
Compact: it can run in less than 5k memory.

15
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Simple: very easy to implements.

Variably secure: the key length is variable and can be as long as 448 bits. This allows a trade
off between higher speed and higher security.
Blowfish is a feistal type model.
ALGORITHM:

• Blowfish is Feistel type model, iterating a simple encryption function 16 times.

• Blowfish block size is 64 & key can be up to 448 bits.

• Blow fish encryption 64bits blocks of plaintext into 64-bit block of cipher.

• Blow fish make use of a key that ranges from 32bits to 448 bits (one to fourteen 32-bit
keys).

• The keys are stored in a k-array (one to 14 32 bits)

K1, K2----Kj where 1≤ j ≤14.

• That key is used to generate 18 “32 bit” subkeys & four “8*32” bits S-boxes.

• The subkeys are stored in the p-array

P1, P2, -------P18

• There are four s-boxes (each s-box size is 8*32 bits) each with 256 32bit 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

Encryption and Decryption

Blowfish uses two primitive operations:

Addition: Addition of words, denoted by +, is performed modulo 2 32.

Bitwise exclusive-OR: This operation is denoted by

16
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

In the above figure

 The plaintext is divided into two 32-bit halves LE, and RE,. We use the variables LE,
and RE, to refer to the left and right half of the data after round i has completed. The
algorithm can be defined by the following pseudocode:

Single round of Blowfish

The function F is shown in below Figure. The 32-bit input to F is divided into 4 bytes. If we
label those bytes a, b, c, and d, then the function can be defined as follows:

17
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

IDEA (International Data Encryption Algorithm):

IDEA originally called “IPES” (Improved proposed Encryption Standard).

IDEA is one of a number of conventional encryption algorithms that have been proposed in
recent years to replace DES
IDEA is one of the most successful of these proposals. For example, IDEA is included in PGP.

Details of IDEA algorithm:

IDEA operates with 64-bit plain text and cipher text blocks and is controlled by a 128 bit key.
It avoids substitution boxes & lookup tables used in the block cipher.
The algorithm structure has been chosen such that different key sub-blocks are used; the
encryption process is identical to the decryption process.

18
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Encryption process in IDEA:

• The design principle behind IDEA is mixing of arithmetical operations form different
algebraic groups.

• The underling operations are

1. Exclusive-OR.

2. Addition of integers modulo 216

3. Multiplication modulo 210+1

• The algorithm structure has been chosen such that when different key sub-blocks are
used, the encryption process is identical to the decryption process

• The IDEA algorithm consists of eight rounds followed by a final transformation

function.
The algorithm divides the input into four 16-bit subblocks. Each of the rounds takes
four
16-bit subblocks as input and produces four 16-bit output blocks. The final
transformation also produces four %-bit blocks, which are concatenated to form the
64-bit ciphertext.
• Each of the rounds also makes use of six 16-bit subkeys, whereas the final
transformation uses four subkeys, for a total of 52 subkeys

19
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Key Expansion (Encryption):

• The 128-bit key is expanded into 52 16-bit keys: K1, K2, .... K52. (in diagram we
represented these keys with Z1 to z52)
Step 1: Keys K1…. K8 are generated by taking 8 chunks of 16-bits each

• Step 2: Keys K9…K16 are generated by starting from the 25 th bit, wrapping around
the first 25 bits at the end, and taking 16-bit chunks.

• Step 3: Wrap around 25 more bits to the end, and generate keys K17…K24. This
process is repeated until all keys K1…K52 are generated

Details of a Single Round:

64-bit data is divided into 4 16bit data blocks. These 4 blocks are processed through 8 rounds
and transformed by the above arithmetical operations among each other and with 6 16 bit
subkeys.

20
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

21
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

BLOCK CIPHER MODES OF OPERATION

• Mode of operation is a Technique for enhancing the effect of a cryptographic
algorithm

• four modes are intended to cover virtually all possible applications of encryption for
which a block cipher could be used
Mode Description Typical Application

Electronic Codebook Each block of 64 plaintext bits is Secure transmission of

encoded independently using the same single and small values
(ECB) key. (e.g., an encryption key)

Cipher Block Chaining The input to the encryption algorithm --General-purpose block
(CBC) is the XOR of the next 64 bits of oriented Transmission
plaintext and the preceding 64 bits of
ciphertext --Authentication

Cipher Feedback Input is processed bits at a time. --General-purpose block

(CFB) Preceding ciphertext is used as input oriented Transmission
to the encryption algorithm to produce
pseudorandom output, which is --Authentication
XORed with plaintext to produce next
unit of ciphertext

Output Feedback Input is processed bits at a time. --General-purpose block

(OFB) Preceding ciphertext is used as input oriented Transmission
to the encryption algorithm to produce
pseudorandom output, which is --Authentication
XORed with plaintext to produce next
unit of ciphertext

Counter (CTR) Each block of plaintext is XORed with --General-purpose block

an encrypted counter. The counter is oriented Transmission
incremented for each subsequent
block. -- Useful for high-speed
requirements

22
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Electronic Codebook (ECB)

• The simplest mode is the electronic codebook (ECB) mode, in which plaintext is
handled one block at a time and each block of plaintext is encrypted using the same
key (Figure 6.3).

• The term codebook is used because, for a given key, there is a unique ciphertext for
every b bit block of plaintext.

We can define ECB mode as follows

Advantages:
• The ECB method is ideal for a short amount of data, such as an encryption key. Thus,
if you want to transmit a DES key securely, ECB is the appropriate mode to use.
• The most significant characteristic of ECB is that the same b-bit block of plaintext, if
it appears more than once in the message, always produces the same ciphertext.
Disadvantages:
• For lengthy messages, the ECB mode may not be secure. If the message is highly
structured, it may be possible for a cryptanalyst to exploit these regularities.
• For example, if it is known that the message always starts out with certain predefined
fields, then the cryptanalyst may have a number of known plaintext ciphertext pairs to
work with.

23
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Cipher Block Chaining Mode(CBC)

To overcome the security deficiencies of ECB, we would like a technique in which the same
plaintext block, if repeated, produces different ciphertext blocks.
A simple way to satisfy this requirement is the cipher block chaining (CBC) mode (Figure
6.4). In this scheme, the input to the encryption algorithm is the XOR of the current plaintext
block and the preceding ciphertext block; the same key is used for each block. In effect, we
have chained together the processing of the sequence of plaintext blocks

We can define CBC mode as follows

Initialization Vector:
• To produce the first block of ciphertext, an initialization vector (IV) is XORed with
the first block of plaintext.
• On decryption, the IV is XORed with the output of the decryption algorithm to
recover the first block of plaintext.
• The IV must be known to both the sender and receiver but be unpredictable by a
third party.
• For maximum security, the IV should be protected against unauthorized changes.

24
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Cipher Feedback Mode(CFB)

For AES, DES, or any block cipher, encryption is performed on a block of b bits. In the case
of DES, b=64 and in the case of AES, b=128. However, it is possible to convert a block cipher
into a stream cipher, using one of the three modes to be discussed in this and the next two
sections: cipher feedback (CFB) mode, output feedback (OFB) mode, and counter (CTR)
mode.
● Message is treated as a stream of bits.

● Result is feedback for next stage (hence name)

● CFB-64 is used most often (most efficient)

● Applications: stream data encryption, authentication

The encryption function is

We can define CBC mode as follows

25
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Output feedback mode:

The output feedback (OFB) mode is similar in structure to that of CFB. As can be seen in
Figure 6.6, it is the output of the encryption function that is fed back to the shift register in
OFB, whereas in CFB, the ciphertext unit is fed back to the shift register. The other difference
is that the OFB mode operates on full blocks of plaintext and ciphertext, not on an n-bit
subset. Encryption can be expressed as

26
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

We can define OFB mode as follows

Advantage of OFB:
• One advantage of the OFB method is that bit errors in transmission do not
propagate.
• For example, if a bit error occurs in C1 only the recovered value of is P1 affected;
subsequent plaintext units are not corrupted.
Disadvantage of OFB:
• The disadvantage of OFB is that it is more vulnerable to a message stream
modification attack than is CFB.

27
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Counter Mode

Although interest in the counter (CTR) mode has increased recently with applications to ATM
(Asynchronous transfer mode) network security and IP sec (IP security)
• A counter, equal to the plaintext block size is used. The only requirement is that the
counter value must be different for each plaintext block that is encrypted.
• Typically, the counter is initialized to some value and then incremented by 1 for each
subsequent block (modulo 2b where b is the block size).
• For encryption, the counter is encrypted and then XORed with the plaintext block to
produce the ciphertext block; there is no chaining

We can define CTR mode as follows

Advantages of CTR mode:

• Hardware and software efficiency: Unlike the three chaining modes, encryption (or
decryption) in CTR mode can be done in parallel on multiple blocks of plaintext or
ciphertext.

28
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

• Preprocessing: The execution of the underlying encryption algorithm does not depend
on input of the plaintext or ciphertext. Therefore, if sufficient memory is available and
security is maintained.
• Random access: The ith block of plaintext or ciphertext can be processed in random-
access fashion. With the chaining modes, block Ci cannot be computed until the i - 1
prior block are computed.
• Provable security: It can be shown that CTR is at least as secure as the other modes
discussed in this section.
• Simplicity: Unlike ECB and CBC modes, CTR mode requires only the
implementation of the encryption algorithm and not the decryption algorithm.

NUMBER THEORY:
Prime Numbers

Relative Prime Numbers

Two numbers are said to be relative prime numbers when they share no factors in common other
than one

If two integers a, b are relatively prime if gcd (a,b)=1.

Examples:

1) 15 and 28 are relatively prime numbers

29
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

15=the factors are (1,3,5)

28=the factors are (1,2,4,7)
2) 7 and 20 are relatively prime numbers
3) 12 and 13 are relatively prime numbers

MODULAR ARITHMETIC

The Modulus

If ‘a’ is an integer and ‘n’ is a positive integer, we define a mod n to be the remainder when is ‘a’
is divided by ‘n’. The integer is called the modulus. Thus, for any integer, we can write the
Equation as follows:
a = qn + r

example:11 mod 7 = 4; - 11 mod 7 = 3

Congruence

Two integers and are said to be congruent modulo n, if (a mod n)= (b mod n).This is written
as

We say that a is congruent to b modulo m if m divides b-a or a-b. Examples:

20 0( mod 10)

Properties of Congruences

Modular Arithmetic Operations

30
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Examples:

Modular Addition and Multiplication

Table 4.2 provides an illustration of modular addition and multiplication modulo 8

31
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Properties of Modular Arithmetic

32
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

33
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

X=8

34
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

35
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

36
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

37
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

38
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

DISCRETE LOGARITHMS

Primitive root

If a is a primitive root of n then its powers

39
UNIT-2 CRYPTOGRAPHY & NETWORK SECURITY

Logarithms in modular arithmetic:

40