SHA256 / 512 设计上是怎么做到不能化简(循环 100000 次简化到 1 次的计算量)的?

查看 101|回复 8
作者:drymonfidelia   
是指代码高度优化,把中间计算步骤全部都优化掉?好像普通的 hash 算法都没办法化简,比如 MD5/SHA1
tool2dx   
@tool2dx 是指通过一次计算拿到 100000 次循环计算自身 hash 的结果
drymonfidelia
OP
  
你这化简就相当于,求函数 f' = f(f(f...))
可是有些函数,人类就是找不到更快的 f' 呀?不然你把 sigmoid 重复 100000 次,写一个更快的函数出来?
ipwx   
人类找不到不就等于没有嘛( doge
ipwx   
对了,哪怕你求 x^100000 次方,你也只不过能化简为 (x^50000)^2 ... 以此类推,大概需要 log 100000 次乘法
再怎么也没法变成 O(1)
ipwx   
有,我们可以称之为打表法,具体的做法是找一个充分大的存储空间把 hash 算法产生的所有可能结果都存储下来,然后首次 hash 后的结果就可以直接命中缓存了
XiLingHost   
打表法的缺点是,不能加盐
XiLingHost   
首先一个根本性错误:SHA256/512 依然是速度优先的,根本没有什么「循环 100000 次」的过程,中间每个 chunk 最多也就循环 64 次。
对于「循环 100000 次」的问题,楼上说得很清楚了:次方还是对一个数做 N 次乘法呢,你能化简次方运算为 1 次吗?
回到正题,加密循环可参考这篇文章: https://blog.csdn.net/u011583927/article/details/80905740
总的来说就是右旋和位运算叠加的过程,原理上来说因为要读取整个文件(而不是什么「循环 100000 次」),不能化简。
w568w   
如果有这项优化 ssh-key 是不是也不安全了?所有 ssh 主机都要瘫
您需要登录后才可以回帖 登录 | 立即注册

返回顶部