S-DES algorithm

 The S-DES encryption algorithm takes

 an 8-bit block of plaintext (e.g., 10111101)
 10-bit key as input and
 produces an 8-bit block of ciphertext as output.
 The S-DES decryption algorithm takes
 an 8-bit block of ciphertext and
 the same 10-bit key used
 produce the original 8-bit block of plaintext.
 Simplified DES
Encryption 10-Bit key Decryption

8-bit Plaintext P 10 8-bit Plaintext

Shift
IP IP-1

K1 P8 K1
fk fk

Shift
SW SW

K2 P8 K2
fk fk

IP-1 IP

8-bit Ciphertext 8-bit Ciphertext

S-DES encryption
The encryption algorithm involves five functions:
1. an initial permutation (IP);
2. a complex function labeled f k, which involves both
permutation and substitution operations and
depends on a key input;
3. a simple permutation function that switches (SW)
the two halves of the data;
4. The function f k again; and
5. a permutation function that is the inverse of the
initial permutation (IP-1).
The encryption algorithm as a composition of functions

Decryption is essentially the reverse of encryption

 Simplified DES - Encryption

➢ Two permutation functions (initial - IP, and final IP-1), where

IP-1 is the inverse of IP; that is IP-1(IP(X)) = X.

➢ Two permutation/substitution functions f k each using one sub-key,

on the left (L) and right (R) data elements. That is:

f k(L,R) = (L  F(R, SK), R)

where SK is a sub-key and  is the bit-by-bit Exclusive OR.

➢ One switch function SW that interchanges the left and right 4 bits
so the second instance of f k operates on a different set of bits.
Simplified DES - Initial & Final Permutation
IP

IP
2 6 3 1 4 8 5 7

Input = 01001101
Output = 11000110

IP-1

IP-1
4 1 3 5 7 2 8 6

Input = 11000110
Output = 01001101

Result is IP-1(IP(X)) = X
Simplified DES - Function f k

Assume output of the IP stage is = 10111101

Then L, R = 1011, 1101

And fk(L,R) = (L  F(R, SK), R)

So fk(1011, 1101) = (1011  F(R, SK), 1101)

Now assume F(R, SK) = F(1101, SK) for some sub-key = 1110 (this
value will change depending on the sub-key).

Then: fk(1011, 1101) = (1011  1110, 1101) = 0101, 1101

Next we need to describe the complex function F(R,SK).

Simplified DES - Function F(R,SK)
IP
4 bits

Expand/Permute
8 bits
 K1
4 bits 4 bits

S0 S1
4 bits F(R,SK)
2 bits 2 bits

4 bits
P4
4 bits

4 bits
SW
Simplified DES - Function Parts of F(R,SK)
Expansion/Permutation (4 bits n1, n2, n3, n4) to 8 bits

E/P
4 1 2 3 2 3 4 1

Arrange these bits as follows:

n4 | n1 , n2 | n3 (left half of expansion/permutation)

n2 | n3 , n4 | n1 (right half)

Compute: n4  k11 | n1  k12 , n2  k13 | n3  k14

n2  k15 | n3  k16 , n4  k17 | n1  k18
Simplified DES - Function Parts of F(R,SK)
Rename these 8 bits:
Row 1 p0,0 | p0,1 p0,2 | p0,3
Row 2 p1,0 | p1,1 p1,2 | p1,3

The first 4 bits, row 1 are input to the s-box S0, 2nd row to S-box S1
to produce a 2-bit output for each input bit as follows;

0 1 2 3 0 1 2 3
0 1 0 3 2 0 0 1 2 3
1 3 2 1 0 1 2 0 1 3
S0 2 0 2 1 3 S1 2 3 0 1 0
3 3 1 3 2 3 2 1 0 3

For example, S0, p0,0 = 01; S1, p1,1 = 00

 Simplified DES - Function Parts of F(R,SK)
P4 Permutation: 2 bit input from S0, 2 bits from S1

P4
2 4 3 1

P4 output = output of fk

Switch function: interchanges the left and right halves so the second
instance of fk using the second key operates on different data.

The second instance of fk operates the same as described above

using the k2 sub-key and the switched input.

Decryption uses all the same functions run backwards.

Simplified DES Encryption Detail
 Simplified DES - Key Generation
10 bits
Permutation
P10
5 bits 5 bits Split Key, Circular Shift
LS-1 LS-1
5 bits
5 bits

P8 Permutation - K1 output
K1
8 bits
Split Key, Circular Shift
LS-2 LS-2
5 bits 5 bits
Permutation, K2 output
P8
K2
8 bits
S-DES Key Generation
 S-DES depends on the use of a 10-bit key shared
between sender and receiver.
 Two 8-bit subkeys are produced for use in particular
stages of the encryption and decryption algorithm.
Simplified DES - Key Generation

P10 Permutation:
Split the permuted key into 2 five-bit halves and circular left shift 1
Input = 10000 01100 Output = 00001 11000

P8 Permutation - selects and permutes 8 of the 10 bits

P8
6 3 7 4 8 5 10 9

Result is Sub-key K1 = 10100100

Simplified DES - Key Generation

To get sub-key K2:

Take output of original circular left shift 1 and shift an additional 2

Input = 00001 11000 Output = 00100 00011

Apply P8 to this value to produce K2

K2 = 01000011

This completes the generation of K1 and K2

 Simplified DES Key Generation
1010000010 10 bit Key 10 bit Key

35274101986 P10
5 5 10000 | 01100 P10 5 5

00001 11000 LS-1 LS-1

5 5 5 5
637485109 P8
K1 8 K1 8

10100100
00100 00011 LS-2 LS-2

5 5 5 5
637485109 P8

8 8
K2 01000011 K2
Simplified DES
8 Plaintext
4 4 IP
4
4
E/P E/P
8 8
8 K2 8 K1

4 4 4 4
S0 S1 S0 S1
2 2 2 2
P4 P4
4 4

4 4
IP-1 SW
8 Ciphertext
 Simplified
0123
DES
0 1032 8 Plaintext
12345678
1 3210 26314857 IP
S0= 11110011 PT 4
2 0213 4
1011 | 1101 IP 41232341 E/P
3 3132 8
11101011 E/P
8 K1
0123 10100100 K1 4 4
0 0123
01001111 Xor S0 S1
1 2013 2 2
S1= 11 S0 11 S1
2 3010 2431 P4
1111 P4 4
3 2103
1011 L
0100 Xor 4
SW

1101 0100
 Simplified
0123
DES 1101 0100
0 1032
1 3210 4 4
S0=
2 0213
00101000 E/P 41232341 E/P
3 3132 8
01000011 K2 8 K2
0123
01101011 Xor 4 4
0 0123
10 S0 01 S1 S0 S1
1 2013 2 2
S1= 0101 P4
2 3010 2431 P4
1101 L 4
3 2103
1000 Xor
10000100 +RS 4
IP-1 41357286
8 Ciphertext
01000001