魔方按照一定的顺序转动，是否必然会回到初始状态？ hash 值也同理吗？

[tdjnodj]

对于魔方，重复 R U R' U'、R U R' U 等一定方法转动，最终都会回到初始状态。曾经无聊转了好久的 R U，最终也回到了初始状态。于是我产生了一个猜想：魔方按照一定规律重复转动，最终都会回到初始状态。 可惜本人能力有限，无法证明。

由此，我产生了类似的疑问：对于某个 hash 值（ hash1 ），通过同样的 hash 算法得出 hash2 ，再用同样的算法得出 hash3 ...... 最终能回到 hash1 吗？最少需要计算几次？

同理，用某个加密算法重复加密某段信息，每次使用同样的密钥，最终能不能得到原来的信息呢？最少需要加密几次？

[GuuJiang]

魔方的操作构成置换群
后面两个例子都为伪

[ThirdFlame]

一楼已经给出了答案。

[ElDanno]

hash function 是有分 N-way independent 的，如果你有足够多的线性方程是可以直接算出来下一个的 hash 结果的。这个可以看看著名红色的算法导论的 hash 部分，需要一些概率基础

[yk000123]

求证：给定任意一个魔方操作序列，在经过有限次重复操作该序列后，魔方的状态和初始状态相同。

证：f(x) = y ，表示经过 f 操作序列后，魔方状态由 x 变为 y 。假设魔方初始状态为 a ，那么多次操作后，状态的序列为 abcd…。因为魔方的状态总数是有限的，所以这个序列一定会出现重复，可以理解为单链表里存在环。又因为存在 f 的反向操作 g ，使得 g(y) = x ，不可能存在两个不同的魔方状态在经过同一个魔方变换序列后得到同样的新状态，所以单链表的环不可能在中间形成（那样的话两个不同的节点的 next 指向了同一个节点），只能在单链表的头部形成，所以魔方一定会回到初始状态 a 。

这个证明里有几个前置条件：


1. f(x)=y 中 x 和 y 同属于一个有限的集合。
2. f 是可逆的。

hash 和加密都不满足 f 可逆的条件。即使 hash 和加密的状态集合是有限的（包括原始输入），也只能证明环是存在的，并不能证明单链表的头在环里。

[yk000123]

PS: 对于对称加密，f 是可逆的，但是密文长度不固定，所以状态集合是无限的。

[yk000123]

当然，特殊设计的 hash 算法或加密算法是可以满足状态有限和可逆的要求的。比如对 int32 类型的 hash：f(x) = -x ，或者将字符串反向输出的加密算法，这些是可以逆向出原始输入的。但是谁会设计这些有 bug 的 hash 或加密算法呢？

[leonshaw]

魔方群不是循环群，应该不行

[leonshaw]

#7 理解错了，以为是任意状态复原了。
重复加密一个 block 应该是可以的，因为它也是一个可逆映射，构成置换群

[DefoliationM]

流密码的解密就是再加密一次，异或运算。不过现在基本都是结合着用，变成 aead 这种的认证加密，必不行。

[kxuanobj]

hash：通常情况下不能回到 hash1 。
hash 主要用于提取信息摘要。y=hash(x)，从 x 种状态经过 hash 运算转换得到 y 种状态。
通常情况下，y 的状态数比 x 的状态数少。所以，必然有一部分 x 的状态需要被转换为同一种 y 状态（哈希冲突）。
所以在这种情况下，必然有一些状态经过任意次 hash 计算后，无法回到自己的原本的状态。

举一个例子：hash(x) = x % 2 。举例：初始 x0=3 ，x1 = hash(3) = 1 。永远不会回到 3 。


加密：不清楚……感觉上这与魔方的问题是类似的，都是在有限群做相同变换。
但有一部分对称加密算法的加密、解密过程是一致的。比如 AES-CTR/Chacha20 。
再比如 AEAD 类算法，这类算法是流加密+HASH 函数的组合体，比如 AES-CCM ，是 AES-CTR+AES-CMAC 的组合；再比如 AES-GCM ，是 AES-CTR+GHASH 的组合体。起机密性保护的流加密部分，就是原流加密算法，性质完全相同。

对于这些算法，由于加密、解密过程是一致的，你只需要把第二次加密看做是“解密”即可。对原文加密两次必然会得到原文。