>>45
Expanding on this, to make it a bit clearer:
Chaining
f(x) 100 times is equivalent to turning it into
f(x) = (x+100) mod 100, which is just
x.
If in DES, we create the set
Y by feeding in all possible 8 char inputs in
X, and we assume that
X and
Y are subsets of each other (they share all elements), then we can turn the DES hash function into a function that associates each input in
X with a
position, or
index in
Y.
So we can represent each element
x in
X as a natural number, from 0 to 281,474,976,710,656, and associate with it another number,
j that maps
x to its corresponding (equal) entry
y in
Y. If we restrict all numbers
j to be positive, then the function for getting the
y in
Y associated to the
x in
X equivalent to:
f(x) = (x + j) mod 281,474,976,710,656.
Now, we see that this is equivalent to the previous ``simple'' hash function that just added 1 to x. The addition in the previous function was constant, whereas this one changes depending on
x. If there are no collisions, then for any 2 distinct
x and
j,
x +
j is unique.
So, to find a ``cyclic quine'', we are trying to find a series of
x in
X that generate a series of
j so that the sum of
all those
j and
j mod 281,474,976,710,656 is equal to
x.
In other words, you're trying to find a series of
x and associated
j, which, when all summed together, result in 281,474,976,710,656 +
s, where
s is the first
x that fed to the chain.
Calculating the amount of cyclic quines for any amount of cycles
c is the subset sum problem, which is
NP-Complete.
So just
calculating all quines for cycle
c through applying all
j for all
x would take more time than the lifetime of the Universe. Finding one by bruteforce is not likely.