2
$\begingroup$

While performing encryption using public key and decryption using the private key, I am always finding that encryption takes more time than decryption in elliptic curve cryptography (ECC). It's the same for signing and verifying. The key is 60 bytes.

Is this the normal behavior or I am using the wrong implementation of ECC?

If this behavior is normal then what is the reason behind it? Thanks in advance.

$\endgroup$
  • 1
    $\begingroup$ This could depend on a lot of things. Can you be more specific about what cryptosystem you're talking about, what implementation you're using, and how you're measuring the performance difference? $\endgroup$ – Squeamish Ossifrage Apr 7 at 5:52
  • $\begingroup$ I performed ECC in raspberry pi and calculated time for encryption, decryption, signing, verifying. @SqueamishOssifrage $\endgroup$ – Anik Islam Abhi Apr 7 at 11:47
  • $\begingroup$ What's the cipher suite? ECC curve, symmetric encryption algorithm (assuming hybrid encryption, ECIES), etc? $\endgroup$ – Natanael Apr 7 at 12:39
  • $\begingroup$ @AnikIslamAbhi What ECC cryptosystem, what software did you use, how did you invoke it, etc.? $\endgroup$ – Squeamish Ossifrage Apr 7 at 14:40
  • 1
    $\begingroup$ @AnikIslamAbhi What did you do with the software? What parts did you measure? How did you measure them? What inputs did you use? What specific cryptosystems? $\endgroup$ – Squeamish Ossifrage Apr 8 at 1:21
5
$\begingroup$

It appears that the public-key anonymous encryption scheme in question is ECIES. ECIES encryption requires generating a single-use key pair and doing a DH key agreement with it, while ECIES decryption only requires doing a DH key agreement and so should cost considerably less than encryption.

Specifically, the sender knows the recipient's public key, $A$, a point on an elliptic curve. The sender picks an ephemeral secret scalar $t$ and computes $T := [t]G$, where $G$ is the standard base point on the curve; then the sender computes $k := H([t]A)$ and uses $k$ as the key for a symmetric authenticated cipher. Finally, the sender sends $T$ alongside the authenticated ciphertext. This operation requires computing two scalar multiplications: $[t]G$ and $[t]A$.

The recipient knows the secret scalar $a$ such that $A = [a]G$, and can recover $$H([a]T) = H([a][t]G) = H([a\cdot t]G) = H([t\cdot a]G) = H([t][a]G) = H([t]A) = k,$$ with which they can then decrypt the authenticated ciphertext. This operation requires computing only one scalar multiplication: $[a]T$.

So it is to be expected that the encryption operation would cost more than the decryption operation. In a naive implementation—and I would not be surprised if libgcrypt, as the software you cited uses, is naive—encryption will cost approximately twice as much as decryption. It could be made faster in a less naive implementation by using a precomputed table for the fixed-base $t \mapsto [t]G$ computation, but encryption will still be slower than decryption.


The signature scheme in this library is probably ECDSA. Making a signature with ECDSA costs one fixed-base scalar multiplication, while verifying a signature costs one double-base scalar multiplication, so verification should cost a little less than twice what signing costs.

Specifically, the verification equation for a signature $(r, s)$ on a message $m$ under a public key $A$ is $$r \equiv x\bigl([H(m) \cdot s^{-1}] G + [r \cdot s^{-1}] A\bigr) \pmod n,$$ which requires computing $s^{-1}$, the scalars $H(m) \cdot s^{-1}$ and $r \cdot s^{-1}$, and the double-base scalar multiplication $[\alpha] G + [\beta] A$ where $G$ is the standard base point of order $n$.

The signer, who knows the secret $a$ such that $A = [a]G$, picks a scalar $k$ uniformly at random, computes $r = x([k]G)$, and then solves $k \equiv H(m) \cdot s^{-1} + r \cdot s^{-1}$ for $s$ with one inversion and two multiplications modulo $n$.

That said, ECDSA is about the stupidest elliptic curve signature scheme around—it was designed as it was in order to deliberately avoid patents that have long since expired on more sensible schemes. You should use Ed25519 instead.

$\endgroup$
  • $\begingroup$ Thanks for the explanation. I am really grateful for your input and suggestions. $\endgroup$ – Anik Islam Abhi Apr 8 at 6:44

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.