algorithm - 是否有任何已知的算法、开源程序或白皮书可以在给定密码的已知部分的情况下破解密码？

Question

基本上，我的一个 friend 将自己锁在了他创建的加密容器之外。他一定是在输入密码时输入了错误，因为他无法访问该容器。我们知道它应该是什么，并且实际密码肯定是它的变体和/或与其非常相似。我正在寻找代码或白皮书来处理这种“模糊”密码破解的概念，给定密码的已知部分或密码遵循的已知模式。语言不重要。我已经开发出一种暴力破解密码提示的方法，我需要的是开发一种算法，让我可以智能地尝试破解它，这样我就不必尝试所有可能的组合。但是，我认为其他人已经这样做了。我在一定程度上理解这背后的概念，但我正在寻找代码或白皮书，其中可能有人已经解决了这个问题。

更新 因此，我使用密码短语中可能包含的字符构建了一个字典(Python，但可以随意发送任何语言的示例)。考虑因素包括标准 QWERTY 键盘上的击键接近度、1337 种等效语言以及每个字母的意外“/”字符，因为它靠近 shift 键。从那里提供示例密码短语，并尝试每个字母。这是以下示例:http://code.activestate.com/recipes/535171-password-cracker/

import os
from commands import getoutput

known = {
    '_': ('_', ' ', '-', '.', '/'),
    'b': ('b', 'B', '3', '8', '*', 'v', 'V', 'n', 'N', 'g', 'G', 'h', 'H', ' ', '/'),
    'g': ('g', 'G', '6', '^', 'f', 'F', 'h', 'H', 'b', 'B', 'v', 'V', 't', 'T', '/'),
    'l': ('l', 'L', '1', '!', ';', ':', 'k', 'K', 'o', 'O', '.', '>', ',', '<', 'p', 'P', '/'),
    'e': ('e', 'E', '3', '#', '4', '$', 'r', 'R', 'w', 'W', 'd', 'D', '/'),
    'h': ('h', 'H', '4', '$', 'g', 'G', 'j', 'J', 'y', 'Y', 'b', 'B', 'n', 'N', '/'),
    'i': ('i', 'I', '1', '|', '!', '\\', 'u', 'U', 'o', 'O', 'k', 'K', '8', '*', '9', '(', '/'),
    't': ('t', 'T', '7', '&', '+', 'r', 'R', 'y', 'Y', 'g', 'G', '4', '5', '%', '6', '^', '/'),
    'r': ('r', 'R', 'e', 'E', 't', 'T', 'f', 'F', '4', '$', '5', '%', '/'),
}

command = 'open-sesame %s' # hey, use your imagination ;)
# I obviously supplied only needed letters for this example, I can't tip you 
# off to the real pass phrase ;) This conveys the general idea....
passwdBasic = 'Big_Leg_Hitter'

def main():
    arrays = [known[ltr] for ltr in passwdBasic]
    start = [ltrs[0] for ltrs in arrays]
    end = [ltrs[-1] for ltrs in arrays]
    indexes = [0] * len(arrays)
    maxes = [len(ltrs)-1 for ltrs in arrays]
    chrs = [ltrs[i] for ltrs, i in zip(arrays, indexes)]
    while chrs != end:
        passx = ''.join(chrs)
        open('tries.txt', 'a+').write(passx + '\n')
        out = getoutput(command)
        if 'wrong password' not in out:
            print 'GOT IT!', passx
            return
        # Next letter
        for i in range(len(indexes)-1, -1, -1):
            if indexes[i] <= maxes[i]-1:
                indexes[i] += 1
                break
            else:
                indexes[i] = 0
        # Make up the chrs
        chrs = [ltrs[i] for ltrs, i in zip(arrays, indexes)]


if __name__ == '__main__':
    main()

虚构的“芝麻开门”是一个修改后的实用程序，用于装载这种特殊类型的加密卷，它不是用 Python 编写的，而是被制作成一个命令行工具，以便该脚本可以与之交互。

一些挑战/研究方向:

• 如果不小心按下了“/”字符而不是 shift 键，这实际上会在密码短语中添加一个字符，因此可能出现在任何字母之前。这需要在解决方案中加以考虑。
• 最好将其与@rrenaud 提出的拼写检查实用程序集成:http://norvig.com/spell-correct.html
• 我对用于解决拼写检查问题的贝叶斯概率统计定理的应用着迷；我想知道是否有关于错误击键以及在键入某些单词和/或短语时按某些键而不是其他键的可能性的任何研究。这种逻辑可以以与拼写检查实用程序大致相同的方式应用于密码破解，拼写检查实用程序受益于已知的常见拼写错误列表。我没有可用于“训练”神经网络实用程序的错误击键数据。

我感谢所有的大力帮助，我只是想分享我到目前为止的进展，以便大家受益。

Answer 1

您是否尝试过从给定的已知错误密码中枚举编辑？如果您只差几处编辑(就像打字错误一样)，那么可能性真的不多。

它枚举一级编辑由这个 beautiful code 解决由 Norvig 在 edits1() 函数中进行拼写更正。您可以先以加深深度的方式应用它，因此您首先尝试单个编辑，然后是编辑的编辑、编辑的编辑的编辑等等。