求助： 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 呢？

代码已经好了，综合的#5 和 #7 链接中的算法，经过简单测试没有问题。还需要更多的测试，有时间这个java版的也会开源

/***
 * 通过公钥指数和私钥指数构造一个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
		
		//反推P、Q
		BigInteger n = BigX(modulus);
		BigInteger e = BigX(exponent);
		BigInteger d = BigX(dOrNull);
		BigInteger p = findFactor(e, d, n);
		BigInteger q = n.divide(p);
		if (p.compareTo(q) > 0) {
			BigInteger t = p;
			p = q;
			q = t;
		}
		BigInteger exp1 = d.mod(p.subtract(BigInteger.ONE));
		BigInteger exp2 = d.mod(q.subtract(BigInteger.ONE));
		BigInteger coeff = q.modInverse(p);
		
		Val_P=p.toByteArray();//prime1
		Val_Q=q.toByteArray();//prime2
		Val_DP=exp1.toByteArray();//exponent1
		Val_DQ=exp2.toByteArray();//exponent2
		Val_InverseQ=coeff.toByteArray();//coefficient
	}
}
/**java byte是负数，需要加前导0转成正整数**/
static public BigInteger BigX(byte[] data) {
	if(data[0]<0) {
		byte[] c=new byte[data.length+1];
		System.arraycopy(data,0,c,1,data.length);
		data=c;
	}
	return new BigInteger(data);
}
private static BigInteger findFactor(BigInteger e, BigInteger d, BigInteger n) {
	BigInteger edMinus1 = e.multiply(d).subtract(BigInteger.ONE);
	int s = edMinus1.getLowestSetBit();
	BigInteger t = edMinus1.shiftRight(s);
	
	long now=System.currentTimeMillis();
	for (int aInt = 2; true; aInt++) {
		if(aInt%1000==0 && System.currentTimeMillis()-now>3000) {
			throw new RuntimeException("推算RSA.P超时");
		}
		
		BigInteger aPow = BigInteger.valueOf(aInt).modPow(t, n);
		for (int i = 1; i <= s; i++) {
			if (aPow.equals(BigInteger.ONE)) {
				break;
			}
			if (aPow.equals(n.subtract(BigInteger.ONE))) {
				break;
			}
			BigInteger aPowSquared = aPow.multiply(aPow).mod(n);
			if (aPowSquared.equals(BigInteger.ONE)) {
				return aPow.subtract(BigInteger.ONE).gcd(n);
			}
			aPow = aPowSquared;
		}
	}
}

BigInteger.toByteArray 对于 RSA的这些字段也有问题，RSA里面正整数应当去掉保证正整数的前导0，生成PEM的时候再加上，不然多出来的这个首位0就是多出了一个字节。

public RSA_PEM(byte[] modulus, byte[] exponent, byte[] dOrNull) {
	.....
		Val_P=BigB(p);//prime1
		Val_Q=BigB(q);//prime2
		Val_DP=BigB(exp1);//exponent1
		Val_DQ=BigB(exp2);//exponent2
		Val_InverseQ=BigB(coeff);//coefficient
	.....
}

/**java byte是负数，需要加前导0转成正整数**/
static public BigInteger BigX(byte[] data) {
	if(data[0]<0) {
		byte[] c=new byte[data.length+1];
		System.arraycopy(data,0,c,1,data.length);
		data=c;
	}
	return new BigInteger(data);
}
/**BigInt导出byte整数首字节>0x7F的会加0前导，保证正整数，因此需要去掉0**/
static public byte[] BigB(BigInteger bigx) {
	byte[] val=bigx.toByteArray();
	if(val[0]==0) {
		byte[] c=new byte[val.length-1];
		System.arraycopy(val,1,c,0,c.length);
		val=c;
	}
	return val;
}

[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 :( 所以，只能看数学方面的问题 😂，这个算法学习了