UNIT - II

Traditional Symmetric-Key Ciphers

Module I
Traditional Symmetric-Key Ciphers: Introduction, Substitution Ciphers, Transpositional
Ciphers, Stream and Block Ciphers.
Module II
Data Encryption Standard (DES): Introduction, DES Structure, DES Analysis, Security of
DES, Multiple DES, Examples of Block Ciphers influenced by DES. Module III
Advanced Encryption Standard: Introduction, Transformations, Key Expansion, The AES
Ciphers, Examples, Analysis of AES.
Module I-Objectives
 To define the terms and the concepts of symmetric key ciphers
 To emphasize the two categories of traditional ciphers: substitution and transposition ciphers
 To describe the categories of cryptanalysis used to break the symmetric ciphers
 To introduce the concepts of the stream ciphers and block ciphers
 To discuss some very dominant ciphers used in the past, such as the Enigma machine
Symmetric cypher model
 Symmetric encryption is a form of crypto system in which encryption and decryption are
performed using the same key. It is also known as Conventional Encryption.
 Symmetric encryption transforms plaintext into ciphertext using a secret key and an encryption
algorithm. Using the same key and a decryption algorithm, the plaintext is recovered from the
ciphertext.
 The two types of attack on an encryption algorithm are cryptanalysis, based on properties of the
encryption algorithm, and brute-force, which involves trying all possible keys.
 Traditional (pre-computer) symmetric ciphers use substitution and/or transposition techniques.
 Substitution techniques map plaintext elements (characters, bits) into ciphertext elements.
 Transposition techniques systematically transpose the positions of plaintext elements.
Terminologies
 Cryptography is the process of making and using codes to secure the transmission of information.
(kryptos-meaning "hidden“ and graphein- meaning “to write”)
 Cryptanalysis is the process of obtaining the original message (called the plaintext) from an encrypted
message (called the ciphertext) without knowing the algorithms and keys used to perform the encryption.
 Encryption is the process of converting an original message into a form that is unreadable to unauthorized
individuals- that is, to anyone without the tools to convert the encrypted message back to its original format.
 Decryption is the process of converting the ciphertext message back into plaintext so that it can be readily
understood.
 Cipher or Crypto system: An encryption method or process encompassing the algorithm, key(s) or crypto
variable(s),and procedures used to perform encryption and decryption.
 Ciphertext or Cryptogram: The encoded message resulting from an encryption.
 Plaintext or cleartext: The original unencrypted message, or a message that has been successfully
decrypted.
 Code: The process of converting components (words or phrases) of an unencrypted message into encrypted
components.
 Decipher: To decrypt, decode, or convert, ciphertext into the equivalent plaintext.
 Encipher: To encrypt, encode, or convert, plaintext into the equivalent ciphertext.
Terminologies
 Key or Cryptovariable: The information used in conjunction with an algorithm to create the
cipher text from the plaintext or derive the plaintext from the ciphertext; the key can be a series
of bits used by a computer program, or it can be a pass phrase used by humans that is then
converted into a series of bits used by a computer program.
 Keyspace: The entire range of values that can be used to construct an individual key.
 Link encryption : A series of encryptions and decryptions between a number of systems,
wherein each system in a network decrypts the message sent to it and then re-encrypts it using
different keys and sends it to the next neighbor, and this process continues until the message
reaches the final destination .
 Steganography: The hiding of messages-for example, within the digital encoding of a picture or
graphic.
 Work factor: The amount of effort (usually in hours) required to perform cryptanalysis to
decode an encrypted message when the key or algorithm (or both) are unknown.
Symmetric and Public key Algorithms
 Encryption/Decryption methods fall into two categories.
1. Symmetric key 2. Public key
 Symmetric key algorithms
 The encryption and decryption keys are known both to sender and receiver.
 The encryption key is shared and the decryption key is easily calculated from it.
 In many cases, the encryption and decryption keys are the same.
 Public key cryptography
 Encryption key is made public, but it is computationally infeasible to find the decryption key
without the information known to the receiver.
Traditional Symmetric - Key Ciphers
 Two requirements for secure use of symmetric encryption:
 A strong encryption algorithm
 A secret key known only to sender/ receiver
 Y= Ek (X)
 X= Dk (Y)
 Figure shows the general idea behind a symmetric-key cipher.
 The original message from Alice to Bob is called plaintext..
 The message that is sent through the channel is called the cipher text.
 To create the cipher text from the plaintext, Alice uses an encryption algorithm and a shared
secret key.
 To create the plaintext from cipher text, Bob uses a decryption algorithm and the same secret key.
General idea of symmetric-key cipher
Symmetric-key cipher
 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:

Kerckhoff’s Principle

 Based on Kerckhoff’s principle, one should always assume that the opponent, 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.

Cryptanalysis attacks
Ciphertext-Only Attack

 In the ‘cipher-only’ attack, the attacker knows the ciphertext of various messages which have
been encrypted using the same encryption algorithm.
 The attacker’s challenge is to figure the ‘key’ which can then be used to decrypt all messages.
 The ‘cipher-only’ attack is probably one of the easiest attacks to commit since it is easy to capture
the ciphertext (by sniffing) but difficult to implement since the knowledge about the encryption
process is limited.
Known-Plaintext Attack

 In the ‘known-plaintext’ attack, the attacker knows some of the plaintext and the
ciphertext.
 He then has to figure the ‘key’ by reverse engineering and he can decipher other messages
which use the same ‘key’ and algorithm.
 The ‘known-plaintext’ attack was effective against simple ciphers such as the ‘substitution
cipher’.
 It was popular for breaking ciphers used during the Second World War.
Chosen-Plaintext Attack
 The ‘chosen-plaintext’ attack is similar to the ‘known-plaintext’ attack, but here the attacker
experiments by choosing his own plaintext and with the generated ciphertext he can figure the
‘key’.
 Once he figures the ‘key’ he can learn more about the whole encryption process and understand
how the ‘key’ is being used.
 With this information, he can decrypt other messages.
Chosen-Ciphertext Attack
 In the ‘chosen ciphertext’ attack, the attacker chooses a portion of the decrypted ciphertext.
 He then compares the decrypted ciphertext with the plaintext and figures out the key.
 This is relatively a harder type of attack and earlier versions of RSA were subject to these
types of attacks.
I.SUBSTITUTION CIPHERS

A substitution cipher replaces one symbol with another.

 If the plaintext is viewed as a sequence of bits, then substitution involves replacing
plaintext bit patterns with cipher text bit patterns.
 To use a substitution cipher, we substitute one value for another, for example a letter in the
alphabet with the letter three values to the right or we can substitute one bit for another
bit that is four places to its left.

 Substitution ciphers can be categorized as :

1. Monoalphabetic ciphers
2. Polyalphabetic ciphers.
Shift Cipher and Caesar Cipher
 Historically, additive ciphers are called shift ciphers.
 Julius Caesar used an additive cipher to communicate with his officers.
 Caesar used a key of 3 for his communications.
 Example:
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.

Plaintext and ciphertext in Z26

Additive Cipher

 When the cipher is additive, the plaintext, ciphertext, and key are integers in Z26.
Examples
I. Use the additive cipher with key = 15 to encrypt the message “hello”.
Solution

We apply the encryption algorithm to the plaintext character

II. Use the additive cipher with key=15 to decrypt the message “WTAAD”.

Solution

We apply the decryption algorithm to the plaintext character

4. Multiplicative Ciphers

 In a multiplicative cipher, the plaintext and ciphertext are integers in Z26; the key is an
integer in Z26*
Examples
I. What is the key domain for any multiplicative cipher?
 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.
II. We use a multiplicative cipher to encrypt the message “hello” with a key of 7. The ciphertext
is “XCZZU”.
Monoalphabetic Substitution Cipher
 Because additive and multiplicative 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.
 In monoalphabetic substitution, the relationship between a symbol in the plaintext to a symbol in
the ciphertext is always one-to-one.
 Alice and Bob can agree on a table showing the mapping for each character.

 Using the above table we can encrypt the message

 The ciphertext is
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.
 Features are:
1. A set of related monoalphabetic substitution rules is used.
2. A key determines which particular rule is chosen for a given transformation.
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.
Playfair Cipher
 Used by British army during world war I.
 Secret key in this cypher is made of 25 characters arranged in 5X5 matrix.
 Letters I and J are counts as one while encrypting.
 An example of a secret key in the Playfair cipher
 The Playfair Cipher Encryption Algorithm: 
The Algorithm consists of 2 steps:  
1. Generate the key Square(5×5): 
 The key square is a 5×5 grid of alphabets that acts as the key for encrypting the plaintext. Each of
the 25 alphabets must be unique and one letter of the alphabet (usually J) is omitted from the table
(as the table can hold only 25 alphabets). If the plaintext contains J, then it is replaced by I.  
 The initial alphabets in the key square are the unique alphabets of the key in the order in which they
appear followed by the remaining letters of the alphabet in order. 
 
M O N A R
C H Y B D
E F G I/J K
L P Q S T
U V W X Z
Playfair Cipher
2. Algorithm to encrypt the plain text: 
 The plaintext is split into pairs of two letters (digraphs). If there is an odd number of letters, a z is
added to the last letter. 

For example:
PlainText: "instruments" After Split: 'in' 'st' 'ru' 'me' 'nt' 'sz'
 Pair cannot be made with same letter. Break the letter in single and add a bogus letter to the
previous letter.
Plain Text: “hello”
After Split: ‘he’ ‘lx’ ‘lo’
Here ‘x’ is the bogus letter.
  If the letter is standing alone in the process of pairing, then add an extra bogus letter with the
alone letter
Plain Text: “helloe”
AfterSplit: ‘he’ ‘lx’ ‘lo’ ‘ez’
Here ‘z’  is the bogus letter.
Rules for Encryption: 

If both the letters are in If both the letters are in If neither of the above
the same row: the same column rules is true

Take the letter to the right Take the letter below each Each plaintext is replaced
of each one (going back to one (going back to the top by the letter that lies in its
the leftmost if at the if at the bottom). own row & column
rightmost position) occupied by the other
plaintext
Diagraph: "st" Encrypted Diagraph: "me" Diagraph: "nt" Encrypted
Text: tl Encrypted Text: cl Text: rq
Example
 Plain Text: "instrumentsz"
 Encrypted Text: gatlmzclrqtx
Playfair Cipher

 Let us encrypt the plaintext “hello” using the key

 Strength of playfair cipher

 Playfair cipher is a great advance over simple monoalphabetic ciphers.
 Since there are 26 letters, 26 x 26 = 676 diagrams are possible, so identification of individual diagram is more
difficult.
Vigenere Cipher

 Developed by Blaise de Vigenere.

 The Vigenère cipher is a method of encrypting alphabetic text by using a series of interwoven
Caesar ciphers, based on the letters of a keyword.
 It employs a form of polyalphabetic substitution.
 A Vigenere Cipher uses a different strategy to create the key frame.
 The key stream is a repetition of initial key stream of length m where we have 1<=m<=26.
 For generating key, the given keyword is repeated in a circular manner until it matches the length of
the plain text.
 Unlike other poly alphabetic cyphers ,this cypher does not depends on plain text but depends only
on the position of characters in plain text.
Examples
 We can encrypt the message “She is listening” using the 6-character keyword “PASCAL” , key
stream is (15,0,18,2,0,11).
 Let us see how we can encrypt the message “She is listening” using the 6-character keyword
“PASCAL”. The initial key stream is (15, 0, 18, 2, 0, 11). The key stream is the repetition of this
initial key stream (as many times as needed).
Vigenere Cipher
 Vigenere cipher can be seen as combinations of m additive ciphers.
Vigenere tableau
 Each of the 26 ciphers is laid out horizontally, with the key letter for each cipher to its left.
 A normal alphabet for the plaintext runs across the top.
 The process of Encryption is simple: Given a key letter X and a plaintext letter y, the cipher
text is at the intersection of the row labeled x and the column labeled y.
 Example:
Plaintext s e n d m o n e y
Key l o c k l o c k l
ciphertext D S P N X C P O J

 In Decryption ,the key letter again identifies the row. The position of the cipher text letter in
that row determines the column, and the plaintext letter is at the top of that column.
 Strength of Vigenere cipher
• There are multiple cipher text letters for each plaintext letter.
• Letter frequency information is concealed.
Vigenere tableau
the additive cipher is a special case of Vigenere cipher in which m = 1
One-Time Pad
 One of the goals of cryptography is perfect secrecy.
 A study by Shannon has shown that perfect secrecy can be achieved if each plaintext symbol is
encrypted with a key randomly chosen from a key domain.
 This idea is used in a cipher called one-time pad, invented by Vernam.
 It is an unbreakable cryptosystem. It represents the message as a sequence of 0’s and 1’s.
 This can be accomplished by writing all numbers in binary or by using ASCII.
 The key is a random sequence of 0"s and 1"s of same length as the message. Once a key is
used, it is discarded and never used again. The system can be expressed as follows:
 Ci = Pi Ki
 Ci - ith binary digit of ciphertext
 Pi- ith binary digit of plaintext
 Ki - ith binary digit of key
One-Time Pad
 Exclusive
  OR
 Ciphertext is generated by performing the bitwise XOR of the plaintext and the key.


 Decryption also uses the same key. Because of the properties of XOR, decryption simply involves the same
bitwise operation:

 Advantage
 Encryption method is completely unbreakable for ciphertext only attack.
 Disadvantages
 It requires a very long key which is expensive to produce and expensive to transmit.
 Once a key is used, it is dangerous to reuse it for a second message; any knowledge on the first message would
give knowledge of the second.
Example
 Plaintext – Hello and a pad – uBV,; will give you a cipher text- =‘:@T

1001000
1110101
0111101 = 61
II.TRANSPOSITION CIPHERS

 A transposition cipher does not substitute one symbol for another, instead it changes the location
of the symbols.
 A transposition cipher reorders symbols.
 A symbol in the first position may appear in tenth position of the cyphertext.
 Three types
 Keyless Transposition Ciphers
 Keyed Transposition Ciphers
 Combining Two Approaches
1. Keyless Transposition Ciphers
 Simple transposition ciphers, which were used in the past, are keyless.
I. 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” by sending first row followed by second row.
 Bob receives the cypher text and divides it into half.
 First half forms first row and second half second row.
 Bob reads the result in zig zag.
 Disadvantage
 Cryptanalysis of cyphertext would be very easy.
Keyless Transposition Ciphers
II. 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 characters column by

column.
 Bob writes the received message column by column and read row by row as the plaintext.
 Disadvatantage
 Eve can easily decipher the message if she knows the no of columns.
Example
 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 (08, 12). In each section, the difference between the two adjacent numbers is
4.
2. 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

Bob divides the cyphertext into 5-character groups and using the key in reverse order, finds the plaintext.
3. Combining Two Approaches

Encryption/decryption keys in transpositional ciphers

Key inversion in a transposition cipher
Using Matrices
We can use matrices to show the encryption/decryption process for a transposition cipher.

Figure shows the encryption process. Multiplying the 4 × 5 plaintext matrix by the 5 × 5
encryption key gives the 4 × 5 ciphertext matrix.
Double Transposition Ciphers
• The transposition cipher can be made significantly more secure by performing more than one stage
of transposition.
• The result is a more complex permutation that is not easily reconstructed.
Vernam Cipher
 The Verna m Cipher is based on the principle that each plaintext character from a message
is 'mixed' with one character from a key stream.
 If a truly random key stream is used, the result will be a truly ' random ' ciphertext which
bears no relation to the original plaintext.
 In that case the cipher is similar to the unbreakable One -Time Pad (OTP).
 As it was generally used with tele printers and 5-level punched tape, the system is also
known as One-Time Tape or OTT.
8. Hill Cipher

 The Hill cipher was developed by Lester Hill .

 To encrypt a message, each block of n letters is multiplied by an invertible
n × n matrix, against modulus 26. [P=KC mod 26]
 To decrypt the message, each block is multiplied by the inverse of the matrix used for
encryption.[C= K-1P mod 26
 The key matrix in the Hill cipher needs to have a multiplicative inverse.
Example
I. The plaintext “code is ready” can make a 3 × 4 matrix when adding extra bogus character “z” to the
last block and removing the spaces. The ciphertext is “OHKNIHGKLISS”.
III. STREAM AND BLOCK CIPHERS

 The literature divides the symmetric ciphers into two broad categories: stream ciphers and
block ciphers.
 Although the definitions are normally applied to modern ciphers, this categorization also
applies to traditional ciphers.

1. Stream Ciphers
1. Block Ciphers
2. Combination
1.Stream Ciphers
 the plaintext is processed one bit at a time i.e. one bit of plaintext is taken, and a series of
operations is performed on it to generate one bit of ciphertext.
 Technically, stream ciphers are block ciphers with a block size of one bit.
Continued..
 Additive ciphers can be categorized as stream ciphers in which the key stream is the repeated
value of the key. In other words, the key stream is considered as a predetermined stream of keys
or K = (k, k, …, k). In this cipher, however, each character in the ciphertext depends only on the
corresponding character in the plaintext, because the key stream is generated independently
 The monoalphabetic substitution ciphers discussed in this chapter are also stream ciphers.
However, each value of the key stream in this case is the mapping of the current plaintext
character to the corresponding ciphertext character in the mapping table.
 Vigenere ciphers are also stream ciphers according to the definition. In this case, the key stream
is a repetition of m values, where m is the size of the keyword. In other words,
2. Block Ciphers
 In this scheme, the plain binary text is processed in blocks (groups) of bits at a time; i.e. a
block of plaintext bits is selected, a series of operations is performed on this block to
generate a block of ciphertext bits.
 The number of bits in a block is fixed.
 For example, the schemes DES and AES have block sizes of 64 and 128, respectively.I
Examples
 Playfair ciphers are block ciphers. The size of the block is m = 2. Two characters are
encrypted together.
 Hill ciphers are block ciphers. A block of plaintext, of size 2 or more is encrypted together
using a single key (a matrix). In these ciphers, the value of each character in the ciphertext
depends on all the values of the characters in the plaintext. Although the key is made of m
× m values, it is considered as a single key.
 Digital Encryption Standard (DES), Triple DES, Advanced Encryption Standard (AES),
Twofish, Serpent etc. are also examples of block cypher.
Padding in Block Cipher
 Block ciphers process blocks of fixed sizes (say 64 bits).
 The length of plaintexts is mostly not a multiple of the block size.
 For example, a 150-bit plaintext provides two blocks of 64 bits each with third block of
balance 22 bits.
 The last block of bits needs to be padded up with redundant information so that the length
of the final block equal to block size of the scheme.
 In our example, the remaining 22 bits need to have additional 42 redundant bits added to
provide a complete block.
 The process of adding bits to the last block to make fixed size block is referred to
as padding.
Stream Cipher vs Block Cipher

S.NO Block Cipher Stream Cipher

Block Cipher Converts the plain text into Stream Cipher Converts the plain text into
1. cipher text by taking plain text’s block at a cipher text by taking 1 byte of plain text at
time. a time.

Block cipher uses either 64 bits or more than

2. While stream cipher uses 8 bits.
64 bits.

3. The complexity of block cipher is simple. While stream cipher is more complex.

Block cipher Uses confusion as well as

4. While stream cipher uses only confusion.
diffusion.

While in stream cipher, reverse encrypted

5. In block cipher, reverse encrypted text is hard.
text is easy.

Block cipher is slow as compared to stream While stream cipher is fast in comparison
6
cipher. to block cipher.

Example: Additive cipher, monoalphabetic

7. Example: Playfair cipher, hill cipher, etc.
cipher, etc.
3. Combination
 In practice, blocks of plaintext are encrypted individually, but they use a stream of keys to
encrypt the whole message block by block.
 In other words, the cipher is a block cipher when looking at the individual blocks, but it is
a stream cipher when looking at the whole message considering each block as a single
unit.
Feistel cipher
 In cryptography, a Feistel cipher is a symmetric structure used in the construction of block
ciphers.
 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 number of rounds used in a Feistel Cipher depends on desired security from the system
Encryption Process

 The encryption process uses the Feistel structure consisting multiple rounds of processing of the plaintext,
each round consisting of a “substitution” step followed by a permutation step.
 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.
 In real implementation of the Feistel Cipher, such as DES, instead of using the whole encryption key during
each round, a round-dependent key (a subkey) is derived from the encryption key. This means that each
round uses a different key, although all these subkeys are related to the original key.
 The permutation step at the end of each round swaps the modified L and unmodified R. Therefore, the L for
the next round would be R of the current round. And R for the next round be the output L of the current
round.
 Above substitution and permutation steps form a ‘round’. The number of rounds are specified by the
algorithm design.
 Once the last round is completed then the two sub blocks, ‘R’ and ‘L’ are concatenated in this order to form
the ciphertext block.
Decryption Process

 Instead of starting with a block of plaintext, the ciphertext block is fed into the start of the
Feistel structure and then the process thereafter is exactly the same as described in the
given illustration.
 In the case of decryption, the only difference is that the subkeys used in encryption are
used in the reverse order.
 The final swapping of ‘L’ and ‘R’ in last step of the Feistel Cipher is essential. If these are
not swapped then the resulting ciphertext could not be decrypted using the same algorithm.
Encryption n Decryption
Data Encryption Standard
(DES)
Module II-Objectives

❏ To review a short history of DES

❏ To define the basic structure of DES

❏ To describe the details of building elements of DES

❏ To describe the round keys generation process

❏ To analyze DES
INTRODUCTION
 The Data Encryption Standard (DES) is a symmetric- key block cipher published by the National Institute of Standards
and Technology (NIST).

In 1973, NIST published a request of proposals for a national symmetric-key cryptosystem.

 A proposal from IBM, a modification of a project called Lucifer, was accepted as DES.

 DES was published in the Federal Register in March 1975 as a draft of the Federal Information Processing Standard (FIPS).

 DES is a symmetric key block cypher which encrypts data in the blocks of size 64 bits and includes 16 rounds and each
round is a Feistel round.

 DES is based on the two fundamental attributes of cryptography: substitution (also called as confusion) and transposition
(also called as diffusion).
Overview

Encryption and decryption with DES

DES STRUCTURE
 The encryption process is made of two permutations (P- boxes), which we call initial and
final permutations, and sixteen Feistel rounds.
Steps involved are:
1. Initial Permutations
2. 16 Feistel Rounds
3. Swapping/ left-right swap
4. Final Permutations/Reverse Initial Permutations
General structure of DES
Initial and Final Permutations
• The initial and final permutations are straight P-boxes that are inverses of each other.
• They have no cryptography significance in DES.
• For example, it says that the IP replaces the first bit of the original plain text block with the 58th bit of the
original plain text, the second bit with the 50th bit of the original plain text block and so on.
• This is nothing but jugglery of bit positions of the original plain text block. the same rule applies for all the
other bit positions which shows in the figure.

Initial and final permutation tables

Initial and final permutation steps in DES
Rounds
 DES uses 16 rounds. Each round of DES is a Feistel cipher. ( the structure consist of
identical rounds of processing)
DES Function
 The heart of DES is the DES function. The DES function applies a 48-bit key to the
rightmost 32 bits to produce a 32-bit output.
Expansion P-box
 Since RI−1 is a 32-bit input and KI is a 48-bit key, we first need to expand RI−1 to 48 bits.

 Although the relationship between the input and output can be defined mathematically, DES
uses following table to define this P-box.
Example

D O N T G I V E T H E M O N E Y

Y D O N T G T G I V E T E T H E M O M O N E Y D

So here 4 bits are converted in to 6 bits

Whitener (XOR)

After the expansion permutation, DES uses the XOR operation on the expanded right section
and the round key.
Note that both the right section and the key are 48-bits in length. Also note that the round key
is used only in this operation.
S-Boxes
 The S-boxes do the real mixing (confusion).
 DES uses 8 S- boxes, each with a 6-bit input and a 4-bit output.

 S-Box rule Calculation of F(R,K)

S-Boxes
The 48-bit input is divided into eight 6-bit chunks and each chunk is fed into a box
The result of each box is a 4-bit chunk
The substitution in each box follows a pre-determined rule based on a 4-row by 16-column
table
The combination of bits 1 and 6 of the input defines one of the four rows
The combination of bits 2 through 5 defines one of the sixteen columns
S-box Table
Key Generation
 The round key generator creates bit keys out of a 56-bit key.
 However, the cipher key is normally given as a 64-bit key, 8 extra bits are the parity bits
 Bits 8, 16, 24, 32,…64
 The 8 bits are dropped before the actual key-generation process)
 After the parity-bit drop, the key is divided into two 28-bit parts.
 Each part is shifted left one or two bits.
 In rounds 1,2,9 and 16, shifting is one bit.
 In the other rounds, shifting is two bits.
 The two parts are then combined to form a 56-bit part.
 The compression permutation changes the 56 bits to 48 bits, which are used as a key for a round.
Key Generation
Example
Cipher and Reverse Cipher

 Using mixers and swappers, we can create the cipher and reverse cipher, each having 16 rounds.
 Cipher is used at the encryption site and reverse cipher is used at decryption site.
 First approach
 To achieve this goal, one approach is to make the last round (round 16) different from the
others; it has only a mixer and no swapper
 Alternate approach
 We can make all 16 rounds the same by including one swapper to the 16th round and add
an extra swapper after that
 Two swappers cancel the effect of each other
DES cipher and reverse cipher for the first approach
DES ANALYSIS

 Critics have used a strong magnifier to analyze DES.

 Tests have been done to measure the strength of some desired properties in a block cipher.
 Topics discussed are:
 Properties
 Design Criteria
 DES Weaknesses
Properties

 Two desired properties of a block cipher are the avalanche effect and the completeness.
 Avalanche effect- A small change in plaintext should create a significant change in cyphertext.
 Example-To check the avalanche effect in DES, let us encrypt two plaintext blocks (with the same key)
that differ only in one bit and observe the differences in the number of bits in each round.

 Although the two plaintext block differ only in the rightmost bit, the ciphertext block differ in 29 bits.
Changing 1.5% of plaintext create a change of approximately 45% in cyphertext.
 Completeness effect means that each bit of the ciphertext needs to depend 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
Design Criteria
 S-Boxes-The design provides confusion and diffusion of bits from each round to
the next.
 P-Boxes- They provide diffusion of bits.
 Number of Rounds- DES uses sixteen rounds of Feistel ciphers. the ciphertext is
thoroughly a random function of plaintext and ciphertext
DES Weaknesses

 During the last few years critics have found some weaknesses in cypher design.
1. Weaknesses in Cipher Design
S-boxes
i)In S-box 4, the last three output can be derived in the same ways the first
output bit by complimenting some of the input bits.
ii) two specifically chosen inputs to an S-box array can create the same output.
iii) It is possible to obtain the same output in a single round by changing bits in only three
neighboring S-boxes
P-boxes
i) It is not clear why designers of DES used the initial and final permutations; these have no security
benefits.
ii) In the expansion permutation , the first and fourth bits of every 4-bit series are repeated.
DES Weaknesses

2.Weaknesses in Cipher Key

Key size
 Critics believe that the most serious weakness of DES is in its key size (56 bits).
 To do a brute-force attack on a given ciphertext block, the adversary needs to check 256 keys.
 DES with a cipher key of 56 bits is not safe enough to be used comfortably
Weak Keys
 Four out of 256 possible keys are called weak keys.
 A weak key is the one that, after parity drop operation, consists either of all 0s, all 1s, or half 0s and half 1s.
Semi-weak Keys
 There are six key pairs that are called semi-weak keys.
 A semi-weak key creates only two different round keys and each of them is repeated eight times.
Possible weak keys
 There are 48 keys that are called possible weak keys and creates only four different round keys .
 16 round keys are divided into 4 group and each group is made up of equal keys.
 Key clustering
 Two or more different keys can create the same cyphertext from the pliantext.
Double encryption and decryption with a
weak key
A pair of semi-weak keys in encryption and
decryption
Multiple DES
 The major criticism of DES regards its key length. Fortunately DES is
not a group. This means that we can use double or triple DES to
increase the key size.
 Two concepts:
 Double DES
 The output of 2-DES is :
 C = Ek2 (Ek1 (m)). To decrypt similarly, P = Dk1 (Dk2 (C)).
 The cipher 2-DES obtained by the repeated application of DES is called,
2 – DES = DES X DES.
This is called a product cipher obtained by the composition of two ciphers.
 Triple DES
Double DES (2DES)
Uses 2 different keys( 56 +56=112).

Cyphertext= E(k2, E(k1,P))

For decryption, first decrypted using k2, and the 64-bit middle text is decrypted using k1.

Plaintext= D(k1, D(k2,C))

Meet-in-the-Middle Attack

• This attack involves encryption from one end and decryption from the other end and matching
the result in the middle, hence the name.
• The goal of a meet-in-the-middle attack, is to use the intermediate values -- the values between
the encryption stages -- to solve for all used encryption keys; which for a double DES, is two.

• Using a known-plaintext attack called meet-in- the-middle attack proves that double DES
improves this vulnerability slightly (to 257 tests), but not tremendously (to 2112).
Meet-in-the-Middle Attack
 A meet-in-the-middle attack targets block cipher cryptographic functions.
 The intruder applies brute-force techniques to both the plaintext, which is ordinary text before
it is encrypted, and the ciphertext, or encrypted text that has been transformed from plaintext,
of a block cipher.
 The intruder then attempts to encrypt the plaintext according to various keys to achieve an
intermediate ciphertext, or text that has only been encrypted by one key.
 Simultaneously, the intruder attempts to decrypt the ciphertext according to various keys,
seeking a block of intermediate ciphertext that is the same as the one created by encrypting the
plaintext.
 If there is a match of intermediate ciphertext, it is highly probable that the key used to encrypt
the plaintext and the key used to decrypt the ciphertext are the two encryption keys used for
the block cipher.
Triple DES
2 or 3 keys are used
much stronger than double DES

Triple DES with two keys

Triple DES with Three Keys
 The possibility of known-plaintext attacks on triple DES with two keys has enticed some
applications to use triple DES with three keys.
 Triple DES with three keys is used by many applications such as PGP
Security of DES
 DES, as the first important block cipher, has gone through much scrutiny.
 Among the attempted attacks, three are of interest:
I. Brute-Force Attack
 We have discussed the weakness of short cipher key in DES.
 Combining this weakness with the key complement weakness, it is clear that DES can be broken using 255
encryptions.

II. Differential Cryptanalysis

 It has been revealed that the designers of DES already knew about this type of
attack and designed S-boxes and chose 16 as the number of rounds to make DES
specifically resistant to this type of attack.
III. Linear Cryptanalysis
 Linear cryptanalysis is newer than differential cryptanalysis.
 DES is more vulnerable to linear cryptanalysis than to differential cryptanalysis.
 S-boxes are not very resistant to linear cryptanalysis.
 It has been shown that DES can be broken using 243 pairs of known plaintexts.
 However, from the practical point of view, finding so many pairs is very unlikely.
Advanced Encryption Standard
(AES)
Module III- Objectives

❏ To review a short history of AES

❏ To define the basic structure of AES

❏ To define the transformations used by AES

❏ To define the key expansion process

❏ To discuss different implementations

INTRODUCTION
 The Advanced Encryption Standard (AES) is a symmetric-key block cipher published
by the National Institute of Standards and Technology (NIST) in December 2001.

AES is a non-Feistel cipher that encrypts and decrypts a data block of 128 bits.

AES has defined three versions, with 10, 12, and 14 rounds.

Each version uses a different cipher key size (128, 192, or 256), but the round keys are
always 128 bits.

No of keys generated by key expansion algorithm=(no of rounds + 1)

Data Units
 AES uses Five units of measurement to refer to data
 Bit, Byte(8 bits), Word( 4 bytes/32 bits), Block, State.
AES Structure
AES Encryption Process
General design of AES encryption cipher
Structure of Each Round

Structure of each round at the encryption site

TRANSFORMATIONS

 To provide security, AES uses four types of transformations:

Steps included are:
1. Substitution
2. Permutation
3. Mixing
4. Key Adding
Substitution

 AES, like DES, uses substitution.

 AES uses two invertible transformations: SubBytes transformation and InvSubBytes
transformation.
 SubBytes- The first transformation, SubBytes, is used at the encryption site.
 To substitute a byte, we interpret the byte as two hexadecimal digits.
 The SubBytes operation involves 16 independent byte- to-byte transformations.
 The result is in a matrix of four rows and four columns.
Substitution- S-boxes
Example
Permutation

Another transformation found in a round is shifting, which permutes the bytes.

 In the encryption, the transformation is called ShiftRows.
 In the decryption, the transformation is called InvShiftRows and the shifting is to the right.
 Number of shifts depends on the row of the state matrix.

ShiftRows transformation
Example
Mixing
 We need an interbyte transformation that changes the bits inside a byte, based on the bits inside
the neighboring bytes.
 We need to mix bytes to provide diffusion at the bit level.
 Take each word or column(4 X 1) from previous state matrix, multiply a constant matrix( 4 X 1)
and the output (4 X 1) which is 4 bytes, stored in output state matrix.

Mixing bytes using matrix multiplication

Mixing

 The MixColumns transformation operates at the column level; it transforms each column of the
state to a new column.

 The InvMixColumns transformation is basically the same as the MixColumns transformation.

 The MixColumns and InvMixColumns transformations are inverses of each other.
Key Adding
 AddRoundKey proceeds one column at a time.
 AddRoundKey performs XOR operation with a round key word and each state column matrix.
Key Expansions
 The AES key expansion algorithm takes as input a four-word (16-byte) key and produces a linear
array of 44 words (44*4=176 bytes), resulting in 11 round keys (176/11=16 bytes or 128 bits).
 The key is copied into the first four words of the expanded key. The remainder of the expanded key
is filled in four words at a time. Each added word w[i] depends on the immediately preceding word,
w[i - 1], and the word four positions back, w[i - 4].
 In three out of four cases, a simple XOR is used.
 ● Number of round keys = Nr + 1. Where Nr is the number of rounds (which is 10 in case of 128 bits
key size) So here the round keys = 11.
Key Expansions
AES ciphers-original design
ANALYSIS OF AES

 The three characteristics of AES are

 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.
END OF UNIT II
THANK U 