Author: Fox

一、隨機數(shù)

軟件實現(xiàn)的隨機數(shù)生成器(random number generator, RNG)生成的隨機數(shù)列大多是惟定數(shù)列，因此一般被稱作偽隨機數(shù)(pseudorandom number, PRN)，而基于熱噪聲(thermal noise)、光電效應(yīng)(photoelectric effect)、放射性衰變(radioactive disintegration)等不可預(yù)知的物理現(xiàn)象實現(xiàn)的硬件隨機數(shù)生成器(hardware random number generator)生成的隨機數(shù)才被認(rèn)為是真隨機數(shù)(truly random number)。PRN在計算機領(lǐng)域主要用于仿真(simulation)和密碼學(xué)(cryptography)。

本文僅討論偽隨機數(shù)軟件實現(xiàn)算法，并且僅討論滿足均勻分布(uniform distribution, UD)的偽隨機數(shù)發(fā)生器(pseudorandom number generator, PRNG)。非均勻分布(non-uniform distribution, NUD)的PRNG可通過滿足均勻分布的PRNG與非線性函數(shù)生成。

本文討論的PRNG應(yīng)滿足以下三點：

a. 在取值空間內(nèi)滿足UD，即等概率取得取值空間內(nèi)任意值。

b. 充分隨機，即該隨機數(shù)列周期(period)應(yīng)盡量長。此點由所謂的熵(entropy)度量。

c. 唯一輸入或稱種子(seed)對應(yīng)唯一輸出PRN。這一點ms是計算機的強項，也是PRN惟定的根源，也是算法被破解的根源。

由于PRN sequence(PRNS)惟定，所以算法的安全性主要取決于熵的選擇和算法的復(fù)雜性。

二、可預(yù)測PRNG與不可預(yù)測PRNG

所謂可預(yù)測(determined)PRNG，也被稱為統(tǒng)計意義上的PRNG(statistic PRNG)，一般只有一個seed，而對于同一個seed，生成的PRNS是惟定的。

不可預(yù)測(indetermined)PRNG，從理論上講，不可預(yù)測的PRNG是不存在的，這兒指密碼學(xué)安全的PRNG(cryptographically secure PRNG, CSPRNG)。

三、常用PRNGs

1、線性同余發(fā)生器(linear congruential generators, LCG)

單博偉在標(biāo)準(zhǔn)庫rand()函數(shù)的缺陷以及Blitz++隨機數(shù)生成的簡介中給出了The C Programming Langurage 2nd的實現(xiàn)，我手頭沒有這本書，所以無從查證，FallHunter應(yīng)該還有吧。

?1 unsigned? int ?next? = ? 1 ;
?2
?3 /**/ /* ?rand:?return?pseudo-random?integer?on?0..32767? */
?4 int ?rand( void )
?5 {
?6 ?next? = ?next? * ? 1103515245 ? + ? 12345 ;
?7 ? return ?(unsigned? int )(next / 65536 )? % ? 32768 ;
?8 }
?9
10 /**/ /* ?srand:?set?seed?for?rand()? */
11 void ?srand(unsigned? int ?seed)
12 {
13 ?next? = ?seed;
14 }

VS2003中給的實現(xiàn)是：

?1 /**/ /* **
?2 *rand.c?-?random?number?generator
?3 *
?4 *???????Copyright?(c)?Microsoft?Corporation.?All?rights?reserved.
?5 *
?6 *Purpose:
?7 *???????defines?rand(),?srand()?-?random?number?generator
?8 *
?9 ****************************************************************************** */
10
11 #include? < cruntime.h >
12 #include? < mtdll.h >
13 #include? < stddef.h >
14 #include? < stdlib.h >
15
16 #ifndef?_MT
17 static ? long ?holdrand? = ? 1L ;
18 #endif ??/*?_MT?*/
19
20 /**/ /* **
21 *void?srand(seed)?-?seed?the?random?number?generator
22 *
23 *Purpose:
24 *???????Seeds?the?random?number?generator?with?the?int?given.??Adapted?from?the
25 *???????BASIC?random?number?generator.
26 *
27 *Entry:
28 *???????unsigned?seed?-?seed?to?seed?rand?#?generator?with
29 *
30 *Exit:
31 *???????None.
32 *
33 *Exceptions:
34 *
35 ****************************************************************************** */
36
37 void ?__cdecl?srand?(
38 ????????unsigned? int ?seed
39 ????????)
40 {
41 #ifdef?_MT
42
43 ????????_getptd() -> _holdrand? = ?(unsigned? long )seed;
44
45 #else ??/*?_MT?*/
46 ????????holdrand? = ?( long )seed;
47 #endif ??/*?_MT?*/
48 }
49
50
51 /**/ /* **
52 *int?rand()?-?returns?a?random?number
53 *
54 *Purpose:
55 *???????returns?a?pseudo-random?number?0?through?32767.
56 *
57 *Entry:
58 *???????None.
59 *
60 *Exit:
61 *???????Returns?a?pseudo-random?number?0?through?32767.
62 *
63 *Exceptions:
64 *
65 ****************************************************************************** */
66
67 int ?__cdecl?rand?(
68 ???????? void
69 ????????)
70 {
71 #ifdef?_MT
72
73 ????????_ptiddata?ptd? = ?_getptd();
74
75 ???????? return (?((ptd -> _holdrand? = ?ptd -> _holdrand? * ? 214013L
76 ???????????? + ? 2531011L )? >> ? 16 )? & ? 0x7fff ?);
77
78 #else ??/*?_MT?*/
79 ???????? return (((holdrand? = ?holdrand? * ? 214013L ? + ? 2531011L )? >> ? 16 )? & ? 0x7fff );
80 #endif ??/*?_MT?*/
81 }

2、LFG, LFSR等

限于篇幅，有興趣的TX可以參考后面的資料，主要是Wikipedia，上面給的算法還是非常詳細(xì)的，CSPRNGs包括Blum Blum Shub、Fortuna等。

如果出于安全性的考慮，PRNG的輸出不應(yīng)直接作為種子。在《構(gòu)建安全的軟件》一書中，作者認(rèn)為“一個好的PRNG具有這樣的性質(zhì)：給足夠的熵，即使攻擊者知道全部的算法細(xì)節(jié)，還是不能猜出生成的數(shù)據(jù)流”。

三、PRNG的安全測試

FIPS-140標(biāo)準(zhǔn)包含了對RNs的測試規(guī)范。這個標(biāo)準(zhǔn)我也沒有去仔細(xì)看，所以沒法給出更多的信息。被提到的測試包有DIEHARD、pLab。

四、隨機數(shù)在游戲中的應(yīng)用

1、隨機數(shù)為游戲帶來更多的不確定性，不確定性產(chǎn)生可玩性

這個應(yīng)該是所有游戲的根本了吧。游戲中玩家、怪物、NPC的很多屬性都是一個范圍，比如攻擊就有最小攻擊和最大攻擊，每次的實際攻擊傷害總在二者之間。

同樣的，玩家樂此不疲的一次次“洗裝備”、“碰運氣”。其他類推吧?。

2、游戲的AI更多的依賴于隨機數(shù)

如果怪物、NPC的AI一切盡在玩家的掌握中，游戲的樂趣就大大降低了，這一點在單機游戲中有著很好的體現(xiàn)。War3中，人機對戰(zhàn)，電腦的戰(zhàn)術(shù)并不單一（但還是有規(guī)律可循，人類玩家尚且如此），這其中固然有多方面 的因素。但隨機數(shù)的功勞也不容抹殺。

3、隨機數(shù)減少數(shù)據(jù)存儲，一個種子可以代替一批數(shù)據(jù)

游戲中含有大量數(shù)據(jù)，如果每一項都要存取，對時間和空間都是一個考驗。對于場景中隨機生成的怪物信息，如果給定一個相同的種子。呃，是不是要簡單一些呢？

五、相關(guān)內(nèi)容

至于為什么PRNGs大多使用素數(shù)，需要更多的數(shù)論知識，對密碼學(xué)有了解的TX應(yīng)該能夠體會到安全和數(shù)論之間的緊密聯(lián)系。因為手頭沒有數(shù)論的書，所以不多加妄測了。到時寫論文的時候，再填充上吧。

六、參考文獻

1. 構(gòu)建安全的軟件. [美]John Viega, Gary McGraw. 鐘向群, 王鵬 譯.? 北京. 清華大學(xué)出版社, 2003.

2. Pseudorandom number generator及相關(guān)鏈接. http://en.wikipedia.org/wiki/Pseudorandom_number_generator

3. PRNG - Pseudo-Random Number Generator. http://statmath.wu-wien.ac.at/prng/

-------------------------------------------------------------------------

PS01：手上的幾本書

從幾位TX那兒拿的幾本書，放在桌上大半年了，一直沒有怎么翻過。想想周末還給他們算了，于是就拿過來翻翻，立此存照，如果以后用到的話，再來查。

a. 《用TCP/IP進行網(wǎng)際互聯(lián)》Vol. III，主要是針對Linux/POSIX套接字的C/S架構(gòu)實現(xiàn)。因為MMORPG的C/S架構(gòu)多依賴于TCP，上面第8、10-16章的內(nèi)容可以關(guān)注一下。

b. 《構(gòu)建安全的軟件》，上面關(guān)于開源、閉源的口水(Chap. 4)，關(guān)于緩沖區(qū)溢出(Chap. 7)，關(guān)于隨機數(shù)(Chap. 10)，關(guān)于數(shù)據(jù)庫安全(Chap. 14)，關(guān)于客戶端安全(Chap. 15)，都是值得一看的東西。

c. 《UNIX環(huán)境高級編程》，進程控制(Chap. 8)、線程控制(Chap. 12)、進程通信(Chap. 15, 17)、套接字(Chap. 16)、數(shù)據(jù)庫(Chap. 20)。

d. 《UNIX網(wǎng)絡(luò)編程》Vol.I，如果涉及到泛UNIX操作系統(tǒng)下網(wǎng)絡(luò)編程，可以當(dāng)作參考書翻。

e. 《計算機安全原理》，加密(Chap. 5)、認(rèn)證(Chap. 6)、協(xié)議安全(Chap. 7)、入侵檢測(Chap. 13)、惡意攻擊(Chap. 15)、災(zāi)難恢復(fù)(Chap. 19)。

PS02：微軟宣布不會抬高收購Yahoo價格

消息來自Wall Street Journal，不過當(dāng)天可是April Fool。

PS03：關(guān)于Wikipedia

不是說Wikipedia被禁的嗎？很久沒有訪問過了，這么好的東西，被封了還是很遺憾的。

PS04：有問題

發(fā)現(xiàn)問題，找Google；解決問題，找Wikipedia。

PS05：歡迎補充

-------------------------------------------------------------------------

Added on Apr.10th

今天從CodeProject上看到一篇文章Applied Crypto++: Pseudo Random Number Generators)，作者Jeffrey Walton對密碼學(xué)和安全比較有研究。

Jeffrey Walton對Knuth的The Art of Computer Programming Vol.2中關(guān)于隨機數(shù)的部分作了概括。

這篇文章從一個工程師的角度給出了隨機數(shù)的應(yīng)用和實現(xiàn)，很具有參考性。

作者還從FIPS 140-2標(biāo)準(zhǔn)中引用了下面一段話：

Random Number Generators fall into one of two classes: deterministic and nondeterministic. A deterministic RNG consists of an algorithm that produces a sequence of bits from an initial value called a seed. A nondeterministic RNG produces output that is dependent on some unpredictable physical source that is outside human control.

這一段話很好的說明，依賴于算法的RNG所生成的隨機數(shù)列只可能是偽隨機數(shù)，真隨機數(shù)依賴于不可預(yù)測的物理源。