After reading a comprehensive paper  covering various kinds of generalized Feistel networks, I've tried to implement the Unbalanced Numeric Feistel variant, which relies on modular arithmetic for splitting and joining an integer in two smaller parts.
Given the scarcity of example implementations for this kind of cipher, I had to figure out some inexplicit details on my own in order to come up with the algorithm below. Therefore, I would like to pose some questions to clarify my remaining doubts:
Does the implementation below follow accurately the described network generalization? If not, what operations are wrong and what would be the right way of performing them?
Is there any way of reversing the modulus addition ⊞ on the encryption function other than by using modulus subtraction ⊟ on the decryption function? Given two integers $a$ and $b$ from a finite field of length $x$, the operation $(-a-b) \bmod x$ would be reversible in a similar way to the bitwise exclusive-or, but (obviously) the ciphertext would not be the same as the one obtained with the current operations.
What would be the implications of dynamically computing $first$ and $second$ so the $first \cdot second$ finite field is strictly equal to the input $data$?
Given two finite fields of lengths $first$ and $second$ greater than $2$, a number of $rounds$ greater than $2$, a positive integer $data$ on the finite field of length $first \cdot second$ and a positive integer $key$:
Please note that the LaTeX code above was inserted as an image due to the technical limitations of the MathJax formatting. The markdown source of this question contains a commented-out block with the code used to render it.
(Python implementation that can be used to test the described algorithm).
import random class NumericFeistel: def __init__(self, key: int, rounds: int, first: int, second: int): assert all(number >= 2 for number in (rounds, first, second)) self.first, self.second = first, second self.key, self.rounds = key, rounds def function(self, data: int, round: int) -> int: globals().update(self.__dict__) random.seed(data + key + round) return random.choice(range(first)) def encrypt(self, data: int) -> int: globals().update(self.__dict__) assert data < first * second for round in range(rounds): left, right = data // second, data % second left += self.function(right, round) data = first * (right % second) + (left % first) return data def decrypt(self, data: int) -> int: globals().update(self.__dict__) assert data < first * second for round in reversed(range(rounds)): left, right = data % first, data // first left -= self.function(right, round) data = second * (left % first) + (right % second) return data for test in range(1000): random.seed() feistel = NumericFeistel( rounds = 2 + random.choice(range(1000)), first = 2 + random.choice(range(1000)), second = 2 + random.choice(range(1000)), key = 42 ) data = random.choice(range(feistel.first * feistel.second)) assert feistel.decrypt(feistel.encrypt(data)) == data
Using and abusing the
random module for producing pseudorandom numbers and implementing the one-way round function may be a really bad idea, but this code is intended to be as readable as possible, and its hypothetical insecurity is a minor concern.
Please note that this only is a recreational exercise and nobody plans to use it for anything but demonstrative purposes. This is not another rolling out my own crypto question.
- Hoang V.T., Rogaway P. (2010) On Generalized Feistel Networks. In: Rabin T. (eds) Advances in Cryptology – CRYPTO 2010. CRYPTO 2010. Lecture Notes in Computer Science, vol 6223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14623-7_33