这是一个创建于 2006 天前的主题，其中的信息可能已经有所发展或是发生改变。
正在写一个 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 呢？
第 1 条附言 2020-04-13 12:31:17 +08:00
代码已经好了，综合的#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; } } } 第 2 条附言 2020-04-13 16:53:20 +08:00
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; }  | 1 terencelau 2020-04-12 21:12:27 +08:00  1 如果是 CRT-RSA 的话： DP = P mod d DQ = Q mod d InvQ * Q \equiv 1 mod P 所以，没有 P, Q 反向计算就是做大数分解 |
| 2 terencelau 2020-04-12 21:13:11 +08:00 |
 | 3 xiangyuecn OP @terencelau 要大数分解的意思就是无解了 |
| 4 terencelau 2020-04-12 22:20:36 +08:00 @xiangyuecn 就我的知识水平来看，只有这些是算不出来的 |
 | 5 qwerthhusn 2020-04-13 10:09:35 +08:00 1 https://stackoverflow.com/questions/43136036/how-to-get-a-rsaprivatecrtkey-from-a-rsaprivatekey 这个，已知 RSAPrivateKey 算出 RSAPrivateCRTKey |
 | 6 lapulasi 2020-04-13 11:53:15 +08:00 1 如果相对于 N，D 的值比较小，那么通过 Wiener Attack 可以分解 N，得到 P 和 Q 。有了 P 和 Q，就可以算出 DP 、DQ 、InverseQ 。 |
| 7 xiangyuecn OP @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 似乎搞定了 |
| 8 xiangyuecn OP @lapulasi 已经有算法了，1024 位处理速度还可以 |
| 9 terencelau 2020-04-14 11:46:48 +08:00 @xiangyuecn 噢噢，因为我不熟悉 PEM :( 所以，只能看数学方面的问题 ，这个算法学习了 |
Select Language