正在写一个 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;
}
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 :( 所以,只能看数学方面的问题 😂,这个算法学习了
|