Also thanks for the proof around 30min. It is quite nice and easy, and lends itself well to a discussion of "confusion" from your suggested article. Here is another notation using Fold:
FeistelForm[kn_] := {#[[2]], Xor[#[[1]], F[#[[2]], kn]]} &
FoldList[#2@#1 &, {L, R}, {
FeistelForm[k1], FeistelForm[k2], FeistelForm[k3], Reverse,
FeistelForm[k3], FeistelForm[k2], FeistelForm[k1], Reverse
}] ;
SameQ[%[[1]], %[[-1]]]
Out[] = True
Let's try and make this a little easier for Physicists (or former) by assuming that
$F$ is just addition, then the naive form reduces to linear algebra:
NaiveFeistelForm[kn_] := {{0, 1}, {1, 1}} . # + {0, F[kn]} &
FoldList[#2@#1 &, {L, R}, {
NaiveFeistelForm[k1], NaiveFeistelForm[k2], NaiveFeistelForm[k3],
Reverse,
NaiveFeistelForm[k3], NaiveFeistelForm[k2], NaiveFeistelForm[k1],
Reverse
}] /. {_Integer?EvenQ -> 0, _Integer?OddQ -> 1};
SameQ[%[[1]], %[[-1]]]
Out[]=True
What happens here is basically a nesting
$g \cdot( \ldots( g\cdot(g\cdot s + p_1) + p_2 ) \ldots ) + p_n $, and it's easy to see if distributive holds we get
$g^n \cdot s +P$ where
$s$ is signal,
$P$ a summed pad, and mixing matrix
$g$ satisfies
$g^3=Id$. This is the same problem I mentioned previously, where Feistel scheme essentially reduces to a one time pad. However if the pair of operations
$(\cdot,+)$ do not allow distributive property, then the nested form above might actually be a decent characterization of what is meant (loosely) by "Feistel Scheme".
There is one alternative, applying the pad before the mixing:
$g \cdot( \ldots( g\cdot(g\cdot (s + p_1) + p_2 ) \ldots + p_n) $. In this case distributive does not hold if
$g\cdot (s + p_1) \neq g\cdot s +g\cdot p_1 $, which is what we want to fix the previous algorithm. Start by generating test data:
SeedRandom["confusion"];
randPad = RandomInteger[{0, 4}, 32];
randMessage = RandomInteger[{0, 4}, 32];
And weakly prove (in terms of test data) distributive holds in the previous case:
SameQ[ Flatten[ Mod[ForwardMix . Partition[Plus[randPad, randMessage], 8], 5]],
Flatten[Mod[Plus[ ForwardMix . Partition[randPad, 8],
ForwardMix . Partition[randMessage, 8]], 5]]]
Out[]=True
This is what we don't want, so we need to add new Addition and Subtraction functions (the idea is taken from Dariia's suggested reference above):
BoxSubtract[dat1_, dat2_, part_, base_] :=With[{ints = (FromDigits[#, base] & /@
Partition[#, part]) & /@ {dat1, dat2}}, Flatten[
IntegerDigits[#, base, part] & /@ Mod[Subtract @@ ints, base^part]]]
BoxPlus[dat1_, dat2_, part_, base_] := With[{ints = (FromDigits[#, base] & /@
Partition[#, part]) & /@ {dat1, dat2}}, Flatten[
IntegerDigits[#, base, part] & /@ Mod[Plus @@ ints, base^part]]]
(* test inverse property *)
SameQ[BoxSubtract[BoxPlus[randPad, randMessage, 8, 5], randPad, 8, 5], randMessage]
Out[]=True
Again here is a proof that distributive doesn't hold:
(* not distributive *)
SameQ[ Flatten[ Mod[ForwardMix . Partition[BoxPlus[randPad, randMessage], 8], 5]],
Flatten[Mod[BoxPlus[ ForwardMix . Partition[randPad, 8],
ForwardMix . Partition[randMessage, 8]], 5]]]
Out[]=False
Then our Encode / Decode functions need only minor modification, replacing Plus and Subtract for BoxPlus and BoxSubtract:
EncodeRound[sig_, AGmat_] := Flatten[
Mod[ForwardMix . Partition[BoxPlus[sig, AGmat, 8, 5], 8], 5]]
DecodeRound[sig_, AGmat_] := Mod[BoxSubtract[ReplaceAll[
Mod[Flatten[ReverseMix . Partition[sig, 8]], 5], Div4], AGmat,
8, 5], 5]
Using these updated functions, we can produce another set of encrypts:
These are possibly better than the previous set since we are doing a little more than just padding, but the run statistics really don't look any better. I am still skeptical--What exactly do we gain by requiring non-distributive property? Is one data set easier to decrypt than another?
I think that the non-distributive property must be an important defining part of what makes a Feistel Cipher, but I don't yet completely understand the theory why. Anyone else, agree / disagree? Thoughts?
