0
$\begingroup$

As mentioned here the verification of a Ed25519 signature takes roughly 3 times as the time for the generation of a signature. Two questions on that:

1) Can I assume that this is a rule of thumb for this algorithm? I can imagine that the ratio of the times differ for different CPUs

2) How can I exactly see (using the algorithm) why verification takes (much) longer?

| improve this question | |
$\endgroup$
  • 3
    $\begingroup$ On my computer, I got this this ratio with the command ./openssl speed ed25519 . You can see why it takes a longer time by looking where Ed25519 sign and verify differ on RFC 8032 for example. Basically, verification needs to compute a double scalar multiplication which is slower to compute than a single scalar multiplication. $\endgroup$ – corpsfini Oct 2 '19 at 12:52
  • $\begingroup$ Sorry, for asking again: I am supposed to compare signing and verification from section 3.3. and 3.4 respectively? $\endgroup$ – user35869 Oct 2 '19 at 13:17
  • $\begingroup$ I would look at section 5.1.6 and 5.1.7, there are more details. You'll see signing needs a single scalar multiplication on the elliptic curve with the base point (it means an implementation probably have precomputation hardcoded to make it fast). Verifying needs two scalar multiplications, one with the base point and one with a variable point, hence why it will be slower. $\endgroup$ – corpsfini Oct 2 '19 at 14:33
2
$\begingroup$

In elliptic curve cryptography, the main operation is point multiplication: given an integer $k$ and a point $P$, compute $kP$ ($P$ added to itself $k$ times).

If the point $P$ is known beforehand, the computation can be sped up by using precomputation tables.

EdDSA signing requires computing $rB$ where $B$ is a fixed point (the "base"), therefore can be sped up.

EdDSA verifying requires computing $sB - hA$, i.e one fixed point multiplication and one "random" point multiplication ($A$ comes from the signer's public key). If you assume the fixed point multiplication is twice as fast than random point multiplication, then the result is that verification is three times slower than signing.

But of course, it depends on the implementation. In a naive implementation that doesn't optimize the fixed point case, verification will be two times slower than signing. It also depends on the size of the precomputation tables used.

This is described abstractly in sections 3.3 and 3.4 of the RFC 8032 (which are slightly confusing due to the $2^c$ factors), and more concretely in 5.1.6, 5.1.7 for Ed25519 and 5.2.6, 5.2.7 for Ed448 (which explain that you can ignore the $2^c$ factors).

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the answer! What I don’t understand: why Your answer is not involving all the encodings, decodings and hash calculations (as in 5.16, 5.17). $\endgroup$ – user35869 Oct 2 '19 at 18:46
  • $\begingroup$ Also for the signing (5.16) you did not mention the calculation for S. Is it negligible ? $\endgroup$ – user35869 Oct 2 '19 at 18:49
  • 1
    $\begingroup$ @Marm yes, all of these are very fast compared to point multiplication $\endgroup$ – Conrado Oct 3 '19 at 1:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy