PRNG中的熵与可预测性

Question

如果熵是奇数的度量，并且给定的PRNG分布是均匀的，那么熵就会很高。因此，Mersenne Twister(MT)具有很高的熵。

但MT也是可以预测的。您可以检索其过去的位元并预测其未来的位元。

熵和可预测性之间有什么关系？

Answer 1

熵是衡量惊奇的尺度。

这是非正式的，简短的，非定量的，但在这个范围内是正确的。在随机数发生器的情况下，我们必须指出:熵是RNG输出中令人惊讶的度量，对于一个知道RNG设计的熟练人员(具有任意大的计算能力)，包括任何参数( MT: Mersenne素数和其他几个参数)。这是为未知种子(如果有的话)假定一致随机，但任意大的计算能力，熟练的人(除非另有说明)。

这里考虑的熵是生成器的属性，而不是它输出的特定位串的属性。

熵还可以定义为发电机的总输出，或每输出位。在密码学中，我们测量了比特的熵，使得理想的均匀真RNG的每输出比特为1比特。

对于任何伪RNG，从设计、参数和种子来看，整个输出都是可预测的，因此整个输出中的熵被限制在产生其种子的熵上，这是有限的。随着输出尺寸向无穷远方向的增大，每个输出比特的熵减小到零。

Mersenne Twister(MT)具有很高的熵。

不，因为它是一个PRNG (见上文)。

MT也是可预测的。

是的，有足够的输出和很少的计算能力。

熵和可预测性之间有什么关系？

如果一个位串生成器具有从有限长度前缀(如MT)可以预测其全部输出的性质，则该生成器具有有限的总熵(以所述有限长度为界，以比特为Shannon熵)，且每个输出比特的熵非常小。

相反，对于可预测的实际定义，则是错误的。特别是，有实际的密码安全PRNG(因此有限的总熵)是实际不可预测的。

要使事情变得量化:考虑一个任意长的位字符串的生成器G。注意G_b，生成器仅限于其第一个b位。G_b容易生成2^b不同的b-bit位字符串B，其各自的概率为p_B (可能是某些B的0 )，1=\sum p_B (之和超过2^b项B)。G_b在比特中具有Shannon熵

H(G_b)=\sum_{B\text{ with }p_B\ne0}p_B\,\log_2\left(\frac1{p_B}\right)

其平均每比特熵为H(G_b)/b。

对于理想的TRNG (输出是一致随机的独立位)和任何b，所有b-bit位串都与p_B=2^{-b}相等，而它就是H(G_b)=b。

对于任何带有s-bit种子的PRNG(按任何分布)，H(G_b)\le \max(b,s)。发电机整个输出的熵为H(G)=\displaystyle\lim_{b\to\infty}H(G_b)。当所有种子产生不同的输出，且种子是一致随机的时，这在H(G)=s中是最大的。

Answer 2

为了使位串的熵有意义，它必须是在某个特定的随机或部分随机过程中选择的，它具有一定的产生精确串的概率，以及产生其他东西的概率。然后，一个字符串的熵大概是(*)，产生该字符串的进程会这样做的概率的负日志。因此，如果某个进程生成一个具有8位熵的字符串，这意味着该进程将有1/ 256的机会生成该特定的字符串。

(*)测量熵的方法有很多种，但在大多数情况下，它们彼此接近，一个简单的近似可以合理地接近所有这些方法。

如果一个过程不以相同的概率生成字符串，那么通常应该将过程产生的熵看作是概率最高的字符串。因此，如果一个进程产生16位零字符串的几率为50%，而生成任何其他16位字符串的几率为131,070 %，则通常将该过程视为产生一位熵的过程--甚至可以过滤输出以产生更多的输出(例如，生成一个不是全部为零的比特字符串将产生15.999978比特的熵，而平均只需要生成一位比特的两倍时间)。

Answer 3

可以说，PRNG会有一个伪均匀分布。实际上，它的输出之间是相互关联的。因此，它的熵仅限于种子的熵。

拥有(真正的)低熵使得一些事情是可以预测的，因为你可以用暴力强迫种子。然而，相反的说法是不正确的。一个设计不佳的PRNG会以一种对手可以利用的方式泄漏熵(除非PRNG不打算抵抗对手，比如电子游戏)。当一个好的PRNG泄漏熵时，它在计算上是不可行的，因此从实际的角度来说，它的熵是不会降低的。