10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ N does not change. Likely the library is using padding. The padding is random, so the cipher text changes. $\endgroup$
    – mikeazo
    Jun 11, 2015 at 18:05
  • $\begingroup$ @mikeazo That makes sense, if the length of the message is encrypted along with plaintext. Could you tell me the format of the message. Do all libs have different ways of implementing algos or can I use some other lib to decrypt this message. $\endgroup$
    – Mayank
    Jun 11, 2015 at 18:12
  • $\begingroup$ It is likely the standard OAEP which most libraries should implement. $\endgroup$
    – mikeazo
    Jun 11, 2015 at 18:25
  • $\begingroup$ @mikeazo Not darn likely, most Java implementations default to PKCS#1 v1.5 padding, and they cannot change that as it would break the existing applications out there. One big reason - among many others - why I am against using defaults for cryptographic algorithms. In this case however the link specifies Cipher rsaCipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA1AndMGF1Padding", "SC"); so it's certain that it is OAEP. Lucky you. $\endgroup$
    – Maarten Bodewes
    Jun 12, 2015 at 10:48
  • $\begingroup$ @MaartenBodewes I knew I should have purchased a lotto ticket :) $\endgroup$
    – mikeazo
    Jun 12, 2015 at 11:34

3 Answers 3

11
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Your answer is a little above my capabilities. I understood most of it with a few google searches. You mention "against using defaults for cryptographic algorithms", I absolutely agree, but discussions say that it is better to use the standards than make your own lest we make some mistakes that compromises security. What are the other reasons? Secondly, I followed this, but I want to learn more about cryptography and network security and best practices(advanced stuff). Could you refer me some book or link. Please? $\endgroup$
    – Mayank
    Jun 12, 2015 at 12:32
  • $\begingroup$ You are already using OAEP in the code. You describe textbook RSA in your question. So you don't have to change the code. OAEP is part of the PKCS#1 standard. I'm not sure what is in the book. One thing I can recommend to you is to look up the actual standard documents such as RSA as specified in PKCS#1 (usually linked from Wikipedia). They are often easier to understand than most imagine. $\endgroup$
    – Maarten Bodewes
    Jun 12, 2015 at 12:41
  • $\begingroup$ Cleaned up the answer, please comment if there are still things you don't understand. $\endgroup$
    – Maarten Bodewes
    Jun 12, 2015 at 12:47
  • $\begingroup$ Your answer was equally good last time, but thank you. Could you please answer two of my follow up questions, I have added them as Edit in the question itself. $\endgroup$
    – Mayank
    Jun 12, 2015 at 13:11
  • $\begingroup$ Also what are the other reason why you don't suggest using default methods? I know too many question, but thank you so much? $\endgroup$
    – Mayank
    Jun 12, 2015 at 13:13
7
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Your answer is very descriptive. Thanks !. Could you also answer some follow up questions(I have added them to the question under Edit). Cheers ! $\endgroup$
    – Mayank
    Jun 12, 2015 at 13:16
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.