使用Jsch生成4096位RSA密钥比2048位慢
Gra*_*ory 7 java performance rsa jsch
我需要为客户端/服务器应用程序创建公共和私有RSA密钥,我正在使用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(因为库本身及其来自的网站旁边没有文档).
更新:我做了一些分析.这是keygen时间图表,从512位开始,最高可达4096,每个键大小有30个样本.
这是一个类似的图表,排除了4096位试验(相同的数据集):
这些看起来非常相似,表示相当平滑的指数增加的时间.我想我只是不耐烦了!
Iri*_*ium 10
生成RSA密钥需要找到两个满足特定条件的大型随机素数.找到这样的素数基本上是挑选随机数,然后通过执行某些测试来检查它们是否是素数.该素数定理告诉我们,素数越来越大,他们也得到罕见的,所以你必须为了找到一个总理,以产生更多的随机数.确定数字是否为素数的检查对于更大的数字也需要更长的时间.
所有上述因素都会导致生成更大的密钥所需的时间增加,但是除此之外,听起来这个库并不是特别快.在相当现代的PC上使用OpenSSL,我可以在约1秒内生成2048位密钥,在<10秒内生成4096位密钥,因此10秒和3-5分钟的时间似乎过多.如果性能是一个问题,我建议尝试一个不同的库,理解比任何库生成大键比较小的库要慢!
答案有点晚了，但由于其他答案纯粹是启发式的，这里有一些关于为什么需要这么长时间的背景：
RSA 密钥生成中最慢的部分通常是 Fermat 测试，该测试必须对每个素数候选 x 运行，并包括检查 2^{x-1} = 1 modulo x 是否（使用 2 可以比使用其他更快）基地）。那么费马测试所需的时间与 x 的位长度有何关系呢？
乘法的运行时间大约是因子位长度的二次方，因此长度加倍会使时间增加四倍（这对于学校乘法而言；如果您使用 Karatsuba，那么时间大约是三倍；对于更复杂的乘法方法，位- RSA 的长度太短）。
模幂运算的运行时间与指数的位长度成线性关系。
随机n位数为素数的概率为1:log(2^n)，其中log为自然对数，即1:(n*log(2))。
因此，对于 RSA 密钥生成的运行时间，将位长度加倍可以得到 (1) 的 4 倍以及 (2) 和 (3) 的 2 倍的两倍，因此 Fermat 测试的运行时间总计上升 16 倍（或使用 Karatsuba 时上升 12 倍）。
由于密钥生成的其他部分的运行时间不会增加得那么快，因此如 Iridium 的答案所示，大约 10 的因子是合理的。