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

Question

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

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

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()

的“open-sesame”是一个修改过的实用程序，用于安装这种特定类型的加密卷，它不是用 python 编写的，而是已制成命令行工具，以便该脚本可以与之交互。

几个挑战/研究方向：

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

我感谢所有的巨大帮助，我只是想分享我到目前为止的情况，以造福每个人。

Answer 1

您是否尝试过从给定的已知错误密码中枚举编辑内容？如果您只需要进行一些编辑（就像拼写错误一样），那么实际上并没有那么多可能性。

Norvig 的这个 漂亮的代码 解决了编辑一级的编辑问题，用于 edits1( ） 功能。您可以以加深深度优先的方式应用它，因此您首先尝试单个编辑，然后是编辑的编辑，以及编辑的编辑的编辑等。

Answer 2

• 首先你需要你的字符集。特殊字符有可能吗？大写和小写？数字？

• 接下来你需要你最初的猜测。也许有两种猜测，第二种猜测是将大写和小写颠倒，以防止大写锁定键按下。 (fuzzY v. FUZZy)

• 现在您需要迭代...编辑、删除和插入的所有可能性。

• • 您有 3 组初始猜测

• 现在你决定你想走多远。也许 2 次编辑、2 次删除或 2 次插入...或 1 次编辑和 1 次插入，或 1 次删除和 1 次插入等。

一些 JavaScript 代码来说明：

var charset = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
var guesses = {"passWORD":true, "PASSword":true};

function getProps(obj) {
 var lst = [];
 for(var g in obj)
  lst.push(g);
 return lst;
}
function transformEdit(guesses) {
 var lst = getProps(guesses);
 for(var x=0; x<lst.length; x++) {
  var guess = lst[x];
  for(var y=0; y<guess.length; y++) {
   for(var z=0; z<charset.length; z++) {
    guesses[guess.slice(0,y) + charset.charAt(z) + guess.slice(y+1)]=true;
   }
  }
 } 
}
function transformDelete(guesses) {
 var lst = getProps(guesses);
 for(var x=0; x<lst.length; x++) {
  var guess = lst[x];
  for(var y=0; y<guess.length; y++) {
   guesses[guess.slice(0,y) + guess.slice(y+1)]=true;
  }
 }
}
function transformInsert(guesses) {
 var lst = getProps(guesses);
 for(var x=0; x<lst.length; x++) {
  var guess = lst[x];
  for(var y=0; y<guess.length+1; y++) {
   for(var z=0; z<charset.length; z++) {
    guesses[guess.slice(0,y) + charset.charAt(z) + guess.slice(y)]=true;
   }
  }
 } 
}

// not the most efficient way
// but you'll get every possible edit, delete and insert
transformDelete(guesses);
transformInsert(guesses);
transformEdit(guesses);

getProps(guesses).length; //1759604

该代码没有提供最有效的解决方案，因为有很多重叠是可以避免的，但这是为了生成一个一次性问题的密码列表，所以......

我使用 JS 对象属性列表作为猜测的哈希集。

您可以通过迭代 getProps(guesses) 返回的数组来将猜测输出到密码列表。