## 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.

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 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

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