7
$\begingroup$

I need to choose an encryption system, so I am trying to understand the differences between the existing options. I always find that people compare ECIES (Elliptic Curve Integrated Encryption Scheme) with RSA or ElGamal. It is clear that elliptic-curve-based encryption schemes are much more robust than RSA and ElGamal. So, I have decided to use an EC-based solution.

The problem now is that there are different EC-based encryptions--ECIES, ECDHE (Elliptic Curve Diffie-Hellman Encryption), EC-ElGamal--but I have been unable to find a clear explanation of their common features and differences.

Could someone provide me with a reference/study/comparison of these EC-based encryption solutions? Or could someone explain to me their basic differences? In particular, which one is the best in terms of resources consumption?

$\endgroup$
3
  • 3
    $\begingroup$ ECDHE is usually short for Elliptic Curve Diffie Hellman (Ephemeral) and is a way to establish a shared secret, not an encryption protocol. $\endgroup$ May 18, 2019 at 17:10
  • 1
    $\begingroup$ I guess we could remove it from the question, as it is not answered by Squamish. However, let's leave it in, as others make this easy to make interpretation mistake as well. Note that ECDHE is rather specific to SSL/TLS although other protocols may pick up the name as well. $\endgroup$
    – Maarten Bodewes
    May 19, 2019 at 19:00
  • $\begingroup$ Please do accept the best answer for your questions if they fully answer your questions. You can do this by hitting the V mark next to the answer. Note that it is possible to change the accept after it has been given. This notifies other users and search engines that the question has been answered, besides giving reputation to the answerer, of course. $\endgroup$
    – Maarten Bodewes
    May 19, 2019 at 19:02

1 Answer 1

10
$\begingroup$

Fix a group $G$ of order $q$ in which discrete logs are hard, and fix a standard base point $g \in G$. Fix an authenticated cipher $E_k$ of bit strings.

  • In (EC)IES, roughly: A public key is a point $h \in G$.

    • To encrypt a message $m$, the sender:

      1. picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random,
      2. computes an ephemeral public key $t = g^y$,
      3. computes an ephemeral shared secret $s = h^y$, and
      4. sends $t$ alongside $c = E_k(m)$ where $k = H(s)$ is a hash of the shared secret.

      Note: The total computational cost is two exponentiations; the total ciphertext overhead is one group element. Effectively, we are generating an ephemeral Diffie–Hellman key pair $(y, t)$ and doing a Diffie–Hellman key agreement with it.

    • The receiver, who knows the secret exponent $x \in \mathbb Z/q\mathbb Z$ such that $h = g^x$, computes $k = H(t^x)$ and decrypts $c$ with $k$.

      Note: The total computational cost is one exponentiation.

  • In (EC-)Elgamal: A public key is a point $h \in G$.

    • To encrypt a message $m$, the sender:

      1. picks an exponent $y \in \mathbb Z/q\mathbb Z$ uniformly at random,
      2. computes an ephemeral public key $t = g^y$,
      3. computes an ephemeral shared secret $s = h^y$,
      4. picks $k$ uniformly at random from some subset of $G$,
      5. computes the product $z = k \cdot s$, and
      6. sends $t$, and $z$, alongside $c = E_k(m)$.

      Note: The total cost is two exponentiations and one multiplication; the total ciphertext overhead is two group elements.

    • The receiver, who knows the secret exponent $x \in \mathbb Z/q\mathbb Z$ such that $h = g^x$, computes $k = z\cdot t^{-x}$ and decrypts $c$ with $k$.

      Note: The total cost is one exponentiation and one multiplication.

As you read, you may see a resemblance here! Elgamal does essentially everything IES does, plus some extra work that adds no security, which I have written in bold.

In the elliptic curve case, Elgamal is even trickier. Why?

  • In the finite field case where $G = \mathbb Z/p\mathbb Z$, the integers modulo a prime $p$ (or where $G = \operatorname{GF}(2^n)$), $k$ can be (say) a 256-bit string that serves a dual purpose as an AES key and, interpreted as an integer in little-endian, as an element of $G$.
  • In the elliptic curve case, there's no natural map between bit strings and elements of $G$, so you need to choose some correspondence between random elements of $G$ and (say) AES keys—like a hash function $H(k)$. But if you were going to hash an element of $G$ into a key anyway, you might as well have just used ECIES!

Even worse, Elgamal requires computing multiplication in $G$, not just exponentiation $G$, which means that you can't take advantage of DH functions like X25519 which support only the equivalent of exponentiation (‘$x$-restricted scalar multiplication on Curve25519’, using the fast constant-time Montgomery ladder) but not the equivalent of multiplication (‘point addition on Curve25519’).

The only reason to use Elgamal is exotic applications that require expert guidance like voting systems, where the message $m$ is concealed directly, rather than some key $k$ used for an authenticated cipher; this happens only if you are exploiting the homomorphic properties of Elgamal, and doesn't work with arbitrary bit string messages but rather requires you to be very judicious about what messages are and how they are chosen.

If you want public-key anonymous encryption, you should use libsodium crypto_box_seal, which is conceptually the same idea as ECIES (with all the details I go into done differently). Note, of course, that public-key anonymous encryption is a kind of weird thing to do that most applications, outside journalists accepting leaks, don't need. More likely, you want public-key authenticated encryption, for which you should use NaCl/libsodium crypto_box_curve25519xsalsa20poly1305, if you have a definite notion of a sender and receiver who know one another's public keys and want to exchange unforgeable secret messages.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much, the explanation is really good! $\endgroup$
    – SAliaMunch
    May 19, 2019 at 12:00

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.