这两天在弄 chinapay 的接口,文档也不全。其中的签名方法用用到 rsa 相关的内容。
现在是能获取到 rsa 的 p
,q
,dp
,dq
四个值,以及衍生的其他值,需要何获取e
和d
。
这是我已经实现的一个计算 e 的方法
ed ≡ 1 (mod φ(n))
φ (n) ≡ (p-1) * (q-1)
dp ≡ d mod (p-1)
dq ≡ d mod (q-1)
public static BigInteger calcE(BigInteger p, BigInteger q, BigInteger dp, BigInteger dq) {
BigInteger e = BigInteger.ONE;
BigInteger p_1 = p.subtract(BigInteger.ONE);
BigInteger q_1 = q.subtract(BigInteger.ONE);
BigInteger phiN = p_1.multiply(q_1);
while (true) {
BigInteger d = e.modInverse(phiN);
try {
if (d.mod(p_1).equals(dp) && d.mod(q_1).equals(dq)) {
break;
}
} catch (Exception ignored) { }
e = e.add(BigInteger.ONE);
}
return e;
}
但是感觉这样遍历不太妥当,虽然我手上这个的e
是常见的 65537,计算起来也不算慢……
总结一下问题
有没有其他好的方法通过p
,q
,dp
,dq
计算e
和d
或者有没有什么算法简化上面的过程,即
x mod m = a
x mod n = b
m,n,a,b 均为已知值,求最小 x 值
1
yangff 2017-08-03 01:35:41 +08:00 via Android 1
中国剩余定理
|
2
SoloCompany 2017-08-03 01:51:30 +08:00 1
|
3
Kilerd 2017-08-03 02:25:45 +08:00 via iPhone
通常为了加快计算速度,会把 e 设为定值,也就是你说的 65537,然后用 EGCD 算 d。
当然啦,你也可以随机一个素数 e 出来,再用 EGCD 算 d |
4
xgfan OP @yangff 感谢。这个方法应该是很合理的了。
唉,数学不好是硬伤啊。 @SoloCompany 这个默认用的是 RSAKeyGenParameterSpec.F4,也是 65537, 或者是传入的 AlgorithmParameterSpec 里定义好的 F4。 |
6
geelaw 2017-08-03 03:05:41 +08:00
这个计算方法简直吓尿,把多项式问题变成指数问题了……
d=((p-1).modInverse(q-1)*(p-1)*dq+(q-1).modInverse(p-1)*(q-1)*dp)%((p-1)*(q-1)) |
7
yinheli 2017-08-03 14:30:01 +08:00 1
|