1
$\begingroup$

Given a cryptographic permutation $\{0,1\}^n \rightarrow \{0,1\}^n$ does it follow that after some number of iterations you must eventually map the input to itself?

$\endgroup$
2
$\begingroup$

Let's put in a layman's explanation on top of the mathematical one by kub0x.

You cannot have a mapping between two elements where one has been visited before for whatever iteration. Because obviously another element has already mapped to it, and in a permutation you cannot have two starting values map to the same destination value. The only exception to this rule is the one element that you've started with. If you map to that one then you've created a cycle and mapped back.

Of course you could also map to an element that you haven't visited before. However, now you've just grown the amount of elements that you have visited before, and you are in the same situation: either you close the cycle by mapping to the starting element, or you add one to the number of elements you've already visited. You can only keep growing until you have $2^n$ elements, after which you have created the greatest cycle possible, and you move back to the starting position.

You can do this for any starting position. It means that any permutation consists of one or more cycles and that any element is part of just one such a cycle. How fast you return to the starting position depends on the size of the cycle that you are in. If you have the maximum of $n$ cycles then you will reach your starting position in one step: the permutation is the identity function where $f(x) = x$ - the equivalent of adding zero to a number.

| improve this answer | |
$\endgroup$
2
$\begingroup$

A permutation $\sigma$ on $n$ symbols is a bijective mapping $X \mapsto X$ that is represented as composition of $r$ disjoint cycles, where $X=(1,\cdots,n)$.

This is $\sigma = c_1 \cdots c_r$ where $\sum_{i=1}^{r} \vert c_i \vert = n$. So it could happen that i.e your value $x \in X$ maps into itself after $\vert c_1 \vert$ iterations if the symbol $x$ lies in $c_1$. You don't need to iterate $k$ times where $k$ is the permutation order, this is, $f^k(x)=x$ is not necessary when $\sigma$ is a composition of $r>1$ cycles. Here $k = lcm(\vert c_1 \vert, \cdots, \vert c_r \vert)$.

In the case that $r=1$ this is, if $\sigma$ is a permutation on $n$ symbols is just a $n$-cycle then $f^n(x)=x$.

| improve this answer | |
$\endgroup$
2
$\begingroup$

Any permutation $f$ (cryptographic or not) on a finite set $X$ satisfies $f^n=id$ for some $n>0$.

To see this, note that there's only finitely many functions from $X$ to itself. Hence $f,f^2,f^3,\dots$ aren't all distinct, so $f^k=f^l$ for some $k$ and $l$ with $l<k$. Now $$id=f^{-l}f^l=f^{-l}f^k=f^{k-l}$$ so we can set $n=k-l$.

| improve this answer | |
$\endgroup$
-3
$\begingroup$

A 256-bit hashing algorithm is a permutation of 2^256 input values.

The permutation is the product of an unknown number of cycles with a total length of 2^256.

One particular 256 bit value is member of a cycle of some length l <= 256 and will reappear after l iterations.

If you let L = least common multiple of all cycle lengths then applying hashing L times is the identity, that is each value is mapped to itself.

Obviously l is likely so large that you can’t perform the operation, while L could be ridiculously huge.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Are you sure about that initial statement? Because this doesn't look like cycles in a permutation to me... $\endgroup$ – Maarten Bodewes Mar 7 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.