Why the output of elliptic curve based cryptosystems is smaller than the ordinary public key cryptosystems?

Question

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)

Answer 1

Why is the output of elliptic curve based cryptosystems smaller than for ordinary public key cryptosystems?

There are common Elliptic Curve Cryptography public-key cryptosystems which output is just as small as "ordinary" ones, if we take that as pre-ECC. Take for example Schnorr signature: even when based on arithmetic modulo a 16384-bit prime, it has a signature just as compact as its ECC equivalent: $3b$ or $4b$ bits for $b$-bit security (depending on if you want belt only, or belt and suspenders).

---

Let's now more precisely define "ordinary" asymmetric cryptosystems. Take these as those working in $\Bbb Z_n$ and assuming the difficulty of integer factorization of $n$ like RSA encryption and signature; or working in $\Bbb Z_p$ with $p$ prime and assuming the difficulty of the Discrete Logarithm Problem like the original ElGamal encryption or the aforementioned original Schnorr signature.

One way to justify why these "ordinary" cryptosystem require larger public keys and operands than ECC ones is:   they operate directly using multiplication in a field.

This implies two internal laws (addition and multiplication) in the set, with the distributive property linking them. Contrast with Elliptic Curve Cryptography, which operates on a set (the points on the curve including the point at infinity) with a single well-defined operation between elements of the set: point addition. In turn, having a richer algebraic structure enables more algorithms.

That is most apparent when it comes to the Discrete Logarithm problem, which can be posed in the same terms in the two cases: for 128-bit security we need a field $\Bbb Z_p$ with like $2^{2560}$ elements when operating directly on it, because we have index calculus and other sub-exponential algorithms to solve it; when we can make ECC on a group with like $2^{256}$ elements, because only algorithms that work in a generic group, like Pollard's rho, seem to be applicable.

---

For the question from the standpoint of the size of ciphertext, see poncho's 's excellent answer.

The classic approach to solve that issue is hybrid encryption. In a nutshell: to send a large amount of data encrypted, draw a random secret key, and

1. Encrypt it using an asymmetric cipher with the receiver's public key, and output that as the start of the ciphertext.
2. Use that secret key (in the form before encryption) as the key to an efficient symmetric encryption (authenticated, preferably), e.g. Chacha-Poly1305 or AES-GCM-SIV, producing the rest of the ciphertext.

The receiver side gets the start of the ciphertext, deciphers it with it's private key, and now has the symmetric key. It proceeds with the decryption (and check) of the rest.

It's the best of both worlds. Everything does that: PGP, Whatsapp, younameit.

Answer 2

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).