Implementation of Feistel Networks (free to use)

Feel free to use for sheet 9

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Implementation of Feistel Networks (free to use)
Update 2020-01-09 17:02: Fixed some bug in function substitution.

TL;DR: I implemented Feistel Networks in Scala together with simplification rules. Code and examples can be found at https://scalafiddle.io/sf/jBBvWwg/3 – scroll to the bottom on first read. Here’s one sample code:

val network = Feistel.generateFull("f", rounds = 1) val output = network.compute(FeistelData(Variable("L0"), Variable("R0"))) println(output.fullSimplify()) // "R0 || L0 ⊕ f1(R0)"

You can also do arbitrarily many rounds, arbitrarily complex input expressions and inversion of Feistel networks.

I wrote this for sheet 9 as writing long equations with pen & paper annoyed me too much :slight_smile: Especially, I hope you can prove that 3-round Feistel networks are not sPRPs by using my code.

Warning: There is one StackExchange answer on the Internet spoiling the solution for Exercise 8-2b). Note that it confuses some variable names and is thus slightly wrong. Swap some variable names and argument positions :slight_smile:

PS: I asked multiple mathematics students before implementing it whether I could do the envisioned tasks in any CAS they know. They all said “perhaps in XYZ, maybe UVW, …”. I really wonder why nobody of them could give a definitive answer. One of them even developed a GAP library already, so it’s not the case that the tools are completely unknown to them.

2 Likes

here is a python 3 ! implementation, that might also help, but no garuantee for correctness:

#!/usr/bin/python
import sys

def round(list):
	if len(list)!= 2:
		exit()
		print("abort due to list not formatted properly")
	return ["{}".format(list[1]), "{0} xor F({1})".format(list[0],list[1])]


def main():
	if len(sys.argv)!= 2:
		print("abort due to incorrect arguments to the script")
		exit()
	rounds = int(sys.argv[1])
	print("forward for {} rounds".format(rounds))
	tmp = ["L", "R"]
	for x in range(0, rounds):
		tmp = round(tmp)
	print(tmp)
	print("inverse for {} rounds".format(rounds))
	tmp = ["R{}".format(rounds), "L{}".format(rounds)]
	for x in range(0, rounds):
		tmp = round(tmp)
	print(tmp)

main()

and here is a prolog (https://swish.swi-prolog.org/) implementation:

round([L,R],[R,L+f(R)]).
    

feistel([L,R],0,[L,R]).

feistel([L,R],Rounds,Result):-
    NewRounds is Rounds -1,
    round([L,R],[NewL,NewR]),
    feistel([NewL,NewR],NewRounds,Result).

query a normal feistel cipher by

?- feistel([l,r],2,Res).

and an inverse calculation via

?- feistel([r2,l2],2,Res).
1 Like