为什么 KeyPairGenerator.genKeyPair() 这么慢

Question

我有一些 Java 代码，当我运行运行 KeyPairGenerator.genKayPair() 时，它可以运行 40 秒或更长时间。如何改变这种状况？如果我运行

openssl req -x509 -nodes -days 365 -newkey rsa:4096 -keyout server.key -out cert.pem

工作 3 秒。慢码：

KeyPairGenerator gen = KeyPairGenerator.getInstance("RSA");
SecureRandom random = new SecureRandom();
gen.initialize(4096, random);        
keyPair = gen.generateKeyPair();        
PublicKey pubk = keyPair.getPublic();
PrivateKey prvk = keyPair.getPrivate();

Answer 1

首先，虽然 Java 在业务逻辑方面肯定很快，但优化的 C 代码（在重要的地方使用汇编）将在密码学方面大放异彩。

Java 将使用 BigInteger 来执行这些计算，并且 BigInteger - 并不总是包含针对所有功能的本机优化方法。请注意，Oracle JDK / OpenJDK has made several changes when this answer was posted 并允许 intrinsics 用于几个 BigInteger 方法，从 JDK 开始8，包括蒙哥马利乘法。脚本语言通常比 Java 差很多，除非它们调用本机代码。

Java也需要时间来优化字节码。这意味着如果多次调用它运行得更快。因此，您至少需要先调用一个密钥生成器，然后才能查看如果在您的应用程序中多次调用这样的方法会发生什么。在这种情况下，运行时间可能非常高，以至于它已经能够优化 - 这取决于 VM 实现。

RSA 密钥生成主要取决于找到两个个大小约为密钥大小一半的大素数。寻找大素数是一个非常 CPU 密集的过程。它还依赖于随机数生成器来创建起点。所以实际使用的随机数生成器实现有很大的不同 - 特别是 如果随机数生成器可以在没有足够的熵可用时阻塞。因此，尝试使用可用的随机数生成器，直到找到足够快速和安全的随机数生成器。

寻找一定长度的素数是一个没有指定运行时间的过程； 过程不是确定性的。选择一个非常大的数字（在这种情况下，大小约为 4096 / 2 = 2048 位）并开始测试后续数字是否为质数。这就是打击您的 CPU 的原因。因此，您需要计算生成素数的平均运行时间 - 以防您生成大量素数 - 否则您将不得不忍受它所花费时间的不确定性。

虽然这一切都没有实际意义。一般来说，您不需要大量的 RSA 密钥——您可以为每个用户生成一到三个密钥。所以这只会在以下情况下成为问题：

你有很多用户
您的协议需要大量密钥对或
您需要非常大的 RSA 密钥。

如果您想要更快地生成密钥对，您可以做一些事情：

获取已知速度很快的 Java Provider 的本机实现，例如使用本机代码或 HSM 等专用硬件；
切换到另一种密钥对生成速度很快的算法，例如椭圆曲线密码术；
使用 openssl 生成密钥，并在您的 Java 应用程序中 import/use 生成密钥。

通常您需要修复协议而不是密钥对生成器。通常你只使用不需要经常生成的静态密钥对（编辑：除了提供前向安全的密钥建立，但为此你通常使用（椭圆曲线）Diffie-Hellman，而不是 RSA）。

为什么 KeyPairGenerator.genKeyPair() 这么慢

Why KeyPairGenerator.genKeyPair() so slow

java

openssl

cryptography

rsa

key-generator