求助： RSA 密钥，已知 modulus、publicExponent、D(privateExponent) 如何推算出 P(prime1)、Q、DP、DQ、InverseQ(coefficient)

[xiangyuecn]

正在写一个 RSA 私钥 PEM 文件的生成，用于轻量级的转换 PKCS#1 、PKCS#8，但卡在了这个反向计算上，不会算😂

正在写 java 版代码：

/***
 * 通过公钥指数和私钥指数构造一个 PEM
 * @param modulus 必须提供模数
 * @param exponent 必须提供公钥指数
 * @param dOrNull 私钥指数可以不提供，导出的 PEM 就只包含公钥
 */
public RSA_PEM(byte[] modulus, byte[] exponent, byte[] dOrNull) {
	Key_Modulus=modulus;//modulus
	Key_Exponent=exponent;//publicExponent
	
	if(dOrNull!=null) {
		Key_D=dOrNull;//privateExponent
		
		//TODO 如何计算？
		Val_P=null;//prime1
		Val_Q=null;//prime2
		Val_DP=null;//exponent1
		Val_DQ=null;//exponent2
		Val_InverseQ=null;//coefficient
	}
}

//这些 byte[] 通过 BigInteger 转成大数进行运算

PEM 的解析以前已经写好了，现在 java 代码直接 copy 的 c#的代码，https://github.com/xiangyuecn/RSA-csharp/blob/master/RSA_PEM.cs 以前也是不会算，所有没有加由 Modulus 、Exponent 、D 的直接构造方法，要是加上就完美了

那么，是怎么样反向计算出 P 、Q 、DP 、DQ 、InverseQ 呢？

[terencelau]

如果是 CRT-RSA 的话：
DP = P mod d
DQ = Q mod d
InvQ * Q \equiv 1 mod P

所以，没有 P, Q 反向计算就是做大数分解

[terencelau]

@terencelau 写错了
DP = d mod P-1
DQ = d mod Q-1

[xiangyuecn]

@terencelau 要大数分解的意思就是无解了😂

[terencelau]

@xiangyuecn 就我的知识水平来看，只有这些是算不出来的

[qwerthhusn]

https://stackoverflow.com/questions/43136036/how-to-get-a-rsaprivatecrtkey-from-a-rsaprivatekey

这个，已知 RSAPrivateKey 算出 RSAPrivateCRTKey

[lapulasi]

如果相对于 N，D 的值比较小，那么通过 Wiener Attack 可以分解 N，得到 P 和 Q 。有了 P 和 Q，就可以算出 DP 、DQ 、InverseQ 。

[xiangyuecn]

@qwerthhusn 这个算法可以，1024 位的只需要 4ms 进行反解

我另外找到一个算法 https://stackoverflow.com/questions/2921406/calculate-primes-p-and-q-from-private-exponent-d-public-exponent-e-and-the 但需要 8ms 进行反解

测试生成的 pem 虽然和原 pem 的 P 、Q 不相同，但能正常拿这个 pem 解密公钥加密的内容，不提供 P 、Q 的私钥直接报错，有了就不会报错了

@terencelau 似乎搞定了😁

[xiangyuecn]

@lapulasi 已经有算法了，1024 位处理速度还可以😁

[terencelau]

@xiangyuecn 噢噢，因为我不熟悉 PEM :( 所以，只能看数学方面的问题 😂，这个算法学习了