Blum Blum Shub与AES-CTR或其他CSPRNG

#1 楼

Blum-Blum-Shub是一种流密码：给定一个短密钥，它将产生一个有效的无限制长度的伪随机比特流。流密码的其他知名示例包括AES-CTR和RC4。非专家密码学家经常提到Blum-Blum-Shub。我怀疑这是因为它带有安全性的“证明”，听起来像是一件很棒的事情。在“应用密码学”中提到BBS可能不会感到伤害，并且某些开发人员可能已经摆脱了认为BBS是蜜蜂的膝盖的想法。

但是，我个人不建议使用BBS。事实证明，安全性证明极具误导性，并且带有一些精美的字样，使该证明在实践中几乎变得毫无用处。您最好使用AES-CTR（计数器模式下的AES）。 AES经过了严格的审查，得到了广泛的信任。 AES-CTR应该提供出色的安全性-同时还提供出色的性能。

BBS存在两个问题：


BBS非常慢-非常慢。 br />此外，“安全证明”的存在极具误导性，而且通常会被误解。实践人员几乎总是从“安全证明”中得出错误的结论。

这两个问题是联系在一起的。安全性的标准证明是，如果选择的模数N足够大，则攻击者将无法有效破坏BBS。但是，标准证明没有说要达到任何期望的安全级别，N必须有多大。最近，研究人员已经弄清了所需的模数，并且（可以看到：）需要N足够大才能具有可证明的安全性。我将在下面总结他们的一些结果：

结果1.假设您使用具有768位模数的BBS。您已经了解到768位足以使分解不可行，因此听起来很桃花。您已经了解到，在每次迭代中提取O（lg n）位都是安全的；这里n = 768，lg n = 9.58，因此您决定在每次迭代中提取9位。您可以使用它生成107位的伪随机流（大约1MB的伪随机数据）。您得到多少安全性？答：安全证明可确保对使用最多2-264个计算步骤的任何对手的安全性。是的，这是完全荒谬和无用的说法！用简单的英语来说，安全证明绝对不能保证没有任何用处。

课程是：使用自然大小的参数，不能保证您在实践中使用BBS的安全性。 “安全性证明”对普通大小的参数没有用。

结果2.假设您了解了此结果，并决定使用更长的模数。假设您决定使用6800位模数的BBS，并在每次迭代中提取5位。假设您从BBS生成器中提取的伪随机位不超过一百万。然后，有证据表明，要打破BBS，至少需要2100个计算步骤（给定合理的假设）。这意味着您应该具有合理的安全级别。我的估计是，在我的机器上，使用BBS产生一百万比特（128KB）的输出大约需要5-10分钟，而使用AES-CTR则需要不到一秒钟。

换句话说，为了在实践中达到中等程度的安全性，BBS需要巨大的模数-比您在RSA中使用的任何东西都要长。这个很大的模数使BBS非常慢。它比AES慢得多，而且可能也要弱得多，因为即使您提取了超过一百万位的伪随机输出，也可以相信AES可以安全使用。

结果3.这是另一种思考方式。第三位研究人员计算出BBS和代理之间的安全级别比率。他发现可能会发生破坏BBS的攻击，并且比任何分解算法（分解BBS模数）的算法快1054n3倍的攻击。例如，对于1024位模数（n = 1024），某人可能能够以他们认为可以的最快速度破坏BBS 1063倍。因为我们知道您可以用少于1024个计算步骤来分解1024位模数，所以这种关于1024位BBS的保证完全没有用：它根本不能保证安全。

作为另一个示例，对于8192位模数，结果表明，可能存在一些巧妙的算法来使BBS中断速度比我们知道的如何计算8192位模数快1065倍。这是一个很大的比例。它说BBS的破解可能比RSA容易得多。这意味着仅当我们使用巨大的模数并且仅当我们认为分解该大小的模数非常困难时，我们对BBS的安全性证明才有意义。如果我们愿意假设分解这样一个模量非常困难，我们可以推断出破坏BBS相当困难。但是由于我们需要使用如此大的模数，因此所得的BBS方案将非常慢。

有关更多详细信息，请参见以下研究论文：


另请参见“紧密性”，Sanjit Chatterjee，Alfred Menezes和Palash Sarkar，《 2011年密码学的某些领域》。
Blum-Blum-Shub伪随机生成器的安全性，Andrey Sidorenko和Berry Schoenmakers，2005年密码学和编码。
/>以及来自Dan Bernstein的sci.crypt帖子：Re：BBS PRNG强度推荐参数


关于术语的脚注：理论家有时将流密码称为“伪随机生成器”（PRG） ）。令人困惑的是，这与“伪随机数生成器”（PRNG）不同。

术语“伪随机数生成器”（PRNG）并非始终使用一致。有两种可能的含义。有些人将其用作流密码的同义词。就个人而言，我更喜欢将PRNG保留给用于生成伪随机数的方案，该方案不使用任何显式输入（而是以某种方式从环境中收集熵）。用我的首选术语，您可以使用PRNG来生成短密码密钥。然后您使用流密码（PRG）将短加密密钥扩展为很长的伪随机比特密钥流。但是其他人对该术语的使用却有所不同。

给这个混乱的机会，如果从上下文中不清楚该术语的含义，最好避免使用PRNG。

#2 楼

BBS有一个所谓的“安全证明”，它表明只要二次残留问题很难解决，它就可以保持安全。后者被认为与整数因式分解一样困难，而整数因式分解本身被认为是很难解决的问题。

Gee，对Wikipedia二次余数问题的描述确实缺乏明确性。用简单的话来说，问题是：给定一个大整数N，它是两个大小相似的素数p和q的乘积，以使p和q等于3模4，而值y是N模，决定是否y是一个平方（即是否存在整数x使得x2 = y模N）。以N为模的约N / 4个整数就是这样的平方。在3N / 4个非正方形中，很容易确定N / 2不是带有Jacobi符号的正方形。其余的N / 4称为伪平方：这些值不是平方，但Jacobi符号仍为其返回1。QRP的目的是区分真平方与伪平方。

最著名的方法解决QRP的方法是分解N（一旦分解了N，即揭示了p和q，就可以对p和q进行模运算，并容易地确定一个值是否为素数的平方）。当N足够大并由随机p和q生成（当前记录为768位）时，用于分解大整数的最著名算法仍然非常昂贵。

请注意我对“相信”一词的使用：BBS的安全性仅由QRP证明。没有证据表明QRP像分解一样难。而且，也没有证据表明因式分解确实很难（但是2500多年的研究还没有提出一种有效的因式分解方法，因此它绝非轻而易举）。因此，BBS的安全状态与RSA相似。使用2048位模数N，就可以了。

其他PRNG（例如，处于CTR模式的AES或来自eSTREAM的流密码）没有如此精巧的安全证明。它们依靠手工艺：人们认为它们是安全的，因为聪明的人试图破坏它们，但没有成功。只要所说的人都是受过训练的密码学家，就足够了，他们至少有几十个，他们花了几个月或几年的时间来研究算法，并且他们在算法的封面上没有发现丝毫凹痕。 AES或eSTREAM产品组合就是这种情况。自制设计在两周之内被拍打在一起并毫不费力地推向了野外，情况并非如此。此类设计中最好的是RC4，它有一些偏差（虽然没有什么严格要求，但在学术上还是“折断”），并且在分析中生存了很长时间，主要是因为设计师是Ron Rivest，而且Ron非常聪明。

因此，即使在安全范围上与BBS一样有限，安全证明也是一件不错的事情，这解释了为什么定期建议使用它。

另一方面，BBS非常慢。在现代的PC内核上，您可能会每秒生成价值12千字节的随机数据，而任何体面的加密PRNG的运行速度都将快10000倍。 BBS的缓慢性是许多应用程序的瓶颈。