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

Question

我需要为客户端/服务器应用程序创建公共和私有RSA密钥，我正在使用JSch library这样做。到目前为止，我一直在生成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（因为图书馆本身和它来自的网站旁边没有文档）。

更新：我做了一些分析。这是keygen时间图表，从512位开始，最高可达4096，每个键大小有30个样本。

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

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

Answer 1

生成RSA密钥需要找到两个满足特定条件的大型随机素数。找到这样的素数基本上是挑选随机数，然后通过执行某些测试来检查它们是否是素数。 Prime Number Theorem告诉我们，随着素数越来越大，它们也越来越少，所以你必须生成更多的随机数才能找到一个素数。确定数字是否为素数的检查对于更大的数字也需要更长的时间。

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

Answer 2

回答有点迟，但由于其他答案纯粹是启发式的，所以这里有一些背景知道为什么需要这么长时间：

RSA密钥生成的最慢部分通常是Fermat测试，必须为每个主要候选x运行，并且包括检查2 ^ {x-1} = 1模x（使用2可以比使用其他更快）基地）。那么Fermat测试所需的时间如何取决于x的位长？

1. 乘法的运行时间大约是因子的比特长度的二次方，因此加倍的长度使时间翻了四倍（对于学校乘法;如果你使用Karatsuba，那么它的时间大约是三倍;对于更复杂的乘法方法， RSA的长度太短）。
2. 模幂运算的运行时间在指数的位长度上是线性的。
3. 随机n位数为素数的概率为1：log（2 ^ n），其中log是自然对数，即，它是1：（n * log（2））。

因此，对于RSA密钥生成的运行时间而言，将位长加倍可得到（1）的因子4和来自（2）和（3）的因子2的两倍，因此总计Fermat测试的运行时间上升了16倍（或使用Karatsuba的12倍）。

由于密钥生成的其他部分的运行时间不会那么快，因此大约10的因素as indicated in the answer of by Iridium是合理的。

Answer 3

生成4096位长密钥比2048位密钥花费的时间要长得多，请参阅基准数字here。