java - 使用 Jsch 生成 4096 位 RSA key 比 2048 位慢得多

Question

我需要为客户端/服务器应用程序创建 RSA 公钥和私钥，我正在使用 JSch library这样做。到目前为止，我一直在生成 4096 位 key ，因为我希望获得尽可能最好的安全性。然而，这需要 3~5 分钟，而生成 2048 位 key 需要大约 10 秒。有一个 sscce:

import com.jcraft.jsch.JSch;
import com.jcraft.jsch.JSchException;
import com.jcraft.jsch.KeyPair;

public class KeyGenerator {

    public static void main(String[] args) {
        JSch jsch = new JSch();

        System.out.println("Starting...");

        try {
            KeyPair keyPair = KeyPair.genKeyPair(jsch, KeyPair.RSA, 4096);
        }
        catch (JSchException e) {
            e.printStackTrace();
        }

        System.out.println("Done.");
    }
}

这种巨大的生成时间差异是否在预料之中？我不太清楚 RSA key 是如何生成的(因此使用库)，但我想所需的时间可能是指数级的？它似乎...太指数化了。

这是 JSch API (因为图书馆本身和它来自的网站几乎没有文档)。

更新:我做了一些分析。这是 key 生成时间的图表，从 512 位开始到 4096 位，每个 key 大小有 30 个样本。

下面是排除了 4096 位试验的类似图表(相同数据集):

这些看起来非常相似，这表示时间呈相当平滑的指数增长。我想我只是不耐烦了!

Answer 1

生成 RSA key 需要找到两个满足特定条件的大随机质数。找到这样的素数本质上就是选择随机数，然后通过执行某些测试来检查它们是否为素数。 Prime Number Theorem告诉我们，随着素数变大，它们也变得越来越稀有，因此您必须生成更多随机数才能找到一个素数。对于更大的数字，检查以确定数字是否为素数也需要更长的时间。

上述所有因素都会导致生成更大 key 所需的时间增加，但除此之外，听起来这个库并不是特别快。在相当现代的 PC 上使用 OpenSSL，我可以在 ~1 秒内生成一个 2048 位 key ，在 <10 秒内生成一个 4096 位 key ，所以你的 10 秒和 3-5 分钟的时间似乎过长。如果性能是个问题，我建议尝试使用不同的库，理解任何库生成大 key 的速度都会比生成小 key 慢!