Kendall's Online blog

Wednesday, March 15, 2006

Cryptography Primer II: Data Encryption Standard (DES/3DES)

Introduction to DES
DES is the most widely used cryptographic algorithm. It has been used in most banking application since 1977 when it was released as a free license by NIST (then NBS), it was replaced in 2000 by AES and is used in IPSEC and SSL security protocols. DES is a block cipher that encrypts a 64-bit block (not variable) of cipher text using a 56-bit key. The key is padded with 8 parity bits giving it a total length of 64 bits. Every eight bit is used for parity and ensures that each byte has an odd number of 1’s.

DES Encryption
The DES encryption algorithm for one round of DES is as follows for a plaintext m as described in
m is permuted by IP(Initial permutation) i.e.. (m0 = IP(m)).
m0 is split into two 32-bit parts L0R0.
For I = 1 to 16
Li = Ri-1
Ri = Li-1 (+) f(Ri-1, Ki ) where Ki is the ith roundkey.
Switch L16R16 such that m16 = R16L16 and apply inverse of initial permutation on m
i.e. C=IP-1(R16L16)


The DES blocks are described as follows:
Initial permutation (IP): It is just a mere reordering/permutation of the 64 bits of the plaintext. Function f: The steps to compute function f are as follows:
R is expanded by expansion function (E)
The output of E is then bitwise XORed with the ith roundkey (B = E(R) (+) K)
For I = 1 to 16
Each Bi is substituted from S-Box Si to give Ci of length 4 bits
The 32 bit C is now permuted for the last time by permutation P

Expansion Permutation (E): This expands the 32 bit of Ri by reordering using the expansion permutation table which duplicates certain bits to form a 48 bit block
S-Box Substitution (S): Each value of Si is substituted by S-box Si. Bi = b1b2….b6. The value Ci of the substitution is obtained by checking row b1b6 and column bi2bi3bi4b5Si (000 is first column and 00 is first row). Ci is 4 bits long and each of the 8 S-boxes produce a value for Ci making C 32 bits long.
Permutation (P): This is just another reordering of the 32 bits of C and gives the final output of function f. The table for the permutation is found in Key Generation: Each round uses a different key derived from the first round key K0 . The 56 bit key obtained when all parity bits are removed undergoes three transformations. The 56 bit key is permuted by a key permutation table PC1 to produce CoDo. Co and Do are both 28bits long each. Ci and Di are left shifted one or two bits to the left. For rounds 1, 2,9,16 they are shifted once and for all other rounds it is shifted twice. Finally the 48 bits of the 56 bits of concatenated C16D16 obtained after a final permutation using table PC2 to produce K.

DES decryption
This is the same process as DES encryption but the round keys are applied in reverse order. i.e the last round key is applied first then other round keys are applied in decreasing order.

Triple DES (3DES)
3DES is a much stronger version of DES and is more resistant to differential cryptanalysis and makes brute force attck more difficult. There are two variants:
Use of three different keys and DES encryption (E). 3DES in this variant is Ek1(Ek2(Ek3(m)))
Use of two different keys and DES encryption (E) and decryption (D). 3DES in this variant is Ek1(Dk2(Ek1(m))) where k1, k2 and k3 are different keys
3DES can be implemented in serial or in parallel using 3 blocks of DES. The parallel implementation takes up less hardware resources

REFERENCES
A. T. Abdel-Hamid, S. Tahar, E. Aboulhamid, “IP Watermarking Techniques: Survey and Comparison”, IEEE International Workshop on System-on-Chip for Real-Time Applications (IWSOC'03)) June 30 - July 02, 2003, Calgary, Alberta, Canada, pp. 60 - 65
P. C. van Oorschot, A. J. Menezes, S.A. Vanstone, “Handbook of Applied Cryptography,” CRC Press Inc., Florida , 1996.
W. Trappe, L.C. Washington, “Introduction to Cryptography with Coding Theory,” Prentice Hall, New Jersey, 2002
V. Pasham, S Trimberger, “High-Speed DES and Triple DES Encryptor/DecryptorCryptographic Algorithm Metrics,” (http://www.xilinx.com/xapp/xapp270.pdf)

0 Comments:

Post a Comment

Links to this post:

Create a Link

<< Home