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 :
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.