我正在尝试计算长度为 N 的所有可能的随机字符串的 Shannon entropy 的分布。 (随机,我的意思是每个位置的每个字母都以相同的概率被选中)
为了计算香农熵,我使用类似于以下的公式: https://stackoverflow.com/a/2979208/145999.
prob = [ float(string.count(c)) / len(string) for c in dict.fromkeys(list(string)) ]
entropy = - sum([ p * math.log(p) / math.log(2.0) for p in prob ])
现在我正在尝试找到一个阈值 t,以便例如99% 的随机字符串的熵将高于 t。
给定字符串的长度、可能的不同字母的数量以及应该具有更高熵的字符串的所需比例,如何计算这个阈值熵?
看起来快速而肮脏的方法是进行蒙特卡罗:
from typing import *
import math
import random
def get_entropy(string: str) -> int:
prob = [float(string.count(c)) / len(string) for c in dict.fromkeys(list(string))]
return - sum([p * math.log2(p) for p in prob])
def get_random_string(length=10, chars='abcdefghijklmnopqrstuvwxyz'):
return random.choices(chars, k=length)
def monte_carlo_entropy(random_function: Callable[[], str], num_sims=10000) -> list[int]:
entropies = []
for i in range(num_sims):
entropies.append(get_entropy(random_function()))
entropies.sort()
return entropies
def get_percentile(sorted_entropies: list[int], percentile=0.99) -> int:
index = int(len(sorted_entropies) * percentile)
return sorted_entropies[index]
entropies = monte_carlo_entropy(lambda: get_random_string(10))
print(get_percentile(entropies, 0.99))
对于特定的长度、字符集和均匀分布,我得到 3.321 位。
值得注意的是,这个熵定义有点奇怪,可能不适合这个应用程序。无论密码有多长,小写 a-z 密码的最大熵为
-26 * (1/26 * log2(1/26))
~= 4.700。