Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
