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$
8
  • 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$ Apr 7, 2019 at 5:52
  • $\begingroup$ I performed ECC in raspberry pi and calculated time for encryption, decryption, signing, verifying. @SqueamishOssifrage $\endgroup$ Apr 7, 2019 at 11:47
  • $\begingroup$ What's the cipher suite? ECC curve, symmetric encryption algorithm (assuming hybrid encryption, ECIES), etc? $\endgroup$
    – Natanael
    Apr 7, 2019 at 12:39
  • $\begingroup$ @AnikIslamAbhi What ECC cryptosystem, what software did you use, how did you invoke it, etc.? $\endgroup$ Apr 7, 2019 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$ Apr 8, 2019 at 1:21

1 Answer 1

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$
1
  • $\begingroup$ Thanks for the explanation. I am really grateful for your input and suggestions. $\endgroup$ Apr 8, 2019 at 6:44

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.