如何处理身份值和其他“明显”弱秘密随机值？

Question

在RSA、ECDSA、ElGamal和其他相当多的方案中，使用等于1的秘密(随机)值可能无法提供任何形式的安全性，而在数学上仍然是合理的。

例如，对于RSA、ECDSA或ElGamal，秘密随机值通常是秘密指数。或者对于ElGamal和ECDSA，这可能是我们需要加密或签名的短暂秘密( 臭名昭著k#qcStackCode#ECDSA)。

可以说，这适用于小于80位的秘密值，否则很可能会受到暴力搜索攻击。

对于机密值，其机密性对当前方案的安全性至关重要，例如ECDSA签名中使用的短暂的k，也是如此，尽管特定的方案可能有特定的指导方针，这取决于它们的具体需求。

为了避免这些明显的问题，是否有任何(官方或标准的)建议来拒绝基于某些标准的“坏”随机值？

或者更广泛地说，就像我们有关于组大小的建议或者生成大素数的方法一样(参见keylength.com)，我们是否有某种准则来生成密码软件中的“秘密随机值”。(例如，我没有看到根据k为ECDSA生成的FIPS 186-4值执行任何类型的“正常检查”，即使是至关重要的用于k值是无偏的。我所知道的唯一的“标准”指定了如何生成秘密随机值，它只涉及生成k的具体情况，就是RFC6979，并且正在使用脱皮术，就像EdDSA (RFC8032)的标准一样。但对于秘密值来说，这并不总是可能的。)

这是记录在其他NIST文档中，还是在某些RFC中？

PS:注意这个问题是假设随机性难以实现，因此最好以一种让纵深防御纵深防御安装“故障安全”的方式。

Answer 1

在RSA、ECDSA、ElGamal和其他相当多的方案中，使用等于1的秘密(随机)值可能无法提供任何形式的安全性，而在数学上仍然是合理的。

人们可能会争辩说，指数'1‘没有任何安全性(因为计算1G的离散日志很容易)；另一方面，您也可以同样地争辩说，值z = 8827773752...7876547109同样不能提供任何安全性，因为攻击者可以很容易地计算zG，如果他看到这一点，他就知道离散日志。

可以说，这适用于小于80位的秘密值，否则很可能会受到暴力搜索攻击。

这是正确的，如果攻击者事先知道秘密值小于80位。实际上，如果攻击者知道这一点，他可以通过O(2^{40})努力找到离散日志，这是可以由访问略多于平均计算资源的个人完成的。

另一方面，取一个随机的kG值，并使该猜测成功(假设256位曲线)的概率约为2^{-176}。此外，这不仅适用于小于80位的秘密；如果攻击者猜测前176个比特是值z (上面)，那么他可以计算kG - (z2^{80})G；如果他的猜测是正确的，这将在0G到2^{80}G的范围内，因此蛮力的努力将成功(并且具有相同的成功概率)。

因此，很难说碰巧在1G … 2^{80}G范围内的点比恰好在(z2^{80}+1)G … (z2^{80}+2^{80})G范围内的点弱(对于z的某些值，所有的点都在这样的范围内)。

在密码软件中，我们是否有生成“秘密随机值”的指导方针？

为什么，是的，是的，我们需要。您指出了FIPS 186-4中关于如何生成这样的随机值的部分(实际上，我们在这里讨论的是FIPS )。

尽管k值必须是无偏的，这也是至关重要的。

而这些建议恰恰实现了这一点。他们确实认为，所使用的已批准的RBG生成了不可区分的随机比特模式；据我们所知，批准的RBG正是这样做的。

您似乎是在要求一些拒绝某些值的测试(例如1)；这样的测试会引入一种偏见(如果可能是很小的)；这种偏见正是我们试图避免的……