Feistel Networks

Horst Feistel helped develop DES (Data Encryption Standard) in the 1970s, which was eventually replaced by AES (Advanced Encryption Standard), due to its short key length.

The structure of DES is called a Feistel cipher or a Feistel network (same thing). Feistel ciphers are used throughout cryptography, for example in Twofish, padding schemes for digital signatures on certificates, and key schedules.

A Feistel Cipher is a framework or structure for building encryption algorithms, that inputs a key and n encryption rounds, and outputs a cipher.

Feistel networks use inequality function XOR (exclusive or), meaning "TRUE IF (and only IF) the operands are different".

The ^ operator in Python can perform an "exclusive or" on binary representations (i.e., using their bits) of numbers:

X = 4 #in binary: 100
Y = 3 #in binary: 011
print(X ^ Y) #in binary: 111 = 7

X = 7 #in binary: 111
Y = 2 #in binary: 010
print(X ^ Y) #in binary: 101 = 5

Run Code

The same operator can be applied to sets to generate the symmetric difference. The logical operation yields a similiar result, as shown here with sets X Δ Y:

X = {'a','b'}
Y = {'b','c'}
print(X ^ Y) #{'a','c'}

X = {1,2,3}
Y = {1,3,5,7}
print(X ^ Y) #{2,5,7}

Run Code

The following encryption algorithm uses the plain text {3,4} and key {1,2,3}:

plainText = {3,4} #my secret PIN

key = {1,2,3}

cipherText = key ^ plainText

print(cipherText) #{1,2,4}

Run Code

The cipher text {1,2,4} can be deciphered using the same keyblock {1,2,3} using the same XOR process:

cipherText = {1,2,4}

key = {1,2,3}

plainText = key ^ cipherText

print(plainText) #my secret PIN: {3,4}

Run Code

In multiple rounds (could be referred to as a permutation) of a Feistel network, the round function is run on half of the data to be encrypted, and its output is 'XORed' with the other half of the data. This is repeated a fixed number of times, and the final output is the encrypted data.

The magic of XOR is that you can use it on the same data to reverse itself! As shown here:

Encryption

Decryption

Python

def permutation(key, text):
  result = key ^ text
  print("A:", key, "B:", text, "AΔB:", result)
  return result

text = {1,2,3,4} #my PIN number - secret! 
keys = [ {1,2}, {2,3}, {3,4} ] #3 rounds

for k in keys: #encryption to {2, 3}
  text = permutation(k, text) 

for k in keys: #decryption
  text = permutation(k, text)

Run Code