Why are RSA ciphertexts different for the same plaintext? I am using SpongyCastle for a project on android. I have used RSA to encrypt the data and then decrypt it in another activity, the keys are stored in the shared preferences.
I discovered a thing I cannot explain.
My keys are generated only once and stored for future use without being changed. On encrypting the same plain text, I get two different outputs.
I encrypted the plaintext a and got the following outputs :
&quot;G4srxAxUnoikOIQdlj30rmyUiGz3P0R0VE6BflSTo4UQqJVSBpQtyFSB6tt73Z693D0LMkykDEPB
    lPg0IEH/R6tOJCyCU8HxKQ8nfo5OGUYFgkup3aGPkRqb+gCLpc5YGSmLztaynKq1H6kplryx0q1+
    KTCchc6PswAMpaMwMTk=&quot;

&quot;j2r5MsaGRNazElAxG4BIBgZYtrjdxaErbs+19ObsCyOuVwTiu0cvKcKTOPuUOOjcGVaDup53wdEk
    AHHsy8zA1gR29uSdW4C2JIDnQVGCcfzqOcbzeS4WgV+2WpLTahBj6Df8pya2YksIp3KSLSnhH3nn
    B2kf/Wi53SQmJJWSf84=&quot;

&quot;Yz3xhiObUI5C8UA31VNH3VqUXGmotGpTz9A3U2n81lJ7p1//x4CI15r4JUZGJlN1aPnSayIuk6D8
    hMIp32o53YEmm69gve91+dCVDQkZOUE9UuA2nEcjR21nUgWPQJdwqQ7P4XFeWsBaokpwNCA6j2qb
    b1Glfp+AVpUNm7syiUY=&quot;

...

I know that RSA is $Y = X^e \pmod{n}$
Since neither $X$ (plaintext) nor $e$ (public key) changes, I'm guessing $n$ changes each time.
The decryption works just fine for each case.
So, if $n$ changes each time, for decryption to know the value of $n$ it has to be passed on with the message itself.
My questions:
Am I correct in assuming the above? If yes, where is $n$, and what is the format for storing the message? If No, what is the correct method?
The output is 172 characters each time? How does that work out?
P.S. : I am following this.
Edit:
I can conclude that from the answers that padding is responsible for this. If padding is different each time, shouldn't it be mentioned or the length of the actual message be mentioned with the ciphertext so that deciphering code can differentiate the padding from the actual message? If it is the same, wouldn't it give the same result each time, we would still need to pass the length of the actual message encrypted as it may be. (I think it's random)
I also found out that I can't encrypt more than 86 characters. Why? Is there a limit on the number of characters by RSA?
Giving me this:
06-12 18:09:37.192    9217-9217/? E/AndroidRuntime﹕ FATAL EXCEPTION: main
Process: com.chatr, PID: 9217
java.lang.RuntimeException: java.lang.RuntimeException: java.lang.ArrayIndexOutOfBoundsException: too much data for RSA block
        at crypto.RSA.encryptWithKey(RSA.java:87)
        at crypto.RSA.encryptWithStoredKey(RSA.java:93)

Also, the same error comes when I try to decrypt the ciphertext when I replace = with something else, and obviously hash fails when I change some other character. What does = signify. I'm assuming padding.
Am I correct in assuming the above?


No you are not. You are showing textbook/raw RSA, which is little more than modular exponentiation. To be secure RSA has to use padding methods. Without padding, RSA would indeed generate the same ciphertext each time. This alone would break the security requirements of a cipher. There are many other attacks on textbook RSA. Fortunately the code you linked to specifies OAEP encryption, which is assumed to be secure.


  If yes, where is $n$ and what is the format for storing the message?


$n$ is not part of the ciphertext. It is however part of both the public key and the private key. The output format of RSA/OAEP is simply a byte array of the same size - in bytes - as the modulus, almost indistinguishable from random.
In your case it is base 64 encoded, which is needed if you want to store or send the ciphertext as printable text. See also the answer on your last question below.


  If No, what is the correct method?


The method used in the code, OAEP, is specified in PKCS#1 v2.1 and 2.2 of RSA labs. As these standards keep changing location I usually use the RFC 3447 instead.


  The output is 172 characters each time? How does that work out?


The output of the RSA encryption is of course always less than the modulus. As part of the PKCS#1 algorithm it is put through the I2OSP transformation (see the RFC). This encodes the resulting number from the calculation to an octet string (or byte array) with the same size as the modulus, in bytes. To be precise, it is transformed into a byte aligned, statically sized, unsigned, big endian encoding.

Now you see the output as Base 64. That means that it consists of $(172 / 4) * 3 = 129$ bytes. However, there is one padding character =, so that means a ciphertext of 128 bytes or a ciphertext of 1024 bits. This means that your modulus and therefore your key size is also 1024 bits. You should upgrade to a higher key size. 


  If padding is different each time, shouldn't it be mentioned or the length of the actual message be mentioned with the cipher text so that deciphering code can differentiate the padding from the actual message?


The trick is that first the ciphertext is converted in the number, then after modular exponentiation the padded plaintext message appears. The padding is self descriptive; it isn't just random characters.


  I also found out that I can't encrypt more than 86 characters. Why? Is there a limit on the number of characters by RSA?


There is a relatively high amount of padding, including said overhead. So the type and minimum amount of padding determines the limit that can be encrypted using a single "block" encrypt of RSA. Usually a random symmetric data key is encrypted, which in turn encrypts the plaintext. This is because RSA is highly inefficient. This type of protocol is called a hybrid cryptosystem. Instead of PKCS#1 compatible RSA, RSA KEM could also be used for encryption.