如何测试随机生成器

Question

我需要测试一个随机数生成器，它会随机产生数字。如何确保生成的数字是随机的。

Answer 1

无论如何，您只能测试统计随机性，而这并不能证明数字序列在密码上是否强大。统计测试一个PRNG需要相当多(10甚至100G字节)的生成比特。

Dieharder是一个非常好的测试套件。

http://www.phy.duke.edu/~rgb/General/dieharder.php

而且TestU01也很出名。

http://www.iro.umontreal.ca/~simardr/testu01/tu01.html

Answer 2

使用卡方检验。你用的是什么语言？我可以提供一个C++示例。基本上

• 将随机数放入桶中(多次)。
• 桶的数量减去1是桶与“预期”计数的对数，产生卡方结果。
• 使用chi-square calculator查看获得这些结果的概率。

Answer 3

下面是如何开始的详细说明。任何RNG的初步测试都是NIST使用的Monobit测试，它简单地计算1和0的数量。http://csrc.nist.gov/groups/ST/toolkit/rng/stats_tests.html

关于测试随机数生成器的注意事项:我们实际上不需要太多的RNG测试，因为许多测试相互“包含”。

也就是说，这里描述的是一种简单有效的新的比特有序频率测试。此测试包含任何期望50-50的频率测试，因为它更严格。

定义: t= tosses / trials b=bins / urns s=sessions of tosses n=sets of sessions

因为掷硬币通常不是50-50，所以这种新的测试可以使用40,000,000位的池来非常有效地利用。

当硬币被翻转100次时，期望值是一个的53.9795，另一个的46.0205，有时更多的正面，有时更多的反面。50-50不是定序箱的期望值，因此此测试优于任何期望50-50的频率测试。

步骤1:样本大小的选择: 100次/比特。

步骤2:会话数量的选择: 50个会话永远不够，即使有数百万的巨大样本大小也是如此。400通常就足够了。2000收敛得很好，所以使用了2000个不同的样本，共100次。最小增益出现在2000以上。

2000年100次掷硬币的期望值: 50-50 159.1784748 (请注意，50-50出现的概率仅为7.96%.) 51-49 312.1146564 52-48 294.1080416 53-47 266.362 54-46 231.8335926 55-45 193.8971865 56-44 155.8102392 57-43 120.2745706 58-42 89.16907819 59-41 63.47629295 60-40 43.37546685 61-39 28.4429291 62-3817.89152 63-37 10.79171042 64-36 6.238957586 65-35 3.455422663

66-34 1.832421109 67或以上1.747439674

获得b=2和t=100的精确百分比的公式是:对于100-0，赔率为1/ (2^99) =1/ (2^(t-1))然后，从那里累积，对于99-1先前乘以100 (t)除以1对于98-2先前乘以99 (t-1)对于97-3先前乘以98 (t-2)除以3 ...斯基普。对于51-49先前乘以52 (t-48)除以49对于50-50先前乘以51 (t-49)除以50，然后再次除以2。

这个等式适用于任意数量的抛出。

步骤3:对这18个值进行卡方检验，得到17个自由度的p值。

P值在0.999以上接近完美。RNG会不会过于接近完美呢？是的，太容易预测了。低于0.001是确定问题通常发生的地方。一个测试套件认为小数点右边的300个0是非常糟糕的，连续10-14是非常糟糕的。一些人认为6个零已经足够糟糕，足以被定义为明确的失败。有些人，为了安全起见，认为1或2个零就足够了，他们错了。因此，对于优秀的RNG，有时会提供低于0.01的p值，而不是单个集合的单个p值，而是采用多组会话。

步骤4:将p值输入0-1.0直线Kolmogorov-Smirnov检验。不同的专家建议K-S测试的输入数量在10到1000之间。100还不够。200就可以了。500有点攻击性。

下面是获取K-S最大差的伪代码：

Set low := 0;  Set n := 200;  
Set ansForward := 0; Set ansBack := 0;

sort( pval [n] );
for (j := 0; j < n; j := j+1)   
 {  Set Kback := pval [ j ] - low;
    Set low := low +1 / n;    { Ranges from 0 to 1 }
    Set Kforward := low - pval [ j ];  
    if (Kforward > ansForward) Set ansForward := Kforward;
    if (Kback > ansBack) Set ansBack := Kback;
   }
{ Separate analysis can perhaps be made here on ansForward and ansBack.  Someone like Peter Brand might also examine and magnify the bottom 5% and the top 5%. }
if (ansForward > ansBack)
      return ansForward;
else
      return ansBack;   ∎

K-S答案不是p值，对于200p值不应超过0.115。对于良好的RNG，0.03到0.08是正常的。0.115到0.13%是可疑的。

K-S检验非常简单，也非常有效。

上面显示的是一个更好的新的有序频率测试。任何未通过此测试的RNG都不应进行进一步测试并立即更换。但是，下一步呢？

OFTest不包含LOR测试。推荐的游程长度试验的样本量为200,000，15个自由度，输入K-S检验200次。(请注意，“大于j”的最小LOR bin的预期总和等于第j个bin。)

然后呢？对于许多游戏，这两个测试就是您所需要的。有来自NIST，Diehard，Diehard，Crusher的选择倾向。(注意:顽固的重叠和测试是劣质和错误的，不是对Marsaglia的原始Fortran代码的忠实解释。)

使用n=200的几个RNG的结果。

1. LCG 134775813x +1模块2^31 seed=11111:高位: OFT KS: 0.0841通过。LOR KS: 0.04786关。第一个200,000的Monobit：-189次通过。位16: OFT KS: 0.5477失败。第一个200,000: 114的Monobit。从0到15的所有位都没有通过开放傅立叶变换，但通过了单比特测试。
2. 经常受到批评的LCG Randu: 65539x +0 mod 2^31 seed=11111：

高位: OFT KS: 0.03567 LOR KS: 0.07709。前200,000位：-165位18: OFT KS: 0.15143前200,000位：+204从0到17的所有位未通过OFT。

• LCG 69069x +1 mod 2^32 seed=11111:高位: OFT KS: 0.05547 LOR KS: 200,000的0.0456位：-290位17: OFT KS: 0.1467 200,000位：-193从0到13的所有位未通过OFT。

• LCG 3141592653x + 2718281829 mod 2^35 seed=11111:高位:OFT KS: 0.02868LOR KS: 0.06117 200,000位：-69位16: OFT KS: 0.240 200,000位：-13所有从0到15的位未通过操作。

• LCG 23x +0 mod 2^27 seed=11111:高位: OFT KS: 200,000的0.5368位：-235所有位未通过操作。

请注意，任何和每个LCG的低位都应该从返回结果中丢弃。

关于2^35的说明:这是任何RNG的最小周期和重要性，因为抛硬币和掷骰子运行，这样的事情可能会连续发生30次，但35是不会发生的。2^32的周期是不够的，对于现实生活情况来说太小了。

LWAP