随机数发生器

这是一个由美国国家标准协会（NIST）制定并被美国国家安全局（NSA）大力提倡的随机数发生器。Dual_EC_DRBG利用椭圆曲线算法的机制生成随机数。这个算法涉及到在曲线上取点并反复在椭圆曲线上进行“打点”操作。该算法公布之后，据报道可能存在一个后门程序，可以根据一个密码完全预测其返回的数字顺序。最近，RSA公司由于其安全产品生产线上的随机数发生器被设置为默认的伪随机数发生器而召回了它的部分产品。无论这种随机数发生器是否被写了后门程序都不会改变椭圆曲线技术本身的力量，但这确实引起了关于对椭圆曲线标准化过程的一些问题。这也是我们应该将注意力用在确保系统充分使用随机数的部分原因。

在NIST SP 800-90A中包含Dual_EC_DRBG的既定目的是其安全性基于数论的计算硬度假设。数学安全性降低证明可以证明，只要理论问题的数量很难，随机数发生器本身就是安全的。但是，Dual_EC_DRBG的制造商没有公布Dual_EC_DRBG的安全性降低，并且在NIST草案发布后不久就发现了Dual_EC_DRBG确实不安全，因为它每轮输出太多比特。太多位的输出（以及精心选择的椭圆曲线点P和Q）是使NSA后门成为可能的原因，因为它使攻击者能够通过强力猜测来恢复截断。在最终发布的标准中没有更正过多位的输出，使得Dual_EC_DRBG既不安全又无后顾之忧。

在许多其他标准中，意味着任意的常数是通过我的套数原则选择的，其中常数是从例如pi中得出的，其方式几乎没有调整的余地。但是，Dual_EC_DRBG没有指定如何选择默认的P和Q常量，可能是因为它们是由NSA构造为后门的。由于标准委员会意识到了后门的可能性，因此包括了实施者选择自己的安全P和Q的方法。但是标准中的确切表述是这样的，即FIPS 140-2验证需要使用所谓的后向P和Q，因此OpenSSL项目选择实施后门P和Q，即使他们意识到潜在的后门并且更愿意生成他们自己的安全P和Q. 纽约时报后来写道，国家安全局在标准化过程中起作用，最终成为该标准的独立的一个编辑。

后来由Daniel RL Brown和KristianGjøsteen为Dual_EC_DRBG发布了安全证明，表明生成的椭圆曲线点与均匀随机椭圆曲线点无法区分，并且如果在最终输出截断中输出的位数较少，如果两个椭圆曲线点P和Q是独立的，如果显示三个问题很难（通常只接受其中一个是硬的），那么Dual_EC_DRBG是安全的。证据依赖于三个问题很难的假设：决策性的Diffie-Hellman假设（通常被认为很难），以及两个通常不被认为难以解决的新问题：截断点问题和x-对数问题。与许多替代CSPRNG（没有安全性降低）相比，Dual_EC_DRBG相当慢，但Daniel R.L.Brown认为安全性降低使得慢速Dual_EC_DRBG成为一种有效的替代方案（假设实现者禁用明显的后门）。请注意，Daniel R.L. Brown为椭圆曲线加密专利的主要所有者Certicom工作，因此在推广EC CSPRNG时可能存在利益冲突。

所谓的NSA后门将允许攻击者通过查看单轮（32字节）的输出来确定随机数生成器的内部状态;然后可以容易地计算随机数发生器的所有未来输出，直到用外部随机源重新接种CSPRNG。这使得例如SSL / TLS易受攻击，因为TLS连接的设置包括以明文形式发送随机生成的加密随机数。NSA所谓的后门将取决于NSA知道e * Q = P的单个e - 这是一个难题，给定Q和P，但如果你可以选择P和Q则容易生成。因此，e是一个秘密密钥，据推测只有NSA才知道，所谓的后门是一个盗版非对称隐藏后门。Matthew Green的博客文章“Dual_EC_DRBG的多重缺陷”通过使用Crypto 1997中引入的离散日志kleptogram，对所谓的NSA后门如何工作进行了简化解释。