CSPRNG必须通过统计随机性测试，MWC RNG似乎可以满足这一要求。另外，MWC PRNG允许您选择
c < 809430660，它看起来足够大，使人们很难分析选择了MWC PRNG的809430659选项中的哪一个。最后但并非最不重要的一点是，人们称其为“所有RNG的母亲”（请参见George Marsaglia的“所有RNG的母亲”（带有注释的C代码）（通过archive.org）），这意味着它是目前最好的（P）RNG .. 将MWC PRNG与加密安全的PRNG进行比较，结果表明两者都是伪随机的，都产生可比较的随机性，并且都通过了相同的统计检验。有人甚至声称它具有加密质量。但是，我找不到单一的迹象表明它是加密安全的。
因此，我想知道并问：“是什么阻止了MWC PRNG成为CSPRNG？”
或者，换句话说：
缺少CSPRNG的MWC PRNG是什么，应该必须是加密安全的，和/或
MWC PRNG有什么CSPRNG？不必必须具有加密安全性吗？
当前，我怀疑我缺少与加密安全伪随机数生成器相关的一些安全定义，或者也许我没有看到明显的安全问题，该问题使MWC PRNG加密不安全。因此，每一个可以帮助我理解为什么MWC PRNG未能归类为加密安全PRNG的解释都受到高度赞赏。
万一有人需要有关MWC PRNG的参考信息...
MWC的通用维基百科说明
乔治·玛格萨利亚的“所有RNG的母亲”（带注释的C代码）（通过archive.org）
由于伯克利显然在服务器清理期间删除了George Marsaglia的所有工作，所以才发布了stat.berkeley.edu/classes/s243/mother.c此处仅供参考：
/*
Article: 16024 of sci.math.num-analysis
Xref: taurus.cs.nps.navy.mil sci.stat.consult:7790 sci.math.num-analysis:16024
Path: taurus.cs.nps.navy.mil!lll-winken.llnl.gov!uwm.edu!news.alpha.net!news.mathworks.com!udel!ssnet.com!usenet
From: Bob Wheeler <bwheeler@ssnet.com>
Newsgroups: sci.stat.consult,sci.math.num-analysis
Subject: Marsaglia's Mother of all RNG's (Long?)
Date: Fri, 28 Oct 94 19:32:08 EDT
Organization: SSNet -- Public Internet Access in Delaware!
Lines: 285
Distribution: inet
Message-ID: <38s2p1$qaf@marlin.ssnet.com>
NNTP-Posting-Host: echip.com
Mime-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Newsreader: NEWTNews & Chameleon -- TCP/IP for MS Windows from NetManage
Several people have asked me to post this:
First the C program, then George Marsaliga's post with details
about the RNG. He claims a period of about 2^250 for this and
that it passes all of the usual tests. I've tried it enough
to be sure his claim is reasonable.
The program:
*/
#include <string.h>
static short mother1[10];
static short mother2[10];
static short mStart=1;
#define m16Long 65536L /* 2^16 */
#define m16Mask 0xFFFF /* mask for lower 16 bits */
#define m15Mask 0x7FFF /* mask for lower 15 bits */
#define m31Mask 0x7FFFFFFF /* mask for 31 bits */
#define m32Double 4294967295.0 /* 2^32-1 */
/* Mother **************************************************************
| George Marsaglia's The mother of all random number generators
| producing uniformly distributed pseudo random 32 bit values
with
| period about 2^250.
| The text of Marsaglia's posting is appended at the end of the function.
|
| The arrays mother1 and mother2 store carry values in their
| first element, and random 16 bit numbers in elements 1 to 8.
| These random numbers are moved to elements 2 to 9 and a new
| carry and number are generated and placed in elements 0 and 1.
| The arrays mother1 and mother2 are filled with random 16 bit values
| on first call of Mother by another generator. mStart is the
switch.
|
| Returns:
| A 32 bit random number is obtained by combining the output of the
| two generators and returned in *pSeed. It is also scaled by
| 2^32-1 and returned as a double between 0 and 1
|
| SEED:
| The inital value of *pSeed may be any long value
|
| Bob Wheeler 8/8/94
*/
double Mother(unsigned long *pSeed)
{
unsigned long number,
number1,
number2;
short n,
*p;
unsigned short sNumber;
/* Initialize motheri with 9 random values the first time */
if (mStart) {
sNumber= *pSeed&m16Mask; /* The low 16 bits */
number= *pSeed&m31Mask; /* Only want 31 bits */
p=mother1;
for (n=18;n--;) {
number=30903*sNumber+(number>>16); /* One line
multiply-with-cary */
*p++=sNumber=number&m16Mask;
if (n==9)
p=mother2;
}
/* make cary 15 bits */
mother1[0]&=m15Mask;
mother2[0]&=m15Mask;
mStart=0;
}
/* Move elements 1 to 8 to 2 to 9 */
memmove(mother1+2,mother1+1,8*sizeof(short));
memmove(mother2+2,mother2+1,8*sizeof(short));
/* Put the carry values in numberi */
number1=mother1[0];
number2=mother2[0];
/* Form the linear combinations */
number1+=1941*mother1[2]+1860*mother1[3]+1812*mother1[4]+1776*mother1[5]+
1492*mother1[6]+1215*mother1[7]+1066*mother1[8]+12013*mother1[9];
number2+=1111*mother2[2]+2222*mother2[3]+3333*mother2[4]+4444*mother2[5]+
5555*mother2[6]+6666*mother2[7]+7777*mother2[8]+9272*mother2[9];
/* Save the high bits of numberi as the new carry */
mother1[0]=number1/m16Long;
mother2[0]=number2/m16Long;
/* Put the low bits of numberi into motheri[1] */
mother1[1]=m16Mask&number1;
mother2[1]=m16Mask&number2;
/* Combine the two 16 bit random numbers into one 32 bit */
*pSeed=(((long)mother1[1])<<16)+(long)mother2[1];
/* Return a double value between 0 and 1 */
return ((double)*pSeed)/m32Double;
}
/*
*********************
Marsaglia's comments
Yet another RNG
Random number generators are frequently posted on
the network; my colleagues and I posted ULTRA in
1992 and, from the number of requests for releases
to use it in software packages, it seems to be
widely used.
I have long been interested in RNG's and several
of my early ones are used as system generators or
in statistical packages.
So why another one? And why here?
Because I want to describe a generator, or
rather, a class of generators, so promising
I am inclined to call it
The Mother of All Random Number Generators
and because the generator seems promising enough
to justify shortcutting the many months, even
years, before new developments are widely
known through publication in a journal.
This new class leads to simple, fast programs that
produce sequences with very long periods. They
use multiplication, which experience has shown
does a better job of mixing bits than do +,- or
exclusive-or, and they do it with easily-
implemented arithmetic modulo a power of 2, unlike
arithmetic modulo a prime. The latter, while
satisfactory, is difficult to implement. But the
arithmetic here modulo 2^16 or 2^32 does not suffer
the flaws of ordinary congruential generators for
those moduli: trailing bits too regular. On the
contrary, all bits of the integers produced by
this new method, whether leading or trailing, have
passed extensive tests of randomness.
Here is an idea of how it works, using, say, integers
of six decimal digits from which we return random 3-
digit integers. Start with n=123456, the seed.
Then form a new n=672*456+123=306555 and return 555.
Then form a new n=672*555+306=373266 and return 266.
Then form a new n=672*266+373=179125 and return 125,
and so on. Got it? This is a multiply-with-carry
sequence x(n)=672*x(n-1)+ carry mod b=1000, where
the carry is the number of b's dropped in the
modular reduction. The resulting sequence of 3-
digit x's has period 335,999. Try it.
No big deal, but that's just an example to give
the idea. Now consider the sequence of 16-bit
integers produced by the two C statements:
k=30903*(k&65535)+(k>>16); return(k&65535);
Notice that it is doing just what we did in the
example: multiply the bottom half (by 30903,
carefully chosen), add the top half and return the
new bottom.
That will produce a sequence of 16-bit integers
with period > 2^29, and if we concatenate two
such:
k=30903*(k&65535)+(k>>16);
j=18000*(j&65535)+(j>>16);
return((k<<16)+j);
we get a sequence of more than 2^59 32-bit integers
before cycling.
The following segment in a (properly initialized)
C procedure will generate more than 2^118
32-bit random integers from six random seed values
i,j,k,l,m,n:
k=30903*(k&65535)+(k>>16);
j=18000*(j&65535)+(j>>16);
i=29013*(i&65535)+(i>>16);
l=30345*(l&65535)+(l>>16);
m=30903*(m&65535)+(m>>16);
n=31083*(n&65535)+(n>>16);
return((k+i+m)>>16)+j+l+n);
And it will do it much faster than any of several
widely used generators designed to use 16-bit
integer arithmetic, such as that of Wichman-Hill
that combines congruential sequences for three
15-bit primes (Applied Statistics, v31, p188-190,
1982), period about 2^42.
I call these multiply-with-carry generators. Here
is an extravagant 16-bit example that is easily
implemented in C or Fortran. It does such a
thorough job of mixing the bits of the previous
eight values that it is difficult to imagine a
test of randomness it could not pass:
x[n]=12013x[n-8]+1066x[n-7]+1215x[n-6]+1492x[n-5]+1776x[n-4]
+1812x[n-3]+1860x[n-2]+1941x[n-1]+carry mod 2^16.
The linear combination occupies at most 31 bits of
a 32-bit integer. The bottom 16 is the output, the
top 15 the next carry. It is probably best to
implement with 8 case segments. It takes 8
microseconds on my PC. Of course it just provides
16-bit random integers, but awfully good ones. For
32 bits you would have to combine it with another,
such as
x[n]=9272x[n-8]+7777x[n-7]+6666x[n-6]+5555x[n-5]+4444x[n-4]
+3333x[n-3]+2222x[n-2]+1111x[n-1]+carry mod 2^16.
Concatenating those two gives a sequence of 32-bit
random integers (from 16 random 16-bit seeds),
period about 2^250. It is so awesome it may merit
the Mother of All RNG's title.
The coefficients in those two linear combinations
suggest that it is easy to get long-period
sequences, and that is true. The result is due to
Cemal Kac, who extended the theory we gave for
add-with-carry sequences: Choose a base b and give
r seed values x[1],...,x[r] and an initial 'carry'
c. Then the multiply-with-carry sequence
x[n]=a1*x[n-1]+a2*x[n-2]+...+ar*x[n-r]+carry mod b,
where the new carry is the number of b's dropped
in the modular reduction, will have period the
order of b in the group of residues relatively
prime to m=ar*b^r+...+a1b^1-1. Furthermore, the
x's are, in reverse order, the digits in the
expansion of k/m to the base b, for some 0<k<m.
In practice b=2^16 or b=2^32 allows the new
integer and the new carry to be the bottom and top
half of a 32- or 64-bit linear combination of 16-
or 32-bit integers. And it is easy to find
suitable m's if you have a primality test: just
search through candidate coefficients until you
get an m that is a safeprime---both m and (m-1)/2
are prime. Then the period of the multiply-with-
carry sequence will be the prime (m-1)/2. (It
can't be m-1 because b=2^16 or 2^32 is a square.)
Here is an interesting simple MWC generator with
period> 2^92, for 32-bit arithmetic:
x[n]=1111111464*(x[n-1]+x[n-2]) + carry mod 2^32.
Suppose you have functions, say top() and bot(),
that give the top and bottom halves of a 64-bit
result. Then, with initial 32-bit x, y and carry
c, simple statements such as
y=bot(1111111464*(x+y)+c)
x=y
c=top(y)
will, repeated, give over 2^92 random 32-bit y's.
Not many machines have 64 bit integers yet. But
most assemblers for modern CPU's permit access to
the top and bottom halves of a 64-bit product.
I don't know how to readily access the top half of
a 64-bit product in C. Can anyone suggest how it
might be done? (in integer arithmetic)
George Marsaglia geo@stat.fsu.edu
*/
这是Marsaglia原始出版物的副本，该出版物最初在sci上发布.stat.math…
良好的C随机数生成器
来自：George Marsaglia（geo@stat.fsu.edu）
主题：回复：良好的C随机数字生成器
新闻组：comp.lang.c
日期：2003-05-13 08:55:05 PST
组织：佛罗里达州立大学
行数：89
大多数RNG的工作方式是保留一定数量（例如k）的最新生成的整数，然后返回下一个int eger是那些k的函数。假定最初的k个整数（种子）是随机选择的，通常为32位。 RNG的周期与种子的选择数量有关，通常为2 ^（32k），因此要获得更长的周期，您需要增加k。
最常见的类型可能是k = 1 ，并且需要一个种子，每个新整数都是前一个的函数。同构的RNG就是一个例子，多年来一直是VAX中的系统RNG的一种形式：
/* a random initial x to be assigned by the calling program */
static unsigned long x=123456789;
unsigned long cong(void )
{
return (x=69069*x+362437);
}
简单，k = 1，RNG可以在随机性测试中表现出色，例如新版Diehard中的随机性测试。
从k介于4或5到最高4097的RNG中。
这是一个示例，其中k = 5，周期大约2 ^ 160，是最快的长周期RNG之一，返回的值大于120百万随机32位整数/秒（1.8MHz CPU），似乎可以通过所有测试：
另一个示例的k = 257，周期约为2 ^ 8222。使用一个静态数组Q [256]和一个初始进位'c'，该Q数组在调用程序中填充有256个随机的32位整数，并且对于进位乘法运算使用初始进位c <809430660。它非常快速，并且似乎通过了所有测试。
csis.hku.hk/~diehard
Mersenne Twister（检查Google）是一款出色的RNG，k = 624。但是它需要精心设计的C程序，并且比许多在测试中同样出色的RNG慢，具有可比或更长的周期，并且只需要几行代码。
以k = 4097进行RNG传输，并且记录时间接近记录，是Twister的10 ^ 33000倍以上。 （2 ^ 131104与2 ^ 19937）
/* replace defaults with five random seed values in calling program */
static unsigned long x=123456789,y=362436069,z=521288629,w=88675123,v=886756453;
unsigned long xorshift(void)
{
unsigned long t;
t=(x^(x>>7));
x=y;
y=z;
z=w;
w=v;
v=(v^(v<<6))^(t^(t<<13));
return (y+y+1)*v;
}
在ACM 2003年5月的通讯中，您还将发现更多CMWC RNG和有关种子选择的评论。 br />
乔治·马萨利亚
#1 楼
它不是可加密的PRNG，因为它是可预测的：给定一些输出，您可以预测下一个输出。例如，如果您观察到偏移量0、1，和4096处的输出，则可以预测偏移量4097处的输出。它所缺少的是：不是缺少一些小的调整（只需将第7行更改为使用加法而不是xor即可）。它所缺少的是，从根本上讲，它并不是设计来具有强大的加密功能。需要以与非加密PRNG截然不同的方式来设计加密强度高的PRNG。它被设计为非加密PRNG，这就是事实。特别是，听起来好像MWC的设计时间很长。但是长期使用并不能保证PRNG的加密强度。不在附近。加密强度PRNG的要求要高得多，因此没有理由期望统计非加密PRNG在密码学上会很强大（如果没有设计的话，几乎肯定不会）。如果您想要一种加密强度的PRNG，则需要从一开始就选择一种设计成这种方式的PRNG。您选择非加密的PRNG，然后尝试对其进行调整，就不太可能会顺利。
无论如何，我不确定为什么会出现这个问题。我们拥有安全，快速且经过严格审查的加密强度PRNG。我不知道为什么有人会试图基于一种非加密的PRNG设计自己的东西。这样会导致不安全感。如果您认为在设计快速加密强度的PRNG上可以比整个领域做得更好...那么，也许您可以，但是我怀疑您身边的可能性。相反，如果需要加密质量的伪随机数，我建议您使用标准的加密强度PRNG。
评论
$ \ begingroup $
维基百科对“安全”的含义有一个合理的解释。请注意，没有一个RNG可以“通过保留一定数量（例如k个）的最新生成的整数，然后将下一个整数作为这些k的函数来工作”，才能满足下一个比特测试，因为任何看到过它的k个最近生成的整数的人都可以预测其整个将来的输出。
$ \ endgroup $
–戈登·戴维森（Gordon Davisson）
2013年9月15日18:25
#2 楼
即使它通过了一些统计测试，也很难通过3维的光谱测试。您可以使用R复制它：RNGkind("Marsaglia-Multicarry")
RNG <- runif(10000000)
RNG.data <- data.frame(RNG.R)
RNG.data$id <- as.numeric(row.names(RNG.data))
library("rgl")
plot3d (RNG.data[1:9998,1],
RNG.data[2:9999,1],
RNG.data[3:10000,1])
评论
本文可能会有所帮助：eprint.iacr.org/2011/007简短的故事是，鉴于MWC的输出，恢复内部状态并从那里做各种坏事是很容易的。我认为“所有RNG的母亲”主要是历史性的描述，而不是高质量的描述：许多其他RNG后来出现并借鉴了其设计。