Score:0

RSA implementation not working with large values for plaintext

it flag

While implementing RSA encryption/decryption (using python), the plaintext doesn't match with the decrypted ciphertext for large values of plaintext. Works fine for smaller values for plaintext (numeric value).

Input: p=53 q=59 e=3 plaintext = 1000 (private key computed as 2011)

Here, the decryption gives 1000 as the plaintext, which is correct. Now, if

Input: p=53 q=59 e=3 plaintext = 10000 (private key computed as 2011)

Here, after the decryption, the computed plaintext is 619 (which should be 10000)

The code for the same is here,

    def encrypt(plaintext):
            ciphertext = (plaintext**publicKey) % (self.n)
            return ciphertext
   def decrypt(ciphertext):
            plaintext = (ciphertext**privateKey) % (self.n)
            return plaintext

Considering the algorithm will be used to encrypt/decrypt alphanumeric text, which will produce large numeric values, what modifications are needed or am I missing something?

ps: Checking for multiple values of plaintext,it may be happening because n=3127 and any plaintext greater than 3127 will not produce the original plaintext upon decryption. I might be wrong.

How to make it work for plaintext greater than n, here 3127?

kelalaka avatar
in flag
RSA is a trapdoor permutation! How do you expect to get a plaintext that is larger than the modulus size encrypted and decrypted correctly? The message $m$ must be $m < N$ where $N$ is the modulus and $m$ is the message. Before implementing read at least [Wikipedia RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem))?
kelalaka avatar
in flag
may be a duplicate of [How should I address message size limits in RSA encryption?](https://crypto.stackexchange.com/q/71092/18298)
kelalaka avatar
in flag
$10000 \pmod{53\cdot 51} = 619$ as expected!
Maarten Bodewes avatar
in flag
I've answered this more than once I think, but [this answer](https://crypto.stackexchange.com/a/50183/1172) already indicates a way around it for practicing purposes: split your message up and encrypt each piece separately. Beware that you should be able to distinguish separate ciphertext though (i.e. if you cannot distinguish between 5 followed by 23 and 52 followed by 3 then you're in trouble).
SAI Peregrinus avatar
si flag
The better way is to use hybrid encryption. Pick a random number between 0 and N. Call that number X. Use a KDF to derive a key from X. Encrypt using an AEAD like ChaCha20-Poly1305. Encrypt X with RSA. Send the encrypted X and the ciphertext of the message (and IV & tag). Recipient can decrypt X, use the same KDF, verify the tag, and decrypt the message. This is less complicated than using RSA-OAEP and treating RSA like a block cipher.
Maarten Bodewes avatar
in flag
@SAIPeregrinus That generally doesn't work for practice assignments like above. You could of course create a key and then use a many-time pad or Caesar / Vigenere cipher or something similar - those only need a small key size and for the exercise the fact that they are completely insecure is not a problem.
SAI Peregrinus avatar
si flag
Yeah, it's not what the exercise wants. But it's also safe, where what the exercise wants isn't. I think it's worth mentioning the "real world" way to use RSA for encryption (though RSA-OAEP is also common for hybrid schemes) even if it's not the exercise answer.
kelalaka avatar
in flag
Still doesn't required -1.
ayush7ad6 avatar
it flag
After reading your suggestion @MaartenBodewes, I split up the numeric plaintext into digits and encrypted it, and upon decrypting, clubbed the decrypted digits. ALso, thank you for your responses SAI and Maarten
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.