Security-Definition
是什麼阻止 Multiply-With-Carry RNG 成為加密安全的 PRNG？
儘管 Marsaglia 的 MWC PRNG（帶進位乘法隨機數生成器）被認為是*“所有 RNG 之母”，但它似乎並不被認為是 CSPRNG（加密安全偽隨機數生成器），甚至儘管它通過了多項統計隨機性測試，包括ENT和Die-Hard*。
考慮到可以定義種子等，CSPRNG 所缺少的 MWC RNG 是什麼？Simpler 問道：“是什麼阻止了 MWC PRNG 成為 CSPRNG？”
CSPRNG 必須通過 MWC RNG 似乎滿足的統計隨機性測試。此外，MWC PRNG 允許您選擇隨機初始只要
c < 809430660，這似乎足以讓人們難以分析您選擇了哪個 809430659 選項作為 MWC PRNG 的種子。最後但同樣重要的是，人們稱它為“所有 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 的一般維基百科描述
- George Marsaglia 的“所有 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)
主題：Re：好的 C 隨機數發生器
新聞組：comp.lang.c
日期：2003-05-13 08:55:05 PST
組織：佛羅里達州立大學
線路：89
大多數 RNG 的工作方式是保留一定數量的最近生成的整數，比如 k，然後返回下一個整數作為這些 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，
csis.hku.hk/~diehard但經驗表明，更好的性能來自於 k 範圍從 4 或 5 到高達 4097 的 RNG。
這是一個 k=5 的範例，週期約為 2^160，是最快的長周期 RNG 之一，每秒返回超過 1.2 億個隨機 32 位整數（1.8MHz CPU），似乎通過了所有測試：
/* 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; }另一個例子有 k=257，週期約為 2^8222。使用靜態數組 Q
$$ 256 $$和一個初始進位“c”，Q 數組在呼叫程序中填充了 256 個隨機 32 位整數，初始進位 c<809430660 用於進位乘法運算。它非常快，似乎通過了所有測試。
/* choose random initial c<809430660 and 256 random 32-bit integers for Q[] */ static unsigned long Q[256],c=362436; unsigned long MWC256(void) { unsigned long long t,a=809430660LL; static unsigned char i=255; t=a*Q[++i]+c; c=(t>>32); return(Q[i]=t); }Mersenne Twister（查看Google）是一個優秀的 RNG，k=624。但它需要一個複雜的 C 程序，並且比許多在測試中表現良好、週期相當或更長並且只需要幾行程式碼的 RNG 慢。
這是一個帶有 k=4097 和接近記錄週期的互補乘法 RNG，是 Twister 的 10^33000 倍以上。（2^131104 與 2^19937）
/* choose random initial c<809430660 and 4096 random 32-bit integers for Q[] */ static unsigned long Q[4096],c=362436; unsigned long CMWC4096(void) { unsigned long long t, a=18782LL; static unsigned long i=4095; unsigned long x,r=0xfffffffe; i=(i+1)&4095; t=a*Q[i]+c; c=(t>>32); x=t+c; if(x<c) { x++; c++; } return(Q[i]=r-x); }您可以在 2003 年 5 月的 ACM 通訊中找到更多 CMWC RNG 和關於種子選擇的評論。
喬治·馬薩利亞
它不是加密強的 PRNG，因為它是可預測的：給定一些輸出，您可以預測下一個輸出。例如，如果您觀察偏移量 0、1 和 4096 處的輸出，您可以預測偏移量 4097 處的輸出。
它缺少什麼：並不是缺少一些小調整（只需將第 7 行更改為使用加法而不是 xor，類似的東西）。它缺少的是，它從根本上不是設計成具有加密強度的。加密強 PRNG 需要以與非加密 PRNG 截然不同的方式設計。這被設計為非加密 PRNG，就是這樣。特別是，聽起來 MWC 的設計週期很長。但是時間長並不能保證 PRNG 具有加密強度；不在它附近。加密強度 PRNG 的要求要高得多，因此沒有理由期望統計的非加密 PRNG 具有加密強度（如果不是設計成這樣，它幾乎肯定不會如此）。如果你想要一個加密強度的 PRNG，你需要選擇一個從一開始就是這樣設計的；通過選擇非加密 PRNG 然後嘗試對其進行調整，您不太可能過得很好。
無論如何，我不確定為什麼會出現這個問題。我們擁有安全、快速且經過嚴格審查的加密強度 PRNG。我不知道為什麼有人會嘗試基於非加密 PRNG 來設計自己的；這種方式會導致不安全感。如果你認為你可以在設計快速加密強度 PRNG 方面做得比整個領域都好……好吧，也許你可以，但我懷疑你的勝算。相反，如果您需要加密質量的偽隨機數，我建議您使用標準的加密強度 PRNG。