Android RSA decryption (fails) / server-side encry

I am trying to decrypt a string in my android application using RSA keys generated on my device. The encryption is done by a php service, using the public rsa key provided by my application. My problem is with decryption, which fails.

I am doing the following :

Generating KeyPair on Android (with KeyPairGenerator.getInstance("RSA")) -> OK
Both keys (public and private) are saved into files after being "base64" encoded with Base64.encode(pubKey.getEncoded()) and the same with the private key. -> OK
When I am calling my webservice, I pass my public key (in base 64) in a post variable -> OK
The web service (a php service), uses the public key to encrypt a short string, with the openssl_public_encrypt function. The encrypted string is converted to base64. -> Seems OK, the function does not return FALSE.
The application retrieves the result of the service, and decodes it (Base64.decode()) -> OK (I have check, the bytes received matches with the one generated by the openssl_public_encrypt() function)
The last thing is to decrypt this string, I am doing the following : -> NOT OK

Cipher cipher = Cipher.getInstance("RSA");

cipher.init(Cipher.DECRYPT_MODE, privateKey);

byte[] decryptedBytes = cipher.doFinal(cryptedBytes);

String decryptedString = new String(decryptedBytes);

System.out.println(decryptedString);

The result of the decryption does not match my original string.

I am missing something ?

OpenSSL uses padding = OPENSSL_PKCS1_PADDING by default. So to have the same padding mechanism at both sides you should use Cipher.getInstance("RSA/ECB/PKCS1Padding"). This is also what you could use in Java SE.

Note that it is very dangerous to depend on default modes of operation in cryptography. Many implementations have different defaults, and those can be hard to look up. So always try to fully specify the algorithm/mode to use.

You could try other RSA padding modes, but note that - unfortunately - Android has disabled a lot of algorithms and aliases from the Bouncy Castle source code they adapted.

[EDIT] This is an old answer, OAEP padding is strongly advised by now, or hybrid cryptography using RSA-KEM.