1
  1. 进化算法使用适应度函数来选择跨代生存的候选者(“适者生存”)。我相信所有适应度函数都假设候选人的值越接近期望值,他们的输入(“键”)必须越接近期望的输入。

  2. 加密散列函数具有“生成具有给定散列的消息是不可行的”的属性。我理解这意味着值的“接近性”与键的“接近性”之间几乎没有相关性或没有相关性。

将这两者放在一起,这是否意味着“适者生存”假设对于加密哈希函数是错误的?意思是,如果您想使用进化算法来尝试找出密码哈希值的倒数,那么适应度函数会将您引向错误的方向。值的“接近性”和键的“接近性”之间的相关性是进化算法的先决条件吗?

4

2 回答 2

9

是的,基于所有三个(良好)加密哈希函数的输出,几乎不可能构建一个始终告诉您值 A 比值 B 更接近目标的适应度函数。这来自您提到的财产。因此,进化算法无法加速在一般情况下反转加密哈希函数。然而,这不应该是一个惊喜:所述属性首先是有用的,因为它恰好打破了进化算法的方法(通过查看哈希值相似性来加速反转)。

概括这一点,进化算法(就像所有其他依赖启发式来指导搜索的算法一样,例如A*)只有在您可以定义有意义的适应度函数(启发式)†</sup> 时才有用。显然,有可能构建不允许这样做的问题(例如,通过提供太少的信息),并且完全有可能存在更多具有相同问题的实际应用程序。进化算法不能治愈癌症,但这也不足为奇(没有什么可以治愈的,否则我们会转向不同的比喻)。

†</sup>附带说明,此适应度函数不必接近任何特定值,存在许多适应度可以无限增长的问题,例如,在优化代码以提高性能时,适应度可能是操作数每秒。

于 2011-09-17T17:49:37.483 回答
1

加密散列函数具有“生成具有给定散列的消息是不可行的”的属性。我理解这意味着值的“接近性”与键的“接近性”之间几乎没有相关性或没有相关性。

您对值与键的“接近性”的理解是正确的。事实上,这是散列函数的主要目的。进化算法在这里不能很好地工作。

但是,这并不是“生成具有给定哈希的消息不可行”的原因。这是因为哈希函数不是一对一的。例如,有可能hash(a) = key = hash(b). 因此,如果给您一个密钥,则无法判断原始消息是 a 还是 b。

于 2012-03-15T21:13:43.720 回答