使用 Jsch 生成 4096 位 RSA 密钥比 2048 位慢得多

我需要为客户端/服务器应用程序创建公钥和私钥 RSA 密钥，并且我正在使用JSch图书馆 http://www.jcraft.com/jsch/这样做。到目前为止，我一直在生成 4096 位密钥，因为我希望获得尽可能最好的安全性。然而，这需要 3~5 分钟，而生成 2048 位密钥则需要大约 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 密钥是如何生成的（因此使用库），但我认为所需的时间可能是指数级的？看起来……太指数化了。

这是JSch API http://epaul.github.io/jsch-documentation/javadoc/（因为图书馆本身及其来源的网站几乎没有文档）。

Update:我做了一些分析。下面是密钥生成时间的图表，从 512 位开始一直到 4096 位，每个密钥大小有 30 个样本。

这是一个类似的图表，排除了 4096 位试验（相同的数据集）：

它们看起来非常相似，这表明时间的指数增长相当平滑。我想我只是不耐烦了！

生成 RSA 密钥需要找到两个满足特定条件的大的随机素数。找到这样的素数本质上就是选择随机数，然后通过执行某些测试来检查它们是否是素数。这素数定理 http://en.wikipedia.org/wiki/Prime_number_theorem告诉我们，随着素数变得越来越大，它们也变得越来越稀有，所以你必须生成更多的随机数才能找到素数。对于较大的数字，确定该数字是否为素数的检查也需要更长的时间。

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