SHA256 / 512 设计上是怎么做到不能化简（循环 100000 次简化到 1 次的计算量）的？

[drymonfidelia]

[tool2dx]

是指代码高度优化，把中间计算步骤全部都优化掉？好像普通的 hash 算法都没办法化简，比如 MD5/SHA1

[drymonfidelia]

@tool2dx 是指通过一次计算拿到 100000 次循环计算自身 hash 的结果

[ipwx]

你这化简就相当于，求函数 f' = f(f(f...))

可是有些函数，人类就是找不到更快的 f' 呀？不然你把 sigmoid 重复 100000 次，写一个更快的函数出来？

[ipwx]

人类找不到不就等于没有嘛（ doge

[ipwx]

对了，哪怕你求 x^100000 次方，你也只不过能化简为 (x^50000)^2 ... 以此类推，大概需要 log 100000 次乘法

再怎么也没法变成 O(1)

[XiLingHost]

有，我们可以称之为打表法，具体的做法是找一个充分大的存储空间把 hash 算法产生的所有可能结果都存储下来，然后首次 hash 后的结果就可以直接命中缓存了

[XiLingHost]

打表法的缺点是，不能加盐

[w568w]

首先一个根本性错误：SHA256/512 依然是速度优先的，根本没有什么「循环 100000 次」的过程，中间每个 chunk 最多也就循环 64 次。

对于「循环 100000 次」的问题，楼上说得很清楚了：次方还是对一个数做 N 次乘法呢，你能化简次方运算为 1 次吗？

回到正题，加密循环可参考这篇文章： https://blog.csdn.net/u011583927/article/details/80905740

总的来说就是右旋和位运算叠加的过程，原理上来说因为要读取整个文件（而不是什么「循环 100000 次」），不能化简。

[valord577]

如果有这项优化 ssh-key 是不是也不安全了？所有 ssh 主机都要瘫

[Bromine0x23]

不满足结合律呗

[xdeng]

不是有硬件加速的么

[w568w]

@valord577 我猜你说的是 RSA ，一种加密算法。SSH 的安全加密是 RSA 算法完成的，SHA256 只是用来确定指纹。

另外 SHA256 是「摘要算法」，不是用来加密的，和加密算法除了都有「算法」俩字，根本没半毛钱关系。在不改变原义的情况下，摘要算法永远是越快越好、越优化越好，所以才有那么多硬件加速。

最后，SHA256 （包括很多摘要算法）本身根本没有什么「几百万次循环」，那也是加密算法才考虑的。不要被楼主一知半解的提问误导了。

[dode]

SHA 哈希算法是用来做全局数据完整性验证的，算法复杂度至少要 O （ N ）吧。
要是有人设计一个更简单的算法，碰撞概率更低，可以得一个图灵奖了吧？

BTC 就是基于 SHA256 计算难设计的，要是这个算法被攻破了，BTC 网络肯定又会分叉。

[w568w]

@w568w #12 再补充几点：

1. SHA256 不慢。一般人说「 SHA256 慢」，也不是因为算法本身过于复杂；
2. 不仅 SHA256 没有，RSA 也没有「几百万次循环」；
3. 摘要算法不存在常规意义的「破解」一说。一般说有安全问题都是指证明了不具有抗碰撞性、抗第一原象性（这是一般人理解的「破解」，即从摘要值恢复原文）和抗第二原象性。目前基本没有摘要算法被「破解」。

更多摘要算法介绍可以看这篇： https://thiscute.world/posts/practical-cryptography-basics-2-hash/

[villivateur]

比如你要计算 1+2+...+100 ，你可以梯形公式化简成乘法
如果要计算 1*2*...*100 ，也能化简成一个指令叫 100!

但关键是，计算机不是万能的，计算机的基本指令一般也就是乘法，没有求阶乘的指令。所以也就没法化简了。

有些算法会有特定的指令集，比如 AES ，可能可以“化简”

[cybort]

请楼主告诉我（ a+b ）^2 怎么化简

[drymonfidelia]

@cybort aa+2ab+bb 十年没用了还记得这个公式

[cybort]

@drymonfidelia 再看看计算次数，这是化简还是化繁

[qbqbqbqb]

@w568w 所谓“几百万次循环”应该指的是 pbkdf2 这种可以指定迭代次数的密钥派生算法，原理就是反复应用类似 SHA256 这样的密码学安全的 hash 算法，通过增加运算次数来减慢速度，抵抗暴力破解。OP 想问的应该就是这类算法为什么是安全的。

[w568w]

@qbqbqbqb 也许吧。但楼主看到却没有回复我这两条，也没有更改自己的问题，那就默认楼主知道自己在说什么吧。