BadPaddingException : Data must start with zero

BadPaddingException : Data must start with zero

I implemented data encryption/decryption with RSA. It works if I just
encrypt/decrypt locally, however if I send my encrypted data I get
BadPaddingException: Data must start with zero.
In order to send my data over network I need to change it from byte array
to String (I'm sending it in a header) on the client side and then
retrieve it and change it back to byte array on the server side.
Here's my code for local encryption/decryption (I'm using private key to
encrypt and public key do decrypt):
// Encryption:
String message = "HELLO";
Cipher rsa = Cipher.getInstance("RSA");
rsa.init(Cipher.ENCRYPT_MODE, privateKey); // privateKey has type
java.security.PrivateKey
byte [] encryptedBytes = rsa.doFinal(message.getBytes());
// Decryption:
rsa.init(Cipher.DECRYPT_MODE, publicKey); // type of publicKey:
java.security.PublicKey
byte [] ciphertext = rsa.doFinal(encryptedBytes);
String decryptedString = new String(ciphertext, "UTF-8");
DecryptedString and message are the same and everything works fine.
Then I use the same code on the client side just for encryption plus I
change ciphertext to a String using:
String encryptedString = new String(ciphertext, "UTF-8");
And on the server side I do:
String message = request.getHeader("Message");
byte [] msgBytes = message.getBytes("UTF-8");
Cipher rsa = Cipher.getInstance("RSA");
rsa.init(Cipher.DECRYPT_MODE, publicKey);
byte [] decryptedMsg = rsa.doFinal(msgBytes);
String decryptedString = new String(decryptedMsg, "UTF-8");
This doesn't work and I get BadPaddingException.
I have tried using different instance of cipher, e.g.
"RSA/ECB/PKCS1Padding" or "RSA/ECB/NoPadding" but this didn't help. I also
tried converting Strings using BASE64 but then I get a different
exception: IllegalBlockSizeException.
I know I probably do sth wrong with converting Strings into byte arrays
and vice versa, but I just can't figure out the correct way of doing that.
Please help!