Question

i) Explain in brevity S DES.

ii) Discuss how keys are generated in IDEA.

iii)  Explain the working of DES.

Answer 1

1.

The process of encrypting a plan text into an encrypted message with the use of S-DES has been divided into multi-steps which may help you to understand it as easily as possible.

Points should be remembered.
It is a block cipher.
It has 8-bits block size of plain text or cipher text.
It uses 10-bits key size for encryption.
It is a symmetric cipher.
It has Two Rounds.
Let’s start the game!

Key Generation of S-DES or How to Generate the Key of Simplified DES

First and foremost, we need to generate a key. With the help of this key we will encrypt the message.
Now the interesting question is, how to generate the key, and where the key is to be used. Just follow the steps.

Step 1:

Just select a random key of 10-bits, which only should be shared between both parties which means sender and receiver.
As I selected below!

Select key:1010000010

Note:You can select any random number of 10-bits.

Step 2:

Put this key into P.10 Table and permute the bits.

P.10 Table:


Input   1       2       3       4       5       6       7       8       9       10
Output Should be        3       5       2       7       4       10      1       9       8       6

As I put key into P.10 Table.
Input   1       0       1       0       0       0       0       0       1       0
Output  1       0       0       0       0       0       1       1       0       0

Now the output will be:

Key: 1000001100

Step 3:

Divide the key into two halves, left half and right half;
{1 0 0 0 0} | {0 1 1 0 0}

Step 4:

Now apply the one bit Round shift on each half:
Before round shift: {10000} | {01100}
After round shift: {00001} | {11000}
The output will be:
{0 0 0 0 1} {1 1 0 0 0}

Step 5:

Now  once again combine both halve of the bits, right and left. Put them into the P8 table. What you get, that will be the K1 or First key.
Combine: 0 0 0 0 1 1 1 0 0 0

Permute into 8bit table:
 
P8-Table
Input   1       2       3       4       5       6       7       8       9       10
Combine-bits    0       0       0       0       1       1       1       0       0       0
Output Should be        6       3       7       4       8       5       10      9       
Output bits     1       0       1       0       0       1       0       0       

See the table the 1 and 2 number of bits are removed and other are permuted, as 6 in place of one, 9 in place of 8 and so on.

The output and K1 or key One will be:

K1=1 0 1 0 0 1 0 0

Step6:

As we know S-DES has two round and for that we also need two keys, one key we generate in the above steps (step 1 to step 5). Now we need to generate a second bit and after that we will move to encrypt the plain text or message.

It is simple to generate the second key. Simply, go in step 4 copy both halves, each one consists of 5 bits. But be careful on the taking of bits. Select those halves which are output of first round shift, don’t take the bits which are not used in the first round. In simple words, take the output of first round shift in above step 4.

Which are: {00001} | {11000}

Step 7:

Now just apply two round shift circulate on each half of the bits, which means to change the position of two bits of each halves.
left half: 00001
Right half: 11000

After the two rounds shift on each half out-put of each half will be.
Left half: 00100
Right half: 00011
Combine both together: As: 0 0 1 0 0 – 0 0 0 1 1

Step 8:

Now put the bits into 8-P Table, what you get, that will be your second key. Table is also given in step 5.

But here the combinations of bits are changed because of two left round shift from step 5. Check it in depth.
Combine bits: 0 0 1 0 0 0 0 0 1 1

2.

The Simplified International Data Encryption Algorithm (IDEA) is a symmetric key block cypher that:

uses a fixed-length plaintext of 16 bits and
encrypts them in 4 chunks of 4 bits each
to produce 16 bits ciphertext.
The length of the key used is 32 bits.
The key is also divided into 8 blocks of 4 bits each.
This algorithm involves a series of 4 identical complete rounds and 1 half-round. Each complete round involves a series of 14 steps that includes operations like:

Bitwise XOR
Addition modulo 

(2^4)
Multiplication modulo 

(2^4)+1
After 4 complete rounds, the final “half-round” consists of only first 4 out of the 14 steps previously used in the full-rounds. To perform these rounds, each binary notation must be converted to its equivalent decimal notation, perform the operation and the result obtained should be converted back to the binary representation for the final result of that particular step.

Key Schedule: 6 subkeys of 4 bits out of the 8 subkeys are used in each complete round, while 4 are used in the half-round. So, 4.5 rounds require 28 subkeys. The given key, ‘K’, directly gives the first 8 subkeys. By rotating the main key left by 6 bits between each group of 8, further groups of 8 subkeys are created, implying less than one rotation per round for the key (3 rotations).






K1      K2      K3      K4      K5      K6
Round 1 1101    1100    0110    1111    0011    1111
Round 2 0101    1001*   0001    1011    1100    1111
Round 3 1101    0110    0111    0111*   1111    0011
Round 4 1111    0101    1001    1101    1100    0110*
Round 4.5       1111    1101    0110    0111            
* denotes a shift of bits

Notations used in the 14 steps:

Symbol  Operation
*       Multiplication modulo 

(2^4)+1
+       Addition modulo 

(2^4)
^       Bitwise XOR
The 16-bit plaintext can be represented as X1 || X2 || X3 || X4, each of size 4 bits. The 32-bit key is broken into 8 subkeys denoted as K1 || K2 || K3 || K4 || K5 || K6 || K7 || K8, again of size 4 bits each. Each round of 14 steps uses the three algebraic operation-Addition modulo (2^4), Multiplication modulo (2^4)+1 and Bitwise XOR. The steps involved are as follows:


X1 * K1
X2 + K2
X3 + K3
X4 * K4
Step 1 ^ Step 3
Step 2 ^ Step 4
Step 5 * K5
Step 6 + Step 7
Step 8 * K6
Step 7 + Step 9
Step 1 ^ Step 9
Step 3 ^ Step 9
Step 2 ^ Step 10
Step 4 ^ Step 10
The input to the next round is Step 11 || Step 13 || Step 12 || Step 14, which becomes X1 || X2 || X3 || X4. This swap between 12 and 13 takes place after each complete round, except the last complete round (4th round), where the input to the final half round is Step 11 || Step 12 || Step 13 || Step 14.

After last complete round, the half-round is as follows:

X1 * K1
X2 + K2
X3 + K3
X4 * K4
The final output is obtained by concatenating the blocks.

Example:

Key: 1101 1100 0110 1111 0011 1111 0101 1001 
Plaintext: 1001 1100 1010 1100
Ciphertext: 1011 1011 0100 1011
Explanation:
The explanantion is only for 1st complete round (remaining can be implemented similarly) and the last half round.

Round 1:
From the plaintext: X1 – 1001, X2 – 1100, X3 – 1010, X4 – 1100
From the table above: K1 – 1101, K2 – 1100, K3 – 0110, K4 – 1111, K5 – 0011, K6 – 1111
(1001(9) * 1101(13))(mod 17) = 1111(15)
(1100(12) + 1100(12))(mod 16) = 1000(8)
(1010(10) + 0110(6))(mod 16) = 0000(0)
(1100(12) * 1111(15))(mod 17) = 1010(10)
(1111(15) ^ 0000(0)) = 1111(15)
(1000(8) ^ 1010(10)) = 0010(2)
(1111(15) * 0011(3))(mod 17) = 1011(11)
(0010(2) + 1011(11))(mod 16) = 1101(13)
(1101(13) * 1111(15))(mod 17) = 1000(8)
(1011(11) + 1000(8))(mod 16) = 0011(3)
(1000(8) ^ 1111(15)) = 0111(7)
(1000(8) ^ 0000(0)) = 1000(8)
(0011(3) ^ 1000(8)) = 1011(11)
(0011(3) ^ 1010(10)) = 1001(9)
Round 1 Output: 0111 1011 1000 1001 (Step 12 and Step 13 results are interchanged)
Round 2:
From Round 1 output: X1 – 0111, X2 – 1011, X3 – 1000, X4 – 1001
From the table above: K1 – 0101, K2 – 1001, K3 – 0001, K4 – 1011, K5 – 1100, K6 – 1111
Round 2 Output: 0110 0110 1110 1100
Round 3:
From Round 2 Output: X1 – 0110, X2 – 0110, X3 – 1110, X4 – 1100
From the table above: K1 – 1101, K2 – 0110, K3 – 0111, K4 – 0111, K5 – 1111, K6 – 0011
Round 3 Output: 0100 1110 1011 0010
Round 4:
From Round 3 Output: X1 – 0100, X2 – 1110, X3 – 1011, X4 – 0010
From the table above: K1 – 1111, K2 – 0101, K3 – 1001, K4 – 1101, K5 – 1100, K6 – 0110
Round 4 Output: 0011 1110 1110 0100 (Step 12 and Step 13 results are not interchanged)
Round 4.5:
From Round 4 Output: X1 – 0011, X2 – 1110, X3 – 1110, X4 – 0100
From the table above: K1 – 1111, K2 – 1101, K3 – 0110, K4 – 0111
(0011(3) * 1111(15))(mod 17) = 1011(11)
(1110(14) + 1101(13))(mod 16) = 1011(11)
(1110(14) + 0110(6))(mod 16) = 0100(4)
(0100(4) * 0111(7))(mod 17) = 1011(11) 
Final Ciphertext is 1011 1011 0100 1011.

3.

1.It is the most widely used algorithm for encryption and it is known as data encryption algorithm. (DEA)

2.In DES, data are encrypted in 64 blocks bits using a 56 bit key.

3.The algorithm transforms the 64 bit input in a series of steps into a 64 bit iutput using 56 bit key.

4.The same steps are used to reverse encryption using the same key.

5.The overall scheme of DES encryption is illustrated led into te adjoining figure.

Figure 4.7 Overall Scheme of DES algorithm
Figure 4.7 Overall Scheme of DES algorithm
6.There are 2 inputs to the encryption function, the plain text of 64 bits ( to be encrypted)

7.The key of 64 bits (actually 56 bits + 8 parity bits)

8.The processing of plaintext (LHS) of above figure proceeds in three phases.

9.First the 64 bit plaintext passes through an initial permutation that rearranges the bits to produce permitted output.

10.Output of last round consists of 64 bits that are a function of input plain text and key.

11.The left and right halves of input are swapped to produce pre-output.

12.Finally the pre output is passed through inverse permutation (initially used) to produce 64 bit cipher text.

13.The R.H.S of figure shows the way in which 56 bit key is used.

14.Then for each round, a subkey Ri is produced by combination of left circular shift and permutation.

15.The permutation function is same for each round but a different subkey is produced because of repeated shift of key bits.

Single Round of DES algorithm
The following figure shows the internal structure of a single round.
The left and right halves of each 64 bit intermediate value are treated as separate 32 bit quantities labeled left (L) and Right (R)
Figure 4.8 Single Round of DES algorithm
Figure 4.8 Single Round of DES algorithm
The overall processing of each channel summarized as:

Li=Ri−1Ri=Li−1XORF(Ri−1,ki)