A Bluffers Guide to EdDSA and ECDSA

Prof Bill Buchanan OBE FRSE
9 min readMay 19, 2024

Well, if you’re into cybersecurity, hopefully, you see beyond the fact that ECDSA stands for Elliptic Curve Digital Signature Algorithm, and EdDSA stands for Edwards-curve Digital Signature Algorithm. Both are used to create digital signatures, and where Bob uses his private key to sign for a message, and then Alice proves the signature with the message, the signature and Bob’s public key. Once Bob has signed the message, there should be no way of going back and changing the key to a different key or changing the message — as these would not verify the signature.

Figure 1 shows an outline of the signatures used in elliptic curve methods. With this, Bob uses his private key (sk) to sign a hash to the message, and produces a signature: (r,s). This signature is then sent to Alice with the message. Alice then also takes a hash of the message and the signature (r,s), and applies Bob’s public key (pk). If the signature checks-out, Alice knows that Bob signed the message.

Figure 1

So what’s the difference? And when would you use ECDSA rather and EdDSA, and vice-versa. For something that is compatible with Bitcoin and Ethereum, ECDSA provides the best solution. Unfortunately it relies on a random nonce value to be created, and if the nonce is not random, it can significantly reduce the security of the signature. EdDSA has around the same speed performance as ECDSA, but it naturally supports the aggregation of keys in order to merge them within a signing process. This is because they are based on the Schnorr signature method.

ECDSA has been around for over two decades and was first proposed in the following paper [1][here]:

and in 2011, Ed25519 was proposed as a method for fast, and secure digital signatures [2][here]:

Meet the Schnorr signature

In Feb 1989, Claus Schnorr submitted a patent that was assigned to no one. It has 11 claims, and allowed digital signatures which could be merged for multiple signers [here]:

With the Schnorr signature, we create a signature (R,s) for a hash of the message (MM). We first generate a private key (x) and then derive the public key from a point on the elliptic curve (G) to get:

P=x⋅G

Next, we select a random value (k) to get a signature value of R:

R=k⋅G

The value of s is then:

s=k−Hash(M,R)⋅x

Our signature of M is (s,R) and the public key is P.

To check the signature we calculate

P⋅Hash(M,R)+s⋅G

This becomes x⋅G⋅Hash(M,R)+(k−Hash(M,R)⋅x)⋅G

which is:

x⋅G⋅Hash(M,R)+k⋅G−Hash(M,R)⋅x⋅G=k⋅G

The value of k⋅G is equal to R, and so if the result is the same as R, the signature checks out.

EdDSA and Ed25519

The Edwards-curve Digital Signature Algorithm (EdDSA) is used to create a digital signature using an enhancement of the Schnorr signature with Twisted Edwards curves.

Overall it is faster than many other digital signature methods and is strong for security. One example of EdDSA is Ed25519, and which is based on Curve 25519. It provides around 128-bit security and generates a 64-byte signature value of (R,s). Along with this, it has 32-byte values for the public and the private keys.

The following is the Golang code [here]:

package main
import (
"crypto/ed25519"
"encoding/base64"
"fmt"
"os"
)
func Base64Encode(message []byte) []byte {
b := make([]byte, base64.StdEncoding.EncodedLen(len(message)))
base64.StdEncoding.Encode(b, message)
return b
}
func main() {
msg := "Hello 123"
argCount := len(os.Args[1:])
if argCount > 0 {
msg = os.Args[1]
}
publ, priv, _ := ed25519.GenerateKey((nil))
m := []byte(msg)
sig := ed25519.Sign(priv, m)
fmt.Printf("=== Message ===\n")
fmt.Printf("Msg: %s\nHash: %x\n", msg, m)
fmt.Printf("\n=== Public key ===\n")
fmt.Printf("Public key: %x\n", publ)
fmt.Printf(" Public key (Base64): %s\n", Base64Encode(publ))
fmt.Printf("\n=== Private key ===\n")
fmt.Printf("Private key: %x\n", priv[0:32])
fmt.Printf(" Private key (Base64): %s\n", Base64Encode(priv[0:32]))
fmt.Printf(" Private key (Base64) Full key: %s\n", Base64Encode(priv))
fmt.Printf(" Private key (Full key): %x\n", priv)
fmt.Printf("\n=== Signature (R,s) ===\n")
fmt.Printf("Signature: R=%x s=%x\n", sig[0:32], sig[32:64])
fmt.Printf(" Signature (Base64)=%s\n\n", Base64Encode(sig))
rtn := ed25519.Verify(publ, m, sig)
if rtn {
fmt.Printf("Signature verifies")
} else {
fmt.Printf("Signature does not verify")
}
}

A sample run with the message of “Hello” is [here]:

=== Message ===
Msg: Hello
Hash: 48656c6c6f
=== Public key ===
Public key: c3903a26c73a433554325859c963056acd2d503fc36313ae21647f911e723fab
Public key (Base64): w5A6Jsc6QzVUMlhZyWMFas0tUD/DYxOuIWR/kR5yP6s=
=== Private key ===
Private key: fc225cb6dd8969541e57754b4120b51e6a92673107c7c8e1dc25a7a3e6b1066b
Private key (Base64): /CJctt2JaVQeV3VLQSC1HmqSZzEHx8jh3CWno+axBms=
Private key (Base64) Full key: /CJctt2JaVQeV3VLQSC1HmqSZzEHx8jh3CWno+axBmvDkDomxzpDNVQyWFnJYwVqzS1QP8NjE64hZH+RHnI/qw==
Private key (Full key): fc225cb6dd8969541e57754b4120b51e6a92673107c7c8e1dc25a7a3e6b1066bc3903a26c73a433554325859c963056acd2d503fc36313ae21647f911e723fab
=== Signature (R,s) ===
Signature: R=fbee75ddd533296a9ebacbe653a3335d1b9a99d6e6c7941d4651e04a6268ad2e s=086b3da235c4f4e426d1a2e76a731c0a81844d98fe59f412abd869fb3008d00d
Signature (Base64)=++513dUzKWqeusvmU6MzXRuamdbmx5QdRlHgSmJorS4Iaz2iNcT05CbRoudqcxwKgYRNmP5Z9BKr2Gn7MAjQDQ==
Signature verifies

The signature is 64 bytes long, made up of 32 bytes for the R value, and 32 bytes for the s value. The public key is also 32 bytes long, and the private key is 32 bytes. Overall Ed25519 produces one of the smallest signature sizes that is possible and has a small size of the public and private key. In a more distributed environment, the usage of Schnorr signatures supports the splitting of the keys into shares, and allow different parties to come together and generate their part of the signature. This method supports the deletion of a private key, and then for it to be split into secret shares.

What’s so good about Ed25519 for digital signatures:

  • Super fast for signing: As a benchmark, for signing, it takes less than 90K cycles on popular CPUs
  • Super fast for verification: As a benchmark, for verification, it takes less than 300K cycles on popular CPUs and is even faster for batch verification (less than 134K cycles per signature).
  • Super fast for key generation: This takes less than 6K cycles on popular CPUs.
  • Good security levels: Ed25519 is on a par with 128-bit AES, NIST P256 and 3K RSA.
  • Collision resilient. A hash collision does not break Ed25519.
  • Small signatures: Ed25519 signatures are only 512 bits long (64 bytes).
  • Small keys and deriving public key: Ed25519 keys are only 256 bits long (32 bytes), and where the public key can be derived from the private key.
  • They are deterministic: The same input data will always lead to the same signature, unlike ECDSA which needs a random nonce value.
  • Fairly immune from side-channel attacks.

Here are examples:

ECDSA

The ECDSA method significantly improved the performance of signing messages than the RSA-based DSA method. Its usage of elliptic curve methods speeded up the whole process and supported much smaller key sizes. Its crown and glory were being selected by Satoshi Nakamoto for his Bitcoin protocol, and then its adoption into Ethereum. It does struggle though in signature aggregation and in splitting keys within a distributed environment.

There are a bit more maths involved in ECDSA:

Again we generate an (r,s) pair, and which can be validated. Overall there are some differences here, and rather than using Curve 25519, we can use a range of curves, such as secp256k1 (P256k1), P244 and P521.

The security level of secp256k1 is about the same as Ed25519. Within Ed25591, we only use the y co-ordinate points when we have a point on the elliptic curve, whereas in ECDSA we typically have an (x,y) co-ordinate point. The public key — which is a point on the curve — is this 512 bits long, whereas the private key is only 256 bits long. Overall the public key is larger in ECDSA than EdDSA. The main drawback with ECDSA, though, is that it does not naturally support a merging of keys and signatures.

The code is [here]:

package mainimport (
"crypto/ecdsa"
"crypto/elliptic"
"crypto/rand"
"crypto/sha256"
"fmt"
"os"
"strings" "github.com/dustinxie/ecc"
)func getCurve(s string) elliptic.Curve {
if strings.Contains(s, "224") {
return (elliptic.P224())
} else if strings.Contains(s, "384") {
return (elliptic.P384())
} else if strings.Contains(s, "521") {
return (elliptic.P521())
}
return (ecc.P256k1())
}func main() { msg := "Hello 123"
curveType := "" argCount := len(os.Args[1:])
if argCount > 0 {
msg = os.Args[1]
}
if argCount > 1 {
curveType = os.Args[2]
} pubkeyCurve := getCurve(curveType)
m := []byte(msg)
digest := sha256.Sum256(m) privatekey, _ := ecdsa.GenerateKey(pubkeyCurve, rand.Reader) pubkey := privatekey.PublicKey r, s, _ := ecdsa.Sign(rand.Reader, privatekey, digest[:]) fmt.Printf("=== Message ===\n")
fmt.Printf("Msg=%s\nHash=%x\n", msg, digest)
fmt.Printf("\n=== Private key ===\n")
fmt.Printf("Private key=%x\n", privatekey.D)
fmt.Printf("Curve=%s\n", privatekey.Curve.Params().Name)
fmt.Printf("Bit size=%d\n", privatekey.Curve.Params().BitSize)
fmt.Printf("Base point (G) =(%d, %d)\n", privatekey.Curve.Params().Gx, privatekey.Curve.Params().Gy)
fmt.Printf("Prime=%d, Order=%d", privatekey.Curve.Params().P, privatekey.Curve.Params().N)
fmt.Printf("\n=== Public key (X,Y) ===\n")
fmt.Printf("X=%s Y=%s\n", pubkey.X, pubkey.Y)
fmt.Printf(" Hex: X=%x Y=%x\n", pubkey.X.Bytes(), pubkey.Y.Bytes())
fmt.Printf("\n=== Signature (R,S) ===\n")
fmt.Printf("R=%s S=%s\n", r, s)
fmt.Printf(" Hex: R=%x S=%x\n", r, s) rtn := ecdsa.Verify(&pubkey, digest[:], r, s) if rtn {
fmt.Printf(\n"Signature verifies")
} else {
fmt.Printf("\nSignature does not verify")
}
}

A sample run [here]:

=== Message ===
Msg=Hello 123
Hash=859e38d581e214dc7c8c871c425642913363a829065cf4acddd120ed5391b04b=== Private key ===
Private key=b3645f2efea9a96d28cbeb5bf8a5304a3dc96b2a42bee21c0b3aaa88f595df2d
Curve=P-256k1
Bit size=256
Base point (G) =(55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
Prime=115792089237316195423570985008687907853269984665640564039457584007908834671663, Order=115792089237316195423570985008687907852837564279074904382605163141518161494337
=== Public key (X,Y) ===
X=77007236596272499552697218405908714888874625059778411542685725622785792316534 Y=20745252821220973789342590850065442758134973002375340605949893038975196614597
Hex: X=aa408d244da8a2ea673213ef63536ea96486ce0412a5294c9cdf0959cc689476 Y=2ddd65a19ed17f361b0381a72713f740b63d4fdca059427c389239da39004fc5=== Signature (R,S) ===
R=33027995512220841690000083421269061534408622570666620793995266029032826750381 S=44867240085578618664628913670877492263668786345184239470907981535519639811276
Hex: R=49052ed8fcf1903f530bda10ea9b578b6bb77487ea6b22b5558fc68524e045ad S=6331f53ce5e1a64e4043712631aeeb3f5c0ed753140a0fd76a8c5367e69b34cc
Signature verifies

Here are examples:

Key points on EdDSA and ECDSA

A few key points are:

  1. Ed25519 was proposed in 2011 by Daniel J. Bernstein, Niels Duif, Tanja Lange, Peter Schwabe, and Bo-Yin Yang, while ECDSA was proposed around 2001 by Don Johnson, Alfred Menezes, and Scott Vanstone.
  2. ECDSA uses the secp256k1 curve, and EdDSA uses Curve 25519.
  3. Bitcoin and Ethereum uses ECDSA, while IOTA uses EdDSA.
  4. EdDSA uses the Schnorr signature method, and which is now out of patent. It supports the aggregation of keys in the signature, and also the aggregation of the signature for multiple parties.
  5. For improved security, ECDSA supports a 521-bit curve (P521), while EdDSA supports X448.
  6. ECDSA has a random nonce value created within the signature creation, whereas EdDSA does not. In ECDSA, we need to be careful in making sure that we do not reuse this nonce value, and that it is random.
  7. ECDSA signatures change each time based on the nonce used, whereas EdDSA signatures do not change for the same set of keys and the same message.
  8. ECDSA is often used to keep compatibility with Bitcoin and Ethereum.
  9. ECDSA public keys are (x,y) coordinates and thus have 512 bits (for secp256k1), while Ed25519 uses just the y co-ordinate value for the point, and thus has 256 bits.
  10. ECDSA and EdDSA typically have equivalent performance and security levels.
  11. EdDSA is a deterministic signature (meaning that we always get the same signature for the same private key and message), whereas ECDSA is non-deterministic.
  12. The security of EdDSA and ECDSA are on a par with 128-bit AES and 3K RSA.
  13. EdDSA is fairly immune from side channel attacks.

Conclusions

We need to start building digital systems which are secure by design. At its core of this is the mighty digital signature. Whether it’s ECDSA or EdDSA, you know that maths are making sure that there is some certainty in a transaction.

Find out more about signatures here:

https://asecuritysite.com/signatures/

References

[1] Johnson, D., Menezes, A., & Vanstone, S. (2001). The elliptic curve digital signature algorithm (ECDSA). International journal of information security, 1(1), 36–63.

[2] Bernstein, D. J., Duif, N., Lange, T., Schwabe, P., & Yang, B. Y. (2012). High-speed high-security signatures. Journal of cryptographic engineering, 2(2), 77–89.

--

--

Prof Bill Buchanan OBE FRSE
Prof Bill Buchanan OBE FRSE

Written by Prof Bill Buchanan OBE FRSE

Professor of Cryptography. Serial innovator. Believer in fairness, justice & freedom. Based in Edinburgh. Old World Breaker. New World Creator. Building trust.

No responses yet