3

I have a java.security.interfaces.RSAPrivateKey and the corresponding java.security.interfaces.RSAPublicKey containing (only) modulus, private exponent and public exponent.

If I understand RSA right, it should be possible to recover the numbers for java.security.interfaces.RSAPrivateCrtKey (for CRT keys).

If so, how do I do it? (I assume there is some implementation already).

Artjom B.
  • 61,146
  • 24
  • 125
  • 222
Gustave
  • 3,359
  • 4
  • 31
  • 64
  • Before there can be an implementation it has to be possible on mathematical level. AFAIR you can compute a regular RSA key from a RSA-crt key, but not the other way round. But you should make sure and ask on http://crypto.stackexchange.com if it is possible to generate an RSA Chinese Remainder Theorem key from a regular one. – Robert Mar 31 '17 at 09:08
  • My question is possibly a duplicate of https://stackoverflow.com/questions/2921406/. Related questions in crypto.stackexchange.com: https://crypto.stackexchange.com/questions/25907 and https://crypto.stackexchange.com/questions/16036 – Gustave Apr 02 '17 at 16:22

2 Answers2

7

It is possible to do this, and there is a relatively fast algorithm to find the parameters. Here is some Java code that illustrates the algorithm.

The code below is my implementation of the algorithm specified in Chapter 8 of the Handbook of Applied Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone, CRC Press, 1996, section 8.2.2(i):

enter image description here

/**
 * Find a factor of n by following the algorithm outlined in Handbook of Applied Cryptography, section
 * 8.2.2(i). See https://cacr.uwaterloo.ca/hac/about/chap8.pdf.
 *
 */

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);

    for (int aInt = 2; true; aInt++) {
        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;
        }
    }

}

public static RSAPrivateCrtKey createCrtKey(RSAPublicKey rsaPub, RSAPrivateKey rsaPriv) throws NoSuchAlgorithmException, InvalidKeySpecException {

    BigInteger e = rsaPub.getPublicExponent();
    BigInteger d = rsaPriv.getPrivateExponent();
    BigInteger n = rsaPub.getModulus();
    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);
    RSAPrivateCrtKeySpec keySpec = new RSAPrivateCrtKeySpec(n, e, d, p, q, exp1, exp2, coeff);
    KeyFactory kf = KeyFactory.getInstance("RSA");
    return (RSAPrivateCrtKey) kf.generatePrivate(keySpec);

}
President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
1

It didn't work until I switched to "< 0".

I verified this by creating key pairs using KeyPairGenerator.generateKeyPair() and then comparing .getEncoded() for the private key "as is" with KeyFactory.generatePrivate().getEncoded() using the keyspec and got the same result.

Anders Rundgren
  • 21
  • 2