Author: Fox
一、隨機(jī)數(shù)
軟件實(shí)現(xiàn)的隨機(jī)數(shù)生成器(random number generator, RNG)生成的隨機(jī)數(shù)列大多是惟定數(shù)列，因此一般被稱作偽隨機(jī)數(shù)(pseudorandom number, PRN)，而基于熱噪聲(thermal noise)、光電效應(yīng)(photoelectric effect)、放射性衰變(radioactive disintegration)等不可預(yù)知的物理現(xiàn)象實(shí)現(xiàn)的硬件隨機(jī)數(shù)生成器(hardware random number generator)生成的隨機(jī)數(shù)才被認(rèn)為是真隨機(jī)數(shù)(truly random number)。PRN在計(jì)算機(jī)領(lǐng)域主要用于仿真(simulation)和密碼學(xué)(cryptography)。
本文僅討論偽隨機(jī)數(shù)軟件實(shí)現(xiàn)算法，并且僅討論滿足均勻分布(uniform distribution, UD)的偽隨機(jī)數(shù)發(fā)生器(pseudorandom number generator, PRNG)。非均勻分布(non-uniform distribution, NUD)的PRNG可通過滿足均勻分布的PRNG與非線性函數(shù)生成。
本文討論的PRNG應(yīng)滿足以下三點(diǎn)：
a. 在取值空間內(nèi)滿足UD，即等概率取得取值空間內(nèi)任意值。
b. 充分隨機(jī)，即該隨機(jī)數(shù)列周期(period)應(yīng)盡量長。此點(diǎn)由所謂的熵(entropy)度量。
c. 唯一輸入或稱種子(seed)對應(yīng)唯一輸出PRN。這一點(diǎn)ms是計(jì)算機(jī)的強(qiáng)項(xiàng)，也是PRN惟定的根源，也是算法被破解的根源。
由于PRN sequence(PRNS)惟定，所以算法的安全性主要取決于熵的選擇和算法的復(fù)雜性。
二、可預(yù)測PRNG與不可預(yù)測PRNG
所謂可預(yù)測(determined)PRNG，也被稱為統(tǒng)計(jì)意義上的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++隨機(jī)數(shù)生成的簡介中給出了The C Programming Langurage 2nd的實(shí)現(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中給的實(shí)現(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。
四、隨機(jī)數(shù)在游戲中的應(yīng)用
1、隨機(jī)數(shù)為游戲帶來更多的不確定性，不確定性產(chǎn)生可玩性
這個應(yīng)該是所有游戲的根本了吧。游戲中玩家、怪物、NPC的很多屬性都是一個范圍，比如攻擊就有最小攻擊和最大攻擊，每次的實(shí)際攻擊傷害總在二者之間。
同樣的，玩家樂此不疲的一次次“洗裝備”、“碰運(yùn)氣”。其他類推吧?。
2、游戲的AI更多的依賴于隨機(jī)數(shù)
如果怪物、NPC的AI一切盡在玩家的掌握中，游戲的樂趣就大大降低了，這一點(diǎn)在單機(jī)游戲中有著很好的體現(xiàn)。War3中，人機(jī)對戰(zhàn)，電腦的戰(zhàn)術(shù)并不單一（但還是有規(guī)律可循，人類玩家尚且如此），這其中固然有多方面 的因素。但隨機(jī)數(shù)的功勞也不容抹殺。
3、隨機(jī)數(shù)減少數(shù)據(jù)存儲，一個種子可以代替一批數(shù)據(jù)
游戲中含有大量數(shù)據(jù)，如果每一項(xiàng)都要存取，對時間和空間都是一個考驗(yàn)。對于場景中隨機(jī)生成的怪物信息，如果給定一個相同的種子。呃，是不是要簡單一些呢？
五、相關(guān)內(nèi)容
至于為什么PRNGs大多使用素?cái)?shù)，需要更多的數(shù)論知識，對密碼學(xué)有了解的TX應(yīng)該能夠體會到安全和數(shù)論之間的緊密聯(lián)系。因?yàn)槭诸^沒有數(shù)論的書，所以不多加妄測了。到時寫論文的時候，再填充上吧。
六、參考文獻(xiàn)
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進(jìn)行網(wǎng)際互聯(lián)》Vol. III，主要是針對Linux/POSIX套接字的C/S架構(gòu)實(shí)現(xiàn)。因?yàn)镸MORPG的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)于隨機(jī)數(shù)(Chap. 10)，關(guān)于數(shù)據(jù)庫安全(Chap. 14)，關(guān)于客戶端安全(Chap. 15)，都是值得一看的東西。
c. 《UNIX環(huán)境高級編程》，進(jìn)程控制(Chap. 8)、線程控制(Chap. 12)、進(jìn)程通信(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. 《計(jì)算機(jī)安全原理》，加密(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：歡迎補(bǔ)充
-------------------------------------------------------------------------
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)于隨機(jī)數(shù)的部分作了概括。
這篇文章從一個工程師的角度給出了隨機(jī)數(shù)的應(yīng)用和實(shí)現(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所生成的隨機(jī)數(shù)列只可能是偽隨機(jī)數(shù)，真隨機(jī)數(shù)依賴于不可預(yù)測的物理源。