Author: Fox
一、隨機數
軟件實現的隨機數生成器(random number generator, RNG)生成的隨機數列大多是惟定數列，因此一般被稱作偽隨機數(pseudorandom number, PRN)，而基于熱噪聲(thermal noise)、光電效應(photoelectric effect)、放射性衰變(radioactive disintegration)等不可預知的物理現象實現的硬件隨機數生成器(hardware random number generator)生成的隨機數才被認為是真隨機數(truly random number)。PRN在計算機領域主要用于仿真(simulation)和密碼學(cryptography)。
本文僅討論偽隨機數軟件實現算法，并且僅討論滿足均勻分布(uniform distribution, UD)的偽隨機數發生器(pseudorandom number generator, PRNG)。非均勻分布(non-uniform distribution, NUD)的PRNG可通過滿足均勻分布的PRNG與非線性函數生成。
本文討論的PRNG應滿足以下三點：
a. 在取值空間內滿足UD，即等概率取得取值空間內任意值。
b. 充分隨機，即該隨機數列周期(period)應盡量長。此點由所謂的熵(entropy)度量。
c. 唯一輸入或稱種子(seed)對應唯一輸出PRN。這一點ms是計算機的強項，也是PRN惟定的根源，也是算法被破解的根源。
由于PRN sequence(PRNS)惟定，所以算法的安全性主要取決于熵的選擇和算法的復雜性。
二、可預測PRNG與不可預測PRNG
所謂可預測(determined)PRNG，也被稱為統計意義上的PRNG(statistic PRNG)，一般只有一個seed，而對于同一個seed，生成的PRNS是惟定的。
不可預測(indetermined)PRNG，從理論上講，不可預測的PRNG是不存在的，這兒指密碼學安全的PRNG(cryptographically secure PRNG, CSPRNG)。
三、常用PRNGs
1、線性同余發生器(linear congruential generators, LCG)
單博偉在標準庫rand()函數的缺陷以及Blitz++隨機數生成的簡介中給出了The C Programming Langurage 2nd的實現，我手頭沒有這本書，所以無從查證，FallHunter應該還有吧。
?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中給的實現是：
?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，上面給的算法還是非常詳細的，CSPRNGs包括Blum Blum Shub、Fortuna等。
如果出于安全性的考慮，PRNG的輸出不應直接作為種子。在《構建安全的軟件》一書中，作者認為“一個好的PRNG具有這樣的性質：給足夠的熵，即使攻擊者知道全部的算法細節，還是不能猜出生成的數據流”。
三、PRNG的安全測試
FIPS-140標準包含了對RNs的測試規范。這個標準我也沒有去仔細看，所以沒法給出更多的信息。被提到的測試包有DIEHARD、pLab。
四、隨機數在游戲中的應用
1、隨機數為游戲帶來更多的不確定性，不確定性產生可玩性
這個應該是所有游戲的根本了吧。游戲中玩家、怪物、NPC的很多屬性都是一個范圍，比如攻擊就有最小攻擊和最大攻擊，每次的實際攻擊傷害總在二者之間。
同樣的，玩家樂此不疲的一次次“洗裝備”、“碰運氣”。其他類推吧?。
2、游戲的AI更多的依賴于隨機數
如果怪物、NPC的AI一切盡在玩家的掌握中，游戲的樂趣就大大降低了，這一點在單機游戲中有著很好的體現。War3中，人機對戰，電腦的戰術并不單一（但還是有規律可循，人類玩家尚且如此），這其中固然有多方面 的因素。但隨機數的功勞也不容抹殺。
3、隨機數減少數據存儲，一個種子可以代替一批數據
游戲中含有大量數據，如果每一項都要存取，對時間和空間都是一個考驗。對于場景中隨機生成的怪物信息，如果給定一個相同的種子。呃，是不是要簡單一些呢？
五、相關內容
至于為什么PRNGs大多使用素數，需要更多的數論知識，對密碼學有了解的TX應該能夠體會到安全和數論之間的緊密聯系。因為手頭沒有數論的書，所以不多加妄測了。到時寫論文的時候，再填充上吧。
六、參考文獻
1. 構建安全的軟件. [美]John Viega, Gary McGraw. 鐘向群, 王鵬 譯.? 北京. 清華大學出版社, 2003.
2. Pseudorandom number generator及相關鏈接. 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進行網際互聯》Vol. III，主要是針對Linux/POSIX套接字的C/S架構實現。因為MMORPG的C/S架構多依賴于TCP，上面第8、10-16章的內容可以關注一下。
b. 《構建安全的軟件》，上面關于開源、閉源的口水(Chap. 4)，關于緩沖區溢出(Chap. 7)，關于隨機數(Chap. 10)，關于數據庫安全(Chap. 14)，關于客戶端安全(Chap. 15)，都是值得一看的東西。
c. 《UNIX環境高級編程》，進程控制(Chap. 8)、線程控制(Chap. 12)、進程通信(Chap. 15, 17)、套接字(Chap. 16)、數據庫(Chap. 20)。
d. 《UNIX網絡編程》Vol.I，如果涉及到泛UNIX操作系統下網絡編程，可以當作參考書翻。
e. 《計算機安全原理》，加密(Chap. 5)、認證(Chap. 6)、協議安全(Chap. 7)、入侵檢測(Chap. 13)、惡意攻擊(Chap. 15)、災難恢復(Chap. 19)。
PS02：微軟宣布不會抬高收購Yahoo價格
消息來自Wall Street Journal，不過當天可是April Fool。
PS03：關于Wikipedia
不是說Wikipedia被禁的嗎？很久沒有訪問過了，這么好的東西，被封了還是很遺憾的。
PS04：有問題
發現問題，找Google；解決問題，找Wikipedia。
PS05：歡迎補充
-------------------------------------------------------------------------
Added on Apr.10th
今天從CodeProject上看到一篇文章Applied Crypto++: Pseudo Random Number Generators)，作者Jeffrey Walton對密碼學和安全比較有研究。
Jeffrey Walton對Knuth的The Art of Computer Programming Vol.2中關于隨機數的部分作了概括。
這篇文章從一個工程師的角度給出了隨機數的應用和實現，很具有參考性。
作者還從FIPS 140-2標準中引用了下面一段話：
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所生成的隨機數列只可能是偽隨機數，真隨機數依賴于不可預測的物理源。