基于排列的概率排序

Question

举个简单的例子:我正在尝试暴力破解一个4位数的密码。此密码可以由数字0-9组成。

如果我对密码一无所知，我可以按随机顺序或按顺序尝试暴力破解，例如0000、0001、0010、0011等，它应该平均只需要一组可能密码的一半大小。

现在，如果我知道一个事实，数字9很可能比数字0至少出现一次(从一个大的密码样本集中)，是否可以命令我的搜索(平均)导致更快的破解时间？

具体地说，给定出现在代码中的至少一个相应数字的概率集：

[0: 0.1, 1: 0.2, 2: 0.3, 3: 0.4, 4: 0.5, 5: 0.6, 6: 0.7, 7: 0.8, 8: 0.9, 9: 0.95]

我怎样才能写一个迭代器或生成器(用Python或C#)来以最优的方式暴力破解这个密码呢？例如，在这种情况下，它应该测试至少一个8的代码，而不是测试至少一个1的代码。

也许，在生成每个密码进行测试时，应该有95%的概率至少使用数字9一次，90%的概率使用数字8，等等，诸如此类？

这实际上会导致加速吗？有没有我应该研究的算法？

更好的是，对于真正的暴力破解密码，这是以任何特定的顺序完成的吗(因为人们更可能使用英文单词作为密码，元音将比大写Z更常见)？

Answer 1

我可以想出三种可能的方法来解决这个问题：

1.离线生成：

离线生成每个组合的概率，并对其进行反向排序：

df = pd.DataFrame()
df['code'] = [str(i).zfill(0) for i in range(10000)]

## You can update this probability-map to any numbers you want:
prob_map = [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.95]

df['prob'] = df['code'].apply(lambda x: prob_map[x[0]]*prob_map[x[1]]*prob_map[x[2]]*prob_map[x[3]])

df = df.sort_values(by='prob'], ascending=False)

dataframe现在将按照您应该尝试的顺序包含代码列表。

2.在线试用：

使用给定的概率图生成4个随机的1位数。

还要维护一组已经存在的tried代码。

# We first need to adjust the probabilities such that sum(all_probs) = 1:

prob_map = [x/sum(prob_map) for x in prob_map]

dig = [get_digit_with_prob(prob_map) for _ in range(4)]
code = ''.join([str(x) for x in dig])

## get_digit_with_prob() implementation is quite trivial, simply a if-else loop

3.解析解：

如果你仔细观察，数字的概率图提到数字越大，其概率越大。

我们可以简单地扩展这个参数，不仅对于1位数，而且对4位数也是如此。

因此，简单地对rangeo 0，9999进行字母顺序的反向排序就足够了：

codes_to_try_in_order = [str(x) for x in range(10000)].sort(reverse=True)