Usé phpseclib para generar la clave pública y privada RSA.

$rsa = new Crypt_RSA();
$rsa->setHash('sha1');
$rsa->setMGFHash('sha1');
$rsa->setEncryptionMode(CRYPT_RSA_ENCRYPTION_OAEP);
$rsa->setPrivateKeyFormat(CRYPT_RSA_PRIVATE_FORMAT_PKCS1);
$rsa->setPublicKeyFormat(CRYPT_RSA_PUBLIC_FORMAT_PKCS1);
extract($rsa->createKey(2048));  

Luego usé estas dos claves en mi aplicación de Android para cifrar / descifrar datos.

public static final String publicKey = "MIIBIjANBgk......DAQAB";
public static final String privateKey = "MIIEpAI......Zh+0bQ==";  

Puedo cifrar datos en JAVA con clave pública y descifrar esos datos en PHP con clave privada.
Esto funciona bien

public static String encryptData(String data) {
    String ret = null;
    try {
        PublicKey key = KeyFactory.getInstance("RSA").generatePublic(
                new X509EncodedKeySpec(Base64.decode(publicKey, Base64.DEFAULT)));

        Cipher cph = Cipher.getInstance("RSA/ECB/PKCS1Padding");
        cph.init(Cipher.ENCRYPT_MODE, key);
        ret = Base64.encodeToString(cph.doFinal(data.getBytes()),
                Base64.DEFAULT);
    } catch (NoSuchAlgorithmException e) {
        e.printStackTrace();
    } catch (NoSuchPaddingException e) {
        e.printStackTrace();
    } catch (InvalidKeySpecException e) {
        e.printStackTrace();
    } catch (InvalidKeyException e) {
        e.printStackTrace();
    } catch (IllegalBlockSizeException e) {
        e.printStackTrace();
    } catch (BadPaddingException e) {
        e.printStackTrace();
    }
    return ret;
}

Parte PHP

$rsa = new Crypt_RSA();
$rsa->loadKey($privatekey);
echo $rsa->decrypt($encrypted);

Pero cuando intento descifrar el mismo mensaje cifrado en Java mediante esta función,

public static String decryptData(String data) {
    String ret = null;
    try {
        PrivateKey key = KeyFactory.getInstance("RSA").generatePrivate(
                new PKCS8EncodedKeySpec(Base64.decode(privateKey, Base64.DEFAULT)));

        Cipher cph = Cipher.getInstance("RSA/ECB/PKCS1Padding");
        cph.init(Cipher.DECRYPT_MODE, key);
        ret = Base64.encodeToString(cph.doFinal(data.getBytes()),
                Base64.DEFAULT);
    } catch (NoSuchAlgorithmException e) {
        e.printStackTrace();
    } catch (NoSuchPaddingException e) {
        e.printStackTrace();
    } catch (InvalidKeySpecException e) {
        e.printStackTrace();
    } catch (InvalidKeyException e) {
        e.printStackTrace();
    } catch (IllegalBlockSizeException e) {
        e.printStackTrace();
    } catch (BadPaddingException e) {
        e.printStackTrace();
    }
    return ret;
}

Me sale este error

06-05 11:48:26.854: W/System.err(1311): java.security.spec.InvalidKeySpecException: java.lang.RuntimeException: error:0D0680A8:asn1 encoding routines:ASN1_CHECK_TLEN:wrong tag
06-05 11:48:26.862: W/System.err(1311):     at com.android.org.conscrypt.OpenSSLKey.getPrivateKey(OpenSSLKey.java:136)
06-05 11:48:26.862: W/System.err(1311):     at com.android.org.conscrypt.OpenSSLRSAKeyFactory.engineGeneratePrivate(OpenSSLRSAKeyFactory.java:64)
06-05 11:48:26.866: W/System.err(1311):     at java.security.KeyFactory.generatePrivate(KeyFactory.java:186)

Por favor ayuda. Y perdón por la larga pregunta.