2
$\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)

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ :Thanks for your answer. Although your answer covers the title of my question as you wrote in the 1st line yourself,it does not solve my problem. Yes, we know that the "hard problem" that we rely on in ECC (with smaller key size) is as hard as those of $\mathcal{Z}_n$, but my problem is that this implies you be able to encrypt smaller blocks, as a result,for longer messages you will have more blocks in which adding the size of the outputs among all of them would be around that if you have worked on $\mathcal{Z}_n$ from the beginning. What about it? (I'll continue in the next comment) $\endgroup$
    – m123
    Jun 3, 2020 at 15:12
  • $\begingroup$ As you said poncho's answer was a good answer, and I should thank him too but he said we don't use asymmetric encryption for long messages and in this case we share the symmetric keys using asymmetric encryptions then encrypt them with symmetric ones. As far as I know, this somehow limits the applications of public key cryptography since you need the receiver have interaction with the sender. Doesn't it? I suppose there must exist another approach we miss here. This gap between my question and answers was the reason I still haven't tick the answers. $\endgroup$
    – m123
    Jun 3, 2020 at 15:19
  • $\begingroup$ @m123: the classic approach 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 assymetric cipher and output that as the start of the ciphertext 2) use it (in the form before encryption) as the key to an efficient encryption (authenticated, preferably), e.g. Chacha-Poly1305 or AES-GCM-SIV, producing the rest of the ciphertext. You easilly guess what happens on the receiver side. Everything does that: PGP, Whatsapp, younameit. Best of both worlds. $\endgroup$
    – fgrieu
    Jun 3, 2020 at 15:25
  • 1
    $\begingroup$ Thank you. This part of your comment solved all my problem: **output that as the start of the ciphertext **. I had thought it needs extra round! Could you please add this part of your comment to your answer and I tick it? I wonder if it is suitable to be in the comments and I tick it. And I should also say thanks to @poncho for sparking this. $\endgroup$
    – m123
    Jun 3, 2020 at 15:31
5
$\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).

$\endgroup$
1
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Maarten Bodewes
    Apr 14, 2020 at 14:55

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.