伪随机生成器的基本概念

【基本概念】

伪随机生成器

伪随机生成器（Pseudorandom Generator，PRG）是一类高效的确定性程序，它能够将一个较短的、随机选取的种子（Seed）扩展为一个长度更长的伪随机序列（Pseudorandom Sequence）。

其中，伪随机序列是指任何高效算法都无法将其与真正随机生成的序列区分开。虽然伪随机生成器本身是确定性的，但只要输入的种子是随机选择的，输出序列在计算上就应当表现得像真正的随机序列。

伪随机函数

伪随机性的理论不仅可以应用于比特序列，还可以应用于函数，由此得到伪随机函数（Pseudorandom Function，PRF）的概念。

伪随机函数是一类高效、确定性的函数，但对于不知道密钥的高效攻击者而言，它的输入输出行为与一个真正随机选择的函数在计算上不可区分。

伪随机函数是许多密码学应用中的重要工具，可以用于构造对称加密方案、消息认证码、身份认证协议、密钥派生机制等

【研究动机】

现代密码学认为，高效计算（Efficient Computation）为理解随机性的本质提供了一个良好的基础。从计算的角度研究随机性，主要存在两种不同的思路：

1. 本体论方法（Ontological Approach）：研究一个对象本身是否具有简单的解释
2. 行为主义方法（Behavioristic Approach）：研究一个对象对外部观察者表现出的行为是否与随机对象相同

本体论随机性

Kolmogorov 随机性

20 世纪 60 年代初，Solomonoff 和 Kolmogorov 提出了一种基于计算的随机性研究方法，Chaitin 在20世纪70年代初重新发现了这一方法。该方法在本质上属于本体论方法。

宽泛来说，对于一个字符串 $s$，如果生成该字符串的最短程序长度与字符串本身的长度 $|s|$ 相等，那么就认为字符串 $s$ 是 Kolmogorov 随机的（Kolmogorov-Random）。生成字符串 $s$ 的最短程序，可以被看作对该字符串所描述现象的最简单解释。因此，如果不存在一个明显短于 $|s|$ 的程序来生成 $s$，就说明该字符串不存在一个足够简单的解释，从而可以将其视为随机字符串。

也就是说，Kolmogorov 随机性关注的是：一个字符串能否被一个比它自身短得多的程序描述或生成。例如，一个由大量重复模式组成的字符串：

$$010101010101\cdots$$

虽然长度可能很长，但可以通过重复输出 $01$ 这样一个很短的程序生成，因此它不具有较高的 Kolmogorov 随机性。

Kolmogorov 复杂度

一个字符串 $s$ 的 Kolmogorov 复杂度（Kolmogorov Complexity），可以理解为生成该字符串的最短程序的长度。

如果一个字符串不存在明显短于它本身的生成程序，那么该字符串就具有较高的 Kolmogorov 复杂度。也就是说，高 Kolmogorov 复杂度的字符串很难被压缩，也没有明显比它自身更短的描述，因此可以认为它具有较强的随机性。

Kolmogorov 随机性存在两个重要问题：

1. 无法判断一个给定字符串是否是 Kolmogorov 随机的：对于任意给定字符串，不存在一个通用算法能够判断是否存在比该字符串更短的程序来生成它
2. Kolmogorov 复杂度是不可计算的：不存在一个算法能够对任意字符串准确计算其Kolmogorov复杂度

此外，这种方法虽然能够从理论上解释一个字符串本身是否随机，但无法自然地应用于伪随机生成器的研究。

行为主义随机性

伪随机性

行为主义随机性起源于 20 世纪 80 年代初，Kolmogorov 随机性关注一个现象是否具有简单的内部解释，而行为主义方法并不研究对象内部是如何产生的，而是研究该对象对外部环境产生的效果。

宽泛来说，如果不存在任何高效观察者，能够将一个字符串与同长度的均匀随机字符串区分开，那么就认为该字符串具有伪随机性。

这里的核心判断标准是：对于一个高效观察者而言，该字符串看起来是否与真正随机生成的字符串相同。

因此，伪随机性并不要求字符串本身是真正随机产生的，而只要求其外部表现与真正随机字符串不可区分。

计算等价原则

行为主义随机性建立在一个重要假设之上：如果两个对象无法被任何高效过程区分，那么就可以将它们视为等价的。

这两个对象在内部结构或产生方式上可能完全不同，甚至可能具有本质上不同的 Kolmogorov 复杂度，但只要高效观察者无法区分它们，它们在计算意义上就可以被视为相同。

例如，伪随机生成器输出的字符串由一个短种子通过确定性算法生成，因此从 Kolmogorov 复杂度的角度看，它通常具有一个较短的描述：

$$\text{种子}+\text{伪随机生成算法}$$

所以它并不是真正的 Kolmogorov 随机字符串。但是，如果任何高效算法都无法将其与真正的均匀随机字符串区分开，那么它仍然可以被认为是伪随机的。

由此可以看出，两种随机性观点的区别在于：

1. Kolmogorov 随机性：关注对象的内部描述和生成方式
2. 伪随机性：关注对象在高效观察者面前表现出的外部行为

区别

比较内容	Kolmogorov随机性	伪随机性
研究角度	本体论	行为主义
关注重点	是否存在简短描述	是否可被高效区分
判断对象	单个字符串	通常是字符串分布或生成器输出
核心标准	最短生成程序是否足够长	高效观察者能否区别于真随机
是否可计算	不可计算	可通过计算安全定义进行研究
与伪随机生成器的关系	不易直接应用	自然导出伪随机生成器

行为主义方法能够自然地引出伪随机生成器的概念，而伪随机生成器具有大量实际应用，尤其是在密码学领域。

【严格研究方法】

启发式方法

统计测试的评价方法

现实计算机中常用的伪随机生成器，往往采用一种启发式方法（Heuristic Approach）进行评价。

这种方法将伪随机生成器视为能够产生一系列比特序列的程序，并通过一些指定的统计测试（Statistical Tests）判断这些序列是否具有随机性。如果生成器产生的序列能够通过这些统计测试，就认为该生成器输出的序列看起来是随机的。

常见测试可能关注：

• 0 和 1 的出现频率是否接近
• 不同比特组合的分布是否均匀
• 是否存在明显的周期
• 是否存在重复模式
• 不同位置的比特是否具有明显相关性

统计测试的局限性

缺乏系统性

但是，统计测试方法存在明显不足。用于检验伪随机生成器的统计测试通常是人为选择的，其选择具有一定的任意性，缺乏系统的理论基础。

一个生成器通过了某些统计测试，只能说明这些测试没有发现其输出中的规律，并不能说明不存在其他高效算法能够发现规律。

实际上，可以针对实际中常用的伪随机生成器，构造出某些高效的统计测试，从而区分伪随机生成器的输出和同长度的均匀随机字符串。因此，能够通过若干指定测试并不等于在计算意义上是伪随机的。

依赖具体应用

当一个新的应用程序需要使用随机序列时，如果采用启发式伪随机生成器，就必须进行大量测试，以判断应用使用伪随机序列时的行为是否与应用使用真正随机源时的行为相同。

但问题在于，即使一个伪随机生成器在某个应用程序中没有造成明显影响，也不能保证它在另一个应用程序中同样安全。甚至只要对原有应用进行修改，就需要重新比较伪随机生成器和真正随机源，因为生成器输出中隐藏的非随机性，可能不会影响原始应用，却会对修改后的应用造成不良影响。

因此，启发式伪随机生成器的可靠性是依赖于具体应用的，而不是普遍成立的。

密码学中的风险

在密码学应用中，这一问题会更加严重。

一个密码学应用是否安全，不仅取决于算法本身，还取决于攻击者采用的攻击策略，只有在确定了敌手之后，具体的安全攻击场景才被完整确定。但是，密码系统设计者不可能提前知道所有敌手将采用什么攻击方式，也不能合理地假设敌手一定会采用某个已知的固定策略。

因此，无法仅通过有限的实验测试，判断一个伪随机生成器是否会影响某个尚未确定策略的敌手。

也就是说，不能通过测试预先判断伪随机生成器是否会被未来某个未知敌手利用。所以，将仅仅通过若干统计测试的伪随机生成器用于密码学目的，具有很高的风险。

严格定义的伪随机生成器

计算不可区分性要求

高效计算的概念自然地引出了一种新的对象等价关系：如果不存在任何高效过程能够区分两个对象，那么就可以认为这两个对象在计算上是等价的。

计算不可区分性（Computational Indistinguishability）是一种非常自然的等价概念，其不要求两个分布在数学上完全相同，而是要求任何计算能力受到限制的高效算法，都无法以明显高于随机猜测的概率区分它们。

一个严格意义上的伪随机生成器所产生的序列，对于任何高效观察者而言，都应当看起来与真正随机序列相同。

也就是说，不只是要求生成器通过某几个预先选定的统计测试，而是要求它能够通过所有高效的区分过程。其安全要求可以概括为：

不存在任何高效算法，能够以不可忽略的优势（Non-negligible Advantage）区分伪随机生成器的输出和真正的均匀随机序列。

其中，不可忽略的优势是指区分成功率相对于随机猜测存在一个在计算上足够明显的提升。

可替代性

由于严格定义的伪随机生成器能够对任何高效观察者表现得像真正随机源，因此，它的输出可以替代任何高效应用程序中所需的真正随机序列。

只要应用程序本身是高效的，这种替换就不会使应用程序的行为发生可被高效检测的变化。

特别是在密码学中，没有任何高效敌手能够利用这种替换，即敌手无法通过观察系统使用的是伪随机序列还是真正随机序列而获得有效攻击优势。

区别

1. 启发式方法：要求生成器通过一些指定的统计测试
2. 严格方法：要求生成器无法被任何高效算法与真正随机源区分

启发式方法只能说明没有被已选择的测试发现问题，而严格方法则要求不存在任何高效区分算法能够发现问题。

因此，严格定义提供的是一个统一的、与具体应用无关的安全保证，而启发式方法只能提供针对有限测试的经验性保证。