Why are RSA ciphertexts different for the same plaintext?

Question

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 :

"G4srxAxUnoikOIQdlj30rmyUiGz3P0R0VE6BflSTo4UQqJVSBpQtyFSB6tt73Z693D0LMkykDEPB
    lPg0IEH/R6tOJCyCU8HxKQ8nfo5OGUYFgkup3aGPkRqb+gCLpc5YGSmLztaynKq1H6kplryx0q1+
    KTCchc6PswAMpaMwMTk="

"j2r5MsaGRNazElAxG4BIBgZYtrjdxaErbs+19ObsCyOuVwTiu0cvKcKTOPuUOOjcGVaDup53wdEk
    AHHsy8zA1gR29uSdW4C2JIDnQVGCcfzqOcbzeS4WgV+2WpLTahBj6Df8pya2YksIp3KSLSnhH3nn
    B2kf/Wi53SQmJJWSf84="

"Yz3xhiObUI5C8UA31VNH3VqUXGmotGpTz9A3U2n81lJ7p1//x4CI15r4JUZGJlN1aPnSayIuk6D8
    hMIp32o53YEmm69gve91+dCVDQkZOUE9UuA2nEcjR21nUgWPQJdwqQ7P4XFeWsBaokpwNCA6j2qb
    b1Glfp+AVpUNm7syiUY="

...

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.

Answer 1

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.

Answer 2

On encrypting the same plain text, I get two different outputs.

This is in fact a design goal of encryption systems: an adversary who sees two ciphertexts should not be able to tell whether they're equal — that would be an information leak. Even encryption systems that would otherwise be secure use an initialization vector or other similar unique value (often random) when encrypting (usually an IV is necessary for other purposes).

I know that RSA is $Y = X^e \pmod{n}$

That's textbook RSA. Textbook RSA is the fundamental mathematical operation behind RSA cryptosystems, but as is it isn't a good security primitive. Because of its simple mathematical structure, it allows some mathematical transformations to be made which can allow attacks such as decrypting a ciphertext $C_1$ from knowing another ciphertext $C_2$ and the corresponding plaintext $P_2$ (which can be easy to carry out if the adversary can request the encryption of a $P_2$ of its choice). RSA as a cryptosystem is built on textbook RSA plus a padding scheme. The padding operation makes transformations that break the mathematical structure and thus break the attacks based on that structure.

There are three standard padding schemes for RSA, known as “PKCS#1 v1.5” (after the name of the document that describes it; used both for encryption and for signature), PSS (used for signature) and OAEP (for encryption). PKCS#1 v1.5 should not be used in new protocols, because it has defects, though the defects are a lot less bad than textbook RSA.

Since neither $X$ (plaintext) nor $e$ (public key) changes, I'm guessing $n$ changes each time.

No, $n$ is part of the public key ($e$ is the public exponent; the public key is $(n,e)$). It doesn't change. What changes is the padding, which includes a random part.

So, if $n$ changes each time, for decryption to know the value of $n$ it has to be passed on with the message itself.

$n$ doesn't change. The padding changes, but decryption discards the padding anyway (after verifying that it is valid).

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

The output you're seeing is evidently a base64 encoding. With 172 characters and the last one being =, that's a representation of a 128-byte string.

The output of an RSA operation is a number in the range $[0,n)$, encoded as a string of bytes (the encoding of the number as bytes is standardized). For a 1024-bit key, you get a 128-byte result.

Answer 3

Imagine I run a vote, where 200 people send either “yes” or “no”, obviously encrypted. And a hacker collects all the encrypted messages and their sources. Then the hacker knows which 127 people voted one way and which 73 voted another way. And if the result of the vote is published then the hacker knows exactly who voted “yes” and who voted “no”.

So the encryption algorithm will automatically add random padding to each message before encryption and the decryption algorithm will automatically remove it after decryption. Which means your encryption will give you different cipher text each time, fixing this security hole, without the sender having to be careful about what they send.