游戏人生

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所生成的随机数列只可能是伪随机数，真随机数依赖于不可预测的物理源。