1
$\begingroup$

I am trying to understand how much the output of elliptic curve based cryptosystems (for example elliptic curve ElGamal) is smaller than the ordinary public key cryptosystems.

I know that the security of a EC key size from a moduli of 160 bits is about the security of an RSA cryptosystem with a 1024 bits moduli. But my problem is that we usually have long messages, so we have to partition it into several blocks and then encrypt it. Therefore, when we have a 2048 bits long messages we make around 12 blocks and then encrypt them. Since the output is in the form of pairs, the out put will have a length of 2*13*150= 3900 bits. Now we consider this example with RSA. in order to use RSA for such a message, since its moduli can accept up to 1024 bits messages, we need only 2 blocks as the input(each one 1024 bits long). RSA output is not in the form of pairs, so the final output will have 2048 bits long.

In conclusion: The output of RSA has the same length as input, while the output of EC base cryptosystems length is as twice as the input.

What's the problem? How EC is said to be smaller?

Based on what I wrote, I think it is smaller only for messages that their whole length is smaller than the moduli!

(Please see Table 5 of this as an example of EC's smaller outputs)

| improve this question | | | | |
$\endgroup$
3
$\begingroup$

But my problem is that we usually have long messages, so we have to partition it into several blocks and then encrypt it. Therefore, when we have a 2048 bits long messages we make around 12 blocks and then encrypt them.

No, that's not what we do in practice. Instead, when we need to public key encrypt a large message, we pick a random symmetric key, encrypt that key with the public key algorithm (RSA or ECC), and encrypt the large message with the symmetric key (e.g. with AES-GCM or ChaCha20-Poly1305). We then send the two ciphertexts as a joint message.

That has the advantage of being computationally far cheaper (as we need to perform one public key encryption/decryption operation, no matter how long the message is).

In any case:

Now we consider this example with RSA. in order to use RSA for such a message, since its moduli can accept up to 1024 bits messages, we need only 2 blocks as the input(each one 1024 bits long).

Even if we were to use RSA in such a multi-block mode, we wouldn't want to divide the message into blocks, and use RSA in the straight-forward manner. If we did, then

  • If the adversary had a guess to the plaintext, he could encrypt the plaintext with the public key, and see if he gets the ciphertext

  • If we happened to encrypt related messages (for example, the two 2 block messages $M_0 || M_1$ and $M_0 || M_2$), the fact that there are related would be obvious.

Because of these reasons, we have to add randomness whenever we RSA encrypt a message (or key).

| improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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