Perl:rand()的输出是否可以部分预测？

Question

我正在玩perl的rand(),并注意到当提供大于2 ^ 32的参数时,输出的最后几位变得可预测.

我发现说明它的最清晰的方法是使用以下脚本:

srand(); for $i (1..10) { printf "%4x\n",rand(2**48)%2**16 }

每当我执行输出时

5101
6378
2a23
62f2
8d15
effc
9657
2d16
f669
40c0

(这不只是前10个值,但我没有看到复制一长串"随机"数字的观点)

对srand()的调用是多余的,但它可以很容易地提供一个参数,并且看到它不会改变任何东西.

我试过这个:

• Debian挤压有perl 5.10(randbits = 48)
• Debian wheezy有perl 5.14(randbits = 48)
• Debian jessie有perl 5.20(randbits = 48)

我知道rand()不应该是加密安全的,但是可预测的最后16位比我理解的更糟糕.我使用的任何功能都错了吗？

Answer 1

这不仅仅是"默认"种子的实现(srand没有参数调用或者根本没有被调用),正如您可能从Schwern的回答中看到的那样:所有 srand调用(以及所有初始化RNG状态的方法)都受此问题的影响.

目前(自5.20)Perl使用基于FreeBSD的自己的RNG的实施drand48和srand48; 在此之前,使用perl drand48并且srand48如果可用,那么Linux上的行为实际上是相同的.在任何一种情况下,srand实现仅使用32位输入,将它们置于48位RNG状态的高32位; 低16位被初始化为0x330e.如果你0x330e经历了一轮LCG算法(只需要前一个状态的底部16位来获得下一个状态的最后16位),乘以0xe66d并加0x000b,你最终得到的0x5101是你观察到的第一个值.

显然,这种低位的可预测性是不好的,我不确定为什么它没有得到解决,特别是现在perl有自己的RNG实现,很容易被48位清理.但是,显然它比将高位始终初始化为已知状态的损害要小.

目前,我建议如果你想对perl的RNG做任何严肃的事情,每次调用最多使用32位,必要时组合多个调用以获得更高的精度/范围.