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

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

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

随机性

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

统计学伪随机性

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

密码学安全伪随机性

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

可忽略函数

由可忽略速度增长的函数是可忽略函数。可忽略函数的更准确的定义如下：当输入趋近于无穷大时，一个函数 $\mu :\mathbb {R} \to \mathbb {R}$ 的输出小于任何多项式函数的反函数，则该函数是可忽略函数。换言之， $\lim _{x\to \infty }{|\mu (x)|-{\frac {1}{|poly(x)|}}}<0$ 。比如说，我们知道，在输入趋近于无穷大时，任何指数函数的增长速度大于任何多项式函数，因此，任何指数函数的反函数的增长速度一定小于任何多项式函数的反函数。指数函数的反函数是对数函数，因此，所有的对数函数都是可忽略函数。

真随机性

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

开放问题

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

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

注解

^ 显著大于1/2定义为，大于1/2的部分是一个关于CSPRNG的可能的内部状态的数量的以可忽略速度增长的函数的输出。所有的CSPRNG在运行时均具有被称为“内部状态”的数据，这部分数据的作用之一是保证了在一定输出范围内，CSPRNG“知道”自己走在哪一步上，以避免其输出重复的值，从而破坏伪随机性。如果CSPRNG的可能的内部状态过少，敌手（攻击者）将可以通过穷举内部状态并与比特序列匹配，得到CSPRNG的输出。由于可变长CSPRNG内部状态的下一状态步进算法一般为固定且公开的，一旦敌手获知CSPRNG在某一时间点的内部状态，就（至少）可以演算出其之后的状态。这与“不能通过给定的随机序列的一部分演算出其他部分”这一定义相冲突。因此内部状态过少的伪随机数生成器往往不在讨论范围中。
^ 如果不能以显著大于1/2的概率计算出比特序列的任何其他部分，那么就说明无法以显著大于1/2的概率计算出任何一个其他位置的比特，因此保证每一个比特位都无法在没有密钥的情况下仅通过计算得到。
^ 这是一个简化的说法。实际上，只有放射性物质在某一时刻的衰变概率恰好为0.5时，其衰变数据才是真随机数。

参考

^ ^1.0 ^1.1 Jonathan Katz and Yehuda Lindell, 現代密碼學——原理與協議 (Introduction to Modern Cryptography: Principles and Protocols), ISBN 9787118070651

[2] 显著大于1/2定义为，大于1/2的部分是一个关于CSPRNG的可能的内部状态的数量的以可忽略速度增长的函数的输出。所有的CSPRNG在运行时均具有被称为“内部状态”的数据，这部分数据的作用之一是保证了在一定输出范围内，CSPRNG“知道”自己走在哪一步上，以避免其输出重复的值，从而破坏伪随机性。如果CSPRNG的可能的内部状态过少，敌手（攻击者）将可以通过穷举内部状态并与比特序列匹配，得到CSPRNG的输出。由于可变长CSPRNG内部状态的下一状态步进算法一般为固定且公开的，一旦敌手获知CSPRNG在某一时间点的内部状态，就（至少）可以演算出其之后的状态。这与“不能通过给定的随机序列的一部分演算出其他部分”这一定义相冲突。因此内部状态过少的伪随机数生成器往往不在讨论范围中。

[3] 如果不能以显著大于1/2的概率计算出比特序列的任何其他部分，那么就说明无法以显著大于1/2的概率计算出任何一个其他位置的比特，因此保证每一个比特位都无法在没有密钥的情况下仅通过计算得到。

[4] 这是一个简化的说法。实际上，只有放射性物质在某一时刻的衰变概率恰好为0.5时，其衰变数据才是真随机数。

[Katz-1] 1.0 ^1.1 Jonathan Katz and Yehuda Lindell, 現代密碼學——原理與協議 (Introduction to Modern Cryptography: Principles and Protocols), ISBN 9787118070651

[1]

[注 1]

[注 2]

[注 3]