This site Web

Cipher - DES Algorithm

Part:   1  2  3  4 

(Continued from previous part...)

Permuted Choice 2 - PC2:

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

Left shifts (number of bits to rotate) - r1, r2, ..., r16:

 r1  r2  r3  r4  r5  r6  r7  r8  r9 r10 r11 r12 r13 r14 r15 r16 
  1   1   2   2   2   2   2   2   1   2   2   2   2   2   2   1

DES Decryption Algorithm

The decryption algorithm of a block cipher should be identical to encryption algorithm step by step in reverse order. But for DES cipher, the encryption algorithm is so well designed, that the decryption algorithm is identical to the encryption algorithm step by step in the same order, only with the subkeys applied in the reverse order.

DES decryption algorithm:

Input: 
   CC: 64 bits of cipher text
   k16, k15, ..., k1: 16 round keys
   IP: Initial permutation
   FP: Final permutation
   f(): Round function
   
Output: 
   TT: 64 bits of clear text

Algorithm:
   CC' = IP(CC), applying initial permutation
   (LL0, RR0) = CC', dividing CC' into two 32-bit parts
   (LL1, RR1) = (RR0, LL0 ^ f(RR0, k16))
   (LL2, RR2) = (RR1, LL1 ^ f(RR1, k15))
   ......
   TT' = (RR16, LL16), swapping the two parts
   TT = FP(TT'), applying final permutation

Here is how to approve the decryption algorithm:

Let: 
   T: 64 bits of clear text
   C: 64 bits of cipher text encrypted from T
   CC: 64 bits of cipher text
   TT: 64 bits of clear text decrypted from CC

If: 
   CC = C
   
Then: 
   TT = T

Prove:
   CC' = IP(CC)               First step of decryption
      = IP(C)                 Assumption of CC = C
      = IP(FP(C'))            Last step of encryption
      = C'                    IP is the inverse permutation of FP

   (LL0, RR0) = CC'           Initializing step in decryption
      = C'                    CC' = C'
      = (R16, L16)            Swapping step in encryption
       
   (LL1, RR1) = (RR0, LL0 ^ f(RR0, k16))
                              First round of decryption
      = (L16, R16 ^ f(L16, k16))
                              Previous result
      = (R15, (L15 ^ f(R15,k16)) ^ f(R15, k16))
                              (L16, R16) = (R15, L15 ^ f(R15, k16))
      = (R15, L15)           ^ reverse itself
       
   ......   

   (LL16, RR16) = (R0, L0)
   
   TT' = (RR16, LL16)         Swapping in decryption
      = (L0, R0)              Previous result
      = T'                    Initializing step in encryption

   TT = FP(TT')               Last step in decryption
      = FP(T')                Previous result
      = FP(IP(T))             First step in encryption
      = T                     FP is the inverse permutation of IP

Conclusions:

• DES is a 64-bit block cipher.
• 16 round keys are derived from a single 64-bit key.
• Decryption algorithm is identical to the encryption algorithm except for the order of the round keys.

Now we know how DES encryption algorithm works, let's try to implement it in Java. See the next two chapters.

Part:   1  2  3  4