How to teach DES using Python? The easy way… Part-1: DES Subkey Generation
The use and necessity of Cryptography algorithms are well established and doesn’t require any further debate. This established requirement also makes it important topic while teaching about “security” in Computer Science subject. By nature, understanding these cryptography system is not too easy and many time push out learners. Recently, I got a chance to teach cryptography to Computer Science students most of them were from Computer science background and have limited knowledge and interest in Mathematic. So, going by mathematical explanation was clearly not a option and hence believing in learning by doing, the best was to go through implementation.
This post is about teaching the class about Data Encryption Standard (DES) using Python implementation. The implemented code is surely not to be use in real world but can be use for the purpose of explaining the inner working of DES and to show the output of DES encryption and Decryption module.
DES is a symmetric encryption algorithm that means for encryption and decryption it uses the same secret key which is shared among sender and receiver. DES is also a block cipher i.e. it process the input plain-text block by block and 64-bit is used as block size by DES. DES working is based on Feistel Structure [ https://en.wikipedia.org/wiki/Feistel_cipher].
Basically DES uses 16 round of similar operation on input plain text with the help of unique key in each round. The unique key in fact is sub-key generated through the initial 64-bit key. Each round perform a Feistel function on half of plaintext (32-bit) and the 48-bit round key. So, to understand DES, one must have to understand about key generation, Feistel function, DES round operation for encryption and decryption. This split this post in four part, each one deals with one of them respectively. In this part 1, the DES key generation is explained.
DES sub-key Generation:
As we can see in figure 1 that key generation starts with 64bit initial key and by performing action like parity drop, split, left shift and compression using P-box in a round manner able to generate 16 unique subkey each one for each round of DES encryption and Decryption. In further section, each of these action is explain by walking through Python code snippets. For, the example purpose we consider 64-bit key as string of binary bit (‘10100101’).
Parity Drop:
The very first step of subkey generation is parity drop which is carried out by the help of a permutation table (explain later), so this step also known as permutation step. The permutation table has 56 number between 1–64 in a predefined order and do has 8,16,24,32,40,48,56 and 64 (these are parities bits). For the Python implementation, this table can be consider as a list object and it value will be used as index to select bit from the initial 64-bit key string. Thus the resulting string will have 56 bits according to the permutation table.
Split Key in Half:
After converting initial key into 56 bits by applying permutation table the next step is to split the 56 bits key into two half 28–28 bits in each. Both half is then process separately in all round to generate the all 16 sub keys. splitting can be done in many ways in Python the easiest is by use of string slice because we know the length or each half. So, for easy handling this will be also implemented as Python method.
Circular Left shift
In every round of key generation, the both half is circularly left shifted and the number of bits for left shifting is round dependent as mentioned in Figure 1 (in round 1,2,9,16 each half is shifted 1 bit position and in the rest of rounds 2 bits are shifted to left in circular fashion. Currently, we will implement a circular left shift method which will take 28 bits, and number of shift position as input and return the circularly left shifted bits as output. Left shift can be achieved by bitwise operator but for the simplicity and easy understanding we will go with simple string slice method.
Compression P box
In each round the circular left shifted both half is passed to compression which utilized a compression table to compress 56 bits key to a 48 bits key. The output of compression is the final key of a particular round. Again, the compression P box can be implemented as Python list object and its value can be used to select bits from the key string.
Subkey generation and Round:
Once every step of key generation is implemented as function, the output of each round can be achieved by looping and gluing each function together. The value of circular shift of each round can be seen a Python list and in each round the value can be access accordingly.
That’s it. By this way we will have 16, 48-bit subkeys generated from the seed 64-bit key. In next, post (Part-2), I will explain the Feistel function F() which is used in each round of DES.
# Note: Please comment for any errors or doubts. This is my first post so errors and mistakes are expected, please help me to improve this with your comments.
