I am performing some measurements of P256 ecdsa signature generation and verification latency and I was expecting that the signature verification will be faster than the signature generation, but is was not the case. what makes the signature generation faster ? what is the most computationally expensive operation in signature verification ?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I was expecting that the signature verification will be faster than the signature generation
Because signature verification is faster in RSA? Well, as you can see, RSA != ECDSA; the operations involved in both signing and verification are completely different.
what makes the signature generation faster ?
Because signature generation involves only one point multiplication (plus a modular inverse; rather cheaper, but not of insignificant cost), while signature verification involves two point multiplcations.
Of course, if you dig beneath the textbook definition, there are available optimizations for both sides:
On the signature side:
The point multiplication $k \times G$ (and I'll be using the notation on the Wikipedia page) uses a fixed (defined by the Elliptic Curve definition) point; there are a number of ways to speed this up considerably by precomputing takes based on $G$.
In addition, the expensive operations involved with the signing operation don't depend on the message being signed. Hence, if your implementation has some idle time, it could pregenerate $k$ and $r$ values; when it gets the message, it can use those values to sign the message with quite low latency.
Also, a word of warning: if you were thinking of using the same $k, r$ values for signing multiple messages, don't go there - that will leak you private signing key. You really need a fresh $k$ value selected randomly for each signed message.
On the verification side, the expensive operation is the computation $u_1 \times G + u_2 \times Q_A$
One could use the precomputed table to compute $u_1 \times G$ quickly; this means that the time to compute $u_2 \times Q_A$ is the bulk of the time (and if you know you'll be verifying with a specific public key $Q_A$ lots of times, you could precompute tables based on that - I haven't heard of anyone going to that effort, as you'd need to verify thousands of signatures from that one public key to make it worth while).
Alternatively, there is Shamir's trick, which is a computational method to compute $a \times P + b \times Q$ in not much more time than it takes to compute a single point multiplication. However, you lose the speed up from a precomputed table.
However, neither of these ideas results in a verification method that is as fast as signing with precomputed tables.
$\begingroup$
$\endgroup$
Using the notation there, ECDSA signature generation requires a single Elliptic Curve point multiplication, $k\times G$. Whereas naive signature verification uses two, computing $u_1\times G$ and $u_2\times Q_A$ before adding them. Point multiplication is typically by far the slowest operation in signature generation/verification, beside perhaps the hash (which is common to signature generation and verification). That can explain the timing difference observed.
However, that's far from always the case, and there are other reasons that can inverse or at least mitigate this:
- Various techniques such as Shamir's trick or interleaving of wNAFs allow to compute $u_1\times G+u_2\times Q_A$ with must less work than two point multiplications. And on some CPUs, there can be parallelization.
- Random generation of $k$ is necessary only for generation, and can be slow on some platforms.
- There are secret data manipulated on generation, not verification, and that can motivate countermeasures which slow things (and may require more randomness). In particular, a common security practice is to verify a generated signature before revealing it, and that would inverse things.