UNIT -II

Symmetric Encryption
Mathematics of Symmetric Key Cryptography, Introduction to Modern Symmetric Key Ciphers,
Data Encryption Standard, Advanced Encryption Standard.

Mathematics of Symmetric Key Cryptography:

Cryptography ?
Cryptography is a technique of securing information and communications through use of codes. Thus
preventing unauthorized access to information. The prefix “crypt” means “hidden” and suffix graphy means
“writing”.
Cryptography Types:

1) Symmetric Key Cryptography:

The sender and receiver of message use a single common key to encrypt and decrypt messages.

2) Asymmetric Key Cryptography:

A pair of keys is used to encrypt and decrypt information. A public key is used for encryption and a private
key is used for decryption. Even if the public key is known by everyone the intended receiver can only
decode it because he alone knows the private key.

3) Hash Functions:
There is no usage of any key in this algorithm. A hash value with fixed length is calculated as per the
plain text which makes it impossible for contents of plain text to be recovered..

Symmetric Key Cipher

The sender and receiver of message use a single common key to encrypt and decrypt messages.

If P is the plaintext, C is the ciphertext, and K is the key,

 We assume that Bob creates P1; we prove that P1 = P:

Figure Locking and unlocking with the same key

Kerckhoff’s Principle
Based on Kerckhoff’s principle, one should always assume that the adversary, Eve, knows the
encryption/decryption algorithm. The resistance of the cipher to attack must be based only on the secrecy
of the key.

Cryptanalysis
As cryptography is the science and art of creating secret codes, cryptanalysis is the science and art of breaking those
codes.

Ciphertext-Only Attack
Figure Ciphertext-only attack

In Ciphertext-Only Attack , the attacker knows only some cipher text. He try to find
corresponding key and plain text using various methods.
Brute-Force attack: Attacker tries all possible keys. We assume that he knows key domain
Statistical attack: The cryptanalyst can benefit from some inherent charactersistics of the plain text language
to perform statistical attack. Example: Letter E is most frequently used character in English.
Known-Plaintext Attack
Figure Known-plaintext attack

In this attack, he know some cipher text and plain text pairs that were sent previously by Alice to Bob. Attacker has
kept both cipher text and plain text to use them to break the next secrete message.

Chosen-Plaintext Attack
Figure Chosen-plaintext attack

This is similar to known-plaintext attack, but plaintext/cipher text pairs have been choosen by the attacker .
This can happen when attacker has access to Alice computer. She can choose some plaintext and interpret
ciphertext.

Chosen-Ciphertext Attack
Figure Chosen-Ciphertext attack

This is similar to Chosen Plaintext attack except eve chooses some ciphertext and decrypt it to from a
cipher/plain text pairs. This can happen when Eve has access to Bob computer.
 Categories of Traditional Ciphers:

1. SUBSTITUTION CIPHERS
A substitution cipher replaces one character with another
2. TRANSPOSITION CIPHERS
A Transposition cipher reorders symbols
1. SUBSTITUTION CIPHERS
A substitution cipher replaces one symbol with another. Substitution ciphers can be categorized as either
monoalphabetic ciphers or polyalphabetic ciphers.
Note:
A substitution cipher replaces one symbol with
Monoalphabetic Ciphers:

In monoalphabetic substitution, the relationship between a symbol in the plaintext to a symbol in the ciphertext is alway

Example 1
The following shows a plaintext and its corresponding ciphertext. The cipher is probably
monoalphabetic because both l’s (els) are encrypted as O’s.

Example 2
The following shows a plaintext and its corresponding ciphertext. The cipher is not monoalphabetic
because each l (el) is encrypted by a different character. The first l (el) is encrypted with N;the second as Z

Additive Cipher
The simplest monoalphabetic cipher is the additive cipher. This cipher is sometimes called a shift cipher and
sometimes a Caesar cipher, but the term additive cipher better reveals its mathematical nature.
Figure Plaintext and ciphertext in Z26

Figure Additive cipher

Note:
When the cipher is additive, the plaintext, ciphertext, and key are integers in Z26.
Example:
Use the additive cipher with key = 15 to encrypt the message “hello”.
Solution
We apply the encryption algorithm to the plaintext, character by character:

Example:
Use the additive cipher with key = 15 to decrypt the message “WTAAD”.
Solution
We apply the decryption algorithm to the plaintext character by character:

Shift Cipher and Caesar Cipher

Historically, additive ciphers are called shift ciphers. Julius Caesar used an additive cipher to
communicate with his officers. For this reason, additive ciphers are sometimes referred to as the Caesar
cipher. Caesar used a key of 3 for his communications.
Note:
Additive ciphers are sometimes referred to as shift ciphers or Caesar cipher

Multiplicative Ciphers
Figure Multiplicative cipher
Note:

In a multiplicative cipher, the plaintext and ciphertext are integers in Z26; the key is an integer in Z26*.

Example1:

What is the key domain for any multiplicative cipher?

Solution: The key needs to be in Z26*. This set has only 12 members: 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25.

Example2:

We use a multiplicative cipher to encrypt the message “hello” with a key of 7. The ciphertext is “XCZZU”.

Affine Ciphers:
Combine additve and multiplicative Ciphers

Example1:
The affine cipher uses a pair of keys in which the first key is from Z26* and the second is from Z26.
The size of the key domain is
26 × 12 = 312.
Example2:
Use an affine cipher to encrypt the message “hello” with the key pair (7, 2).
Monoalphabetic Substitution Cipher
Because additive, multiplicative, and affine ciphers have small key domains, they are very vulnerable to
brute-force attack.
A better solution is to create a mapping between each plaintext character and the corresponding ciphertext
character. Alice and Bob can agree on a table showing the mapping for each character.
Figure An example key for monoalphabetic substitution cipher

Example:

We can use the key in Figure to encrypt the message

The ciphertext is

Reference

Polyalphabetic Ciphers
In polyalphabetic substitution, each occurrence of a character may have a different substitute. The
relationship between a character in the plaintext to a character in the ciphertext is one-to-many.
Example ‘a’ can be enciphered as ‘D’ in the beginning of the text, but as ‘N’ at the middle.
Polyalphabetic has advantage of hiding the letter frequency.
Example: Autokey Cipher

Example:
Assume that Alice and Bob agreed to use an autokey cipher with initial key value k1 = 12. Now
Alice wants to send Bob the message “Attack is today”. Enciphering is done character by character.
TRANSPOSITION CIPHERS
A transposition cipher does not substitute one symbol for another, instead it changes the location of
the symbols. A symbol in the first position may appaer in the tenth position of the cipher. A symbol in
the eighth position may appear in the first osition of the cipher.
Note: A transposition cipher reorders symbols
Keyless Transposition Ciphers
Simple transposition ciphers, which were used in the past, are keyless.
Example 1:
A good example of a keyless cipher using the first method is the rail fence cipher. The ciphertext is
created reading the pattern row by row. For example, to send the message “ Meet me at the park” to Bob,
Alice writes

She then creates the ciphertext “MEMATEAKETETHPR”.

Example 2:
Alice and Bob can agree on the number of columns and use the second method. Alice writes the
same plaintext, row by row, in a table of four columns.

She then creates the ciphertext “MMTAEEHREAEKTTP” by transmitting the characters column by
column. Bob receives the cipher text and follows the reverse process to get plain text .
Example:
The cipher in previous example is actually a transposition cipher. The following shows the permutation of
each character in the plaintext into the ciphertext based on the positions.

The second character in the plaintext has moved to the fifth position in the ciphertext; the third character
has moved to the ninth position; and so on.Although the characters are permuted, there is a pattern in the
permutation: (01, 05, 09, 13), (02, 06, 10, 13), (03, 07, 11, 15), and (4, 8, 12). In each section, the difference
between the two adjacent numbers is 4.
Keyed Transposition Ciphers
The keyless ciphers permute the characters by using writing plaintext in one way and reading it in another
way The permutation is done on the whole plaintext to create the whole ciphertext.
Another method is to divide the plaintext into groups of predetermined size, called blocks, and then use a
key to permute the characters in each block separately.
Example
Alice needs to send the message “Enemy attacks tonight” to Bob..

The key used for encryption and decryption is a permutation key, which shows how the character
are permuted.

The permutation yields

Combining Two Approaches for better result

Encryption or decryption is done in 3 steps:
1) Text is written into row by row
2) Permutation is done by reordering columns
3) New table is read column by column
Example
Keys
In the previous Example, a single key was used in two directions for the column exchange: downward for
encryption, upward for decryption. It is customary to create two keys.

Figure Encryption/decryption keys in transpositional ciphers

Key inversion in a transposition cipher

 Stream Ciphers and Block Ciphers
Stream Ciphers
• A stream cipher is one that encrypts a digital data stream one bit or one byte at a time. Examples of
classical stream ciphers are the autokeyed Vigenère cipher and the Vernamcipher.

Block Ciphers
A block cipher is one in which a block of plaintext is treated as a whole and used to produce a cipher text
block of equal length. Typically, a block size of 64 or 128 bits is used.

Modern Block Ciphers

A symmetric-key modern block cipher encrypts an n-bit block of plaintext or decrypts an n-bit block of
cipher text. The encryption or decryption algorithm uses a k-bit key. The Decryption algorithm must be the
inverse of the encryption algorithm and must use the same secrete key.
Figure A modern block cipher
Example: How many padding bits must be added to a message of 100 characters if 8-bit ASCII is used for
encoding and the block cipher accepts blocks of 64 bits?
Solution
Encoding 100 characters using 8-bit ASCII results in an 800-bit (100x8) message. The plaintext must be
divisible by 64. If | M | and |Pad| are the length of the message and the length of the padding,

A modern block cipher can be designed to act as a substitution cipher or a transposition cipher.
To be resistant to exhaustive-search attack, a modern block cipher needs to be designed as a substitution
cipher.
Example
Suppose that we have a block cipher where n = 64. If there are 10 1’s in the ciphertext, how many trial-and-
error tests does Eve need to do to recover the plaintext from the intercepted ciphertext in each of the
following cases?
a. The cipher is designed as a substitution cipher.
b. The cipher is designed as a transposition cipher.

Solution
a) In the first case, Eve has no idea how many 1’s are in the plaintext. Eve needs to try all possible 264
64-bit blocks to find one that makes sense.
b) In the second case, Eve knows that there are exactly 10 1’s in the plaintext. Eve can launch an
exhaustive-search attack using only those 64-bit blocks that have exactly 101’s.

Components of a Modern Block Cipher

Modern block ciphers normally are keyed substitution ciphers in which the key allows only partial mappings
from the possible inputs to the possible outputs. It usses P-Boxes,S-Boxes.
P-Boxes
P-Boxes(also called ad D-Box means Diffusion box)
A P-box (permutation box) parallels the traditional transposition cipher for characters. It transposes bits.
Three types of P-boxes

Example
Figure shows all 6 possible mappings of a 3 × 3 P-box.

The possible mappings of a 3 × 3 P-box

Straight P-Boxes
Table Example of a permutation table for a straight P-box(64x64)
At output of P-Box:
Input 58 goes to 1st position, input 50 goes to 2nd position, input 42 to 3rd position,….

Example

Design an 8 × 8 permutation table for a straight P-box that moves the two middle bits (bits 4 and 5) in the
input word to the two ends (bits 1 and 8) in the output words. Relative positions of other bits should not be
changed.
Solution

We need a straight P-box with the table [4 1 2 3 6 7 8 5]. The relative positions of input bits 1, 2, 3, 6, 7,
and 8 have not been changed, but the first output takes the fourth input and the eighth output takes the fifth
input.
Compression P-Boxes
Example of a 32 × 24 permutation table

Some of the input bits are blocked at output: example: 7,8,9,15,16,23,24,25

Expansion P-Boxes
Example of a 12 × 16 permutation table

1,3,9,12 are mapped to two outputs

P-Boxes: Invertibility
A straight P-Box is invertible, that means we use straight P-Box in encryption cipher and its inverse in
decryption cipher.

Note

A straight P-box is invertible, but compression and expansion P-boxes are not.

Example

Figure shows how to invert a permutation table represented as a one-dimensional table.

Figure Compression and expansion P-boxes are non-invertible

S-Box
An S-box (substitution box) can be thought of as a small substitution cipher
Note
An S-box is an m × n substitution unit, where m and n are not necessarily the same.
Linear S-Box: if the inputs are x1,x2,x3… and outputs are y1,y2,y3… and relationship between them is
Y1=f1(x1,x2,x3..) ,
Y2=f2 (x1,x2,x3..)
…..
Then above relation can be expressedas
Y1=a11x1+a12x2+…
Y2=a21x1+a22x2+…

Example: In a nonlinear s-box, such boxes can have ‘and’ terms like x1x2, x3x5…
In an S-box with three inputs and two outputs, we have

The S-box is linear because a1,1 = a1,2 = a1,3 = a2,1 = 1 and a2,2 = a2,3 = 0. The relationship can be
represented by matrices, as shown below:

Example
In an S-box with three inputs and two outputs, we have
where multiplication and addition is in GF(2). The S-box is nonlinear because there is no linear relationship
between the inputs and the outputs.
Example
The following table defines the input/output relationship for an S-box of size 3 × 2. The leftmost bit of the
input defines the row; the two rightmost bits of the input define the column. The two output bits are values
on the cross section of the selected row and column.

Based on the table, an input of 010 yields the output 01. An input of 101 yields the output of 00.
S-Boxes: Invertibility
An S-box may or may not be invertible. In an invertible
S-box, the number of input bits should be the same as the number of output bits.
Example
Figure shows an example of an invertible S-box. For example, if the input to the left box is 001, the output
is 101. The input 101 in the right table creates the output 001, which shows that the two tables are inverses
of each other.

Exclusive-OR
An important component in most block ciphers is the exclusive-or operation.
Invertibility of the exclusive-or operation

Product Ciphers
Shannon introduced the concept of a product cipher. A product cipher is a complex cipher combining
substitution, permutation, and other components .
Combination of S-box and P-box transformation—a product cipher.
Two classes of product ciphers:
a) Feistel ciphers, Example DES(data encryption standard)
b) Non-feistel Ciphers, Example AES(Advanced Encryptin system)
Diffusion
The idea of diffusion is to hide the relationship between the ciphertext and the plaintext.

Confusion
The idea of confusion is to hide the relationship between the ciphertext and the key.

Rounds
Diffusion and confusion can be achieved using iterated product ciphers where each iteration is a
combination of S-boxes, P-boxes, and other components.

Figure A product cipher made of two rounds

Feistel Cipher Structure:

• Feistel Cipher is not a specific scheme of block cipher. It is a design model from which many
different block ciphers are derived.
• DES is just one example of a Feistel Cipher.
• A cryptographic system based on Feistel cipher structure uses the same algorithm for both
encryption and decryption.
• The input block to each round is divided into two halves that can be denoted as L and R for the left
half and the right half.
• In each round, the right half of the block, R, goes through unchanged. But the left half, L, goes
through an operation that depends on R and the encryption key. First, we apply an encrypting
function ‘f’ that takes two input − the key K and R. The function produces the output f(R,K). Then,
we XOR the output of the mathematical function with L.
Block Cipher Design Principles
Block size: Larger block sizes mean greater security (all other things being equal) but reduced
encryption/decryption speed for a given algorithm. The greater security is achieved by greater diffusion.
Key size: Larger key size means greater security but may decrease encryption/ decryption speed. The
greater security is achieved by greater resistance to brute-force attacks and greater confusion
Number of rounds: The essence of the Feistel cipher is that a single round offers inadequate security but
that multiple rounds offer increasing security. A typical size is 16 rounds.
Subkey generation algorithm: Greater complexity in this algorithm should lead to greater difficulty of
cryptanalysis.
Round function F: Again, greater complexity generally means greater resistance to cryptanalysis.
Diffusion And Confusion:- The terms diffusion and confusion were introduced by Claude Shannon to
capture the two basic building blocks (Plain Text & Cipher Text) for any cryptographic system.
Data Encryption Standard (DES)
The Data Encryption Standard (DES) is a symmetric-key block cipher published by the National Institute of
Standards and Technology (NIST).
DES is an implementation of a Feistel Cipher. It uses 16 round Feistel structure. The block size is 64 -bit.
Though, key length is 64-bit, DES has an effective key length of 56 bits, since 8 of the 64 bits of the key are
not used by the encryption algorithm (function as check bits only).
 DES Symmetric key Block Cipher
algorithm. DES follows Feistel cipher
structure.
Plain Text Block Size :
64 Bits Cipher Text Size :
64 Bits
Master Key Size : 64 / 56
Bits No. Of Rounds 16
Round Key / Subkey Size: 48 Bits.

Initial Permutation & Inverse Initial Permutation

The initial permutation and its inverse are defined by tables, as shown in Tables.
The tables are to be interpreted as follows.
The input to a table consists of 64 bits numbered from 1 to 64.
The 64 entries in the permutation table contain a permutation of the numbers from 1 to 64.
Each entry in the permutation table indicates the position of a numbered input bit in the output, which also
consists of 64 bits.
The initial and final permutations are straight Permutation boxes (P-boxes) that are inverses of each other.
Note:
Initial Permutation & Inverse Initial Permutations have no cryptography significance in DES.

Input Table

In output
At 1st place 58
At 2nd place 50
At 3rd place 42 ..

In output
At 1st place 40
At 2nd place 8
At 3rd place 48 ..

Rounds
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 as defined by Table.
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. These transformations are
defined in Table 3.3, which is interpreted as follows: The first and last bits of the input to box Si form a 2-
bit binary number to select one of four substitutions defined by the four rows in the table for Si. The middle
four bits select one of the sixteen columns. The decimal value in the cell selected by the row and column is
then converted to its 4-bit representation to produce the output. For example, in S1, for input 011001, the
row is 01 (row 1) and the column is 1100 (column 12). The value in row 1, column 12 is 9, so the output is
1001.
Round Function
The heart of this cipher is the DES function, f. The DES function applies a 48-bit key to the rightmost 32
bits to produce a 32-bit output.

Expansion Permutation Box − Since right input is 32-bit and round key is a 48-bit, we first need to expand
right input to 48 bits. Permutation logic is graphically depicted in the following illustration −

The graphically depicted permutation logic is generally described as table in DES specification illustrated as
shown −
XOR (Whitener). − After the expansion permutation, DES does XOR operation on the expanded right
section and the round key. The round key is used only in this operation.
Substitution Boxes. − The S-boxes carry out the real mixing (confusion). DES uses 8 S-boxes, each with a
6-bit input and a 4-bit output. Refer the following illustration −

The S-box rule is illustrated below −

There are a total of eight S-box tables.
The output of all eight s-boxes is then combined in to 32 bit section.
The 32-bit output from the eight S-boxes is then permuted, so that on the next round, the output from
each S-box immediately affects as many others as possible.

Straight Permutation
− The 32 bit output of S-boxes is then subjected to the straight permutation with rule shown in the
following illustration:

DES Key Generation

The round-key generator creates sixteen 48-bit keys out of a 56-bit cipher key. The process of key
generation is depicted in the following illustration −
DES Decryption

As with any Feistel cipher, decryption uses the same algorithm as encryption, except that the application of
the subkeys is reversed.

DES Analysis
Two desired properties of a block cipher are the Avalanche effect and the completeness.
Avalanche effect :
A small change in plaintext results in the very great change in the ciphertext.

Completeness effect:
Completeness effect means that each bit of ciphertext needs to depends on many bits on the plaintext. The
diffusion and confusion produced by P-Boxes and S-Boxes in DES, show a very strong completeness effect.

DES Weaknesses Analysis

Weakness in Cipher Design:
It is not clear why the designers of DES used the initial and final permutations; these have no security
benefits.
In the expansion permutation, the first and fourth bits of every 4-bit series are repeated.
Weakness in Cipher Key:
o DES Key size is 56 bits. To do Brute force attack on a given ciphertext block, the adversary needs to
check 256 keys.
With available technology it is possible to check 1 million keys per second

Double – DES
 Triple – DES

Triple DES was developed in 1999 by IBM – by a team led by Walter Tuchman. DES prevents a meet-in-
the-middle attack. 3- DES has a 168-bit key and enciphers blocks of 64 bits.

3-DES with 2 Keys:

3- DES with 3 Keys:
The encryption-decryption process is as follows −
Encrypt the plaintext blocks using single DES with key K1.
Now decrypt the output of step 1 using single DES with key K2.
Finally, encrypt the output of step 2 using single DES with key K3.
The output of step 3 is the ciphertext.
Decryption of a ciphertext is a reverse process. User first decrypt using K 3, then encrypt with K2, and finally
decrypt with K1.

Advanced Encryption Standard

(AES Algorithm)
• The Advanced Encryption Standard (AES) was published by the National Institute of Standards and
Technology (NIST) in 2001.
• AES is a symmetric block cipher that is intended to replace DES.
The features of AES are as follows −
• Symmetric key symmetric block cipher
• 128-bit data, 128/192/256-bit keys
• Stronger and faster than Triple-DES
• Provide full specification and design details
• Software implementable in C and Java

AES is an iterative rather than Feistel cipher. It is based on ‘substitution–permutation network’. It

comprises of a series of linked operations, some of which involve replacing inputs by specific outputs
(substitutions) and others involve shuffling bits around (permutations).
Interestingly, AES performs all its computations on bytes rather than bits. Hence, AES treats the 128 bits
of a plaintext block as 16 bytes. These 16 bytes are arranged in four columns and four rows for
processing as a matrix.
 Unlike DES, the number of rounds in AES is variable and depends on the length of the key.
AES uses 10 rounds for 128-bit keys, 12 rounds for 192-bit keys and 14 rounds for 256-bit keys. Each
of these rounds uses a different 128-bit round key, which is calculated from the original AES key.

The schematic of AES structure is given in the following illustration

ROUNDS
• Unlike DES, the number of rounds in AES is variable and depends on the length of the key.
• AES uses 10 rounds for 128-bit keys,
• 12 rounds for 192-bit keys and
• 14 rounds for 256-bit keys.
• Each of these rounds uses a different 128-bit round key, which is calculated from the original AES
key.

Each round comprise of four sub-processes. The first round process is depicted below −
AES Transformations:

There are four transformation functions used in AES Cipher at each round.
1. Substitute Bytes Transformation
 2. ShiftRows Transformation
3. MixColumns Transformation
4. AddRoundKey Transformation

1. Byte Substitution (SubBytes)

The 16 input bytes are substituted by values as specified in a
table (S-box) given in design.
Each input 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(in hexadecimal form) and the rightmost 4
bits are used as a column value(in hexadecimal form) in S-boxtable.
For example, the hexadecimal value {95} references row 9, column 5 of the S-box, which contains the
value {2A}. Accordingly, the value {95} is mapped into the value {2A}.

2. ShiftRows Transformation:

 In this transformation bytes are permuted(shifted).

 In the Encryption, the tranformation is called Shiftrows and the shifting is to the left.
 The number of shifts depends on the row number(0,1,2,or 3) of the state matrix as shown below:
The following is an example of ShiftRows.

The inverse shift row transformation, called InvShiftRows, performs the circular shifts in the
opposite direction for each of the last three rows, with a 1-byte circular right shift for the second row, and so
on.

3. MixColumns Transformation:
Mixing is the transformaton that changes bits inside byte.
This operation takes 4 bytes(a column) and by multiplying it with a constant matrix then mixes them that
produces new bytes.
MixColumn: operates on each column individually. Each byte of a column is mapped into a new value.
It takes a column from state and multiply it with a constant square matrix.
The byte values are represented as polynomials with coefficients in GF(2) and mulitplications are done in
GF(28)

Constant matrices for multiplications:

4. AddRoundKey Transformation:
 To make the ciphertext more secrete, we add cipher key to the data in a state.
 AddRoundKey is same as to MixColumns but performs addition operation instead of multiplication.
The following is an example of AddRoundKey:

The first matrix is State, and the second matrix is the round key.

AES Key Expansion:

 The AES key expansion algorithm takes as input a four-word (16-byte) key and produces a linear
array of 44 words (176 bytes). This is sufficient to provide a four-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 remain- der 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]. 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. Figure
illustrates the generation of the expanded key, using the symbol g to represent that complex function.
The function g consists of the following subfunctions.
For example, suppose that the round key for round 8 is
EA D2 73 21 B5 8D BA D2 31 2B F5 60 7F 8D 29 2F
Then the first 4 bytes (first column) of the round key for round 9 are calculated as follows:
ANALYSIS OF AES
Security
• AES was designed after DES. Most of the known attacks on DES were already tested on AES.
• Brute-Force Attack
• AES is definitely more secure than DES due to the larger-size key.
• Statistical Attacks
• Numerous tests have failed to do statistical analysis of the ciphertext.
• Differential and Linear Attacks
• There are no differential and linear attacks on AES as yet.
Implementation
• AES can be implemented in software, hardware, and firmware. The implementation can use table
lookup process or routines that use a well-defined algebraic structure.
Simplicity and Cost
• The algorithms used in AES are so simple that they can be easily implemented using cheap
processors and a minimum amount of memory.
UNIT –III
Asymmetric Encryption
Mathematics of Asymmetric Key Cryptography, Asymmetric Key Cryptography

Primes and Related Congruence Equations

PRIMES
Asymmetric-key cryptography uses prime numbers extensively.
A prime is divisible only by itself and 1.

Figure Three groups of positive integers

Example 1:
What is the smallest prime?
The smallest prime is 2, which is divisible by 2 (itself) and 1.
Example 2:
List the primes smaller than 10.
There are four primes less than 10: 2, 3, 5, and 7. It is interesting to note that the percentage of primes
in the range 1 to 10 is 40%. The percentage decreases as the range increases.
Cardinality of Primes
We can use infinite Number of Primes.
Number of Primes
π(x) is the number of primes less than or equal to x. π is not similar to mathematics π.
The primes under 25 are 2, 3, 5, 7, 11, 13, 17, 19 and 23 so π(3) = 2, π(10) = 4 and π(25) = 9.

A Table of values of π(x)

Example 1
Find the number of primes less than 1,000,000.
The approximation gives the range 72,383 to 78,543.
The actual number of primes is 78,498.
Checking for Primeness
Given a number n, how can we determine if n is a prime? The answer is that we need to see if the number is
divisible by all primes less than

We know that this method is inefficient, but it is a good start.

Example 1:
Is 97 a prime?
The floor of π(97) = 9. The primes less than 9 are 2, 3, 5, and 7. We need to see if 97 is divisible by any of
these numbers. It is not, so 97 is a prime.
Example 2:
Is 301 a prime?
The floor of π(301) = 17. We need to check 2, 3, 5, 7, 11, 13, and 17. The numbers 2, 3, and 5 do not divide
301, but 7 does. Therefore 301 is not a prime.

Fermat’s Little Theorem

First Version: if p is prime and a is positive integer, then
ap − 1 ≡ 1 mod p
Second Version:
ap ≡ a mod p
This means that if we divide ap by p then the remainder should be ‘a’.

Example 1:
Find the result of 610 mod 11.
We have 610 mod 11 = 1. This is the first version of Fermat’s little theorem where p = 11.
Example 2
Find the result of 312 mod 11.
Here the exponent (12) and the modulus (11) are not the same. With substitution this can be solved using
Fermat’s little theorem.

Multiplicative Inverses
a−1 mod p = a p − 2 mod p
Example
The answers to multiplicative inverses modulo a prime can be found without using the extended Euclidean
algorithm:
 Example:
How to calculate multiplicative inverse of 5 modulo 23 that is 5-1 mod 23?
Solution:
1. 5-1 mod 23 = 523-2 mod 23 (Ref: a-1 mod p= ap-2 mod p)
2. 523-2 mod 23 = 521 mod 23
3. Calculate following to solve 521 mod 23:
51 mod 23 = 5
52 mod 23=25 mod 23=2
54 mod 23= (52)2 mod 23= (2)2 mod 23=4
58 mod 23= (54)2 mod 23 (4)2 mod 23=16
516 mod 23= (58)2 mod 23 (16)2 mod23=256 mod 23=3
Now binary equivalence of 21 is 10101, so multiply 51 , 54 and 516 values, leave 52 and 58 because these are
0’s in binary form.
521 mod 23 = (516 x 54 x 51 ) mod 23=(3x4x5) mod 23=60 mod 23= 14 mod 23.
Finally 5-1 mod 23 = 521 mod 23 = 14 mod 23

Euler's totient function

Euler's totient function, also known as phi-function ϕ(n), this function counts the number of integers that are
both smaller than n and relatively prime to n (coprime). Two numbers are coprime if their greatest
common divisor equals 1.
Here are values of ϕ(n) for the first few positive integers:

Example: Find co-primes of 9?

If we check gcd(9,1), gcd(9,2), gcd(9,4), gcd(9,5), gcd(9,7), gcd(9,8) =1,
So, coprimes to 9 are 1,2,4,5,7,8 and their count ϕ(9)=6
Properties
• ϕ(1)=0
• If p is a prime number, ϕ(p)=p−1
• If a and b are relatively prime, then: ϕ(ab)=ϕ(a)⋅ϕ(b).
• If p is a prime, ϕ(pe)=pe - pe-1
Examples:
1) Find ϕ(7)?
ϕ(7)=7-1=6
2)Find ϕ(21)?
ϕ(21)= ϕ(3x7) = ϕ(3)x ϕ(7)=2x6=12
3)Find ϕ(77)?
ϕ(77)= ϕ(7x11) = ϕ(7)x ϕ(11)=6x10=60
4) Find ϕ(32)?
ϕ(32)= (32)- (32-1) = 9-3=6
5) What is the value of ϕ (13)?
Because 13 is a prime, ϕ (13) = (13 −1) = 12.
6)What is the value of ϕ (10)?
We can use the third rule: ϕ (10) = ϕ (2) × ϕ (5) = 1 × 4 = 4, because 2 and 5 are primes.
7)What is the value of ϕ (240)?
We can write 240 = 24 × 31 × 51. Then
ϕ (240) = (24 −23) × (31 − 30) × (51 − 50) = 64
8)Can we say that ϕ (49) = ϕ (7) × ϕ (7) = 6 × 6 = 36?
No. The third rule applies when m and n are relatively prime. Here 49 = 72. We need to use the fourth rule: ϕ
(49) = 72 − 71 = 42.
9) What is the number of elements in Z *?
14
The answer is ϕ (14) = ϕ (7) × ϕ (2) = 6 × 1 = 6. The members are 1, 3, 5, 9, 11, and 13.

Note: Interesting point: If n > 2, the value of f(n) is even.

Euler’s Theorem
First Version:For every a and n, they are relatively prime then
a ϕ(n) ≡ 1 (mod n)
Second Version
a k × f(n) + 1 ≡ a (mod n)
Note: The second version of Euler’s theorem is used in the RSA cryptosystem.

Example 2:
Find the result of 624 mod 35.
Solution
We have 624 mod 35 = 6 ϕ (35) mod 35 = 1.
Example :
Find 34 mod 10 ?
Solution

Example 3:
Find the result of 2062 mod 77.
Solution
If we let k = 1 on the second version,
we have f(77)= f(7)x f(11)=6x10=60
2062 mod 77 = (20 mod 77) (2060+1 mod 77) mod 77=
(20 mod 77) (20f(77) + 1 mod 77) mod 77
= (20)(20) mod 77 = 15.
Multiplicative Inverses
Euler’s theorem can be used to find multiplicative inverses modulo a composite.
Example:
The answers to multiplicative inverses modulo a composite can be found without using the extended
Euclidean algorithm if we know the factorization of the composite:

Primitive Root and Multiplicative Orders

Multiplicative Order:
If 'a' and 'n‘ are relatively prime, then
The multiplicative order of ‘a’ modulo n is smallest positive integer 'k' with
ak≡1 (mod n)
The order of modulo ‘n’ is written as ordn(a) or On(a)
Example 1: Define multiplicative order of 4 mod 7
41=4 ≡ 3 (mod 7)
42=16 ≡ 2 (mod 7)
43=64 ≡ 1 (mod 7)
Ord7(4)=3 because 43 is congruent to 1 modulo 7.
Example 2: Define multiplicative order of 2 mod 7
21=2 ≡ 2 (mod 7)
22=4 ≡ 4 (mod 7)
23=8 ≡ 1 (mod 7)
Ord7(2)=3 because 23 is congruent to 1 modulo 7.

Primitive Root :
If the Group G=<Zn*,x> has any primitive root, the number of primitive roots is
ϕ(ϕ (n))
Example: Find the Number of primitive roots of 25
ϕ (25)=20
Find the primitive root of 761
ϕ (ϕ (761))= ϕ (760)
= ϕ (23x5x19) = ϕ (23)x ϕ (5)x ϕ (19)
=(23 - 22)x 4x18=4x4x18
=288

CHINESE REMAINDER THEOREM

The Chinese remainder theorem (CRT) is used to solve a set of congruent equations with one variable but
different moduli, which are relatively prime, as shown below:

Solution To Chinese Remainder Theorem

1. Find M = m × m × … × m . This is the common modulus.
1 2 k
2. Find M = M/m , M = M/m , …, M = M/m .
1 1 2 2 k k
3. Find the multiplicative inverse of M , M , …, M using the
1 2 k
corresponding moduli (m1, m2, …, mk). Call the inverses
M1−1, M2−1, …, Mk −1.
4.
The solution to the simultaneous equations is
Example:
Find the solution to the simultaneous equations:

Solution:
We follow the four steps.
1. M = 3 × 5 × 7 = 105
2. M1 = 105 / 3 = 35, M2 = 105 / 5 = 21, M3 = 105 / 7 = 15
3. The inverses are M −1 −1 −1
1 = 2, M 2 = 1, M 3= 1
4. x = (2 × 35 × 2 + 3 × 21 × 1 + 2 × 15 × 1) mod 105 = 23 mod 105
Example 2:
Find an integer that has a remainder of 3 when divided by 7 and 13, but is divisible by 12.
Solution
This is a CRT problem. We can form three equations and solve them to find the value of x.

If we follow the four steps, we find x = 276. We can check that

276 = 3 mod 7, 276 = 3 mod 13 and 276 is divisible by 12 (the quotient is 23 and the remainder is zero).

Example 3
Assume we need to calculate z = x + y where x = 123 and y = 334, but our system accepts only numbers less
than 100.

Adding each congruence in x with the corresponding congruence in y gives

Now three equations can be solved using the Chinese remainder theorem to find z. One of the acceptable
answers is z = 457.

QUADRATIC CONGRUENCE
Quadratic Congruence is a congruence of the equation of the form a2x2 + a1x + a0 ≡ 0 (mod n).
We limit our discussion to quadratic equations in which
a2 = 1 and a1 = 0, that is equation of the form.
x2 ≡ a (mod n)
There are two ways:
1. Quadratic Congruence Modulo a Prime
2. Quadratic Congruence Modulo a Composite
Quadratic Congruence Modulo a Prime
In this, we consider the modulus is a prime number. That is the form. x2 ≡ a (mod p)
Where p is a prime and ‘a’ is an integer.
Example 1: Solve the x2 ≡ 3 (mod 11)
Solution: 3 congruent to modulo 11 are 3,14,25 (25 is 5x5 or (-5)x(-5))
The given equation has two solutions:
x2 ≡ 25 (mod 11)
x ≡ 5 (mod 11) and x ≡ -5 (mod 11),
But -5 ≡ 6 (mod 11)
So, the solutions are 5 and 6
Check the result: substitute x=5
52 ≡ 25 =3 (mod 11)
substitute x=6
62 ≡ 36 =3 (mod 11)
Example 2: Solve the y2 ≡ 10 (mod 13)
Solution: The number 10 congruent to 13 are 10,23,36 (36 is 6x6 or (-6)x(-6))
The given equation has two solutions:
x ≡ 6 (mod 13) and x ≡ -6 (mod 13),
But -6 ≡ 7 (mod 13)
So, the solutions are 6 and 7
Check the result: substitute x=6
62 ≡ 36 ≡ 10 (mod 13)
substitute x=7
7 ≡ 49 ≡ 10 (mod 13)
Quadratic Congruence Modulo a Composite
Quadratic Congruence Modulo a Composite can be solved by set of Quadratic Congruence Modulo a Prime.
Decomposition of congruence modulo a composite:

Example: Assume that x2 ≡ 36 (mod 77).

We know that 77 = 7 × 11. We can write

The answers are x ≡ +1 (mod 7), x ≡ − 1 (mod 7),

x ≡ + 5 (mod 11), and x ≡ − 5 (mod 11). Now we can make four sets of equations out of these:
The answers are x = ± 6 and ± 27.

ASYMMETRIC KEY /PUBLIC KEY

CRYPTOGRAPHY
Asymmetric key cryptosystems / public-key cryptosystems use a pair of
keys: public key (encryption key) and private key (decryption key).
Public Key Cryptography ?
 Public key cryptography also called as asymmetric cryptography.
 It was invented by whitfield Diffie and Martin Hellman in 1976.
Sometimes this cryptography also called as Diffie-Helman Encryption.
 Public key algorithms are based on mathematical problems which admit
no efficient solution that are inherent in certain integer factorization,
discrete logarithm and Elliptic curve relations.
Public key Cryptosystem Principles:
 The concept of public key cryptography is invented for two most difficult
problems of Symmetric key encryption.
 The Key Exchange Problem
 The Trust Problem
The Key Exchange Problem: The key exchange problem arises from the fact that
communicating parties must somehow share a secret key before any secure
communication can be initiated, and both parties must then ensure that the key
remains secret. Of course, direct key exchange is not always feasible due to risk,
inconvenience, and cost factors.

The Trust Problem: Ensuring the integrity of received data and verifying the identity of the source of
that data can be very important. Means in the symmetric key cryptography system, receiver doesn‟t know
whether the message is coming for particular sender.
 This public key cryptosystem uses two keys as pair for encryption of
plain text and Decryption of cipher text.
 These two keys are names as “Public key” and “Private key”. The private
key is kept secret where as public key is distributed widely.
 A message or text data which is encrypted with the public key can be
decrypted only with the corresponding private-key
This two key system very useful in the areas of confidentiality (secure) and
authentication

A public-key encryption scheme has six

ingredients
1 Plaintext This is the readable message or data that is fed into the algorithm as input.

2 Encryption The encryption algorithm performs various transformations on the plaintext.

algorithm
3 Public key This is a pair of keys that have been selected so that if one is used for
 4 Private key encryption, the other is used for decryption. The exact transformations
performed by the
algorithm depend on the public or private key that is provided as input
This is the scrambled message produced as output. It depends on the
5 Ciphertext plaintext and the key. For a given message, two different keys will produce
two different
ciphertexts.
6 Decryption This algorithm accepts the ciphertext and the matching key and produces the
algorithm original plaintext.

Public key cryptography for providing confidentiality(secrecy)

The essential steps are the following.

1. Each user generates a pair of keys to be used for the encryption and decryption
of messages.
2. Each user places one of the two keys in a public register or other accessible
file. This is the public key. The companion key is kept private. As the above
Figure suggests, each user maintains a collection of public keys obtained
from others.
3. If Bob wishes to send a confidential message to Alice, Bob encrypts the message
using Alice‟s
public key.
4. When Alice receives the message, she decrypts it using her private key. No
other recipient can
decrypt the message because only Alice knows Alice‟s private key.
 There is some source A that produces a message in plaintext X = [X1, X2, . . . ,XM].
The M elements of X are letters in some finite alphabet. The message is intended for destination B. B
generates a related pair of keys: a public key, PUb, and a private key, PRb.
PRb is known only to B, whereas PUb is publicly available and therefore accessible by A.
With the message X and the encryption key PUb as input, A forms the ciphertext Y = [Y1, Y2, . . . , YN]:

The intended receiver, in possession of the matching private key, is able

to invert the transformation:
Public key cryptography for proving Authentication:
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

The above diagrams show the use of public-key encryption to provide authentication:

 In this case, A prepares a message to B and encrypts it using A‟s private key
before transmitting it. B can decrypt the message using A‟s public key. Because the
message was encrypted using A‟s private key, only A could have prepared the
message. Therefore, the entire encrypted message serves as a digital signature.

 It is impossible to alter the message without access to A‟s private key, so the
message is authenticated both in terms of source and in terms of data
integrity.

Public key cryptography for both authentication and confidentiality (Secrecy)

It is, however, possible to provide both the authentication function and confidentiality by a double use of

Prepared by Assoc.Professor, CSED,KHIT, Guntur 88

Ch Samsonu,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

the public-key scheme (above figure):

In this case, we begin as before by encrypting a message, using the sender‟s private key. This provides
the digital signature. Next, we encrypt again, using the receiver‟s public key. The final ciphertext can be
decrypted only by the intended receiver, who alone has the matching private key. Thus, confidentiality is
provided.

Applications for Public-Key Cryptosystems

Public-key systems are characterized by the use of a cryptographic algorithm with two keys, one held
private and one available publicly. Depending on the application, the sender uses either the sender‟s
private key or the receiver‟s public key, or both, to perform some type of cryptographic function. the use
of public-key cryptosystems into three categories
• Encryption /decryption: The sender encrypts a message with the recipient‟s public key.
• Digital signature: The sender “signs” a message with its private key. Signing is
achieved by a cryptographic algorithm applied to the message or to a small block
of data that is a function of the message.
• Key exchange: Two sides cooperate to exchange a session key. Several different
approaches are possible, involving the private key(s) of one or both parties.

Applications for Public-Key Cryptosystems

Algorithm Encryption/Decryption Digital Signature Key Exchange
RSA Yes Yes Yes
Elliptic Curve Yes Yes Yes
Diffie-Hellman No No Yes
DSS No Yes No

Public-Key Cryptanalysis
As with symmetric encryption, a public-key encryption scheme is vulnerable to a brute-force attack. The
countermeasure is the same: Use large keys. However, there is a tradeoff to be considered. Public- key
systems depend on the use of some sort of invertible mathematical function. The complexity of
calculating these functions may not scale linearly with the number of bits in the key but grow more
rapidly than that. Thus, the key size must be large enough to make brute-force attack impractical but
small enough for practical encryption and decryption. In practice, the key sizes that have been proposed
do make brute-force attack impractical but result in encryption/decryption speeds that are too slow for
general-purpose use. Instead, as was mentioned earlier, public-key encryption is currently confined to key
management and signature applications.

RSA Algorithm
 It is the most common public key algorithm.
 This RSA name is get from its inventors first letter (Rivest (R), Shamir (S) and
Adleman (A)) in the year 1977.
 The RSA scheme is a block cipher in which the plaintext & ciphertext are
integers between 0 and n-1 for some n.
 A typical size for n is 1024 bits or 309 decimal digits. That is, n is less than 21024

Description of the Algorithm:

 RSA algorithm uses an expression with exponentials.
 In RSA plaintext is encrypted in blocks, with each block having a binary value
less than some number

Prepared by Ch Samsonu, 89
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

n. that is, the block size must be less than or equal to log2(n)
 RSA uses two exponents e and d where e public and d private.
 Encryption and decryption are of following form, for some
PlainText M and CipherText block C

M=Cd mod = (Me mod n) d mod n =(Me)d mod n= Med mod n

Both sender and receiver must know the value of n.

The sender knows the value of e & only the receiver knows the value of d thus this is a public key
encryption algorithm with a
Public key PU={e, n}
Private key PR={d, n}
Steps of RSA algorithm:
Step 1Select 2 prime numbers p & q
Step 2Calculate n=pq
Step 3Calculate Ø(n)=(p-1)(q-1)
Step 4 Select or find integer e (public key) which is relatively prime to Ø(n).
ie., e with gcd (Ø(n), e)=1 where 1<e< Ø(n).
Step 5 Calculate “d” (private key) by using following condition.
d< Ø(n).
Step 6 Perform encryption by using
Step 7 performDecryption by using
Example:
1. Select two prime numbers, p = 17 and q = 11.
2. Calculate n = pq = 17 × 11 = 187.
3. Calculate Ø(n) = (p - 1)(q - 1) = 16 × 10 = 160.
4. Select e such that e is relatively prime to Ø(n) = 160 and less than Ø (n); we choose
e = 7.
5. Determine d such that de ≡1 (mod 160) and d < 160.The correct value is d = 23,
because 23 * 7
= 161
= (1 × 160) + 1;
d can be calculated using the extended Euclid‟s algorithm
6. The resulting keys are public key PU = {7, 187} and private key PR = {23, 187}.
The example shows the use of these keys for a plaintext input of M= 88. For encryption,
we need to calculate C = 887 mod 187. Exploiting the properties of modular arithmetic, we can do this as
follows.

Prepared by Ch Samsonu, 90
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

The Security of RSA

Four possible approaches to attacking the RSA algorithm are
• Brute force: This involves trying all possible private keys.
• Mathematical attacks: There are several approaches, all equivalent in effort to
factoring the product of two primes.
• Timing attacks: These depend on the running time of the decryption algorithm.
• Chosen ciphertext attacks: This type of attack exploits properties of the RSA algorithm.
Trapdoor one-way function
 A trapdoor function is a function that is easy to perform one way, but has a secret that is required to
perform the inverse calculation efficiently.
 That is, if f is a trapdoor function, then y=f(x) is easy to compute, but x=f−1(y) is hard to compute
without some special knowledge k. Given k, then it is easy to computey=f−1(x,k).
 The analogy to a "trapdoor" is something like this: It's easy to fall through a trapdoor, but it's very
hard to climb back out and get to where you started unless you have a ladder.
 An example of such trapdoor one-way functions may be finding the prime factors of large numbers.
Nowadays, this task is practically infeasible.
 On the other hand, knowing one of the factors, it is easy to compute the other ones.
For example: RSA is a one-way trapdoor function
Diffie-Hellman Key Exchange
 Diffie-Hellman key exchange is the first published public key algorithm
 This Diffie-Hellman key exchange protocol is also known as exponential key
agreement. And it is based on mathematical principles.
 The purpose of the algorithm is to enable two users to exchange a key
securely that can then be used for subsequent encryption of messages.
 This algorithm itself is limited to exchange of the keys.
 This algorithm depends for its effectiveness on the difficulty of computing discrete
logarithms.
 The discrete logarithms are defined in this algorithm in the way of define a
primitive root of a prime number.
 Primitive root: we define a primitive root of a prime number P as one whose
power generate all the integers from 1 to P-1 that is if ‘a’ is a primitive root of
the prime number P, then the numbers are distinct and consist of the integers
form 1 through P-1 in some permutation.
Prepared by Ch Samsonu, 91
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

For any integer b and a, here a is a primitive root of prime number P, then
b≡ aimod P 0 ≤ i ≤ (P-1)
The exponent i  is refer as discrete logarithm or index of b for the base a, mod P.
The value denoted as ind a,p(b)
Algorithm for Diffie-Hellman Key Exchange:
Step 1 Select global public numbers q, α
q Prime number
α primitive root of q and α< q.
Step 2  if A & B users wish to exchange a key
a) User A select a random integer XA<q and computes
b) User B independently select a random integer XB <q and computes
c)
Each side keeps the X value private and Makes the Y value available
publicly to the outer side.
Step 3 User A Computes the key as
User B Computes the key as
Step 4 two calculation produce identical results
The result is that the two sides have exchanged a secret key.

Example:

MAN-in the Middle Attack (MITM)

Definition: A man in the middle attack is a form of eavesdropping where communication between two
users is monitored and modified by an unauthorized party.
Generally the attacker actively eavesdrops by intercepting (stoping) a public key message exchange.

Prepared by Ch Samsonu, 92
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

The Diffie- Hellman key exchange is insecure against a “Man in the middle attack”.
Suppose user A & B wish to exchange keys, and D is the adversary (opponent). The attack proceeds as
follows.
1. D prepares for the attack by generating two random private keys XD1 &
XD2 and then computing the corresponding public keys YD1 and YD2.
2. A transmits YA to B
3. D intercepts YA and transmits YD1 to B. and D also calculates
4. B receives YD1 & calculate
5. B transmits YB to A
6. Dintercepts YB and transmits YD2 to „A‟ and „D‟ calculate K1
7. A receives YD2 and calculates
At this point, Bob and Alice think that they share a secret key, but instead Bob and Darth share secret
key K1 and Alice and Darth share secret key K2. All future communication between Bob and Alice is
compromised in the following way.

The key exchange protocol is vulnerable to such an attack because it does not
authenticate the participants. This vulnerability can be overcome with the use
of digital signatures and public-key certificates.
Elliptic Curve Cryptography
 Elliptical curve cryptography (ECC) is a public key encryption technique based on
elliptic curve theory that can be used to create faster, smaller, and more efficient
cryptographic keys. ECC generates keys through the properties of the elliptic
curve equation instead of the traditional method of generation as the product of
very large prime numbers
 An elliptic curve is defined by an equation in two variables with coefficients.
For cryptography, the variables and coefficients are restricted to elements in a
finite field, which results in the definition of a finite abelian group.

Elliptic Curves over Real Numbers

Prepared by Ch Samsonu, 93
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

ECC-Key Exchange:
Take two Global public Elements
Eq(a,b) : Elliptic curve with parameters a,b, & q
G : Point on elliptic curve whose order is large value n
Alice Key Generation:
Select private key nA : nA < n
Calculate public key PA: PA = nAxG
Bob Key Generation:
Select private key nB : nB < n
Calculate public key PB: PB = nBxG
Secrete Key calculation by Alice
K=nAxPB
Secrete Key calculation by Bob
K=nBxPA
ECC- Encryption
 Let the message be M
 First encode the message M into a point on the elliptic curve
 Let this point be Pm
 Now this point is encrypted
 For encryption choose a random positive integer k
 Then Cm={ kG,Pm+kPB } where G is the base point
ECC-Decryption
 Multiply first point in the pair with receivers secrete key
i.e, kG x nB
 Then subtract it from second point in the pair
i.e, Pm + kPB- (kGx nB)

Prepared by Ch Samsonu, 94
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

ELGAMAL CRYPTOGRAPHIC SYSTEM

 In 1984, T. Elgamal announced a public-key scheme based
on discrete logarithms, closely related to the Diffie-Hellman
technique.
 EIGamal Algorithms are used for both digital signatures as well as
encryption.

EIGamal Algorithm:-

Thus, functions as a one-time key, used to encrypt and decrypt

the message. For example, let us start with the prime field
GF(19); that is, q = 19. It has primitive roots {2, 3, 10, 13, 14, 15
}. We choose α = 10.
Alice generates a key pair as follows:

Prepared by Ch Samsonu, 95
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

RABIN CRYPTOSYSTEM
Rabin Cryptosystem is an public-key cryptosystem invented by Michael Rabin, is a variation of the RSA.
RSA is based on the exponentiation congruence; Robin is based on quadratic congruence.
The public key in the Rabin is n, private key is the tuple(p,q). Everyone can encrypt a message using n, only
Bob can decrypt the message using p and q.
Decryption of the message is infeasible It uses asymmetric key encryption for communicating between two
parties and encrypting the message.
The security of Rabin cryptosystem is related to the difficulty of factorization. It has the advantage over the
others that the problem on which it banks has proved to be hard as integer factorization.
It has the disadvantage also, that each output of the Rabin function can be generated by any of four possible
inputs. if each output is a cipher text, extra complexity is required on decryption to identify which of the
four possible inputs was the true plaintext.

Steps in Rabin cryptosystem

Key generation
1. Generate two very large prime numbers, p and q, which satisfies the condition
p ≠ q → p ≡ q ≡ 3 (mod 4)
For example:
p=139 and q=191
2. n = p.q
3. Public_key=n
4. Private_key=(p,q)
5. Return public_key, Private_keys
Encryption
1. Get the public key n.
2. Convert the message to ASCII value. Then convert it to binary and extend the binary value with
itself, and change the binary value back to decimal M.
3. Encrypt with the formula: C
= M2 mod n
4. Send C to recipient.

Prepared by Ch Samsonu, 96
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Decryption
1. Accept C from sender.
2. Compute:
a1 = C(p+1)/4 mod p
a2= - C(p+1)/4 mod p
b1= C(q+1)/4 mod q
b2= - C(q+1)/4 mod q
3. Calculate four Plain text by using Chinese Remainder Algorithm:
M1=Chainese_Remainder(a1,b1,p,q)
M2=Chainese_Remainder(a1,b2,p,q)
M3=Chainese_Remainder(a2,b1,p,q)
M4=Chainese_Remainder(a2,b2,p,q)
4. Choose one of the above (M1,M2,M3 and M4) is the appropriate plaintext.

The Rabin cryptosystem is not deterministic: Decryption creates four equally probable plain texts

Example:
1. Bob selects p=23 and q=7, note both are congruent to 3 mod
4 2.Bob calculates n=pxq=161
3. Bob announces n publickly; he keeps p and q private
4. Allice want to send plain text P=24. Note that 161and 24 are relatively prime; 24 is in Z161*
She calculates C=242 mod 161 =93 mod 161, and sends the ciphertext 93 to Bob
5. Bob receives 93 and calculates four values:
a. a1=+(93(23+1)/4 mod 23=1 mod 23
b. a2=-(93(23+1)/4 mod 23=22 mod 23
c. b1=+(93(7+1)/4 mod 7=4 mod 7
d. b2=-(93(7+1)/4 mod 7=3 mod 7
6. Bob takes four possible answers, (a1,b1), (a1,b2), (a2,b1),(a2,b2) and uses Chinese Remainder Theorem to
find 4 possible plain texts: 116,24,137 and 45.

Case 1:
By using (a1=1,b1=4) combinations with modulo (p=23,q=7), Let X is plain text:
X = 1 mod 23

Prepared by Ch Samsonu, 97
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

X= 4 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23
-1
M1 =7-1 mod 23 = 723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM -1+a
1 2xM2xM -1) mod M
=( 1 x 7 x 10 + 4 x 23 x 4) mod 161 = 438 mod 161=116

Case 2:
By using (a1=1,b2=3) combinations with modulo (p=23,q=7), Let X is plain text:
X = 1 mod 23
X= 3 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23
-1
M1 =7-1 mod 23 = 723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM -1+a
1 2xM2xM -1) mod M
=( 1 x 7 x 10 + 3 x 23 x 4) mod 161 = 346 mod 161=24
Case 3:
By using (a2=22,b1=4) combinations with modulo (p=23,q=7), Let X is plain text:
X = 22 mod 23
X= 4 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23
-1
M1 =7-1 mod 23 = 723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM -1+a
1 2xM2xM -1) mod M
=( 22 x 7 x 10 + 4 x 23 x 4) mod 161 = (1540+368) mod 161=137

Case 4:
By using (a2=22,b2=3) combinations with modulo (p=23,q=7), Let X is plain text:
X = 22 mod 23
X= 4 mod 7
By using Chinese Remainder Theorem:
M=23x7=161, M1=M/23=161/23=7, M2=M/7=161/7=23
-1
M1 =7-1 mod 23 = 723-2 mod 23 = 721 mod 23=10
M2-1=23-1 mod 7 = 237-2 mod 7 = 235 mod 7=4
X= (a1 x M1xM -1+a
1 2xM2xM -1) mod M
=( 22 x 7 x 10 + 3 x 23 x 4) mod 161 = (1540+276) mod 161=45
So, Finally from four cases: we got four plain text messages
Case 1: 116
Case 2: 24
Case 3: 137
Case 4: 45.
Only second answer(24) is Alice plain text, Bob needs to make a decision based on the situation

Secure of the Rabin System:

The Rabin System is secure as long as p and q are large numbers

Prepared by Ch Samsonu, 98
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

UNIT-IV
Data Integrity, Digital Signature Schemes & Key Management

Message Integrity and Message Authentication, Cryptographic Hash Functions, Digital

Signature, Key Management.

Message Integrity and Message Authentication

1. Message Integrity:
The cryptography systems that we have studied so far provide secrecy, or confidentiality, but not
integrity.
However, there are occasions where we may not even need secrecy but instead must have
integrity(Data will not changed).

Document and Fingerprint:

One way to preserve the integrity of a document is through the use of a fingerprint.
If Alice needs to be sure that the contents of her document will not be changed, she can put her
fingerprint at the bottom of the document.

Message and Message Digest:

The electronic equivalent of the document and fingerprint pair is the message and digests pair.
To preserve the integrity of a message, the message is passed through an algorithm called a
cryptographic hash function.

Difference:
The two pairs (document / fingerprint) and (message / message digest) are similar, with some
differences.
The document and fingerprint are physically linked together. The messa ge and message digest
can be unlinked separately, and, most importantly, the message digest needs to be

Prepared by Ch Samsonu, 99
Assoc.Professor,
Cryptography and Network Security B.Tech(CSE) IV Year I Sem

safe from change.

Note: The message digests needs to be safe from change.

Checking Integrity:

Cryptographic Hash Function Criteria:

A cryptographic hash function must satisfy three criteria
1. Pre-image Resistance
2. Second Pre-image Resistance
3. Collision Resistance.
Preimage Resistance: The hash function must be a one-way function: For any given code h, it is
computationally infeasible to find h-1.

Second Preimage Resistance: In this criterion, an adversary is provided with the value of

Prepared by Ch Samsonu, 100

Assoc.Professor,
Cryptography and Network Security B.Tech(CSE) IV Year I Sem

x and is asked to compute the value of x1 ≠ x, such that h(x) = h(x1).

If it difficult for the attacker to perform this computation we claim that the hash
function is second pre-image resistant.

Collision Resistance: Collision of a hash function is the event when two values x and
x1, such that x1 ≠ x hash to the same value, i.e., h(x) = h(x1).

Prepared by Ch Samsonu, 101

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Random Oracle Model:

2. Message Authentication:
 A message digest guarantees the integrity of a message. It
guarantees that the message has not been changed.
 A message digest does not authenticate the sender of the message.
 When Alice sends a message to Bob, Bob needs to know if the
message is coming from Alice.
 To provide message authentication, Alice needs to provide proof that
it is Alice sending the message and not a fraud.
 The digest created by a cryptographic hash function is normally
called a Modification Detection Code (MDC). This code can detect
any modifications in the message.
 What we need for message authentication is a Message Authentication Code
(MAC).

Modification Detection Code (MDC):

 A modification detection code (MDC) is a message digest that can
prove the integrity of the message: that message has not been
changed.
 If Alice needs to send a message to Bob and be sure that the
message will not change during transmission,
 Alice can create a message digest, MDC, and send both the message
and the MDC to Bob. Bob can create a new MDC from the message and
compare the received MDC and thenew MDC. If they are the same, the
message has not been changed.

Prepared by Ch Samsonu, 102

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Message Authentication Code (MAC):

 To ensure the integrity of a message and the data origin
authentication – we need to change a modification detection code
(MDC) to a Message Authentication Code (MAC).
 The difference between MDC and MAC is that the second
include a secrete key between Alice and Bob.

MAC Security
How can Eve forge a message without having the key?
1. If size of the key allows exhaustive search, Eve may try all
possible keys to digest the message.
2. Use preimageattack.
3. Given some pairs of messages and their MACs,
Eve can manipulate them to come up with a new message
and its digest
Note: The security of a MAC depends on the security of the underlying hash algorithm.

Nested MAC:
 To improve MAC security, nested MACs were designed in which hashing is
performed twice.
 In 1st step, the key is concatenated with the message and is
hashed to create an intermediate digest.
 In 2nd step, the key is concatenated with the intermediate digest to create the
final digest.
Prepared by Ch Samsonu, 103
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

HMAC (Hashed MAC):

 HMAC algorithm stands for Hashed or Hash based Message Authentication Code
 it uses the Hashing concept twice, so great resistant to attacker
 HMAC consists of twin benefits of Hashing and MAC
 The working of HMAC starts with taking a message M containing blocks of
length b bits.

 An input signature is padded to the left of the message and the whole
is given as input to a hash function which gives us a intermediate
HMAC.

 Intermediate HMAC again is appended to an output signature and the whole

is applied a hash function again, the result is our final HMAC of n bits

Prepared by Ch Samsonu, 104

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

CMAC (Cipher based MAC)

• This is similar to CBC(Cipher Block Chaining),

• It takes N blocks of message but creates one block of MAC
• The message is divided into N blocks of m-bit size. If last block is
not m-bit size,then
padded with start 1 then 0000…, like 100000…
• The block is encrypted with key K then its output is XOR with the
next block for 2 nd
encryption, so on.
• The last block is encrypted with some addtional k value for more scurity.

Cryptographic Hash Functions

A cryptographic hash function takes a message of arbitrary
length and creates a message digest of fixed length, also called hash.

A cryptographic hash function H accepts a variable-length block of data M as input and

produces a fixed-size hash value.

There are two most promising cryptographic hash algorithms –

 SHA-512

Prepared by Ch Samsonu, 105

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

 Whirlpool

Iterated Hash Function

All cryptographic functions need to create a fixed size digest out of a variable-size
message. Actually, the hash function is fixed size input function, but performs number of
times.
This fixed-size hash function is referred to as a compression function, it compresses m-bit
string input to n bit string.

Merkle-Damgard Scheme

 This is an iterated hash function that is collision resistant

 This is the basis for many cryptographic hash functions today.

Prepared by Ch Samsonu, 106

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

 Message is divided into t-blocks of n-bit size. If necessary some bits are padded
 The blocks are M1,M2,…Mt and the digest created at each compression
function are H1,H2,…Ht
 Before starting the iteration, the digest H0 is set to fixed Value called
IV(initial value or initial vector)
The compression function operates on Hi-1 and Mi to create a new Hi. Hi=f(Hi-1,Mi) where f is
a compression function

Hash Functions Invention

 Several Hash functions were designed by Ron Rivest.
 These are MD(Message Digest), MD2, MD4, and MD5
 MD5 takes blocks of size 512-bits and creates 128-bit digest.
 The 128-bit size digest is too small to resist collision attack.

Secure Hash Algorithm(SHA)

 SHA originally designed by NIST & NSA in 1993

 SHA was revised in 1995 as SHA-1
 adds 3 additional versions of SHA
 SHA-256, SHA-384, SHA-512structure & detail is similar to SHA-1

SHA – 512
 SHA-512 is family of Secure Hash Algorithm
 SHA-512 creates a 512 bit message digest .
 The original message divided into multiple blocks of size 1024bits.
 The Processing of each block involves 80 rounds
 Each block of size(1024bits) can be assumed as 16 words of size 64bits
 The maximum size of message is less than 2128. This means that if the
length of a message equal to or greater than 2128, it will not be
processed by SHA-512

Prepared by Ch Samsonu, 107

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

 SHA-512 based on Merkle-Damgard scheme.

The Following Figure shows internal logic of the SHA-512

STEPS:

1. Append padding bits:

The message is padded with 1000000…. To make the message multiples of 1024.

Prepared by Ch Samsonu, 108

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

2. Append length of the message:

A block of 128 bits is appended to the message. Contains the length of the original message.
Before addition of the length of message , we need to pad as specified in the first step.
The size of padding bits is calculated
as: (|M|+|P|+128)=0 mod 1024
|P|=-|M|-128 mod 1024
Example: What is the number of padding bits if the length of the original message is 2590
Solution: |P|=-2590-128 mod 1024
=-2718 mod 1024 = -670 mod 1024
=(1024-670) mod 1024 = 354
The padding consists of one 1 followed by 353 0’s
Length Field and Padding:
Before the message digest can be created, SHA-512 requires the addition of a 128-bit length field (0-(2128-
1)to the message that defines the length of the message in bits.

Compression Function
The heart of the algorithm is a module that consists of 80 rounds; this module is labeled as F in Block
Diagram.
Each round t takes as input the 512-bit buffer value, abcdefgh, and updates the contents of the buffer.
Each round t makes use of a 64-bit value Wt, derived from the current 1024-bit block being
processed (Mi).
Each round t also makes use of an additive constant Kt (64-bit)
The output of the 80th round is added to the input to the first round (Hi-1) to produce Hi.

Prepared by Ch Samsonu, 109

Assoc.Professor,
Cryptography and Network Security B.Tech(CSE) IV Year I Sem

80-Word Input Sequence

Prepared by Ch Samsonu, 110

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Constants

…..

Initialize hash buffer

Prepared by Ch Samsonu, 111

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

DIGITAL SIGNATURE
 A digital signature is a technique used to validate the authenticity and
integrity of a message.
 In the physical world, A person signs a document to show that it
originated from him or was approved by him. The signature is proof to
recipient that the document comes from the correct entity.
 Similarly, a digital signature is a technique that binds a
person/entity to the digital data. This binding can be
independently verified by receiver as well as any third party.
 Digital signature is a cryptographic value that is calculated from the
data and a secret key known only by the signer.

COMPARISON of conventional signature & DIGITAL SIGNATURE

Inclusion
A conventional signature is included in the document; it is part of the document.
But when we sign a document digitally, we send the signature as a separate document.

Verification Method
For a conventional signature, when the recipient receives a document, he compares the signature on the
document with the signature on file.
For a digital signature, the recipient receives the message and the signature. The recipient needs to apply a
verification technique to the combination of the message and the signature to verify the authenticity.

Relationship
For a conventional signature, there is normally a one-to-many relationship between a signature and
documents. For a digital signature, there is a one-to-one relationship between a signature and a
message.

Duplicity
In conventional signature, a copy of the signed document can be distinguished from the original one on
Prepared by Ch Samsonu, 112
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

file. In digital signature, there is no such distinction unless there is a factor of time on the document.

PROCESS OF DIGITAL SIGNATURE

Figure shows the digital signature process. The sender uses a signing algorithm to sign the message. The
message and the signature are sent to the receiver. The receiver receives the message and the signature and
applies the verifying algorithm to the combination. If the result is true, the message is accepted; otherwise,
it is rejected.

SIGNING THE DIGEST

The drawback of Asymmetric key cryptosystems that is “inefficient for long messages” .t In a digital
signature system can be overcome by “signing the digest of the message”.

SERVICES

The services in cryptography are:

Message confidentiality, authentication, Integrity and Non-repudiation.

Prepared by Ch Samsonu, 113

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

• A digital signature system can provide Message authentication,

Integrity and Non- repudiation, but still need encryption/decryption for
message confidentiality.

Message Authentication
• A secure digital signature scheme, like a secure conventional
signature can provide message authentication
• Example, Bob can verify that the message is sent by Alice because Alice’s public key is used
in verification.
Message Integrity
The integrity of the message is preserved even if we sign the whole message because we cannot get the
same signature if the message is changed.

Nonrepudiation
Nonrepudiation can be provided using a trusted party.

Confidentiality

A digital signature does not provide privacy.

If there is a need for privacy, another layer of encryption/decryption must be applied.

Prepared by Ch Samsonu, 114

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Figure Adding confidentiality to a digital signature scheme

ATTACKS ON DIGITAL SIGNATURE

Attack Types
1. Key-Only Attack
In key-only attack, the public key of A is available to every one and C makes use of this fact and try to
recreate the signature of A and digitally sign the documents that A does not intend to do.
2. Known-Message Attack
In the known message attack, C has few previous messages and signatures of A. Now C tries to forge
the signature of A on to the documents that A does not intend to sign by using the brute force method
by analyzing the previous data to recreate the signature of A
3. Chosen-Message Attack
In this method C has the knowledge about A’s public key and obtains A’s signature on the messages and
replaces the original message with the message C wants A to sign with having A’s signature on them
unchanged.

Forgery Types

1. Existential Forgery
Adversary can create a pair (message, signature), such that the signature of the message is valid.
Adversary has no control on the messages whose signature is forged
2. Selective Forgery
Adversary is able to create valid signatures on a
message chosen by someone else, with a significant
probability.

Prepared by Ch Samsonu, 115

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Adversary controls the messages whose signature is forged

DIGITAL SIGNATURE SCHEMES

Several digital signature schemes have evolved during the last few decades. Some of them have been
implemented.

1. RSA Digital Signature Scheme

2. ElGamal Digital Signature Scheme
3. Schnorr Digital Signature Scheme
4. Digital Signature Standard (DSS)
5. Elliptic Curve Digital Signature Scheme

RSA DIGITAL SIGNATURE SCHEMES

Figure : General idea behind the RSA digital signature scheme

The sender uses his own private key tosign the documemnet, the receivr uses the senders public key to
verify it

RSA DIGITAL SIGNATURE SCHEMES – Key Generation

Key generation in the RSA digital signature scheme is exactly the same as key generation in the RSA.
1. Sender chooses two prime numbers p and q
2. Calculate n=pxq
3. Calculate f(n) = (p-1) x (q-1)
4. Chooses the public exponent e and calculates d (private exponent) such that e
x d = 1 mod f(n)
In the RSA digital signature scheme, d is private; e and n are public. RSA

DIGITAL SIGNATURE SCHEMES – Signing and verifying

Prepared by Ch Samsonu, 116

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Signing: Alice create a signature out of the message using her private exponent,
S=Md mod n and sends the signature to Bob
Verifying: Bob receives M and S. Bob applies A lice public exponent to the signature to create a copy of
the message M1 = Se mod n. Bob compares M and M1 . If both are congruent, accepts the message.
M1 M (mod n)  Se  M (mod n)  Mdxe M (mod n)

RSA DIGITAL SIGNATURE SCHEMES – EXAMPLE

As a trivial example, suppose that Alice chooses p = 823 and q = 953, and calculates n = 784319. The
value of f(n) is 782544. Now she chooses e = 313 and calculates d = 160009. At this point key
generation is complete. Now imagine that Alice wants to send a message with the value of M = 19070 to
Bob. She uses her private exponent, 160009, to sign the message:

Alice sends the message and the signature to Bob. Bob receives the message and the signature. He
calculates

Bob accepts the message because he has verified Alice’s signature

ElGamal Digital Signatures

• signature variant of ElGamal, related to D-H

– so uses exponentiation in a finite Galois field
– security based difficulty of computing discrete logarithms, as in D-H
• use private key for encryption (signing)

Prepared by Ch Samsonu, 117

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

• uses public key for decryption (verification)

• each user (eg. A) generates their key

 Alice signs a message M to Bob by computing

 the hash m = H(M), 0 <= m <= (q-1)
 chose random integer K with 1 <= K <= (q-1) and gcd(K,q-1)=1
 compute temporary key: S1 = ak mod q
 compute K-1 the inverse of K mod (q-1)
 compute the value: S2 = K-1(m-xAS1) mod (q-1)
 signature is:(S1,S2)
 any user B can verify the signature by computing

ElGamal Signature Example

 use field GF(19) q=19 and a=10
 Alice computes her key:
 A chooses xA=16 & computes yA=1016 mod 19 = 4
 Alice signs message with hash m=14 as (3,4):
 choosing random K=5 which has gcd(18,5)=1
 computing S1 = 105 mod 19 = 3
 finding K-1 mod (q-1) = 5-1 mod 18 = 11
 computing S2 = 11(14-16.3) mod 18 = 4
 any user B can verify the signature by computing
 V1 = 1014 mod 19 = 16
 V2 = 43.34 = 5184 = 16 mod 19
since 16 = 16signature is valid

Schnorr Digital Signatures

 also uses exponentiation in a finite (Galois)
 security based on discrete logarithms, as in D-H
 minimizes message dependent computation
 multiplying a 2n-bit integer with an n-bit integer
 main work can be done in idle time
 have using a prime modulus p
 p–1 has a prime factor q of
appropriate size typically p 1024-bit and q
160-bit numbers

Schnorr Key Setup

 choose suitable primes p , q
 choose a such that aq = 1 mod p

Prepared by Ch Samsonu, 118

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

 (a,p,q) are global parameters for all

 each user (eg. A) generates a key
 chooses a secret key (number): 0 < sA < q
 compute their public key: vA = a-sA mod q

 user signs message by

 choosing random r with 0<r<q and computing x = ar mod p
 concatenate message with x and hash result to computing: e = H(M || x)
 computing: y = (r + se) mod q
 signature is pair (e, y)
 any other user can verify the signature as follows:
 computing: x' = ayve mod p
 verifying that: e = H(M || x’)
Digital Signature Standard (DSS)
 US Govt approved signature scheme
 designed by NIST & NSA in early 90's
 published as FIPS-186 in 1991
 revised in 1993, 1996 & then 2000
 uses the SHA hash algorithm
 DSS is the standard, DSA is the algorithm
 FIPS 186-2 (2000) includes alternative RSA & elliptic curve signature variants
 DSA is digital signature only unlike RSA is a public-key technique

Digital Signature Algorithm (DSA)

 creates a 320 bit signature
 with 512-1024 bit security
 smaller and faster than RSA
 a digital signature scheme only
 security depends on difficulty of computing discrete logarithms
 variant of ElGamal & Schnorr schemes
DSA Key Generation
 have shared global public key values (p,q,g):
 choose 160-bit prime number q
 choose a large prime p with 2L-1 < p < 2L
• where L= 512 to 1024 bits and is a multiple of 64
• such that q is a 160 bit prime divisor of (p-1)
 choose g = h(p-1)/q
• where 1<h<p-1 and h(p-1)/q mod p > 1
 users choose private & compute public key:
 choose random private key: x<q
 compute public key: y = gx mod p
DSA Signature Creation
 to sign a message M the sender:
 generates a random signature key k, k<q
 nb. k must be random, be destroyed after use, and never be reused
 then computes
signature pair: r = (gk
mod p)mod q
s = [k-1(H(M)+ xr)] mod q
 sends signature (r,s) with message M
 having received M & signature (r,s)
Prepared by Ch Samsonu, 119
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

 to verify a signature, recipient

DSS Overview

Prepared by Ch Samsonu, 120

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

KEY MANAGEMENT
SYMMETRIC-KEY DISTRIBUTION
• Symmetric-key cryptography is more efficient than
asymmetric-key cryptography for enciphering large
messages.
• Symmetric-key cryptography, however, needs a shared secret key between two
parties.
• Example: If Alice needs to exchange confidential messages with N people,
she need N different keys and if N people need to exchange with each
other, they need N(N-1) keys. If 1 million people need to communicate with
each other , they need more than trillions of keys.
• This proble normally referred as N2 problem, because the number
of required keys for N entitesis N2
• We also has a problem of the distribution of keys through the internet which is
unsecure.

Key-Distribution Center: KDC

A practical solution for the above problem is the use of a trusted thord party, referred as Key-Distribution
Center( KDC )

1. Alice sends a request to the KDC stating that she needs a session secrete key
between her and Bob
2. KDC inform Bob about Alice request
If Bob agrees, a session key is created between the two.

Prepared by Ch Samsonu, 121

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Flat Multiple KDCs

When the number of people using a KDC increases, the system becomes unmanageable.
To solve the problem, we use multiple KDCs. We devide the world into domains

Hierarchical Multiple KDCs

In this, KDCs are arranged in hierarchical model, the international KDC are at root, then national next and
local KDCs at lower level.

Session Keys
A KDC creates a secret key for each member. This secret key can be used only between the member and
the KDC, not between two members.
A session symmetric key between two parties is used only once.

Simple protocol Using a KDC

Figure shows first approach using KDC

Prepared by Ch Samsonu, 122

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

1. Alice sends request to KDC

2. KDC creates ticket to Bob which is encrypted using Bob’s key KB. The ticket
contains the session key (KAB).
3. Alice extracts the Bob’s ticket
4. Alice sends ticket to Bob. Bob opens the ticket and knows that Alice
want to send message to him by using KAB.
Drawback: Eve can use the replay attack at step 3.

Prepared by Ch Samsonu, 123

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Needham-Schroeder Protocol

1. Alice sends message to KDC that include her nonce, RA

2.
KDC sends encrypted ticket for Bob to Alice which contains session key
3.
Alice sends Bobs ticket to him
4. Bob sends his challenge (RB) to Alice which contains session key
5.
Alice responds to Bobs challenge

KERBEROS
Kerberos is an authentication protocol, and at the same time a KDC, that has become very popular.
Several systems, including Windows 2000, use Kerberos.
Originally designed at MIT, it has gone through several versions.

KERBEROS Servers

Three servers are involved in the Kerberos protocol.

Authentication Server (AS)
 The authentication server (AS) is the KDC in the Kerberos protocol.
 Each user registers with AS and is granted a user identity and a password.
 AS verifies the user, issues a session key to be used b/t Alice and TGS.
 and sends a ticket for TGS.

Prepared by Ch Samsonu, 124

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Ticket-Granting Server (TGS)

 The ticket-granting server (TGS) issues a ticket for the real server (Bob).
 Also provides the session key b/t Alice and Bob.
 Kerberos has a separated user verification from issuing of tickets.
 Alice can contact the TGS multiple times to obtained tickets for different
real servers.
Real Server
 The real server (Bob) provides services for the user (Alice).
 Kerberos is designed for client-server programs.
 Kerberos is not used for person – to – person authentication

Prepared by Ch Samsonu, 125

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

SYMMETRIC-KEY AGREEMENT
Alice and Bob can create a session key between themselves without using
a KDC. This method of session-key creation is referred to as the symmetric-
key agreement. Example: Diffie-Hellman Key Agreement

Diffie-Hellman Key Agreement

In this two parties are creating symmetric key without the need of a KDC.
Before establishing, the two parties need to choose two numbers p and g.
The p is a large number on the order of 300 digits.

Steps:
1. Alice chooses a large random integer number x and calculates R1=gx mod p
2. Bob chooses another large number y and calculates R2=gy mod p
3. Alice sends R1 to Bob and Bob sends R2 to Alice
4. Alice calculates key K=(R2)x mod p
5. Bob calculates key
K=(R1)y mod p Where K is the
symmetric key for the session
The symmetric key in the Diffie-Hellman method is K=gxy mod p

Diffie-Hellman Key Agreement- EXAMPLE

Let us give a trivial example to make the procedure clear. Our example uses small numbers, but note that
in a real situation, the numbers are very large. Assume that g = 7 and p = 23. The steps are as follows:
1. Alice chooses x = 3 and calculates R1 = 73 mod 23 = 21.
2. Bob chooses y = 6 and calculates R2 = 76 mod 23 = 4.
3.
Alice sends the number 21 to Bob.
4.
Bob sends the number 4 to Alice.
5.
Alice calculates the symmetric key K = 43 mod 23 = 18.

Prepared by Ch Samsonu, 126

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
6.
Bob calculates the symmetric key K = 216 mod 23 = 18.
7.
The value of K is the same for both Alice and Bob;
gxy mod p = 718 mod 35 = 18.

PUBLIC-KEY DISTRIBUTION

In asymmetric-key cryptography, people do not need to know a symmetric shared key; everyone shields a
private key and advertises a public key.
In public key key cryptography, everyone have access to every one’s public key: public keys are
available to the public.
So, public keys need to be distributed.

1. Public Announcement
2. Trusted Center
3. Controlled Trusted Center
4. Certification Authority

5. X.509
6.Public-Key Infrastructures (PKI)

Public Announcement
The normal method is to announce public keys publicly, but is not secure

Figure Announcing a public key

Trusted Center
A more secure approach is to have a trusted center retain a directory of public keys

Prepared by Ch Samsonu, 127

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Controlled Trusted Center

A higher level security can be achieved when there are added controls on

Prepared by Ch Samsonu, 128

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

UNIT –V
Network Security-I
Security at application layer: PGP and S/MIME, Security at the Transport Layer: SSL and TLS

Security at Application layer and Transport Layer

Various business services are now offered online though client-server applications.
The most popular forms are web application and e-mail.
In both applications, the client communicates to the designated server and obtains services.

While using a service from any server application, the client and server exchange a lot of information on the
underlying intranet or Internet. We are aware of fact that these information transactions are vulnerable to
various attacks.
Network security entails securing data against attacks while it is in transit on a network.

E-mail Security
Nowadays, e-mail has become very widely used network application. Email is one of the most widely
used and regarded network services. Currently message contents are not secure, may be inspected either
in transit or by suitably privileged users on destination system.
E-mail Architecture:

1. UA-User Agent is useful to prepare the messages

2. MTA-Message Transfer Agent is useful to send messages to mail server. This is the Push program
3. MAA-Message Access Agent is useful to receive messages from mail server. This is Pull program

Prepared by Ch Samsonu, 129

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

PGP(Pretty Good Privacy)

 Provides a confidentiality and authentication service that can be used for electronic mail and file
storage applications
 Developed by Phil Zimmermann
 Selected the best available cryptographic algorithms asbuilding blocks
 Integrated these algorithms into a general-purpose application that is independent of operating
system and processor and that is based on a small set of easy-to-usecommands
 Made the package and its documentation, including the source code, freely available via the
Internet, bulletin boards, and commercial networks
 Entered into an agreement with a company to provide a fully compatible, low –cost commercial
version of PGP
PGP Growth

It is available free worldwide in versions that run on a variety of platforms

• The commercial version satisfies users who want a product that comes with vendor support
• It is based on algorithms that have survived extensive public review and are considered extremely secure
• It has a wide range of applicability
• It was not developed by, nor is it controlled by, any governmental or standards organization
• Is now on an Internet standards track, however it still has an aura of an antiestablishment endeavor.

PGP Notation:
Ks = session key used in symmetric encryption scheme
PRa = private key of user A, used in public-key encryption
scheme PUa = public key of user A, used in public-key encryption
scheme EP = public-key encryption
DP = public-key decryption
EC = symmetric encryption
DC = symmetric decryption
H = hash function
|| = concatenation
Z = compression using ZIP algorithm
R64 = conversion to radix 64 ASCII format1

PGP Operation – Authentication:

1. sender creates a message
2. SHA-1 used to generate 160-bit hash code of message
3. hash code is encrypted with RSA using the sender's private key, and result is attached to message
4. receiver uses RSA or DSS with sender's public key to decrypt and recover hash code
5. receiver generates new hash code for message and compares with decrypted hash code, if match,
message is accepted as authentic

Prepared by Ch Samsonu, 130

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

PGP Operation – Confidentiality:

1. sender generates message and random 128-bit number to be used as session key for this message only
2. message is encrypted, using CAST-128 / IDEA/3DES with session key
3. session key is encrypted using RSA with recipient's public key, then attached to message
4. receiver uses RSA with its private key to decrypt and recover session key
5. session key is used to decrypt message

PGP Operation – Confidentiality & Authentication

Uses both services on same message
Create signature & attach to message o encrypt both message & signature o attach RSA encrypted session
key

PGP Operation – Compression

As a default, PGP compresses the message after applying the signature but before encryption. This has the
benefit of saving space both for e-mail transmission and for file storage.

Prepared by Ch Samsonu, 131

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

The placement of the compression algorithm, indicated by Z for compression and Z-1 for decompression.
So can store uncompressed message & signature for later verification & because compression is non
deterministic uses ZIP compression algorithm
PGP Operation – Email Compatibility

 When PGP is used, at least part of the block to be transmitted is encrypted. If only the signature
service is used, then the message digest is encrypted (with the sender’s private key). If the
confidentiality service is used, the message plus signature (if present) are encrypted (with a one-
time symmetric key).
 Thus, part or all of the resulting block consists of a stream of arbitrary 8 -bit octets.
 However, many electronic mail systems only permit the use of blocks consisting of ASCII text.
 To accommodate this restriction, PGP provides the service of converting the raw 8 -bit binary
stream to a stream of printable ASCII characters. The scheme used for this purpose is radix-64
conversion.
 Each group of three octets of binary data is mapped into four ASCII characters. This format also
appends

S/MIME (Secure/Multipurpose Internet Mail Extensions)

Secure/Multipurpose Internet Mail Extension (S/MIME) is a security enhancement to the MIME Internet
e-mail format standard based on technology from RSA Data Security. it appears likely that S/MIME will
emerge as the industry standard for commercial and organizational use, while PGP will remain the choice
for personal e-mail security for many users. S/MIME is defined in a number of documents—most
importantly RFCs 3370, 3850, 3851, and 3852.
S/MIME support in many mail agents eg MS Outlook, Mozilla, Mac Mail etc
To understand S/MIME, we need first to have a general understanding of the underlying e -mail format
that it uses, namely MIME. We have to learn about RFC5322(internet Message Format)
RFC 5322:

• Defines a format for text messages that are sent using electronic mail
• Messages are viewed as having an envelope and contents
• The envelope contains whatever information is needed to accomplish transmission and
delivery
• The contents compose the object to be delivered to the recipient
• RFC 5322 standard applies only to the contents
The content standard includes a set of header fields that may be used by the mail system to create the
envelope

The overall structure of a message that conforms to RFC 5322 is very simple. A message consists of some
number of header lines (the header) followed by unrestricted text (the body). The header is separated from
the body by a blank line. Put differently, a message is ASCII text, and all lines up to the first blank line
are assumed to be header lines used by the user agent part of the mail system.

A header line usually consists of a keyword, followed by a colon, followed by the keyword’s arguments;
the format allows a long line to be broken up into several lines. The most frequently used keywords are
From, To, Subject, and Date. Here is an example message:

Date: October 8, 2009 2:15:49 PM EDT

Prepared by Ch Samsonu, 132

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

From: “William Stallings”

<ws@shore.net> Subject: The
Syntax in RFC 5322
To: Smith@Other-host.com
Cc: Jones@Yet-Another-Host.com

Hello. This section begins the actual message body, which is delimited from the
message heading by a blank line.

Multipurpose Internet Mail Extensions (MIME):

An extension to the RFC 5322 framework that is intended to address some of the problems and limitations
of the use of Simple Mail Transfer Protocol (SMTP) lists the following limitations of the SMTP/5322
scheme.
1. SMTP cannot transmit executable files or other binary objects.
2. SMTP cannot transmit text data that includes national language characters, because these are
represented by 8-bit codes with values of 128 decimal or higher, and SMTP is limited to 7-bit ASCII.
3.SMTP servers may reject mail message over a certain size.
4.SMTP gateways that translate between ASCII and the character code EBCDIC do not use a consistent
set of mappings, resulting in translation problems.
MIME is intended to resolve these problems in a manner that is compatible with existing RFC 5322
implementations. The specification is provided in RFCs 2045 through 2049.

The MIME specification includes the following elements.

1. Five new message header fields are defined, which may be included in an
RFC 5322 header. These fields provide information about the body of the
message.
2. A number of content formats are defined, thus standardizing
representations that support multimedia electronic mail.
3. Transfer encodings are defined that enable the conversion of any content
format into a form that is protected from alteration by the mail system.

The Five Header Fields Defined in MIME: The five header fields defined in MIME are

• MIME-Version: Must have the parameter value 1.0. This field indicates that the
message conforms to RFCs 2045 and 2046.
• Content-Type: Describes the data contained in the body with sufficient detail
that the receiving user agent can pick an appropriate agent or mechanism to
represent the data to the user or otherwise deal with the data in an appropriate
manner.
• Content-Transfer-Encoding: Indicates the type of transformation that has been
used to represent the body of the message in a way that is acceptable for mail
transport.
• Content-ID: Used to identify MIME entities uniquely in multiple contexts.
• Content-Description: A text description of the object with the body; this is useful
when the object is not readable (e.g., audio data).

Prepared by Ch Samsonu, 133

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

MIME Content Types:

MIME Transfer Encodings:

Prepared by Ch Samsonu, 134

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

S/MIME Functionality: S/MIME provides the following functions.

• Enveloped data: This consists of encrypted content of any type and encrypted
content encryption keys for one or more recipients.
• Signed data: A digital signature is formed by taking the message digest of the
content to be signed and then encrypting that with the private key of the
signer. The content plus signature are then encoded using base64 encoding. A
signed data message can only be viewed by a recipient with S/MIME capability.
• Clear-signed data: As with signed data, a digital signature of the content is
formed. However, in this case, only the digital signature is encoded using
base64. As a result, recipients without S/MIME capability can view the message
content, although they cannot verify the signature.
• Signed and enveloped data: Signed-only and encrypted-only entities may be
nested, so that encrypted data may be signed and signed data or clear - signed
data may be encrypted.

S/MIME Messages:

• S/MIME secures a MIME entity with a signature, encryption, or both.

forming a MIME wrapped
Public-Key Cryptography Standards(PKCS) object have a range of content-types:
enveloped data o signed data, clear-signed data o registration request,certificate only message

S/MIME Content Types

S/MIME Certificate Processing:

• S/MIME uses public-key certificates that conform to version 3 of X.509

• The key-management scheme used by S/MIME is in some ways a hybrid
between a strict X.509 certification hierarchy and PGP’s web of trust
• S/MIME managers and/or users must configure each client with a list of
trusted keys and with certificate revocation lists.
The responsibility is local for maintaining the certificates needed to verify incoming signatures and
to encrypt outgoing messages
• The certificates are signed by certification authorities
User Agent Role An S/MIME user has several key-management functions to perform
Prepared by Ch Samsonu, 135
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

• Key generation: The user of some related administrative utility (e.g., one
associated with LAN management) MUST be capable of generating separate Diffie-
Hellman and DSS key pairs and SHOULD be capable of generating RSA key pairs.
Each key pair MUST be generated from a good source of nondeterministic random
input and be protected in a secure fashion. A use agent SHOULD generate RSA key
pairs with a length in the range of 768 to 1024 bits and MUST NOT generate a
length of less than 512 bits.
• Registration: A user’s public key must be registered with a certification authority in
order to receive an X.509 public-key certificate.
•Certificate storage and retrieval: A user requires access to a local list of certificates
in order to verify incoming signatures and to encrypt outgoing messages. Such a
list could be maintained by the user or by some local administrative entity on
behalf of a number of users.

VeriSign Certificates There are several companies that provide certification authority (CA) services. For
example, Nortel has designed an enterprise CA solution and can provide S/MIME support within an
organization. There are a number of Internet-based CAs, including VeriSign, GTE, and the U.S. Postal
Service.
Enhanced Security Services : three enhanced security services have been proposed
in an Internet draft. The three services are : Signed receipts, Security labels, Secure
mailing lists

Transport Level Security:

Web security considerations:
The World Wide Web is fundamentally a client/server application running over the Internet
and TCP/IP intranets
The following characteristics of Web usage suggest the need for tailored security tools:
 The Internet is two-way. Unlike traditional publishing environments—even electronic publishing
systems involving teletext, voice response, or fax-back— the Web is vulnerable to attacks on the
Web servers over the Internet.
 The Web is increasingly serving as a highly visible outlet for corporate and product information and
as the platform for business transactions. Reputations can be damaged and money can be lost if the
Web servers are subverted.
 Although Web browsers are very easy to use, Web servers are relatively easy to configure and
manage, and Web content is increasingly easy to develop, the underlying software is extraordinarily
complex. This complex software may hide many potential security flaws.
 A Web server can be exploited as a launching pad into the corporation’s or agency’s entire computer
complex. Once the Web server is subverted, an attacker may be able to gain access to data and
systems not part of the Web itself but connected to the server at the local site.
 Casual and untrained (in security matters) users are common clients for Web-based services. Such
users are not necessarily aware of the security risks that exist and do not have the tools or knowledge
to take effective countermeasures.

Prepared by Ch Samsonu, 136

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Web security Threats:

Table. A Comparison of Threats on the Web

Web Traffic Security Approaches:

A number of approaches to providing Web security are possible.

1. One way to provide Web security is to use IP security (IPsec) (Figure(a)). The
advantage of using IPsec is that it is transparent to end users and applications
and provides a general- purpose solution. It includes filtering capability that
filters the unwanted data.
2. Another relatively general-purpose solution is to implement security just above
TCP (Figure (b)). The example of this approach is the Secure Sockets Layer (SSL)
and the follow-on Internet standard known as Transport Layer Security (TLS). At
this level, there are two implementation choices. For full generality, SSL (or TLS)
could be provided as part of the underlying protocol suite and therefore be
transparent to applications. Alternatively, SSL can be embedded in specific
packages. For example, Netscape and Microsoft Explorer browsers come
equipped with SSL, and most Web servers have implemented the protocol.
3. Application-specific security services are embedded within the particular
application. Figure (c) shows examples of this architecture. The advantage of
this approach is that the service can be tailored to the specific needs of a given
application.

Prepared by Ch Samsonu, 137

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Figure: relative location of security facilities in the TCP/IP Protocol stack 5.4.

SSL (Secure Socket Layer):

SSL probably most widely used Web security mechanism, and it is implemented at the Transport layer.
SSL is designed to make use of TCP to provide a reliable end-to-end secure service.
Netscape originated SSL. Version 3 of the protocol was designed with public review and input from
industry and was published as an Internet draft document. Subsequently, became Internet standard known
as TLS (Transport Layer Security)
SSL Architecture:

SSL is designed to make use of TCP to provide a reliable end-to-

end secure service. SSL is not a single protocol but rather two
layers of protocols.
Two important SSL concepts are the SSL session and the SSL connection, which are defined in
the specification as follows.
1. Connection: A connection is a transport that provides a suitable type of
service. For SSL, such connections are peer-to-peer relationships. Every
connection is associated with one session.
2. Session: An SSL session is an association between a client and a server.
Sessions are created by the Handshake Protocol. Sessions define a set of
cryptographic security parameters which can be shared among multiple
connections.

Figure: SSL Protocol stack

SSL Record Protocol:

SSL Record Protocol defines two services for SSL connections:

1. Confidentiality: The Handshake Protocol defines a shared secret
key that is used for conventional encryption of SSL payloads. The
message is compressed before being concatenated with the MAC
and encrypted, with a range of ciphers being supported as shown.
2. Message Integrity: The Handshake Protocol also defines a shared
secret key that is used to form a message authentication code
(MAC).

Prepared by Ch Samsonu, 138

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Figure: SSL Record Protocol Operation

Figure shows the overall operation of the SSL Record Protocol. The Record Protocol takes an application
message to be transmitted, fragments the data into manageable blocks, optionally compresses the data,
applies a MAC, encrypts, adds a header, and transmits the resulting unit in a TCP segment. Received data
are decrypted, verified, decompressed, and reassembled before being delivered to higher-level users.

Figure: SSL Record Format

The final step of SSL Record Protocol processing is to prepare a header consisting of the following
fields:
Content Type (8 bits): The higher-layer protocol used to process the enclosed
fragment. Major Version (8 bits): Indicates major version of SSL in use. For
SSLv3, the value is 3. Minor Version (8 bits): Indicates minor version in use. For
SSLv3, the value is 0.
Compressed Length (16 bits): The length in bytes of the plaintext
fragment (or compressed fragment if compression is used). The
maximum value is 214 + 2048.
ChangeCipherSpec Protocol:
The Change Cipher Spec Protocol is one of the three SSL-specific protocols that use the SSL Record
Protocol. It is the simplest, consisting of a single message, which consists of a single byte with the value
1. The sole purpose of this message is to cause the pending state to be copied into the current state,
which updates the cipher suite to be used on this connection.

Prepared by Ch Samsonu, 1
Assoc.Professor, 3
Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Prepared by Ch Samsonu, 1
Assoc.Professor, 3
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

SSL Alert Protocol:

The Alert Protocol is used to convey SSL-related alerts to the peer entity. As with other applications that
use SSL, alert messages are compressed and encrypted, as specified by the current state. Each message in
this protocol consists of two bytes, the first takes the value warning (1) or fatal (2) to convey the severity
of the message. The second byte contains a code that indicates the specific alert.

SSL Handshake Protocol:

The most complex part of SSL is the Handshake Protocol. This protocol allows the server and client to
authenticate each other and to negotiate an encryption and MAC algorithm and cryptographic keys to be
used to protect data sent in an SSL record. The Handshake Protocol is used before any application data is
transmitted. The Handshake Protocol consists of a series of messages exchanged by client and server.

The exchange can be viewed in 4 phases:

• Phase 1. Establish Security Capabilities - this phase is used by the
client to initiate a logical connection and to establish the security
capabilities that will be associated with it
• Phase 2. Server Authentication and Key Exchange - the server begins this
phase by sending its certificate if it needs to be authenticated.
• Phase 3. Client Authentication and Key Exchange - the client should verify that
the server provided a valid certificate if required and check that the
server_hello parameters are acceptable
• Phase 4. Finish - this phase completes the setting up of a secure connection.
The client sends a change_cipher_spec message and copies the pending
CipherSpec into the current CipherSpec. At this point the handshake is
complete and the client and server may begin to exchange application layer
data.

Prepared by Ch Samsonu, 140

Assoc.Professor,
Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Prepared by Ch Samsonu, 141

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Transport Layer Security (TLS) Protocol

In order to provide an open Internet standard of SSL, Internet Engineering Task Force(IETF) released
The Transport Layer Security (TLS) protocol in January 1999. TLS is defined as a proposed Internet
Standard in RFC 5246.
Salient Features
TLS protocol has same objectives as SSL.
It enables client/server applications to communicate in a secure manner by authenticating, preventing
eavesdropping and resisting message modification.
TLS protocol sits above the reliable connection-oriented transport TCP layer in the networking layers’
stack.
The architecture of TLS protocol is similar to SSLv3 protocol. It has two sub protocols: the TLS Record
protocol and the TLS Handshake protocol.
Though SSLv3 and TLS protocol have similar architecture, several changes were made in
architecture and functioning particularly for the handshake protocol.

Comparison of TLS and SSL Protocols:

1. Protocol Version − The header of TLS protocol segment carries the version
number
todifferentiate between number 3 carried by SSL protocol segment header.
2. Message Authentication − TLS employs a keyed-hash message authentication
code (HMAC). Benefit is that H-MAC operates with any hash function, not just
MD5 or SHA, as explicitly stated by the SSL protocol.
3. Session Key Generation − There are two differences between TLS and SSL
protocol for generation of key material.
1. Method of computing pre-master and master secrets is similar. But in TLS
protocol, computation of master secret uses the HMAC standard and
pseudorandom function (PRF) output instead of ad-hoc MAC.
2. The algorithm for computing session keys and initiation values (IV) is
different in TLS than SSL protocol.
4. Alert Protocol Message −
1. TLS protocol supports all the messages used by the Alert protocol of
SSL, except No certificate alert message being made redundant. The client
sends empty certificate in case client authentication is not required.
2. Many additional Alert messages are included in TLS protocol for other error
conditions such as
record_overflow, decode_erroretc.

5. Supported Cipher Suites − SSL supports RSA, Diffie-Hellman and Fortezza

cipher suites. TLS protocol supports all suits except Fortezza.
6. Client Certificate Types − TLS defines certificate types to be requested in a
certificate_request message. SSLv3 support all of these. Additionally, SSL
support certain other types of certificate such as Fortezza.
7. CertificateVerify and Finished Messages −

Prepared by Ch Samsonu, 142

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
1. In SSL, complex message procedure is used for thecertificate_verify
message. With TLS, the verified information is contained in the
handshake messages itself thus avoiding this complex procedure.
2. Finished message is computed in different manners in TLS and SSLv3.
8. Padding of Data − In SSL protocol, the padding added to user data before
encryption is the minimum amount required to make the total data-size
equal to a multiple of the cipher’s block length. In TLS, the padding can be
any amount that results in data-size that is a multiple of the cipher’s block
length, up to a maximum of 255 bytes.

Secure Shell Protocol (SSH):

The salient features of SSH are as follows −

SSH is a network protocol that runs on top of the TCP/IP layer. It is

designed to replace the TELNET which provided unsecure means of
remote logon facility.

SSH provides a secure client/server communication and can be used

for tasks such as file transfer and e-mail.
SSH2 is a prevalent protocol which provides improved network
communication security over earlier version SSH1.

Figure: SSH Protocol stack

Transport Layer Protocol:

In this part of SSH protocol provides data confidentiality, server (host) authentication, and data
integrity. It may optionally provide data compression as well.
Server Authentication − Host keys are asymmetric like public/private keys. A server uses a
public
key to prove its identity to a client. The client verifies that contacted server is a ―known‖ host from
the database it maintains. Once the server is authenticated, session keys are generated.
Prepared by Ch Samsonu, 143
Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
Session Key Establishment − After authentication, the server and the client agree upon cipher
to be
used. Session keys are generated by both the client and the server. Session keys are generated before
user authentication so that usernames and passwords can be sent encrypted. These keys are generally
replaced at regular intervals (say, every hour) during the session and are destroyed immediately after
use.
Data Integrity − SSH uses Message Authentication Code (MAC) algorithms to for data
integrity check. It is an improvement over 32 bit CRC used by SSH1.
User Authentication Protocol:
In this part of SSH authenticates the user to the server. The server verifies that access is given to
intended users only. Many authentication methods are currently used such as, typed passwords,
Kerberos, public-key authentication, etc.
Connection Protocol:
This provides multiple logical channels over a single underlying SSH connection
SSH Services:
SSH provides three main services that enable provision of many secure solutions. These services are
briefly described as follows −
Secure Command-Shell (Remote Logon) − It allows the user to edit files, view the contents of
directories, and access applications on connected device. Systems administrators can remotely
start/view/stop services and processes, create user accounts, and change file/directories permissions
and so on. All tasks that are feasible at a machine’s command prompt can now be performed securely
from the remote machine using secure remote logon.
Secure File Transfer − SSH File Transfer Protocol (SFTP) is designed as an extension for SSH-2 for
secure file transfer. In essence, it is a separate protocol layered over the Secure Shell protocol to
handle file transfers. SFTP encrypts both the username/password and the file data being transferred. It
uses the same port as the Secure Shell server, i.e. system port no 22.
Port Forwarding (Tunneling) − It allows data from unsecured TCP/IP based applications to be
secured. After port forwarding has been set up, Secure Shell reroutes traffic from a program (usually
a client) and sends it across the encrypted tunnel to the program on the other side (usually a server).
Multiple applications can transmit data over a single multiplexed secure channel, eliminating the need
to open many ports on a firewall or router.

Prepared by Ch Samsonu, 144

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
UNIT -VI:
Network Security-II : Security at the Network Layer: IPSec, System Security

1. IP SECURITY OVERVIEW
IPSec is an Internet Engineering Task Force (IETF) standard suite of protocols that provides data
authentication, integrity, and confidentiality as data is transferred between communication points
across IP networks.
IPSec provides data security at the IP packet level. A packet is a data bundle that is organized for
transmission across a network, and it includes a header and payload (the data in the packet).

IPSec SECURITY FEATURES:

IPSec is the most secure method commercially available for connecting network sites.
IPSec was designed to provide the following security features when transferring packets across
networks:
Authentication: Verifies that the packet received is actually from the claimed sender.
Integrity: Ensures that the contents of the packet did not change in transit.
Confidentiality: Conceals the message content through encryption.

IPSec ELEMENTS:
IPSec contains the following elements:
Encapsulating Security Payload (ESP): Provides confidentiality, authentication, and integrity.
Authentication Header (AH): Provides authentication and integrity.
Internet Key Exchange (IKE): Establish shared symmetric key. Provides key management and
Security Association (SA) management.

APPLICATIONS OF IPSec:
IPSec provides the capability to secure communications across a LAN, across private and public
WANs, and across the Internet.
Examples of its use include the following:
 Secure branch office connectivity over the Internet
 Secure remote access over the Internet
Establishing extranet and intranet connectivity with partners:
 IPSec can be used to secure communication with other organizations, ensuring authentication
and confidentiality and providing a key exchange mechanism.
Enhancing electronic commerce security:
 Even though some Web and electronic commerce applications have built-in security protocols,
the use of IPSec enhances that security.

BENEFITS OF IPSEC:
 IPSec provides strong security within and across the LANs.
 Firewall uses IPSec to restrict all those incoming packets which are not using IP. Since
firewall is the only way to enter into an organization, restricted packets cannot enter.
 IPSec is below the transport layer (TCP, UDP) and so is transparent to applications.
 There is no need to change software on a user or server system when IPSec is implemented in
the firewall or router.
 Even if IPSec is implemented in end systems, upper- layer software, including applications, is
not affected. IPSec can be transparent to end users.

Prepared by Ch Samsonu, 145

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
 IPSec can provide security for individual users if needed.

IPSec Scenario:

IPSec Architecture:
Architecture covers general concepts of security requirements, definitions, and mechanisms defining
IPSec technology.

Prepared by Ch Samsonu, 146

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Figure : IPSec Architecture

Encapsulating Security Payload(ESP): The ESP header is designed to provide a mix of security
services in IPv4 and IPv6. ESP may be applied alone, in combination with AH, or in a nested fashion.
It consists of an encapsulating header and trailer used to provide encryption or combined
encryption/authentication. Current specification is RFC 4303

Authentication Header(AH): An extension header to provide message authentication. Current

specification is RFC 4302.

Encryption algorithms: Encryption algorithms encrypt data with a key. The ESP module in IPsec
uses encryption algorithms.

Authentication algorithms: Authentication algorithms produce an integrity checksum value

or digest that is based on the data and a key. The AH module uses authentication algorithms. The ESP
module can use authentication algorithms as well.

Domain of Interpretation(DOI): DOI is the identifier which support both AH and ESP protocols. It
contains values needed for documentation related to each other.

Key Management: It contains the document that describes how the keys are exchanged between
sender and receiver.

Security Associations (SAs)

An SA is a relationship between communicating devices that describes how they will use security
services to communicate securely.
If client wants to communicate with server, it has client Security Association, if Server wants to reply
to client, it has server Security association.
These SAs are one way communications.
If two parties need to communicate, they must determine which algorithms (RSA, 3DES, MD5,

Prepared by Ch Samsonu, 147

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
SHA…) and session keys are used. SA used by IPsec to track all these parameters for each session.
You will need to configure SA parameters and monitor SAs on Cisco routers and the PIX Firewall.
• A separate pair of IPSec SAs are set up for AH and ESPtransform.
• Each IPSec peer agrees to set up SAs consisting of policy parameters to be used during the
IPSec session.
• The SAs are unidirectional for IPSec so that peer 1 will offer peer 2 a policy.
• If peer 2 accepts this policy, it will send that policy back to peer 1. This establishes two one-
way SAs between the peers.
• Two-way communication consists of two SAs, one for each direction.
• Each SA consists of values such as destination address, a security parameter index (SPI), the
IPSec transforms used for that session, security keys, and additional attributes such as IPSec
lifetime.
A security association is uniquely identified by three parameters:
• Security Parameters Index (SPI): A bit string assigned to this SA and having local
significance only. SPI is located in AH and ESP headers. SPI enables the receiving system
under which the packet is to process.
• IP Destination Address: It is the end point address of SA which can be end user system or a
network system.
• Security Protocol Identifier: security protocol identifier indicates whether the associations is
an AH or ESP.
All the SAs are maintained in Security Association Database(SAD)

SA Parameters:
Sequence Number Counter: A 32-bit value used to generate the Sequence Number field in AH or
ESP headers.
Sequence Counter Overflow: A flag indicating whether overflow of the Sequence Number
Counter should generate an auditable event and prevent further transmission of packets on this
SA.
Anti-Replay Window: Avoid duplicate of packets
AH Information: Authentication algorithm, keys, key lifetimes, and related parameters being used
with AH.
ESP Information: Encryption and authentication algorithm, keys, initialization values, key lifetimes,
and related parameters being used with ESP (required for ESP implementations).
Lifetime of This Security Association: A time interval or byte count after which an SA must be
replaced with a new SA or terminated.
IPSec Protocol Mode: This parameter represents the type of mode used for IPSec implementation.
The mode may be a Tunnel or transport.

Transport and Tunnel Modes in IPsec

IPSec operates in two modes:
1)Tunnel Mode
2) Transport Mode

Prepared by Ch Samsonu, 148

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Tunnel Mode:
With tunnel mode, the entire original IP packet is protected by IPSec. This means IPSec wraps the
original packet, encrypts it, adds a new IP header and sends it to the other side.
Original IP Header not visible to attacker(if it is using ESP).
Attacker does not know which hosts are talking.

Figure : IPSec Tunnel mode

Tunnel mode is most commonly used between gateways, end-system to Gateways.

Transport Mode:
IPSec Transport mode is used for end-to-end communications, for example, for communication
between a client and a server or between a workstation and a gateway (if the gateway is being treated
as a host).

When using the transport mode, only the IP payload is encrypted. AH or ESP provides protection for
the IP payload. The original IP header is not changed,
So the passive attackers can see who is talking.

Prepared by Ch Samsonu, 149

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Figure : IPSec Transport Mode

AUTHENTICATION HEADER (AH)

The Authentication Header provides support for data integrity and authentication of IP packets.
Data integrity service insures that data inside IP packets is not altered during the transit.
The authentication feature enables an end system to authenticate the user or application and filter
traffic accordingly. It also prevents the address spoofing attacks
AH is implemented in one way only i.e Authentication along with Integrity.
AH provides authentication for as much of the IP header as possible, but cannot all be protected by
AH.
AH also includes an IPSec sequence number, which provides protection against replay attacks
because this number is also included in authenticated data and can be checked by the receiving party.
Data privacy is not provided by AH.

Figure : Authentication Header Format

1. Next Header: Identifies the type of header that immediately following the AH.
2. Payload Length: Length of Authentication Header in 32-bit words.
3. Reserved: For future use.
4. Security Parameters Index: Identifies a security association.
5. Sequence Number: A monotonically increasing counter value.
6. Authentication Data (variable): A variable-length field that contains the Integrity Check Value
(ICV), or MAC, for this packet.

Prepared by Ch Samsonu, 150

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

Encapsulating Security Payload(ESP):

Security services can be provided between a pair of communicating hosts, between a pair of
communicating security gateways, or between a security gateway and a host. The ESP header is
inserted after the IP header and before the next layer protocol header (transport mode) or before an
encapsulated IP header (tunnel mode). ESP can be used to provide confidentiality, data origin
authentication, connectionless integrity, an anti-replay service (a form of partial sequence integrity),
and (limited) traffic flow confidentiality. The set of services provided depends on options selected at
the time of Security Association (SA) establishment and on the location of the implementation in a
network topology.

Figure : ESP Format

1. Security Parameters Index : Identifies a security association.

2. Sequence Number : A monotonically increasing counter value; this provides an anti-replay
function, as discussed for AH.
3. Payload Data : This is a transport-level segment (transport mode) or IP packet (tunnel
mode) that is protected by encryption.
4. Padding (0-255 bytes):Extra bits or spaces are added to the message in order to maintain
confidentiality
5. Pad Length : Indicates the number of pad bytes immediately preceding this field.
6. Next Header : means the next payload or next data
7. Authentication Data (variable): contains the Integrity Check Value computed over the ESP packet
minus the Authentication Data field.

Security Policy(SP)
A Security Policy is a set of rules that define the type security applied to a packet when it is to be sent
or when it has arrived. It defines the network traffic at the IP layer.

IPSec protects your private network from internet attacks through end-to-end security.

Prepared by Ch Samsonu, 151

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
IPSec policy is determined primarily by the interaction of two databases, the Security Association
Database(SAD) and the Security Policy Databases(SPD)

IPSec policies must be carefully designed, configures, coordinated and managed to ensure that IPSec
communication is successful.

Security Policy Database (SPD)

IPSec Policies are maintained in the Security Policy Database (SPD).

IPSec Policies defines which traffic to be protected, how it is to be protected, and with whom to protect
it.

The sending host determines what policy is appropriate for the packet, depending on various "Selectors"
by checking in the Security Policy Database (SPD).

"Selectors" can include Source and Destination IP Addresses, Name (User ID ir a System Name),
Transport Layer Protocols (TCP or UDP) or Source and Destination Ports.

The Security Policy Database (SPD) indicates what the policy is for a particular packet. If the packet
requires IPsec processing, it will be it is passed to the IPsec module for the required processing.

KEY MANAGEMENT of IPSec

The key management portion of IPSec involves the determination and distribution of secret keys

typical requirement is four keys for communication between two applications: transmit and receive pairs
for both AH and ESP.

Keys are managed by

• Manual: A system administrator manually configures each system with its own keys and with the
keys of other communicating systems. This is suitable for small, relatively static environments.
• Automated: An automated system enables the on-demand creation of keys for SAs and facilitates
the use of keys in a large distributed system.

The default automated key management protocol for IPSec is referred to as ISAKMP/Oakley .

Key management protocol – Elements

1. Oakley Key Determination Protocol

2. Internet Security Association and Key Management Protocol (ISAKMP)

Oakley Key Determination Protocol:

Prepared by Ch Samsonu, 152

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem
• Oakley is a key exchange protocol based on the Diffie-Hellman algorithm but providing added
security.
• Oakley is generic in that it does not dictate specific formats.

The Diffie-Hellman algorithm has two attractive features:

1. Secret keys are created only when needed.

2. The exchange requires no preexisting infrastructure other than an agreement on the global parameters.
However, there are a number of weaknesses to Diffie-Hellman, as pointed outin

3. It does not provide anyinformation about the identities of the parties.

4. It is subject to a man-in-the-middle attack

It is computationally intensive. As a result, it is vulnerable to a clogging attack, in which an opponent

requests a high number of keys. Oakley is designed to retain the advantages of Diffie-Hellman while
countering its weaknesses.

Features of Oakley:

The Oakley algorithm is characterized by five important features:

• It employs a mechanism known ascookies to thwart clogging attacks.

• It enables the two parties to negotiate a group; this, in essence, specifies the global parameters of
the Diffie-Hellman key exchange.
• It uses nonces to ensure against replay attacks.
• It enables the exchange of Diffie-Hellman public key values.
• It authenticates the Diffie-Hellman exchange to thwart man-in-the-middle attacks.

Internet Security Association and Key Management Protocol (ISAKMP):

ISAKMP provides a framework for Internet key management and provides the specific protocol support,
including formats, for negotiation of security attributes.

ISAKMP Header Format:

An ISAKMP message consists of an ISAKMP header followed by one or more payloads. All of this is
carried in a transport protocol. The specification dictates that implementations must support the use of
UDP for the transport protocol.

Prepared by Ch Samsonu, 153

Assoc.Professor,
 Cryptography and Network Security B.Tech(CSE) IV Year I Sem

It consists of the following fields:

1. Initiator Cookie (64 bits): Cookie of entity that initiated SA establishment, SA notification, or SA
deletion.
2. Responder Cookie (64 bits): The cookie of entity that is responding to an SA establishment request,
SA notification, or SA deletion. On the first message, the responder cookie iszero.
3. Next Payload (8 bits): Indicates the type of the first payload in the message
4. Major Version (4 bits): Indicates major version of ISAKMP in use.
5. Minor Version (4 bits): Indicates minor version in use.
6. Exchange Type (8 bits): Indicates the type of exchange.
7. Flags (8 bits): Indicates specific options set for this ISAKMP exchange.
8. Message ID (32 bits): Unique ID for this message.
9. Length (32 bits): Length of total message (header plus all payloads) inoctets.

ion has a high false alarm rate.

Prepared by Ch Samsonu, 154

Assoc.Professor,