计算阈值，使99%的随机字符串具有更高的熵

Question

我正在尝试计算长度为 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。

给定字符串的长度、可能的不同字母的数量以及应该具有更高熵的字符串的所需比例，如何计算这个阈值熵？

Answer 1

看起来快速而肮脏的方法是进行蒙特卡罗：

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。