RSA 如何通过 p,q,dp,dq 计算出 e,d ?

[xgfan]

这两天在弄 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，计算起来也不算慢……

总结一下问题

1. 有没有其他好的方法通过p,q,dp,dq计算e和d

2. 或者有没有什么算法简化上面的过程，即

   x mod m = a

   x mod n = b

   m,n,a,b 均为已知值，求最小 x 值

[yangff]

中国剩余定理

[SoloCompany]

https://github.com/frohoff/jdk8u-dev-jdk/blob/jdk8u60-b10/src/share/classes/sun/security/rsa/RSAKeyPairGenerator.java#L119 ?

[Kilerd]

通常为了加快计算速度，会把 e 设为定值，也就是你说的 65537，然后用 EGCD 算 d。
当然啦，你也可以随机一个素数 e 出来，再用 EGCD 算 d

[xgfan]

@yangff 感谢。这个方法应该是很合理的了。
唉，数学不好是硬伤啊。

@SoloCompany 这个默认用的是 RSAKeyGenParameterSpec.F4,也是 65537，
或者是传入的 AlgorithmParameterSpec 里定义好的 F4。

[xgfan]

@Kilerd 哈哈，是的。但是我这边需要得到 e，d 两个值，要不然我这边签名出来，chinapay 那边就不认了。

[geelaw]

这个计算方法简直吓尿，把多项式问题变成指数问题了……

d=((p-1).modInverse(q-1)*(p-1)*dq+(q-1).modInverse(p-1)*(q-1)*dp)%((p-1)*(q-1))

[yinheli]

https://gist.github.com/yinheli/ec5590a9c0ee6828e7ca05149f7db1d6

[Kilerd]

@xgfan 看看 EGCD 啊