Rebuild of a RSA Private Key from modulus & exponent fails

Question

I'm trying to rebuild a RSA keypair from modulus & private/public exponents. The conversion works correct for the public key but fails to private key when comparing the encoded private keys.

When using this rebuild private/public keypair for encryption it works (!) in Java, but when using the rebuild keypair in PHP, the decryption part fails (encryption is working), so it seems to me that the rebuild private key is something different to the "original" private key.

Just for info: using the "original" keypair everything is working fine in PHP.

So my question: how can I retrieve the "original" private key from (BigInteger) modulus & private exponent?

Edit: see my final edit at the end

My sample code shows the equality of public key vs. rebuild one and that the private keys are different:

Rebuilding of a RSA PrivateKey from modulus & exponent
privateKey equals rebuild: false
publicKey equals rebuild: true

code:

import java.math.BigInteger;
import java.security.*;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.InvalidKeySpecException;
import java.security.spec.RSAPrivateKeySpec;
import java.security.spec.RSAPublicKeySpec;
import java.util.Arrays;

public class RebuildRSAPrivateKey {
    public static void main(String[] args) throws NoSuchAlgorithmException, InvalidKeySpecException {
        System.out.println("Rebuilding of a RSA PrivateKey from modulus & exponent");
        // rsa key generation
        KeyPairGenerator kpGen = KeyPairGenerator.getInstance("RSA");
        //kpGen.initialize(2048, new SecureRandom());
        kpGen.initialize(2048, new SecureRandom());
        KeyPair keyPair = kpGen.generateKeyPair();
        // private key
        PrivateKey privateKey = keyPair.getPrivate();
        // get modulus & exponent
        RSAPrivateKey rsaPrivateKey = (RSAPrivateKey) privateKey;
        BigInteger modulus = rsaPrivateKey.getModulus();
        BigInteger privateExponent = rsaPrivateKey.getPrivateExponent();
        // rebuild the private key
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        RSAPrivateKeySpec rsaPrivateKeySpec = new RSAPrivateKeySpec(modulus, privateExponent);
        PrivateKey privateKeyRebuild = keyFactory.generatePrivate(rsaPrivateKeySpec);
        System.out.println("privateKey equals rebuild: " + Arrays.equals(privateKey.getEncoded(), privateKeyRebuild.getEncoded()));
        // public key
        PublicKey publicKey = keyPair.getPublic();
        // get modulus & exponent
        RSAPublicKey rsaPublicKey = (RSAPublicKey) publicKey;
        BigInteger modulusPub = rsaPublicKey.getModulus();
        BigInteger publicExponent = rsaPublicKey.getPublicExponent();
        // rebuild the public key
        KeyFactory keyFactoryPub = KeyFactory.getInstance("RSA");
        RSAPublicKeySpec rsaPublicKeySpec = new RSAPublicKeySpec(modulusPub, publicExponent);
        PublicKey publicKeyRebuild = keyFactory.generatePublic(rsaPublicKeySpec);
        System.out.println("publicKey equals rebuild: " + Arrays.equals(publicKey.getEncoded(), publicKeyRebuild.getEncoded()));
    }
}

Edit: The following programs will show that a RSA private/public keypair derived from encoded keys can get restored and the encryption and decryption works in Java and PHP. The keys are insecure RSA 512 bit keys and Base64 decoded.

The same keys are then derived from modulus and private/public exponents and the en-/decryption works in Java but not in PHP.

That's why I'd like to get the "original" RSA keys from modulus and exponents, thanks for your kindly help.

Result of Java program:

Rebuilding of a RSA PrivateKey from modulus & exponent v4
privateKey Original Base64: MIIBVgIBADANBgkqhkiG9w0BAQEFAASCAUAwggE8AgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIDAQABAkEAkDpf4gNRrms+W/mpSshyKsoDTbh9+d5ePP601QlQI79lrsjdy2GLgk4RV1XmwYinM9Sk8G+ssyXTYHdby6A2wQIhAPcRtl6tub6PFiIE1jcuIkib/HzAdRYHZx3ZdzRTYDetAiEA4uv43xpGl5N8yG27Kv0DkRoOlr4Ch6oM24hLVw7ClhcCIFgdRAo+MQlqJH2bdf6WAHoez4x6YwepOjhmD2Jk/eK9AiEAtHgI6J5EEB56+gfS+CBa6tZ3Tcl1x6ElMp8Vk/ooJScCIQDUa3LUkcc58yjJYq8ZNQC/86+HIzd5MldTwg5buR1lpw==
privateKey Rebuild  Base64: MIIBVgIBADANBgkqhkiG9w0BAQEFAASCAUAwggE8AgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIDAQABAkEAkDpf4gNRrms+W/mpSshyKsoDTbh9+d5ePP601QlQI79lrsjdy2GLgk4RV1XmwYinM9Sk8G+ssyXTYHdby6A2wQIhAPcRtl6tub6PFiIE1jcuIkib/HzAdRYHZx3ZdzRTYDetAiEA4uv43xpGl5N8yG27Kv0DkRoOlr4Ch6oM24hLVw7ClhcCIFgdRAo+MQlqJH2bdf6WAHoez4x6YwepOjhmD2Jk/eK9AiEAtHgI6J5EEB56+gfS+CBa6tZ3Tcl1x6ElMp8Vk/ooJScCIQDUa3LUkcc58yjJYq8ZNQC/86+HIzd5MldTwg5buR1lpw==
publicKey           Base64: MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==

generate private & public key via modulus and private/public exponent
privateKey Modulus  Base64: MIGzAgEAMA0GCSqGSIb3DQEBAQUABIGeMIGbAgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIBAAJBAJA6X+IDUa5rPlv5qUrIcirKA024ffneXjz+tNUJUCO/Za7I3cthi4JOEVdV5sGIpzPUpPBvrLMl02B3W8ugNsECAQACAQACAQACAQACAQA=
publicKey  Modulus  Base64: MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==

en-/decryption with original keys
ciphertext Original   : fvFPRZ5B2GMgv9aXQjyQsxnRHK2wotfXlLV+zGea1E3nsZC6RMn+LQMOe9yvZ8IcaG2F/8wWv2NkNmBX4wuxaw==
decryptedtext Original: this is the message to encrypt

en-/decryption with keys from modulus & exponent
ciphertext Modulus    : o0tB4xQIwQRFDSsWj1WgWHexXnJOp9jeBymFPJvy+xZBvfJay2yR0XZEy+0VwaedxdTf9CoyKVvgCbn2HCohSQ==
decryptedtext Modulus : this is the message to encrypt

Result of PHP program:

php version: 7.4.6 openssl version: OpenSSL 1.1.1g 21 Apr 2020
plaintext: this is the message to encrypt
rsa encryption with original keys
priBase64:MIIBVgIBADANBgkqhkiG9w0BAQEFAASCAUAwggE8AgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIDAQABAkEAkDpf4gNRrms+W/mpSshyKsoDTbh9+d5ePP601QlQI79lrsjdy2GLgk4RV1XmwYinM9Sk8G+ssyXTYHdby6A2wQIhAPcRtl6tub6PFiIE1jcuIkib/HzAdRYHZx3ZdzRTYDetAiEA4uv43xpGl5N8yG27Kv0DkRoOlr4Ch6oM24hLVw7ClhcCIFgdRAo+MQlqJH2bdf6WAHoez4x6YwepOjhmD2Jk/eK9AiEAtHgI6J5EEB56+gfS+CBa6tZ3Tcl1x6ElMp8Vk/ooJScCIQDUa3LUkcc58yjJYq8ZNQC/86+HIzd5MldTwg5buR1lpw==
pubBase64:MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==
ciphertext Base64:WmvVwqf2EHQc0yb6L4pVJ0/23pNW4QsBun3SNvYE8p/sEk+1GQSYxYpbY/mLbSGF2Lb1P5g5er+z7dWxHmodNA==
decryptedtext: this is the message to encrypt

rsa encryption with keys created via modulus & exponents
priBase64:MIGzAgEAMA0GCSqGSIb3DQEBAQUABIGeMIGbAgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIBAAJBAJA6X+IDUa5rPlv5qUrIcirKA024ffneXjz+tNUJUCO/Za7I3cthi4JOEVdV5sGIpzPUpPBvrLMl02B3W8ugNsECAQACAQACAQACAQACAQA=
pubBase64:MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==
ciphertext Base64:kqn8aZpvfpPzr3u2NBX/XmnlFweEvOm+Qu4l2wiUSQCjA0hutQ10mbLaO55oCox7GixvMgb3VtoDBJ8hfW1zbQ==
Cannot Decrypt error:0407109F:rsa routines:RSA_padding_check_PKCS1_type_2:pkcs decoding error
decryptedtext:

decrypt error: error:0909006C:PEM routines:get_name:no start line

Source Java:

import javax.crypto.BadPaddingException;
import javax.crypto.Cipher;
import javax.crypto.IllegalBlockSizeException;
import javax.crypto.NoSuchPaddingException;
import java.io.IOException;
import java.math.BigInteger;
import java.security.*;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.*;
import java.util.Base64;

public class RebuildRSAPrivateKey4 {
    public static void main(String[] args) throws NoSuchAlgorithmException, InvalidKeySpecException, IllegalBlockSizeException, InvalidKeyException, BadPaddingException, NoSuchPaddingException, IOException {
        System.out.println("Rebuilding of a RSA PrivateKey from modulus & exponent v4");
        // rsa key generation
        KeyPairGenerator kpGen = KeyPairGenerator.getInstance("RSA");
        //kpGen.initialize(2048, new SecureRandom());
        kpGen.initialize(512, new SecureRandom()); // don't use 512 bit keys as they are insecure !!
        KeyPair keyPair = kpGen.generateKeyPair();

        // privateKey   Base64: MIIBVgIBADANBgkqhkiG9w0BAQEFAASCAUAwggE8AgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIDAQABAkEAkDpf4gNRrms+W/mpSshyKsoDTbh9+d5ePP601QlQI79lrsjdy2GLgk4RV1XmwYinM9Sk8G+ssyXTYHdby6A2wQIhAPcRtl6tub6PFiIE1jcuIkib/HzAdRYHZx3ZdzRTYDetAiEA4uv43xpGl5N8yG27Kv0DkRoOlr4Ch6oM24hLVw7ClhcCIFgdRAo+MQlqJH2bdf6WAHoez4x6YwepOjhmD2Jk/eK9AiEAtHgI6J5EEB56+gfS+CBa6tZ3Tcl1x6ElMp8Vk/ooJScCIQDUa3LUkcc58yjJYq8ZNQC/86+HIzd5MldTwg5buR1lpw==
        // publicKey    Base64: MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==
        String privateKeyBase64 = "MIIBVgIBADANBgkqhkiG9w0BAQEFAASCAUAwggE8AgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIDAQABAkEAkDpf4gNRrms+W/mpSshyKsoDTbh9+d5ePP601QlQI79lrsjdy2GLgk4RV1XmwYinM9Sk8G+ssyXTYHdby6A2wQIhAPcRtl6tub6PFiIE1jcuIkib/HzAdRYHZx3ZdzRTYDetAiEA4uv43xpGl5N8yG27Kv0DkRoOlr4Ch6oM24hLVw7ClhcCIFgdRAo+MQlqJH2bdf6WAHoez4x6YwepOjhmD2Jk/eK9AiEAtHgI6J5EEB56+gfS+CBa6tZ3Tcl1x6ElMp8Vk/ooJScCIQDUa3LUkcc58yjJYq8ZNQC/86+HIzd5MldTwg5buR1lpw==";
        String publicKeyBase64 = "MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==";
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        PKCS8EncodedKeySpec privateKeySpec = new PKCS8EncodedKeySpec(Base64.getDecoder().decode(privateKeyBase64));
        PrivateKey privateKey = keyFactory.generatePrivate(privateKeySpec);
        X509EncodedKeySpec publicKeySpec = new X509EncodedKeySpec(Base64.getDecoder().decode(publicKeyBase64));
        PublicKey publicKey = keyFactory.generatePublic(publicKeySpec);
        System.out.println("privateKey Original Base64: " + privateKeyBase64);
        System.out.println("privateKey Rebuild  Base64: " + Base64.getEncoder().encodeToString(privateKey.getEncoded()));
        System.out.println("publicKey           Base64: " + publicKeyBase64);
        // get modulus & private exponent via RSAPrivateKey
        RSAPrivateKey rsaPrivateKey = (RSAPrivateKey) privateKey;
        BigInteger modulus = rsaPrivateKey.getModulus();
        BigInteger privateExponent = rsaPrivateKey.getPrivateExponent();
        // rebuild the private key
        RSAPrivateKeySpec rsaPrivateKeySpec = new RSAPrivateKeySpec(modulus, privateExponent);
        PrivateKey privateKeyModulusExponent = keyFactory.generatePrivate(rsaPrivateKeySpec);
        // public key
        RSAPublicKey rsaPublicKey = (RSAPublicKey) publicKey;
        BigInteger modulusPub = rsaPublicKey.getModulus();
        BigInteger publicExponent = rsaPublicKey.getPublicExponent();
        // rebuild the public key
        RSAPublicKeySpec rsaPublicKeySpec = new RSAPublicKeySpec(modulusPub, publicExponent);
        PublicKey publicKeyModulusExponent = keyFactory.generatePublic(rsaPublicKeySpec);
        System.out.println("\ngenerate private & public key via modulus and private/public exponent");
        System.out.println("privateKey Modulus  Base64: " + Base64.getEncoder().encodeToString(privateKeyModulusExponent.getEncoded()));
        System.out.println("publicKey  Modulus  Base64: " + Base64.getEncoder().encodeToString(publicKeyModulusExponent.getEncoded()));
        System.out.println("\nen-/decryption with original keys");
        String plaintext = "this is the message to encrypt";
        String ciphertextOriginal = encrypt(publicKey, plaintext);
        String decryptedtextOriginal = decrypt(privateKey, ciphertextOriginal);
        System.out.println("ciphertext Original   : " + ciphertextOriginal);
        System.out.println("decryptedtext Original: " + decryptedtextOriginal);
        System.out.println("\nen-/decryption with keys from modulus & exponent");
        String ciphertextModulus = encrypt(publicKeyModulusExponent, plaintext);
        String decryptedtextModulus = decrypt(privateKeyModulusExponent, ciphertextOriginal);
        System.out.println("ciphertext Modulus    : " + ciphertextModulus);
        System.out.println("decryptedtext Modulus : " + decryptedtextModulus);
    }

    private static String encrypt(PublicKey publicKey, String plaintext) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, IOException, BadPaddingException, IllegalBlockSizeException {
        String ciphertext = "";
        Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
        cipher.init(Cipher.ENCRYPT_MODE, publicKey);
        byte[] ciphertextByte = cipher.doFinal(plaintext.getBytes("UTF8"));
        ciphertext = Base64.getEncoder().encodeToString(ciphertextByte).replaceAll("\\r|\\n", "");
        return ciphertext;
    }

    private static String decrypt(PrivateKey privateKey, String ciphertext) throws NoSuchAlgorithmException, NoSuchPaddingException, InvalidKeyException, BadPaddingException, IllegalBlockSizeException {
        Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");
        cipher.init(Cipher.DECRYPT_MODE, privateKey);
        byte[] ciphertextByte = Base64.getDecoder().decode(ciphertext);
        byte[] decryptedtextByte = cipher.doFinal(ciphertextByte);
        return new String(decryptedtextByte);
    }
    private static String bytesToHex(byte[] bytes) {
        StringBuffer result = new StringBuffer();
        for (byte b : bytes) result.append(Integer.toString((b & 0xff) + 0x100, 16).substring(1));
        return result.toString();
    }

}

Source PHP:

<?php

function encrypt($publicKeyBase64, $plaintext){
    $pub = base64_decode($publicKeyBase64);
    // public key conversion der to pem
    $pubPem = chunk_split(base64_encode($pub), 64, "\n");
    $pubPem = "-----BEGIN PUBLIC KEY-----\n" . $pubPem . "-----END PUBLIC KEY-----\n";
    $ublicKey = "";
    $publicKey = openssl_get_publickey($pubPem);
    if (!$publicKey) {
        echo "Cannot get public key" . "<br>";
    }
    $ciphertext = "";
    openssl_public_encrypt($plaintext, $ciphertext, $publicKey);
    if (!empty($ciphertext)) {
        openssl_free_key($publicKey);
        //echo "Encryption OK!" . "<br>";
    } else {
        echo "Cannot Encrypt" . "<br>";
    }
    $ciphertextBase64 = base64_encode($ciphertext);
    return $ciphertextBase64;
}

function decrypt($privateKeyBase64, $ciphertext){
    $pri = base64_decode($privateKeyBase64);
    // private key conversion der to pem
    $priPem = chunk_split(base64_encode($pri), 64, "\n");
    $priPem = "-----BEGIN PRIVATE KEY-----\n" . $priPem . "-----END PRIVATE KEY-----\n";
    $privateKey = openssl_get_privatekey($priPem);
    $Crypted = openssl_private_decrypt($ciphertext, $decryptedtext, $privateKey);
    if (!$Crypted) {
        echo 'Cannot Decrypt ' . openssl_error_string() . '<br>';
    } else {
        openssl_free_key($privateKey);
        //echo "decryptedtext: " . $decryptedtext . "<br>";
    }
    return $decryptedtext;
}

echo 'php version: ' . PHP_VERSION . ' openssl version: ' . OPENSSL_VERSION_TEXT . '<br>';
$plaintext = "this is the message to encrypt";
echo "plaintext: " . $plaintext . "<br>";

// RSA 512 keys from Java GenerateKeysSo.java
echo 'rsa encryption with original keys' . '<br>';
$priBase64 = "MIIBVgIBADANBgkqhkiG9w0BAQEFAASCAUAwggE8AgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIDAQABAkEAkDpf4gNRrms+W/mpSshyKsoDTbh9+d5ePP601QlQI79lrsjdy2GLgk4RV1XmwYinM9Sk8G+ssyXTYHdby6A2wQIhAPcRtl6tub6PFiIE1jcuIkib/HzAdRYHZx3ZdzRTYDetAiEA4uv43xpGl5N8yG27Kv0DkRoOlr4Ch6oM24hLVw7ClhcCIFgdRAo+MQlqJH2bdf6WAHoez4x6YwepOjhmD2Jk/eK9AiEAtHgI6J5EEB56+gfS+CBa6tZ3Tcl1x6ElMp8Vk/ooJScCIQDUa3LUkcc58yjJYq8ZNQC/86+HIzd5MldTwg5buR1lpw==";
$pubBase64 = "MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==";
echo 'priBase64:' . $priBase64 . '<br>';
echo 'pubBase64:' . $pubBase64 . '<br>';
$ciphertextBase64 = encrypt($pubBase64, $plaintext);
echo 'ciphertext Base64:' . $ciphertextBase64 . '<br>';
$ciphertext = base64_decode($ciphertextBase64);
$decryptedtext = decrypt($priBase64, $ciphertext);
echo "decryptedtext: " . $decryptedtext . "<br><br>";

// keys created via modulus & exponent
$priBase64 = "MIGzAgEAMA0GCSqGSIb3DQEBAQUABIGeMIGbAgEAAkEA2wFgcni89ijJ/uijQkzCGF4JiUB1+mEJ48u4Lk0vxB7ym3/FCvOEnN2H7FLUzsGvXRhFriLBiSJlg2tOhV5eiwIBAAJBAJA6X+IDUa5rPlv5qUrIcirKA024ffneXjz+tNUJUCO/Za7I3cthi4JOEVdV5sGIpzPUpPBvrLMl02B3W8ugNsECAQACAQACAQACAQACAQA=";
$pubBase64 = "MFwwDQYJKoZIhvcNAQEBBQADSwAwSAJBANsBYHJ4vPYoyf7oo0JMwhheCYlAdfphCePLuC5NL8Qe8pt/xQrzhJzdh+xS1M7Br10YRa4iwYkiZYNrToVeXosCAwEAAQ==";
echo 'rsa encryption with keys created via modulus & exponents' . '<br>';
echo 'priBase64:' . $priBase64 . '<br>';
echo 'pubBase64:' . $pubBase64 . '<br>';
$ciphertextBase64 = encrypt($pubBase64, $plaintext);
echo 'ciphertext Base64:' . $ciphertextBase64 . '<br>';
$ciphertext = base64_decode($ciphertextBase64);
$decryptedtext = decrypt($priBase64, $ciphertext);
echo "decryptedtext: " . $decryptedtext . "<br><br>";
echo 'decrypt error: error:0909006C:PEM routines:get_name:no start line' . '<br>';
?>

Final Edit solution & conclusion

If we want to use a RSA private-public keypair for encryption (and signing as well ?) in other systems than Java it is of importance that the private key is saved immeditaly. If we are trying to rebuild the private key from the encoded form (via PKCS8EncodedKeySpec) some data are definitely missing. Those rebuild private keys will fail to work (here in PHP/openssl).

If we need to rebuild a private key from the encoded-form (byte[]) the keys need to get enhanced via a method called "createCrtKey" - this method was written by President James K. Polk and all credits go to him. As links sometimes date out I marked my own answer below as accepted one because the createCrtKey-method is documented there.

Thanks to @President James K. Polk, @Topaco and @michalk for guiding me into the right direction.

Answer 1

The minimal information needed to perform the RSA decrypt operation is the modulus n and the decrypt exponent d. There's an optimization that can be applied to RSA decryption involving the Chinese Remainder Theorem whereby exponentiations are done mod the RSA primes separately and then combined to produce a final value, and thus there are some extra fields fields for this purpose in the RSA Private Key syntax and the Java RSAPrivateCrtKey interface modeled after it.

Now the question being raised here is: When are two RSAPrivateCrtKey instances equal? I would argue that they are equal when they function identically in the RSA algorithm. You are asking for a more narrow definition, namely they are equal when their encoded forms are equal. The problem with this definition is that it is too implementation-specific. Currently, when the "Sun" provider generates a key pair it always orders the primes p and q such that p > q. But I like it the other way, where p < q. The RSAPrivateCrtKey interface does not care either way as it does no checking. The Javadocs for the interface do not specify an order. You can change my code to produce what should be the same encoded form as the current "Sun" implementation simply by reversing the comparison in p.compareTo(q) > 0. However, the default implementation can change to match my preference in the future, and it will if my plan to take over the world succeeds. The Javadocs are the specification, and the implementation may change as long as it complies with the Javadocs.

Below I have provided an implementation of an equality function in which I have tried to incorporate the widest possible notion of equality consistent with the specification. That is, any two RSAPrivateCRTKey instances for which keyEquals returns true should produce identical results when used in the RSA algorithm, and if false is returned then there should be at least one value for which they produce different results.

public static boolean keyEquals(RSAPrivateCrtKey k1, RSAPrivateCrtKey k2) {

    final BigInteger ZERO = BigInteger.ZERO;

    boolean result = true;

    result = result && isConsistent(k1) && isConsistent(k2);
    result = result && k1.getModulus().equals(k2.getModulus());
    BigInteger lambda = computeCarmichaelLambda(k1.getPrimeP(), k1.getPrimeQ());

    result = result && k1.getPublicExponent().subtract(k2.getPublicExponent()).mod(lambda).equals(ZERO);
    result = result && k1.getPrivateExponent().subtract(k2.getPrivateExponent()).mod(lambda).equals(ZERO);

    return result;
}

private static boolean isConsistent(RSAPrivateCrtKey k1) {
    final BigInteger ZERO = BigInteger.ZERO;
    final BigInteger ONE = BigInteger.ONE;

    BigInteger n = k1.getModulus();
    BigInteger p = k1.getPrimeP();
    BigInteger q = k1.getPrimeQ();
    BigInteger e = k1.getPublicExponent();
    BigInteger d = k1.getPrivateExponent();

    boolean result = true;

    result = p.multiply(q).equals(n);
    BigInteger lambda = computeCarmichaelLambda(p, q);
    result = result && e.multiply(d).mod(lambda).equals(ONE);
    result = result && d.subtract(key.getPrimeExponentP()).mod(p.subtract(ONE)).equals(ZERO);
    result = result && d.subtract(key.getPrimeExponentQ()).mod(q.subtract(ONE)).equals(ZERO);
    result = result && q.multiply(k1.getCrtCoefficient()).mod(p).equals(ONE);
    return result;
}

private static BigInteger computeCarmichaelLambda(BigInteger p, BigInteger q) {
    return lcm(p.subtract(BigInteger.ONE), q.subtract(BigInteger.ONE));
}

private static BigInteger lcm(BigInteger x, BigInteger y) {
    return x.multiply(y).divide(x.gcd(y));
}

Answer 2

This is the modified version of my program that has the additional code from @President James K. Polk (see link of Topaco above). Even if the rebuild CRT-private key is now longer than the rebuild Private Key it does not match the original (encoded) private key. As I'm using the encoded private and public keys for a PHP RSA encryption/decryption there is the funny fact that the original keys run successfully but the rebuild ones not...

This version uses a 512 bit keylength that is insecure is for demonstration only (to keep the keys shorter).

result:

Rebuilding of a RSA PrivateKey from modulus & exponent
privateKey equals rebuild: false
publicKey equals rebuild: true
privateKey original    encoded: 30820154020100300d06092a864886f70d01010105000482013e3082013a020100024100a45477b9f00f51c8e1d5cb961a485c74ee123aa6da5c5bfd43f62acee9b684a8f140bb7a68996a77d04bdaabc5f259cb38a7bef909f4d85c6a597519a09aec9b0203010001024066ea4fa12f6b28b93a567f0e1e9fbae7b041d261b4d7aaf4ce9f58e8050ebdbd5e2a6261f06de2d72c4fdc6a62465f9cad9e8f5860bb2f8395cd903a214fb441022100e3b260dcced139557591b609470d8f0e518351a97bdbf26a59a41140a68778e9022100b8c1ab98f7b7280bd4b53fa3ed09c11d12aec9873d8a4a05e43152bc0d3346e302201d801ff29bcd19bb8bc6fc29c98de529fabfa3d5ec993b9831d302f5385e36f90220009e0d0fbecc2ae3173bdfd1916a35edfdf0fd95691c3c3116d91f58a786a357022100a810110da3d9d4de34e64029a3535368bb52e7b81055239cb4443d5172aea8e5
privateKey rebuild     encoded: 3081b2020100300d06092a864886f70d010101050004819d30819a020100024100a45477b9f00f51c8e1d5cb961a485c74ee123aa6da5c5bfd43f62acee9b684a8f140bb7a68996a77d04bdaabc5f259cb38a7bef909f4d85c6a597519a09aec9b020100024066ea4fa12f6b28b93a567f0e1e9fbae7b041d261b4d7aaf4ce9f58e8050ebdbd5e2a6261f06de2d72c4fdc6a62465f9cad9e8f5860bb2f8395cd903a214fb441020100020100020100020100020100
privateKey rebuild CRT encoded: 30820153020100300d06092a864886f70d01010105000482013d30820139020100024100a45477b9f00f51c8e1d5cb961a485c74ee123aa6da5c5bfd43f62acee9b684a8f140bb7a68996a77d04bdaabc5f259cb38a7bef909f4d85c6a597519a09aec9b0203010001024066ea4fa12f6b28b93a567f0e1e9fbae7b041d261b4d7aaf4ce9f58e8050ebdbd5e2a6261f06de2d72c4fdc6a62465f9cad9e8f5860bb2f8395cd903a214fb441022100b8c1ab98f7b7280bd4b53fa3ed09c11d12aec9873d8a4a05e43152bc0d3346e3022100e3b260dcced139557591b609470d8f0e518351a97bdbf26a59a41140a68778e90220009e0d0fbecc2ae3173bdfd1916a35edfdf0fd95691c3c3116d91f58a786a35702201d801ff29bcd19bb8bc6fc29c98de529fabfa3d5ec993b9831d302f5385e36f9022030634f5490e1bb4b56a68715d3c80a92c6e8f7c9f3e79f125a9969e6fc095705

code:

import java.math.BigInteger;
import java.security.*;
import java.security.interfaces.RSAPrivateCrtKey;
import java.security.interfaces.RSAPrivateKey;
import java.security.interfaces.RSAPublicKey;
import java.security.spec.InvalidKeySpecException;
import java.security.spec.RSAPrivateCrtKeySpec;
import java.security.spec.RSAPrivateKeySpec;
import java.security.spec.RSAPublicKeySpec;
import java.util.Arrays;

public class RebuildRSAPrivateKey2 {
    public static void main(String[] args) throws NoSuchAlgorithmException, InvalidKeySpecException {
        System.out.println("Rebuilding of a RSA PrivateKey from modulus & exponent");
        // rsa key generation
        KeyPairGenerator kpGen = KeyPairGenerator.getInstance("RSA");
        //kpGen.initialize(2048, new SecureRandom());
        kpGen.initialize(512, new SecureRandom()); // don't use 512 bit keys as they are insecure !!
        KeyPair keyPair = kpGen.generateKeyPair();
        // private key
        PrivateKey privateKey = keyPair.getPrivate();
        // get modulus & exponent
        RSAPrivateKey rsaPrivateKey = (RSAPrivateKey) privateKey;
        BigInteger modulus = rsaPrivateKey.getModulus();
        BigInteger privateExponent = rsaPrivateKey.getPrivateExponent();
        // rebuild the private key
        KeyFactory keyFactory = KeyFactory.getInstance("RSA");
        RSAPrivateKeySpec rsaPrivateKeySpec = new RSAPrivateKeySpec(modulus, privateExponent);
        PrivateKey privateKeyRebuild = keyFactory.generatePrivate(rsaPrivateKeySpec);
        System.out.println("privateKey equals rebuild: " + Arrays.equals(privateKey.getEncoded(), privateKeyRebuild.getEncoded()));
        // public key
        PublicKey publicKey = keyPair.getPublic();
        // get modulus & exponent
        RSAPublicKey rsaPublicKey = (RSAPublicKey) publicKey;
        BigInteger modulusPub = rsaPublicKey.getModulus();
        BigInteger publicExponent = rsaPublicKey.getPublicExponent();
        // rebuild the public key
        KeyFactory keyFactoryPub = KeyFactory.getInstance("RSA");
        RSAPublicKeySpec rsaPublicKeySpec = new RSAPublicKeySpec(modulusPub, publicExponent);
        PublicKey publicKeyRebuild = keyFactory.generatePublic(rsaPublicKeySpec);
        System.out.println("publicKey equals rebuild: " + Arrays.equals(publicKey.getEncoded(), publicKeyRebuild.getEncoded()));
        System.out.println("\nprivateKey original    encoded: " + bytesToHex(privateKey.getEncoded()));
        System.out.println("privateKey rebuild     encoded: " + bytesToHex(privateKeyRebuild.getEncoded()));
        RSAPrivateKey rsaPrivateKeyRebuild = (RSAPrivateKey) privateKeyRebuild;
        RSAPublicKey rsaPublicKeyRebuild = (RSAPublicKey) publicKeyRebuild;
        RSAPrivateCrtKey rsaPrivateCrtKey = createCrtKey(rsaPublicKeyRebuild, rsaPrivateKeyRebuild);
        System.out.println("privateKey rebuild CRT encoded: " + bytesToHex(rsaPrivateCrtKey.getEncoded()));
    }

    /**
     * https://stackoverflow.com/questions/43136036/how-to-get-a-rsaprivatecrtkey-from-a-rsaprivatekey
     * answered Mar 31 '17 at 18:16 President James K. Polk
     * Find a factor of n by following the algorithm outlined in Handbook of Applied Cryptography, section
     * 8.2.2(i). See http://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);
    }

    private static String bytesToHex(byte[] bytes) {
        StringBuffer result = new StringBuffer();
        for (byte b : bytes) result.append(Integer.toString((b & 0xff) + 0x100, 16).substring(1));
        return result.toString();
    }
}