Lecture 3: Block Ciphers and The Data Encryption Standard Lecture Notes On "Computer and Network Security"
Lecture 3: Block Ciphers and The Data Encryption Standard Lecture Notes On "Computer and Network Security"
Lecture 3: Block Ciphers and The Data Encryption Standard Lecture Notes On "Computer and Network Security"
Standard
c
2019 Avinash Kak, Purdue University
Goals:
3.1.1 Size of the Encryption Key for the Ideal Block Cipher 6
2
Computer and Network Security by Avi Kak Lecture 3
• The mapping from the input bit blocks to the output bit blocks
can also be construed as a mapping from the integers correspond-
3
Computer and Network Security by Avi Kak Lecture 3
• The encryption key for the ideal block cipher is the codebook
itself, meaning the table that shows the relationship between the
input blocks and the output blocks.
4
Computer and Network Security by Avi Kak Lecture 3
b b1 b2 b
Plaintext bit block: 0 3
Figure 1: The ideal block cipher when the block size equals
4 bits. (This figure is from Lecture 3 of “Lecture Notes on Computer and Network Security” by
Avi Kak)
5
Computer and Network Security by Avi Kak Lecture 3
• That implies that the encryption key for the ideal block cipher
using 64-bit blocks will be of size 1021.
• The size of the encryption key would make the ideal block cipher
an impractical idea. Think of the logistical issues related to the
transmission, distribution, and storage of such large keys.
6
Computer and Network Security by Avi Kak Lecture 3
• Named after the IBM cryptographer Horst Feistel and first im-
plemented in the Lucifer cipher by Horst Feistel and Don Cop-
persmith.
• The input block to each round is divided into two halves that I
have denoted L and R for the left half and the right half.
7
Computer and Network Security by Avi Kak Lecture 3
Plaintext block
(Divide into two halves, L and R)
Round Keys
L R
K
Round1 1
F(K,R)
L R
K
2
Round
2 F(K,R)
L R
K
n
Round n
F(K,R)
Ciphertext block
8
Computer and Network Security by Avi Kak Lecture 3
• In each round, the right half of the block, R, goes through un-
changed. But the left half, L, goes through an operation that
depends on R and the encryption key. The operation carried out
on the left half L is referred to as the Feistel Function.
• Besides DES, there exist several block ciphers today — the most
popular of these being Blowfish, CAST-128, and KASUMI —
that are also based on the Feistel structure.
9
Computer and Network Security by Avi Kak Lecture 3
• Let LEi and REi denote the output half-blocks at the end of the
ith round of processing. The letter ’E’ denotes encryption.
LEi = REi−1
REi = LEi−1 ⊕ F (REi−1, Ki)
LE16 = RE15
RE16 = LE15 ⊕ F (RE15, K16)
11
Computer and Network Security by Avi Kak Lecture 3
• To prove the above claim, let LDi and RDi denote the left half
and the right half of the output of the ith round.
• That means that the output of the first decryption round con-
sists of LD1 and RD1. So we can denote the input to the first
decryption round by LD0 and RD0. The relationship between
the two halves that are input to the first decryption round and
what is output by the encryption algorithm is:
LD0 = RE16
RD0 = LE16
12
Computer and Network Security by Avi Kak Lecture 3
Encryption Decryption
LE L R RE LD = RE RD = LE
0 0 16 0 16 0
F(K,R)
Round1
F(K,R)
LE RE
1 1 K
2
LD = RE RD = LE
1 15 1
15
F(K,R)
Round
2 F(K,R)
LE RE K
15 15 16
LD = RE RD = LE
1 15 1 15
F(K,R)
Round 16
F(K,R)
LE RE
16 LD = RE RD = LE
16 0 16
0 16
13
Computer and Network Security by Avi Kak Lecture 3
• We can write the following equations for the output of the first
decryption round
LD1 = RD0
= LE16
= RE15
[A ⊕ B] ⊕ C = A ⊕ [B ⊕ C ]
A ⊕ A = 0
A ⊕ 0 = A
14
Computer and Network Security by Avi Kak Lecture 3
15
Computer and Network Security by Avi Kak Lecture 3
• DES uses a 56-bit encryption key. (The key size was apparently
dictated by the memory and processing constraints imposed by
a single-chip implementation of the algorithm for DES.) The key
itself is specified with 8 bytes, but one bit of each byte is used as
a parity check.
16
Computer and Network Security by Avi Kak Lecture 3
17
Computer and Network Security by Avi Kak Lecture 3
• The 32-bit right half of the 64-bit input data block is expanded
by into a 48-bit block. This is referred to as the expansion
permutation step, or the E-step.
Note that what gets prefixed to the first 4-bit block is the last bit
of the last 4-bit block. By the same token, what gets appended
to the last 4-bit block is the first bit of the first 4-bit block. The
18
Computer and Network Security by Avi Kak Lecture 3
reason for why we expand each 4-bit block into a 6-bit block in
the manner explained will become clear shortly.
• The 56-bit key is divided into two halves, each half shifted sep-
arately, and the combined 56-bit key permuted/contracted
to yield a 48-bit round key. How this is done will be explained
later.
• What comes out of the P-box is then XORed with the left half
of the 64-bit block that we started out with. The output of this
19
Computer and Network Security by Avi Kak Lecture 3
XORing operation gives us the right half block for the next round.
• The strategy used for creating the different round keys from the
main key is meant to introduce confusion into the encryption
process. Confusion in this context means that the relation-
ship between the encryption key and the ciphertext must be
as complex as possible. Another way of describing confusion
would be that each bit of the key must affect as many bits as
possible of the output ciphertext block.
20
Computer and Network Security by Avi Kak Lecture 3
LE i−1 RE i−1
32 bits 32 bits
The Feistel Function
F( RE i−1 , K i )
Expansion Permutation
48 bits
Round Key K
i
48 bits
32 bits
LE RE
i i
21
Computer and Network Security by Avi Kak Lecture 3
• Thus, the row lookup for each of the eight S-boxes becomes a
function of the input bits for the previous S-box and the next
22
Computer and Network Security by Avi Kak Lecture 3
48 bits
S1 S2 S3 S4 S5 S6 S7 S8
32 bits
23
Computer and Network Security by Avi Kak Lecture 3
S-box.
• In the design of the DES, the S-boxes were tuned to enhance the
resistance of DES to what is known as the differential cryptanal-
ysis attack, or, sometimes more briefly as differential attack. [As
will be explained in much greater detail (and also demonstrated) in Section 8.9 of Lecture 8, differential
cryptanalysis of block ciphers consists of presenting to the encryption algorithm pairs of plaintext bit
patterns with known differences between them and examining the differences between the correspond-
ing cyphertext outputs. The outputs are usually recorded at the input to the last round of the cipher.
Let’s represent one plaintext bit block by X = [X1 , X2 , ...., Xn ] where Xi denotes the ith bit in the
block, and let’s represent the corresponding output bit block by Y = [Y1 , Y2 , ..., Yn ]. By the difference
between two plaintext bit blocks X ′ and X ′′ we mean ∆X = X ′ ⊕ X ′′ . The difference between the
ferential. In an ideally randomizing block cipher, the probability of ∆Y being a particular value for a
given ∆X is 1/2n for an n-bit block cipher. What is interesting is that the probabilities of ∆Y taking
on different values for a given ∆X can be shown to be independent of the encryption key because of the
properties of the XOR operator, but these probabilities are strongly dependent on the S-box tables. By
feeding into a cipher several pairs of plaintext blocks with known ∆X and observing the corresponding
∆Y , it is possible to establish constraints on the round key bits encountered along the different paths
in the encryption processing chain. (By constraints I mean the following: Speaking hypothetically for
the purpose of illustrating a point and focusing on just one round of DES, suppose we can show that
the following condition can be expected to be obeyed with high probability: ∆Xi ⊕ ∆Yi ⊕ Ki = 0
for some bit Ki of the encryption key, then it must be the case that Ki = ∆X ⊕ ∆Y .) Note that
differential cryptanalysis is a chosen plaintext attack, meaning that the attacker will feed known
plaintext bit patterns into the cipher and analyze the corresponding outputs in order to figure out the
encryption key. In a theoretical analysis of an attack based on differential cryptanalysis, it was shown
by Eli Biham and Adi Shamir in 1990 that the DES’s encryption key could be figured out provided one
24
Computer and Network Security by Avi Kak Lecture 3
could feed known 247 plaintext blocks into the cipher. For a tutorial by Howard Heys on differential
25
Computer and Network Security by Avi Kak Lecture 3
• Shown on the next page are the eight S-boxes, S1 through S8,
each S-box being a 4×16 substitution table that is used to convert
6 incoming bits into 4 outgoing bits.
26
Computer and Network Security by Avi Kak Lecture 3
27
Computer and Network Security by Avi Kak Lecture 3
• The Python code shown below illustrates how you can use the
eight S-boxes for the substitutions you need for the right half of
the input in each round:
#!/usr/bin/env python
## illustrate_des_substitution.py
## Avi Kak
## January 21, 2017 (made Python3 compliant January 12, 2018)
## This is a demonstration of how you can carry out S-boxes based substitution
## in DES. The code shown implements the "Substitution with 8 S-boxes" step
## that you see inside the dotted Feistel function in Figure 4 of Lecture 3 notes.
## IMPORTANT: This demonstration code does NOT include XORing with the round
## key that must be carried out on the expanded right-half block
## before it is subject to the S-boxes based substitution step
## shown here.
expansion_permutation = [31, 0, 1, 2, 3, 4,
3, 4, 5, 6, 7, 8,
7, 8, 9, 10, 11, 12,
11, 12, 13, 14, 15, 16,
15, 16, 17, 18, 19, 20,
19, 20, 21, 22, 23, 24,
23, 24, 25, 26, 27, 28,
27, 28, 29, 30, 31, 0]
s_boxes[0] = [ [14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7],
[0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8],
[4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0],
[15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13] ]
s_boxes[1] = [ [15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10],
[3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5],
[0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15],
[13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9] ]
s_boxes[2] = [ [10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8],
[13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1],
[13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7],
[1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12] ]
s_boxes[3] = [ [7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15],
[13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9],
[10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4],
28
Computer and Network Security by Avi Kak Lecture 3
[3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14] ]
s_boxes[4] = [ [2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9],
[14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6],
[4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14],
[11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3] ]
s_boxes[5] = [ [12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11],
[10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8],
[9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6],
[4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13] ]
s_boxes[6] = [ [4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1],
[13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6],
[1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2],
[6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12] ]
s_boxes[7] = [ [13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7],
[1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2],
[7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8],
[2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11] ]
# For the purpose of this illustration, let’s just make up the right-half of a
# 64-bit DES bit block:
right_half_32bits = BitVector( intVal = 800000700, size = 32 )
# The following statement takes the 48 bits back down to 32 bits after carrying
# out S-box based substitutions:
output = substitute(right_half_with_expansion_permutation)
print(output)
#!/usr/bin/perl -w
## illustrate_des_substitution.pl
## Avi Kak
## January 15, 2018
## This is a demonstration of how you can carry out S-boxes based substitution
## in DES. The code shown implements the "Substitution with 8 S-boxes" step
## that you see inside the dotted Feistel function in Figure 4 of Lecture 3 notes.
## IMPORTANT: This demonstration code does NOT include XORing with the round
## key that must be carried out on the expanded right-half block
## before it is subject to the S-boxes based substitution step
## shown here.
use strict;
use Algorithm::BitVector 1.26;
my $expansion_permutation = [31, 0, 1, 2, 3, 4,
3, 4, 5, 6, 7, 8,
30
Computer and Network Security by Avi Kak Lecture 3
$s_boxes->{0} = [ [14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7],
[0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8],
[4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0],
[15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13] ];
$s_boxes->{1} = [ [15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10],
[3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5],
[0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15],
[13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9] ];
$s_boxes->{2} = [ [10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8],
[13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1],
[13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7],
[1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12] ];
$s_boxes->{3} = [ [7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15],
[13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9],
[10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4],
[3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14] ];
$s_boxes->{4} = [ [2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9],
[14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6],
[4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14],
[11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3] ];
$s_boxes->{5} = [ [12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11],
[10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8],
[9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6],
[4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13] ];
$s_boxes->{6} = [ [4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1],
[13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6],
[1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2],
[6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12] ];
$s_boxes->{7} = [ [13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7],
[1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2],
[7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8],
[2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11] ];
# For the purpose of this illustration, let’s just make up the right-half of a
# 64-bit DES bit block:
my $right_half_32bits = Algorithm::BitVector->new( intVal => 800000700, size => 32 );
31
Computer and Network Security by Avi Kak Lecture 3
# The following statement takes the 48 bits back down to 32 bits after carrying
# out S-box based substitutions:
my $output = substitute($right_half_with_expansion_permutation);
print "$output\n";
## This method implements the step "Substitution with 8 S-boxes" step you see inside
## Feistel Function dotted box in Figure 4 of Lecture 3 notes.
sub substitute {
my $expanded_half_block = shift;
my $output = Algorithm::BitVector->new( size => 32 );
my @segments = map $expanded_half_block->get_slice([$_*6..($_+1)*6]), 0..7;
foreach my $sindex (0..@segments-1) {
my $row = 2*int($segments[$sindex]->get_bit(0)) + int($segments[$sindex]->get_bit(-1));
my $column = int( $segments[$sindex]->get_slice([1..5]) );
$output->set_slice([$sindex*4..$sindex*4+4],
Algorithm::BitVector->new(intVal => $s_boxes->{$sindex}->[$row][$column], size => 4));
}
return $output;
}
• You can download both the Python and the Perl scripts shown
in this section from the lecture notes website.
32
Computer and Network Security by Avi Kak Lecture 3
P-Box Permutation
15 6 19 20 28 11 27 16
0 14 22 25 4 17 30 9
1 7 23 13 31 26 2 8
18 12 29 5 21 10 3 24
• This permutation ‘table’ says that the 0th output bit will be the
15th bit of the input, the 1st output bit the 6th bit of the input,
and so on, for all of the 32 bits of the output that are obtained
from the 32 bits of the input.
• Keep in mind the fact that, when using the BitVector module
in Python or the Algorithm::BitVector module in Perl, a permu-
tation such as the one shown above can be carried out with a
one-line command. For example, in Python, the code fragment
would look like:
sboxes_output = BitVector representation of the
output of the S-Boxes
right_half = sboxes_output.permute( pbox_permutation )
34
Computer and Network Security by Avi Kak Lecture 3
• For generating the round key, we join together the two halves and
apply a 56 bit to 48 bit contracting permutation (this is referred
to as Permutation Choice 2, as shown in Section 3.3.7) to the
joined bit pattern. The resulting 48 bits constitute our round
key.
35
Computer and Network Security by Avi Kak Lecture 3
prior to each round, is meant to ensure that each bit of the original
encryption key is used in roughly 14 of the 16 rounds.
• The two halves of the encryption key generated in each round are
fed as the two halves going into the next round.
• The table shown below tells us how many positions to use for
the left circular shift that is applied to the two key halves at the
beginning of each round:
36
Computer and Network Security by Avi Kak Lecture 3
37
Computer and Network Security by Avi Kak Lecture 3
Key Permutation 1
56 48 40 32 24 16 8
0 57 49 41 33 25 17
9 1 58 50 42 34 26
18 10 2 59 51 43 35
62 54 46 38 30 22 14
6 61 53 45 37 29 21
13 5 60 52 44 36 28
20 12 4 27 19 11 3
• The bit indexing is based on using the range 0-63 for addressing
the bit positions in an 8-byte bit pattern in which the last bit of
each byte is used as a parity bit. [Note that each row shown above has only
7 positions — the positions corresponding to the parity bit are NOT included above.
That is, you will NOT see the positions 7, 15, etc., listed in the permutations shown.
Nevertheless, the bit addressing spans the full 0-63 range.]
The permutations
shown above do not constitute a table, in the sense that the
rows and the columns do NOT carry any special and separate
meanings. The permutation order for the bits is given by reading
the entries shown from the upper left corner to the lower right
corner.
• This permutation tells us that the 0th bit of the output will be
38
Computer and Network Security by Avi Kak Lecture 3
the 56th bit of the input (in a 64 bit representation of the 56-bit
encryption key), the 1st bit of the output the 48th bit of the input,
and so on, until finally we have for the 55th bit of the output the
3rd bit of the input.
• The code snippet shown below illustrates how you can create the
56-bit key from the eight characters supplied by the user.
#!/usr/bin/env python
## get_encryption_key.py
## Avi Kak
## January 21, 2017
## This scripts asks the user to supply eight characters (exactly) for
## the encryption key needed for DES based encryption/decryption.
39
Computer and Network Security by Avi Kak Lecture 3
import sys
from BitVector import *
key_permutation_1 = [56,48,40,32,24,16,8,0,57,49,41,33,25,17,
9,1,58,50,42,34,26,18,10,2,59,51,43,35,
62,54,46,38,30,22,14,6,61,53,45,37,29,21,
13,5,60,52,44,36,28,20,12,4,27,19,11,3]
def get_encryption_key():
key = ""
while True:
if sys.version_info[0] == 3:
key = input("Enter a string of 8 characters for the key: ")
else:
key = raw_input("Enter a string of 8 characters for the key: ")
if len(key) != 8:
print("\nKey generation needs 8 characters exactly. Try again.\n")
continue
else:
break
key = BitVector(textstring = key)
key = key.permute(key_permutation_1)
return key
key = get_encryption_key()
print("Here is the 56-bit encryption key generated from your input:\n")
print(key)
• Shown below is a Perl script for doing the same thing — it il-
lustrates how you can create the 56-bit encryption key from the
eight characters supplied by a user.
#!/usr/bin/perl -w
## get_encryption_key.pl
## Avi Kak
## January 14, 2018
## This scripts asks the user to supply eight characters (exactly) for
## the encryption key needed for DES based encryption/decryption.
use strict;
use Algorithm::BitVector;
my $key_permutation_1 = [56,48,40,32,24,16,8,0,57,49,41,33,25,17,
40
Computer and Network Security by Avi Kak Lecture 3
9,1,58,50,42,34,26,18,10,2,59,51,43,35,
62,54,46,38,30,22,14,6,61,53,45,37,29,21,
13,5,60,52,44,36,28,20,12,4,27,19,11,3];
my $key = get_encryption_key();
print "Here is the 56-bit encryption key generated from your input:\n";
print "$key\n";
sub get_encryption_key {
my $key = "";
print "\nEnter a string of 8 characters for the key: ";
while ( $key = <STDIN> ) {
chomp $key;
if (length $key != 8) {
print "\nKey generation needs 8 characters exactly. Try again: ";
next;
} else {
last;
}
}
$key = Algorithm::BitVector->new( textstring => $key );
$key = $key->permute($key_permutation_1);
return $key
}
41
Computer and Network Security by Avi Kak Lecture 3
Key Permutation 2
13 16 10 23 0 4 2 27
14 5 20 9 22 18 11 3
25 7 15 6 26 19 12 1
40 51 30 36 46 54 29 39
50 44 32 47 43 48 38 55
33 52 45 41 49 35 28 31
42
Computer and Network Security by Avi Kak Lecture 3
• Since there are only six rows and there are 8 positions in each
row, the output will consist of 48 bits.
• The Python code shown below illustrates how you can generate
all 16 round keys using the BitVector module:
#!/usr/bin/env python
## generate_round_keys.py
## Avi Kak
## January 21, 2017
import sys
from BitVector import *
key_permutation_1 = [56,48,40,32,24,16,8,0,57,49,41,33,25,17,
9,1,58,50,42,34,26,18,10,2,59,51,43,35,
62,54,46,38,30,22,14,6,61,53,45,37,29,21,
13,5,60,52,44,36,28,20,12,4,27,19,11,3]
key_permutation_2 = [13,16,10,23,0,4,2,27,14,5,20,9,22,18,11,
3,25,7,15,6,26,19,12,1,40,51,30,36,46,
54,29,39,50,44,32,47,43,48,38,55,33,52,
45,41,49,35,28,31]
shifts_for_round_key_gen = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1]
def generate_round_keys(encryption_key):
round_keys = []
key = encryption_key.deep_copy()
for round_count in range(16):
[LKey, RKey] = key.divide_into_two()
shift = shifts_for_round_key_gen[round_count]
LKey << shift
RKey << shift
43
Computer and Network Security by Avi Kak Lecture 3
def get_encryption_key():
key = ""
while True:
if sys.version_info[0] == 3:
key = input("\nEnter a string of 8 characters for the key: ")
else:
key = raw_input("\nEnter a string of 8 characters for the key: ")
if len(key) != 8:
print("\nKey generation needs 8 characters exactly. Try again.\n")
continue
else:
break
key = BitVector(textstring = key)
key = key.permute(key_permutation_1)
return key
encryption_key = get_encryption_key()
round_keys = generate_round_keys(encryption_key)
print("\nHere are the 16 round keys:\n")
for round_key in round_keys:
print(round_key)
• And the Perl code shown below illustrates how you can generate
all 16 round keys using the Algorithm::BitVector module:
#!/usr/bin/perl -w
## get_encryption_key.pl
## Avi Kak
## January 14, 2018
## This scripts asks the user to supply eight characters (exactly) for
## the encryption key needed for DES based encryption/decryption.
## It subsequently generates the round keys for each of the 16 rounds
## of DES.
use strict;
use Algorithm::BitVector;
my $key_permutation_1 = [56,48,40,32,24,16,8,0,57,49,41,33,25,17,
9,1,58,50,42,34,26,18,10,2,59,51,43,35,
62,54,46,38,30,22,14,6,61,53,45,37,29,21,
44
Computer and Network Security by Avi Kak Lecture 3
13,5,60,52,44,36,28,20,12,4,27,19,11,3];
my $key_permutation_2 = [13,16,10,23,0,4,2,27,14,5,20,9,22,18,11,
3,25,7,15,6,26,19,12,1,40,51,30,36,46,
54,29,39,50,44,32,47,43,48,38,55,33,52,
45,41,49,35,28,31];
my $shifts_for_round_key_gen = [1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1];
my $encryption_key = get_encryption_key();
my @round_keys = generate_round_keys($encryption_key);
print "\nHere are the 16 round keys:\n";
foreach my $round_key (@round_keys) {
print "$round_key\n";
}
sub generate_round_keys {
my $encryption_key = shift;
my @round_keys = ();
my $key = $encryption_key->deep_copy();
foreach my $round_count (0..15) {
my ($LKey, $RKey) = $key->divide_into_two();
my $shift = $shifts_for_round_key_gen->[$round_count];
$LKey = $LKey << $shift;
$RKey = $RKey << $shift;
$key = $LKey + $RKey;
my $round_key = $key->permute($key_permutation_2);
push @round_keys, $round_key;
}
return @round_keys;
}
sub get_encryption_key {
my $key = "";
print "\nEnter a string of 8 characters for the key: ";
while ( $key = <STDIN> ) {
chomp $key;
if (length $key != 8) {
print "\nKey generation needs 8 characters exactly. Try again: ";
next;
} else {
last;
}
}
$key = Algorithm::BitVector->new( textstring => $key );
$key = $key->permute($key_permutation_1);
return $key
}
45
Computer and Network Security by Avi Kak Lecture 3
• The manner in which the round keys are generated from the
encryption key is also very effective as far as confusion is con-
cerned. It has been shown that if you change just one bit of
the encryption key, on the average that affects 35 bits of the
ciphertext.
46
Computer and Network Security by Avi Kak Lecture 3
• Assuming that, on the average, you’d need to try half the keys
in a brute-force attack, a machine able to process 1000 keys per
microsecond would need roughly 13 months to break the code.
However, a parallel-processing machine trying 1 million keys si-
multaneously would need only about 10 hours. (EFF took
three days on a specially architectured machine to
break the code.)
http://www.itl.nist.gov/fipspubs/fip46-2.htm
47
Computer and Network Security by Avi Kak Lecture 3
Let’s say that I write the encrypted output into a different file and
then examine this new file with the ‘hexdump -C’ command.
What will I see in the encrypted file?
48
Computer and Network Security by Avi Kak Lecture 3
9. If we have all the freedom in the world for choosing the Feistel
function F, how should we specify it?
11. DES encryption was broken in 1999. Why do you think that
happened?
12. Since DES was cracked, does that make this an unimportant
cipher?
50
Computer and Network Security by Avi Kak Lecture 3
51