使用哪些算法/方法来实施暴力破解？

Question

在阅读 SO 上的 从给定字符中生成唯一组合 时，我想知道程序使用的是 暴力破解 方法吗？我的意思是制作92个组合以打破用户ID或密码。典型的Windows键盘有大约92个可用于密码的字符。

我不是在问如何通过这种方法破解密码，而是想知道一些复杂程序使用什么方法进行 暴力破解 ？

- Y.E.P

---

请注意，所指的问题要求“排列”-在排列中，某个字符不能重复，这并不是密码的标准限制。 - amit

也许你应该了解一下字典攻击。注意，我并不是在推广这种攻击方式，只是提供一个暴力破解算法的例子。 - Luiggi Mendoza

@LuiggiMendoza 字典攻击和暴力破解攻击是不同的。我猜它永远也无法找到一个密码，比如 ZuntenableZ (untenable)。不是吗？ - Suhail Gupta

Answer 1

使用暴力方法解决问题的天真方式确实是一种简单的回溯，它探索所有可能性，对其进行评估，并选择最佳方案。

然而，对于某些问题，您可能拥有比“解决”或“未解决”更多的信息。例如，对于SAT问题（查找布尔公式是否有解），您可以了解“您究竟如何得出矛盾”（哪些变量无法满足分配）。通常我们称这个问题为约束传播。它应用于DPLL算法下的SAT，该算法经常用于SAT求解器的变体。

如果您感兴趣，使用SAT求解器的现实生活程序是各种各样的，软件验证算法就是其中一个例子，它使用SAT求解器来证明软件（或更常见的硬件）按预期工作。

另一个常见的优化是分支定界——这意味着，在到达叶子节点之前，您可以修剪“搜索树”。一个例子是旅行商问题。如果您已经找到了长度为100的路径，并且正在探索新的路径，并且已经到达101，则无需继续探索此可能性。

- amit