更新:在@SqueamishOssifrage和@PaulUzdak的帮助下,我们发现我的NIST SP800-22有一个错误的通用测试。所以这就成了一个没有意义的问题。
看看这份报告。它似乎通过了所有的测试,但所有的p值的普遍测试下降在前10%。我已经将生成器的种子设置为1。下面是我对assess程序的配置:
$ ./assess 100000
G E N E R A T O R S E L E C T I O N
______________________________________
[0] Input File [1] Linear Congruential
[2] Quadratic Congruential I [3] Quadratic Congruential II
[4] Cubic Congruential [5] XOR
[6] Modular Exponentiation [7] Blum-Blum-Shub
[8] Micali-Schnorr [9] G Using SHA-1
Enter Choice: 0
User Prescribed Input File: mt19937-seed-1.dat
S T A T I S T I C A L T E S T S
_________________________________
[01] Frequency [02] Block Frequency
[03] Cumulative Sums [04] Runs
[05] Longest Run of Ones [06] Rank
[07] Discrete Fourier Transform [08] Nonperiodic Template Matchings
[09] Overlapping Template Matchings [10] Universal Statistical
[11] Approximate Entropy [12] Random Excursions
[13] Random Excursions Variant [14] Serial
[15] Linear Complexity
INSTRUCTIONS
Enter 0 if you DO NOT want to apply all of the
statistical tests to each sequence and 1 if you DO.
Enter Choice: 1
P a r a m e t e r A d j u s t m e n t s
-----------------------------------------
[1] Block Frequency Test - block length(M): 128
[2] NonOverlapping Template Test - block length(m): 9
[3] Overlapping Template Test - block length(m): 9
[4] Approximate Entropy Test - block length(m): 10
[5] Serial Test - block length(m): 16
[6] Linear Complexity Test - block length(M): 500
Select Test (0 to continue): 0
How many bitstreams? 10
Input File Format:
[0] ASCII - A sequence of ASCII 0's and 1's
[1] Binary - Each byte in data file contains 8 bits of data
Select input mode: 1
Statistical Testing In Progress.........
Statistical Testing Complete!!!!!!!!!!!!
$我之所以使用样本大小100000,是因为NIST 800-22提到它是一个可能的大小。(还请参阅附录E,第121页:“在测试阶段,NIST通常在order 10^6上评估序列”)。我不知道什么是理想的尺寸。
------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
generator is
------------------------------------------------------------------------------
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
2 1 1 0 3 0 0 1 1 1 0.534146 10/10 Frequency
4 1 1 0 1 0 0 1 0 2 0.122325 9/10 BlockFrequency
1 2 1 0 1 1 1 1 2 0 0.911413 10/10 CumulativeSums
2 0 1 0 2 0 2 1 2 0 0.534146 10/10 CumulativeSums
1 1 4 0 0 0 2 1 1 0 0.122325 10/10 Runs
1 2 1 1 0 2 1 0 0 2 0.739918 10/10 LongestRun
1 1 1 0 1 2 0 1 2 1 0.911413 10/10 Rank
0 1 0 2 1 1 1 0 3 1 0.534146 10/10 FFT
2 0 2 0 1 0 1 2 1 1 0.739918 10/10 NonOverlappingTemplate
2 2 3 0 0 1 0 0 1 1 0.350485 10/10 NonOverlappingTemplate
0 1 3 1 1 1 0 1 1 1 0.739918 10/10 NonOverlappingTemplate
3 1 0 2 1 1 0 0 1 1 0.534146 10/10 NonOverlappingTemplate
1 2 1 1 1 1 2 0 1 0 0.911413 10/10 NonOverlappingTemplate
1 2 0 2 1 0 0 2 1 1 0.739918 10/10 NonOverlappingTemplate
1 2 0 0 2 2 0 1 1 1 0.739918 10/10 NonOverlappingTemplate
1 1 3 0 0 2 2 0 0 1 0.350485 10/10 NonOverlappingTemplate
0 1 0 2 2 1 1 1 1 1 0.911413 10/10 NonOverlappingTemplate
1 1 0 0 0 1 2 1 1 3 0.534146 10/10 NonOverlappingTemplate
1 0 1 1 2 2 0 1 1 1 0.911413 10/10 NonOverlappingTemplate
1 1 0 3 0 0 2 0 1 2 0.350485 9/10 NonOverlappingTemplate
2 0 1 1 2 1 2 0 1 0 0.739918 10/10 NonOverlappingTemplate
0 3 1 1 2 1 1 0 0 1 0.534146 10/10 NonOverlappingTemplate
0 0 2 2 1 3 1 1 0 0 0.350485 10/10 NonOverlappingTemplate
3 0 1 0 1 3 2 0 0 0 0.122325 10/10 NonOverlappingTemplate
0 0 1 2 2 1 1 2 0 1 0.739918 10/10 NonOverlappingTemplate
1 0 3 1 0 0 2 1 1 1 0.534146 10/10 NonOverlappingTemplate
1 0 1 3 1 1 1 1 1 0 0.739918 10/10 NonOverlappingTemplate
2 1 2 0 0 0 0 3 1 1 0.350485 10/10 NonOverlappingTemplate
2 0 0 1 0 1 2 3 1 0 0.350485 9/10 NonOverlappingTemplate
0 1 1 1 0 0 0 4 1 2 0.122325 10/10 NonOverlappingTemplate
0 3 2 1 1 0 1 1 1 0 0.534146 10/10 NonOverlappingTemplate
1 0 0 0 3 0 2 1 3 0 0.122325 10/10 NonOverlappingTemplate
3 1 0 0 2 0 0 2 1 1 0.350485 9/10 NonOverlappingTemplate
0 1 2 1 0 0 3 2 0 1 0.350485 10/10 NonOverlappingTemplate
0 1 2 1 0 0 2 1 1 2 0.739918 10/10 NonOverlappingTemplate
0 1 1 1 0 1 1 1 2 2 0.911413 10/10 NonOverlappingTemplate
2 2 0 0 0 1 2 2 0 1 0.534146 10/10 NonOverlappingTemplate
1 1 0 2 0 1 0 0 2 3 0.350485 10/10 NonOverlappingTemplate
1 2 0 1 0 0 1 3 2 0 0.350485 10/10 NonOverlappingTemplate
1 1 1 0 0 2 2 2 1 0 0.739918 10/10 NonOverlappingTemplate
1 0 2 1 2 0 2 0 0 2 0.534146 10/10 NonOverlappingTemplate
0 2 1 1 0 1 0 3 0 2 0.350485 10/10 NonOverlappingTemplate
0 1 1 3 3 0 1 0 1 0 0.213309 10/10 NonOverlappingTemplate
0 3 1 0 1 2 0 0 2 1 0.350485 10/10 NonOverlappingTemplate
0 1 1 1 2 0 0 2 1 2 0.739918 10/10 NonOverlappingTemplate
1 1 3 1 1 0 0 1 1 1 0.739918 10/10 NonOverlappingTemplate
0 0 1 0 0 1 2 5 1 0 0.008879 10/10 NonOverlappingTemplate
1 1 0 1 1 1 1 3 0 1 0.739918 10/10 NonOverlappingTemplate
0 1 0 1 1 1 1 2 1 2 0.911413 10/10 NonOverlappingTemplate
1 1 1 0 0 1 1 2 2 1 0.911413 10/10 NonOverlappingTemplate
0 1 1 2 1 1 2 0 1 1 0.911413 10/10 NonOverlappingTemplate
0 1 0 2 1 1 3 0 1 1 0.534146 10/10 NonOverlappingTemplate
1 1 2 2 0 3 0 0 1 0 0.350485 10/10 NonOverlappingTemplate
0 3 1 1 1 1 1 0 0 2 0.534146 10/10 NonOverlappingTemplate
1 2 1 1 0 1 2 2 0 0 0.739918 10/10 NonOverlappingTemplate
0 2 0 1 1 2 3 0 1 0 0.350485 10/10 NonOverlappingTemplate
1 1 1 1 1 0 1 1 1 2 0.991468 10/10 NonOverlappingTemplate
2 0 0 2 0 1 1 2 2 0 0.534146 10/10 NonOverlappingTemplate
1 1 3 0 0 0 4 0 0 1 0.035174 10/10 NonOverlappingTemplate
0 1 1 0 1 0 1 3 0 3 0.213309 10/10 NonOverlappingTemplate
2 1 0 0 2 0 2 1 1 1 0.739918 10/10 NonOverlappingTemplate
2 1 3 1 0 0 0 0 1 2 0.350485 10/10 NonOverlappingTemplate
0 2 1 1 1 2 1 0 2 0 0.739918 10/10 NonOverlappingTemplate
2 0 0 1 0 4 0 1 1 1 0.122325 10/10 NonOverlappingTemplate
1 2 1 0 0 1 2 1 2 0 0.739918 9/10 NonOverlappingTemplate
1 1 1 2 0 0 2 0 2 1 0.739918 10/10 NonOverlappingTemplate
1 1 3 1 0 1 0 1 2 0 0.534146 10/10 NonOverlappingTemplate
0 1 3 2 0 1 0 2 1 0 0.350485 10/10 NonOverlappingTemplate
0 1 0 1 0 3 2 2 0 1 0.350485 10/10 NonOverlappingTemplate
2 1 0 2 0 0 0 4 0 1 0.066882 10/10 NonOverlappingTemplate
0 1 2 1 1 2 0 1 0 2 0.739918 10/10 NonOverlappingTemplate
3 0 1 0 1 0 1 1 0 3 0.213309 10/10 NonOverlappingTemplate
1 1 1 1 1 2 1 0 2 0 0.911413 9/10 NonOverlappingTemplate
0 1 3 0 2 0 1 1 2 0 0.350485 10/10 NonOverlappingTemplate
1 1 1 0 2 0 1 0 2 2 0.739918 10/10 NonOverlappingTemplate
0 1 0 1 3 1 0 0 3 1 0.213309 10/10 NonOverlappingTemplate
2 2 2 0 0 2 0 0 0 2 0.350485 10/10 NonOverlappingTemplate
1 3 0 0 1 3 0 2 0 0 0.122325 9/10 NonOverlappingTemplate
1 1 0 0 2 1 0 1 3 1 0.534146 9/10 NonOverlappingTemplate
0 1 0 2 1 1 2 0 1 2 0.739918 10/10 NonOverlappingTemplate
0 0 1 1 0 1 0 1 3 3 0.213309 10/10 NonOverlappingTemplate
0 0 3 3 0 0 1 1 2 0 0.122325 10/10 NonOverlappingTemplate
2 0 2 0 1 0 1 2 1 1 0.739918 10/10 NonOverlappingTemplate
0 0 3 0 2 0 0 2 2 1 0.213309 10/10 NonOverlappingTemplate
2 3 0 1 1 1 2 0 0 0 0.350485 10/10 NonOverlappingTemplate
1 1 1 0 3 1 0 1 0 2 0.534146 10/10 NonOverlappingTemplate
1 0 1 1 1 1 2 2 0 1 0.911413 10/10 NonOverlappingTemplate
0 1 0 0 1 3 1 0 2 2 0.350485 10/10 NonOverlappingTemplate
2 1 3 0 0 0 2 1 1 0 0.350485 9/10 NonOverlappingTemplate
0 0 2 1 2 2 0 0 0 3 0.213309 10/10 NonOverlappingTemplate
2 2 0 1 0 1 1 1 2 0 0.739918 10/10 NonOverlappingTemplate
0 1 1 1 0 3 1 0 0 3 0.213309 10/10 NonOverlappingTemplate
2 0 2 1 2 1 1 0 1 0 0.739918 10/10 NonOverlappingTemplate
2 2 0 1 2 1 0 0 2 0 0.534146 9/10 NonOverlappingTemplate
2 0 1 1 2 1 2 0 0 1 0.739918 10/10 NonOverlappingTemplate
1 1 0 2 0 3 2 1 0 0 0.350485 10/10 NonOverlappingTemplate
2 0 1 1 1 1 0 2 1 1 0.911413 10/10 NonOverlappingTemplate
0 1 1 2 2 0 1 0 1 2 0.739918 10/10 NonOverlappingTemplate
0 1 2 1 0 3 0 2 1 0 0.350485 10/10 NonOverlappingTemplate
1 1 2 0 2 1 2 0 0 1 0.739918 10/10 NonOverlappingTemplate
0 3 0 0 2 0 1 3 0 1 0.122325 10/10 NonOverlappingTemplate
1 0 0 1 3 1 2 1 1 0 0.534146 10/10 NonOverlappingTemplate
0 0 0 1 1 2 0 0 2 4 0.066882 10/10 NonOverlappingTemplate
1 1 0 2 1 2 1 1 1 0 0.911413 10/10 NonOverlappingTemplate
0 0 1 0 1 2 3 1 2 0 0.350485 10/10 NonOverlappingTemplate
1 4 1 0 1 0 0 0 3 0 0.035174 10/10 NonOverlappingTemplate
1 1 2 3 0 0 0 0 2 1 0.350485 10/10 NonOverlappingTemplate
1 1 0 1 2 2 2 0 1 0 0.739918 10/10 NonOverlappingTemplate
0 1 1 1 3 1 1 0 1 1 0.739918 10/10 NonOverlappingTemplate
1 0 2 0 2 1 0 1 3 0 0.350485 10/10 NonOverlappingTemplate
1 1 0 1 0 0 4 2 1 0 0.122325 9/10 NonOverlappingTemplate
2 2 1 0 3 0 1 1 0 0 0.350485 10/10 NonOverlappingTemplate
2 1 2 2 0 0 1 1 0 1 0.739918 9/10 NonOverlappingTemplate
1 0 0 1 2 2 0 0 2 2 0.534146 10/10 NonOverlappingTemplate
1 2 1 2 1 1 0 0 1 1 0.911413 9/10 NonOverlappingTemplate
2 1 0 2 0 1 3 0 1 0 0.350485 9/10 NonOverlappingTemplate
2 0 1 0 2 1 1 1 0 2 0.739918 10/10 NonOverlappingTemplate
3 2 2 0 1 0 0 0 1 1 0.350485 10/10 NonOverlappingTemplate
2 2 1 0 1 2 1 0 0 1 0.739918 10/10 NonOverlappingTemplate
1 0 2 1 1 2 2 1 0 0 0.739918 9/10 NonOverlappingTemplate
1 0 2 0 1 2 0 0 2 2 0.534146 10/10 NonOverlappingTemplate
1 2 0 0 0 1 2 2 1 1 0.739918 10/10 NonOverlappingTemplate
0 1 1 1 1 0 1 2 2 1 0.911413 10/10 NonOverlappingTemplate
1 0 2 2 0 0 2 3 0 0 0.213309 10/10 NonOverlappingTemplate
1 3 0 0 0 0 2 2 0 2 0.213309 10/10 NonOverlappingTemplate
1 0 2 2 1 1 1 0 0 2 0.739918 10/10 NonOverlappingTemplate
0 3 0 0 1 1 1 1 1 2 0.534146 10/10 NonOverlappingTemplate
1 0 1 3 0 1 2 1 0 1 0.534146 10/10 NonOverlappingTemplate
1 0 0 1 1 4 1 1 1 0 0.213309 10/10 NonOverlappingTemplate
2 0 2 0 2 0 1 1 2 0 0.534146 10/10 NonOverlappingTemplate
1 0 3 0 0 1 0 2 0 3 0.122325 10/10 NonOverlappingTemplate
2 0 2 1 0 1 1 1 1 1 0.911413 10/10 NonOverlappingTemplate
1 4 1 1 1 0 0 1 1 0 0.213309 9/10 NonOverlappingTemplate
2 1 1 1 2 0 1 0 1 1 0.911413 10/10 NonOverlappingTemplate
1 0 0 1 0 5 0 2 0 1 0.008879 10/10 NonOverlappingTemplate
1 1 0 2 1 0 1 0 4 0 0.122325 10/10 NonOverlappingTemplate
1 1 1 2 1 1 1 1 0 1 0.991468 10/10 NonOverlappingTemplate
3 3 0 0 2 0 1 0 0 1 0.122325 10/10 NonOverlappingTemplate
0 0 1 2 1 3 2 0 0 1 0.350485 10/10 NonOverlappingTemplate
1 4 0 0 0 0 1 2 0 2 0.066882 10/10 NonOverlappingTemplate
1 1 0 1 4 1 1 0 0 1 0.213309 10/10 NonOverlappingTemplate
2 0 1 0 1 0 1 2 2 1 0.739918 9/10 NonOverlappingTemplate
0 1 1 2 1 1 1 2 0 1 0.911413 10/10 NonOverlappingTemplate
0 1 1 2 1 2 1 1 1 0 0.911413 10/10 NonOverlappingTemplate
2 2 0 0 1 1 4 0 0 0 0.066882 9/10 NonOverlappingTemplate
1 1 0 1 2 3 0 1 1 0 0.534146 10/10 NonOverlappingTemplate
2 0 0 2 0 1 1 1 1 2 0.739918 10/10 NonOverlappingTemplate
2 1 0 0 2 1 0 2 1 1 0.739918 10/10 NonOverlappingTemplate
3 0 0 0 0 1 2 1 2 1 0.350485 10/10 NonOverlappingTemplate
0 1 3 0 1 1 0 1 2 1 0.534146 10/10 NonOverlappingTemplate
2 1 0 0 0 1 5 0 1 0 0.008879 10/10 NonOverlappingTemplate
1 2 1 1 2 0 2 0 1 0 0.739918 10/10 NonOverlappingTemplate
4 1 2 1 0 0 1 1 0 0 0.122325 9/10 NonOverlappingTemplate
2 0 1 2 1 1 0 1 0 2 0.739918 10/10 NonOverlappingTemplate
1 2 0 2 0 2 1 1 0 1 0.739918 10/10 NonOverlappingTemplate
0 0 3 3 0 0 1 1 2 0 0.122325 10/10 NonOverlappingTemplate
1 1 2 0 2 0 2 1 1 0 0.739918 10/10 OverlappingTemplate
10 0 0 0 0 0 0 0 0 0 0.000000 * 0/10 * Universal
1 0 1 1 2 2 3 0 0 0 0.350485 10/10 ApproximateEntropy
1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions
0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursions
0 0 1 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions
0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursions
1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions
1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions
1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursions
0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursions
0 0 0 1 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 1 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 0 0 1 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 0 0 0 0 1 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 1 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 1 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
1 0 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 1 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 1 0 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 1 0 0 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 0 0 0 1 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 1 0 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 1 0 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 0 1 0 0 0 ---- 1/1 RandomExcursionsVariant
0 0 0 0 0 0 0 1 0 0 ---- 1/1 RandomExcursionsVariant
0 3 0 1 1 0 3 0 0 2 0.122325 10/10 Serial
1 1 0 0 2 1 1 1 2 1 0.911413 10/10 Serial
0 1 1 1 0 2 1 3 0 1 0.534146 10/10 LinearComplexity包含数据的文件是一个二进制文件,包含mt19937以小endian格式输出的所有数字。它是由这个程序制作的。
#include
#include
using namespace std;
int main()
{
unsigned int n;
std::minstd_rand0 generator(1);
for (;;) {
n = generator();
fwrite(&n, sizeof n, 1, stdout);
}
return 0;
}例如,您可以运行
$ ./cppmt19937 > mt19937-seed-1.dat 几秒钟后就打断它。它会产生一些兆字节的数据。
为什么通用考试在这里做得这么好?(FWIW,同样的事情发生了到ranlux48生成器)
发布于 2019-09-23 22:18:46
对于MT作为密钥流生成器的已知弱点,另一个答案是正确的。
Maurer设计了他的测试,通过评估二进制窗口在遍历中重复次数的样本平均值(比I.I.D.更一般)。二进制源具有有限的内存和计算的熵的信源,仅基于这些特征的输出的密钥流。因此,他的检验是一个通用的熵率估计器。
因此,他不是针对特定的缺陷,而是针对结构缺陷。
参见他的论文“这里”第10-11页的讨论.后来,Coron在他的论文中使用的公式Maurer中发现了一个错误,参见这里。想必NIST测试已经考虑到了这一修正。
发布于 2019-09-23 23:52:08
恐怕你的测试哪里错了。
MT在世界各地使用,对大多数科学家来说已经足够好了。是的,它不是密码学的,在更高的维度上有一些很小的缺陷。但是NIST通用考试没有机会发现这一点。如果universal.c中简单的100行代码可以使Twister失效,那么没有人会使用它。
它的输出是零相关的,因为我通过排列测试确定符合NIST 800-90b,§5.1。我使用了snappy、lzma、bz2和zlib算法。cmix (世界上最强大的压缩机之一)不能压缩它。记住,毛雷尔的测试毕竟是一个可压缩的测试。但最重要的是,这是我的NIST通用测试的输出:-
------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
generator is
------------------------------------------------------------------------------
C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 P-VALUE PROPORTION STATISTICAL TEST
------------------------------------------------------------------------------
1 2 1 0 2 1 0 0 1 2 0.739918 10/10 Universal
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 8 for a
sample size = 10 binary sequences.Twister获得了一个10 it的示例。然后,我们必须得出结论,考虑到所有支持Twister的证据,测试方法出了问题。你的台词:-
10 0 0 0 0 0 0 0 0 0 0.000000 * 0/10 * Universal
^^ 与10在一端表明一个非常不稳定的P分布和一个巨大的测试失败。偶然发生这种情况的概率实际上是0.000000。
发布于 2021-01-18 04:27:16
我解决了。这是由于在./评估100000的低范围发生的。在这里,它必须是至少387840,但387840<100000,这是行不通的。此外,评估值必须是>=387840。
https://crypto.stackexchange.com/questions/74548
复制相似问题