RSA密钥生成基准测试深度解析

RSA密钥生成基准测试

RSA密钥生成在概念上很简单，但却是密码学工程领域中最糟糕的实现任务之一。即使对其进行基准测试也很棘手，并且涉及一些数学知识：以下是我们如何生成稳定但具有代表性的"平均情况"，而不是使用普通的统计方法。

RSA密钥生成

假设您要生成一个2048位RSA密钥。思路是生成随机的1024位数字，直到找到两个质数，称它们为p和q，然后计算N = p × q和d = 65537⁻¹ mod φ(N)¹（然后还有一些操作以使运算更快，但您可以在此停止）。d的计算是RSA魔法的所在，但今天我们专注于第一部分。

选择质数候选几乎没有什么特别之处。您从CSPRNG中抽取适当大小的随机数，并且为了避免浪费时间，您设置最低有效位和两个最高有效位：大的偶数不是质数，设置前两位保证N不会太小。

检查数字x是否为质数通常使用米勒-拉宾测试²完成，这是一种概率算法，您选择一个"基数"并用它在x上运行一些计算。它要么最终证明x是合数（即不是质数），要么未能证明。弄清楚需要运行多少次米勒-拉宾测试出人意料地困难：最初您会了解到测试对合数失败的概率是1/4，这表明您需要40轮才能达到2⁻⁸⁰；然后您了解到这只是x最坏情况值的上限³，而随机值的失败几率要低得多；最终您还意识到这并不那么重要，因为您只在质数上运行所有迭代，而大多数合数在第一次迭代中就被拒绝。无论如何，BoringSSL有一个表格，对于1024位质数，我们需要5次带有随机基数的米勒-拉宾测试。

然而，米勒-拉宾有点慢，而且大多数数字都有小除数，因此通常更有效的方法是快速拒绝这些数字，通过进行"试除"或与前几个质数进行GCD。前几十个质数通常是一个重大胜利，但使用越来越多的质数收益递减。

有一百万零一件事可能出错，但有趣的是，您必须特意才能出错：如果完全随机生成大候选数，所有这些情况的发生几率在密码学上可以忽略不计。

总结一下，要生成RSA密钥，您需要生成两个质数。要生成质数，您选择随机数，尝试通过试除排除它们，然后对它们进行几次米勒-拉宾测试。

基准测试

现在，我们应该如何对其进行基准测试？运气会严重影响运行时间：您基本上是在对彩票进行基准测试。在调试性能回归时，Russ Cox运行了数百次测量，仍然得到了一些嘈杂且在有些地方可疑的结果。它也不够快，无法运行数百万次测量并让事情平均出来。

有人可能想通过将运行时间除以测试的候选数来标准化测量，但这不均匀地稀释了所有最终计算，并且仍然受到试除捕获的候选数以及进行米勒-拉宾测试的候选数的干扰。类似地，单独对米勒-拉宾进行基准测试忽略了最终计算，并且没有测量试除的影响。

我们可以做的是使用数学来找出平均代表性的候选序列是什么样的，并对其进行基准测试。由于密钥生成过程是可重复的⁴，我们可以预生成一个黄金候选序列，甚至在不同实现之间共享它以进行同类比较。

生成平均序列

首先，我们需要找出在每个质数之前平均应该期望有多少个合数。质数计数函数近似告诉我们小于x的质数有Li(x)个，这计算出⁵每354个1024位的奇数中有一个质数。

然后，我们对合数的小除数进行标准化。一个随机数有1/p的几率可被p整除，基于此，我们可以计算在遇到质数之前，期望遇到前n个质数整除的合数数量。例如，我们期望33%的数字可被3整除，46%可被3或5整除，69%的数字可被前10个质数之一整除，80%可被前50个质数之一整除，依此类推。反过来，我们使353个合数中的118个可被3整除，47个可被5整除但不能被3整除，27个可被7整除但不能被3或5整除，依此类推。这将使成功试除的次数具有代表性，甚至允许我们在不同试除阈值之间进行对比基准测试，而无需重新生成输入。

除了像密钥生成那样设置最高和最低位之外，我们还取消设置每个候选数的第二最低有效位并设置第三最低有效位，以标准化米勒-拉宾内循环的迭代次数，这取决于x-1的尾随零的数量。

我们不需要担心合数未能通过米勒-拉宾测试：如果5次测试足以达到2⁻¹¹²，那么一次测试失败的最大几率为2⁻²²，这在密码学上不可忽略，但不会在基准测试中出现。类似地，我们不需要担心e在模φ(N)下不可逆：我们使用65537作为e，它是质数，因此只有1/65537的数字不与其互质。

脚本、向量和结果

结果非常稳定，应该在绝对运行时间和不同函数消耗的CPU时间方面都具有代表性，允许进行有意义的性能分析。生成20个随机平均轨迹并对它们进行基准测试产生的方差小于1%。

您可以在Go标准库代码审查中看到它的使用。生成轨迹的脚本以及十个现成的轨迹可在CCTV中获得，欢迎您使用它们来对您的实现进行基准测试！

如果您读到这里，您可能还想在Bluesky上关注我@filippo.abyssdomain.expert或在Mastodon上关注我@filippo@abyssdomain.expert。

或者，如果您想让自己的生活更艰难，代码更复杂而没有实际好处，可以使用λ(N)而不是φ(N)，但这是另一个话题。↩

还有卢卡斯测试，进行一轮基数为2的米勒-拉宾测试和一次卢卡斯测试被称为Baillie-PSW测试。没有已知的合数通过Baillie-PSW测试，这听起来很棒，但卢卡斯测试实现起来非常麻烦。↩

在对抗性环境中，您还需要担心攻击者强制或适应您选择的基数。名为《Prime and Prejudice: Primality Testing Under Adversarial Conditions》由Albrecht等人完成的论文展示了一些有趣的技巧，但主要技巧归结为观察：如果您硬编码基数或从x生成它们，它们就不是随机的。↩

严格来说它不是确定性的，因为测试是随机的，但得出不同结论的几率在密码学上可以忽略，甚至运行时间出现重大偏差的几率也非常小，正如我们将看到的。↩

我进行了一个快速的蒙特卡洛模拟来检查这是否正确，看到数值摆动并收敛到期望值真的很有趣。数学！↩