最近有很多关于邪恶的后门被插入密码标准和工具箱的新闻。其中一种算法，即伪随机比特发生器Dual_EC_DRBG，于2007年被美国国家标准与技术研究所（NIST）批准，并因其具有潜在的后门而备受关注。据称，美国国家安全局在这一算法中插入了后门，然后付钱给RSA使用。那怎么可能呢？这是一本技术入门，它解释了什么是后门，创建自己的后门有多容易，以及dangerou使用一个随机数发生器的后果是有后门的。这必然是一个漫长的技术讨论，但希望到最后应该弄清楚为什么Dual-eu-DRBG有如此糟糕的声誉。后门长期以来，后门的概念给安全行业蒙上了阴影。后门是密码算法或实现中的故意缺陷，它允许个人绕过系统设计用来实施的安全机制。后门是一种让某人从系统中获得一些他们无法从系统中获得的东西的方法。如果一个安全系统是墙，后门就是它下面的秘密隧道。后门可以由懒散的程序员插入，他们出于调试的原因想绕过自己的安全系统，也可以创建后门来故意削弱其他人使用的系统。众所周知，政府机构在常用软件中插入后门，以实现大规模监视。后门可以嵌入到软件、硬件中，甚至可以嵌入到算法的设计中。

理论上，一个设计良好的密码系统不包括后门。实际上，很难保证一个软件是没有后门的。最近在广泛部署的D-Link路由器固件中发现了一个后门。后门允许任何知道秘密用户代理字符串的人登录并修改运行易受攻击软件的任何路由器上的设置。D-Link后门花了很长时间才找到，因为路由器软件的源代码无法供安全研究人员检查。使用开源软件，研究人员可以直接查看验证身份验证和后门检查的代码部分。开源是理解代码如何工作的很好的工具，但它并不是在软件中寻找后门的万能药。在一个复杂的代码库中完整地分析所有代码可能是困难和耗时的。国际模糊C代码竞赛展示了如何使代码变得极其难以理解。秘密的C语言竞赛将这一点做得更进一步，显示出外观良好的代码可以隐藏恶意行为。人类编程语言和机器代码之间的转换步骤也可以用来插入后门。1984年，经典文章《信任的反思》介绍了这一观点。加密社区最近联合起来审核开源磁盘加密软件TrueCrypt的后门。此审核的关键步骤之一是验证为TrueCrypt在线分发的机器代码是否与源代码匹配。这需要使用完全开放源代码编译器重新构建经过审核的源代码，并确保机器代码匹配。可复制的二进制文件有助于证明恶意人员或编译器没有在程序的机器代码中插入后门。随机弱点在某些情况下，即使这样也不够。例如，像大多数加密系统一样，TrueCrypt使用系统的随机数生成器来创建密钥。如果攻击者能够控制或预测系统产生的随机数，他们通常可以破坏其他安全的加密算法。系统随机数生成器中的任何可预测性都可能使其容易受到攻击。使用随机数生成器中的缺陷（有意或无意地创建）绕过安全系统的例子非常常见。最近的一些例子：随机数生成器中的一个缺陷允许人们劫持黑客新闻账户。安卓系统中一个坏掉的随机数生成器允许攻击者劫持价值数千美元的比特币。Debian发行版上的OpenSSL版本存在随机数生成器问题，攻击者可以猜测在这些系统上创建的私钥在依赖随机数的安全系统中，有一个不可预测的随机数来源是绝对必要的。这包括SSL/TLS，这是internet的基本安全层，会话密钥是使用随机数生成的。如果你设计一个随机数发生器，让你预测输出，并说服别人使用它，你就可以破坏他们的系统。这种算法后门就是我们将在这篇博客文章中创建的。不是的随机流pi的数字看起来很随机，但它们不是很好的随机数生成器，因为它们是可预测的。任何知道有人用π的数字作为随机性来源的人都可以用这个来对付他们。说服某人使用基于pi的随机数发生器是一个困难的挑战。许多伪随机数生成器从一个称为种子的数字开始。种子是算法内部状态的起点。该算法通过对内部状态的一些数学运算生成随机数流。只要种子（以及随后的内部状态）是保密的，算法输出的伪随机数对任何观察者都是不可预测的。相反，任何知道状态的人都可以预测输出。Linux使用一个数字池作为其伪随机数生成器/dev/random的内部状态。每次程序从系统请求随机数据时，Linux都会使用算法SHA-1返回其内部状态的加密哈希。这个散列函数是单向的，它很容易计算，但很难找到给定输出的输入。这是非常困难的，从来没有人在没有事先知道输入的情况下发布过SHA-1哈希的反转。这就为随机数生成器的内部状态保密。然后，由哈希函数提取的随机数据混合回到内部状态。周期性地，诸如点击和按键之类的"不可预测"系统事件的时间戳散列也会被混合在一起。下面是一个基本的伪随机数生成器构造图：

在这个图表中F=SHA1G=SHA1+与XOR混合这种结构相当标准。内部状态是保密的，数据通过单向函数输出，内部状态通过混合到状态中来更新。在任何时候，如果攻击者能够找出内部状态，他们就可以预测输出。F公司和G公司的战略选择是使这座建筑安全的。你不会因为与其他事物异或而失去池中的随机性，熵总是上升的。如果F和G被选为两个完全独立的单向函数，它可能仍然是安全的。将SHA-1作为F，MD5（一个不同的散列函数）作为G并不是一个太不合理的选择。这里的关键在于单词的独立性，但首先要跨入椭圆曲线。椭圆曲线与单向函数在之前的一篇博文中，我们对椭圆曲线密码术做了一个温和的介绍。我们讨论了如何将这类曲线用于加密和数字签名算法。我们还暗示椭圆曲线可以用来产生随机数。这就是我们将在这里描述的。椭圆曲线用于密码学的原因是它们所支持的强单向函数。如前所述，有一种几何直观的方法来定义椭圆曲线上的点的算法。

椭圆曲线上的任何两个点都可以"点"在一起（"相乘"）得到曲线上的一个新点。用一个点本身任意次数点一点很快很容易做到，但是回到原点需要大量的计算。此操作可用于从点P1创建一个漂亮而简单的单向函数：给定一个数字n，输出另一个数字m：点P1与自身n次，得到另一个点Q将Q的x坐标输出为m很难从m回到n，因为这足以解决椭圆曲线离散对数问题，这被认为是非常非常困难的。上一篇文章中使用的隐喻是椭圆曲线中的单向函数就像玩一场特殊的台球游戏。如果有人被单独锁在一个房间里，他们可以打出一定数量的球，而球最终会落在一个特定的位置。然而，如果你在某个时候进入房间，仅仅看到了球的位置，那么如果你不自己再打完整场比赛，就很难确定球员投了多少球。有了这个台球的类比，我们可以把这个随机数发生器看作一个新的比扎罗台球游戏。考虑无限长椭圆曲线台球桌上的两个球，黄色的球叫P1，蓝色的球叫P2。

这两个球在它们开始的曲线上有特定的点。这是一个两人游戏，一个人叫发电机，另一个人叫观察者。发电机有一个秘密号码"n"。生成器获取球P1并执行n次击球，并让观察者看到其最终位置。然后它获取P2并执行n个快照，将P2的最终位置作为n的新值。然后P1和P2被重置到它们的原始位置，这就是回合的结束。每转一圈，观察者就会看到P1的一个新的伪随机位置，这就是游戏的输出。T