# Implementing a Feistel cipher with Python

### Background

During my Winter 2020 term at Portland State University, I completed the CS485: Cryptography elective with Dr. Sarah Mocas. During this course, I had a chance to gain hands-on expirience implementing two cryptographic algorithms: a Feistel cipher and the ElGamal encryption algorithm. In this post, I would like to share the details of my implementation of a Feistel cipher using a 64 bit block size and a 64 bit key using Python 3.

### Implementation

I chose Python because of its native support of large numbers, as well as very easy conversion between decimal and hexidecimal numbers. Officiency of the implementation was not an issue due to it being only an educational project to help students gain better understanding of cryptography.

The cipher consist of 3 major steps:

### Step 1: Key generation

The key generation algorithm works as follows:

- Uses the 64 bit secret key
**K**(8 bytes) - Left rotates
**K**by 1 bit 192 times (64 * 3) - Creates 16 new keys of consisting of 12 bytes

1 | def shiftBitLeft(self, block): |

### Step 2: Encryption

- Input whitening step:
- The input is the 64-bit block divided into 4 words
**w**._{0}, w_{1}, w_{2}, w_{3} - XOR each word with 16 bits of the key
**K = K**._{0}K_{1}K_{2}K_{3} - The output is
**R**_{0}= w_{0}⊕ K_{0}, R_{01}= w_{1}⊕ K_{1},**R**_{2}= w_{2}⊕ K_{2}, R_{3}= w_{3}⊕ K_{3}.

- The input is the 64-bit block divided into 4 words
- Set the round number to
**round=0**. After each of the 16 rounds increment**round**by one. - Compute
**F(R**. This function returns two values_{0}, R_{1}, round)**F**and_{0}**F**._{1}- Compute
**R**. This value is_{2}⊕ F_{0}**R**for the next round._{0} - Compute
**R**. This value is_{3}⊕ F_{1}**R**for the next round._{1} - The value
**R**becomes_{0}**R**for the next round._{2} - The value
**R**becomes_{1}**R**for the next round._{3} - Repeat for 16 rounds (but not the whitening step this only happens at the start of the first round).

- Compute
- After the last of the 16 rounds:
- Undo the last swap by setting
**y**to_{0}**R**from the end of the 16th round;_{2}**y**to_{1}**R**from the end of the 16th round;_{3}**y**to_{2}**R**from the end of the 16th round and_{0}**y**to_{3}**R**from the end of the 16th round._{1}

- Undo the last swap by setting
- Output whitening step:
- XOR each word with 16 bits of the key
**K = K**._{0}K_{1}K_{2}K_{3}

The input is**y**. The output is_{0}y_{1}y_{2}y_{3} **C**_{0}= y_{0}⊕ K_{0}, C_{01}= y_{1}⊕ K_{1},**C**_{2}= y_{2}⊕ K_{2}, C_{3}= y_{3}⊕ K_{3}.

The value**C**is the ciphertext._{0}C_{1}C_{2}C_{3}

- XOR each word with 16 bits of the key

1 | def whitening(self, word, key): |

### Step 3: Decryption

The algorithm to decrypt is the same as the algorithm to encrypt except that the keys are generated and used in reverse order.

1 | def decrypt(self, ct_hex): |

### Further Reading

You can find the full code of my implementation here.