密码学安全伪随机数生成器

密码学安全伪随机数生成器（亦作密码学伪随机数生成器，英文：Cryptographically secure pseudorandom number generator，通称CSPRNG），是一种能够通过运算得出密码学安全伪随机数的伪随机数生成器。

介绍密码学安全伪随机数生成器（亦作密码学伪随机数生成器，英文：Cryptographically secure pseudorandom number generator，通称CSPRNG），是一种能够通过运算得出密码学安全伪随机数的伪随机数生成器。相较于统计学伪随机数生成器和更弱的伪随机数生成器，CSPRNG所生成的密码学安全伪随机数具有额外的伪随机属性。1

CSPRNG常被作为密码学原件，用以搭建更复杂的密码学应用。如，可变长CSPRNG和XOR函数搭配即构成流密码的编解码方法。

随机性密码学领域的随机性一般分为如下三类：2

统计学伪随机性随机比特序列匹配在统计学的随机的定义。匹配该定义的比特序列的特点是，序列中“1”的数量约等于“0”的数量；同理，“01”、“00”、“10”、“11”的数量大致相同，以此类推。匹配该类别的随机数生成方法的例子有线性同余伪随机数生成器。

密码学安全伪随机性除了满足统计学伪随机性外，还需满足“不能通过给定的随机序列的一部分而以显著大于1/2的概率在多项式时间内演算出比特序列的任何其他部分”。匹配该类别的密码学安全伪随机数生成器的例子如Trivium (算法)中的CSPRNG部分、SHA-2家族函数和计数器亦可被绑定以构建类似强度的CSPRNG。

可忽略函数

由可忽略速度增长的概率即为概率增长函数是可忽略函数。可忽略函数的定义如下：当输入趋近于无穷大时，一个函数的增长速度小于任何多项式函数的反函数，则该函数是可忽略函数。换言之，。比如说，我们知道，在输入趋近于无穷大时，任何指数函数的增长速度大于任何多项式函数，因此，任何指数函数的反函数的增长速度一定小于任何多项式函数的反函数。指数函数的反函数是对数函数，因此，所有的对数函数都是可忽略函数。

真随机性除满足以上两点，还需要具备“不可重现性”。换言之，不能通过给定同样的数据而多次演算出同一串比特序列。由于计算机算法均具备确定的特性，所以真随机数无法由算法来生成。真随机数的例子有放射性物质在某一时间点的衰变速度、某一地区的本底辐射值、正确使用设计良好的骰子所获得的输出等。

开放问题CSPRNG本质上属于一种单向函数。一个可用的CSPRNG必须要满足给定种子易于计算输出，而给定输出无法容易地计算种子。但是，由于从输出到种子的变换是容易的，因此检查一个种子的正确性是非常容易的。换言之，一个设计良好的CSPRNG从输出求种子的问题必须是NP问题，但必须不是P问题。

由于在数学上面，P = NP与否是尚未有定论的难题，因此设计良好的CSPRNG是否存在是一个开放性问题。如果有一天P = NP得到证明，那么，“输出求种子的问题必须是NP问题，但必须不是P问题”这一条件就无法满足，这直接导致CSPRNG不再存在，也导致依赖强壮CSPRNG的所有密码学应用的强壮性不复存在。

相关条目随机数

伪随机数生成器

可忽略函数，帮助理解“非显著大于1/2”这一概念。

多项式函数、反函数，帮助理解多项式时间和多项式函数的概念。

单向函数

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所