Not logged in. · Lost password · Register

Marcel[Inf]
#faui2k15, GTI-Tutor a. D.
Member since Nov 2015
441 posts
Subject: Implementation of Feistel Networks (free to use)
+2 luisgerh, tyr
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.
This post was edited 2 times, last on 2020-01-09, 18:06 by Marcel[Inf].
tyr
ModKrypt Tutor WS19/20
Avatar
Member since Oct 2014
106 posts
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()
"Debugging is like doing surgery by randomly squeezing stuff in a patient's body and going like 'lmao tell me when this guy stops breathing'." -- Orteil, Creator of Cookie-Clicker
This post was edited on 2020-01-10, 16:49 by tyr.
tyr
ModKrypt Tutor WS19/20
Avatar
Member since Oct 2014
106 posts
+1 siccegge
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).
"Debugging is like doing surgery by randomly squeezing stuff in a patient's body and going like 'lmao tell me when this guy stops breathing'." -- Orteil, Creator of Cookie-Clicker
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen