DATA ENCRYPTION
STANDARD ALGORITHM
DES works by using the same key to
scramble and unscramble a message, so both the sender and the collector must
know and utilize the same private key. Once the go-to, symmetric-key
calculation for the encryption of electronic information, DES has been
superseded by the more secure Advanced Encryption Standard (AES) calculation.
Initially planned by researchers at
IBM in the mid 1970s, DES was approved by the U.S. government as an official
Federal Information Processing Standard (FIPS) in 1977 for the encryption of
business and touchy yet unclassified government PC information. It was the
principal encryption calculation affirmed by the U.S. government for open
exposure.
In this project our main focus is on
DES algorithm, for this project DES algorithm is used.
DES (Data Encryption
Standard) algorithm is a 16-round Feistel cipher with block size of 64 bits.
The figure below
sumarises this algorithm to its best. Plain text goes through initial
permutation process and round functions and at last final permutation is
carried on which results in giving cipher text as the desired output.
 |
| fig : ENCRYPTION |
DES is
a block cipher--meaning it
operates on plaintext blocks of a given size (64-bits) and returns cipher text
. Thus DES results in a permutation among
"2 to the 64th power”. Each block of 64 bits is divided into two blocks of
32 bits each, a left half block L and a right half R.
DES
works on the 64-bit blocks using key sizes of 56- bits. The keys are
actually stored as being 64 bits long, but every 8th bit in the key is ignored.
Let M
be the plain text entered by the user. Then following step will be executed to
get desired output:
 |
| fig : DES ALGORITHM |
Step 1: Create 16 subkeys, 48-bits long.
The 64-bit key is permuted using PC-1. As the first in
the table is "57", this means that the 57th bit of the initial key K becomes
the 1st bit of the permuted key K1. The 49th bit of the
K becomes the 2nd bit of the K1. The 4th bit of the original key is the
last bit of the K1.
PC-1
57 49
41 33 25
17 9
1 58
50 42 34
26 18
10 2
59 51 43
35 27
19 11
3 60 52
44 36
63 55
47 39 31
23 15
7 62
54 46 38
30 22
14 6
61 53 45
37 29
21 13
5 28 20
12 4
Next, key is devided into left and
right halves, C0 and D0,
where each half has 28 bits.
Once C0 and D0 defined, now we make sixteen blocks Cn
and Dn, 1<=n<=16. Every pair of pieces Cn and Dn is framed from the past
pair Cn-1 and Dn-1, separately, for n = 1, 2, ..., 16, utilizing the table of
"left moves" of the past square. To do a left move, move every piece
one place to left.
Iteration Number of
Number Left Shifts
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
In all cases, by one left move is
implied a turn of the bits one spot to left, so that after one left shift the
bits in the 28 positions are the bits that were already in positions 2, 3,...,
28, 1.
We now shape the keys
Kn, for 1<=n<=16, by applying the permutation table to each of the
connected sets Cn Dn. Every pair has 56 bits, however PC-2 just uses 48 of
these.
PC-2
14 17 11 24 1 5
3 28 15 6 21 10
23 19 12 4 26 8
16 7 27 20 13 2
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Hence,1st of Kn is the
14th of CnDn, the 2nd be the 17th, finishing with the 48th of Kn being the 32th
of CnDn.
Step 2: Encode each 64-bit piece of information.
There is an initial
permutation IP of the 64 bits of the message information M. This rearrange the
bits as per the table, where the passages in the table demonstrate the new game
plan of the bits from their previous order. The 58th piece of M turns into the
primary piece of IP. The 50th piece of M turns into the second piece of IP. The
seventh piece of M is the last piece of IP.
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7
Next partition the
permuted block IP into a left half L0 of 32 bits, and a right half R0 of 32
bits.
We now continue through
16 cycles, for 1<=n<=16, utilizing a function f which works on two blocks
- an information block of 32 bits and a key Kn of 48 bits- - to create a block
of 32 bits. Let + indicate XOR expansion.
Ln = Rn-1
Rn = Ln-1 + f(Rn-1,Kn)
This results in a last
block, for n = 16, of L16 R16. That is, in every cycle, we take the right 32
bits of the past result and make them the left 32 bits of the present step. For
the right 32 bits in the present step, we XOR the left 32 bits of the past step
with the calculation f .
Here ‘f’ is known as
round function.
To calculate f, we first
extend every block Rn-1 from 32 bits to 48 bits. This is done by utilizing a
choice table that repeats a portion of the bits in Rn-1 . We'll call the
utilization of this determination table the function E. In this manner E(Rn-1)
has a 32 bit input, and a 48 bit output.
let E be such that the
48 bits of its output, composed as 8 pieces of 6 bits each, are acquired by
selecting the bits in its inputs all together as indicated by the accompanying
table:
E BIT-SELECTION TABLE
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 1
Therefore the initial
three bits of E(Rn-1) are the bits in positions 32, 1 and 2 of Rn-1 while the
last 2 bits of E(Rn-1) are the bits in positions 32 and 1.
Next in the f calculation, XOR the output E(Rn-1)
with the key Kn:
Kn + E(Rn-1).
as far now we have
extended Rn-1 from 32 bits to 48 bits, utilizing the choice table, and XORed
the outcome with the key Kn . We now have 48 bits, or 8 gatherings of 6 bits.
We utilize these groups as locations in tables called "S
boxes"(substitution boxes). Every gathering of six bits will give us a
location in an alternate S box. Situated at that location will be a 4 bit
number. This 4 bit number will supplant the first 6 bits. The net result is
that the eight gatherings of 6 bits are changed into eight gatherings of 4 bits
(the 4-bit yields from the S boxes) for 32 bits absolute.
Compose the past result,
which is 48 bits, in the structure:
Kn + E(Rn-1)
=B1B2B3B4B5B6B7B8,
where every Bi is a
gathering of six bits. We now calculate
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
where Si(Bi) refers to
the output of the i-th S box.
To repeat, each of the
functions S1, S2,..., S8, takes a 6-bit obstruct as input and give a 4-bit
block as output. The table to decide S1 is appeared and clarified beneath:
S1
Column Number
Row
No. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7
1 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8
2 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
3 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
Here s1 is the function
and B is the block of 6 bits. then S1(B) is:
The
first and last bits of B show in base 2 a number in the decimal
range 0 to 3 (or binary 00 to 11). Let that number be a. The middle 4 bits of B represent in base 2 a number in the
decimal range 0 to 15 (binary 0000 to 1111). Let that number be c. Look up in the table
the number in the a-th
row and c-th
column. It is a number in the range 0 to 15 and is uniquely represented by a 4
bit block. That block is the output S1(B) of S1 for the input B. For example, for
input block B = 011011 the first bit is
"0" and the last bit "1" giving 01 as the row. This is row
1. The middle four bits are "1101". This is the binary equivalent of
decimal 13, so the column is column number 13. In row 1, column 13 appears 5.
This determines the output; 5 is binary 0101, so that the output is 0101. Hence S1(011011) =
0101.
The tables defining the functions S1,...,S8 are the following:
S1
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
S2
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
S3
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
S4
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
S5
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
S6
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
S7
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
S8
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
The last stage in the
computation of f is to do a change P of the S-box O/P to get the last
estimation of f:
f =
P(S1(B1)S2(B2)...S8(B8))
The permutation P is
characterized in the accompanying table. P yields a 32-bit O/P from a 32-bit
I/P by permuting the bits of the I/P block.
P
16 7 20 21
29 12 28 17
1 15 23 26
5 18 31 10
2 8 24 14
32 27 3 9
19 13 30 6
22 11 4 25
In the following round,
we will have L2 = R1, which is the square we simply figured, and after that we
should compute R2 =L1 + f(R1, K2), thus on for 16 rounds. Toward the end of the
sixteenth round we have the pieces L16 and R16. We then invert the order of the
two blocks into the 64-bit block.
R16L16
what's more, apply a
last stage IP-1 as characterized by the accompanying table:
IP-1
40 8 48 16 56 24 64 32
39 7 47 15 55 23 63 31
38 6 46 14 54 22 62 30
37 5 45 13 53 21 61 29
36 4 44 12 52 20 60 28
35 3 43 11 51 19 59 27
34 2 42 10 50 18 58 26
33 1 41 9 49 17 57 25
That is, the yield of
the calculation has bit 40 of the preoutput block as its first piece, bit 8 as
its second piece, and so on, until bit 25 of the preoutput square is the last
piece of the O/P.
