Feb 4
Schnorr and Bernstein joins Rivest, Johnson and Kravitz: EdDSA Joins The Digital Signature Hall of Fame
This week NIST published a new update to its FIPS 186 standard with Version 5, and officially adopted the EdDSA signature in the world of DSS (Digital Sigure Standard) [here]:
While EdDSA joins ECDSA and RSA for the first time, DSA (created by David W. Kravitz) is officially only supported for existing implementations. And, so, for digitial signatures it is EdDSA, ECDSA and RSA that are the NIST standards. Both EdDSA and ECDSA are elliptic curve methods, and RSA is, well, an RSA method.
All of them create digital signatures (r,s), 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.
Why ECDSA or EdDSA?
So what’s the difference between ECDSA and EdDSA? 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 verifiesThe 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.
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 verifiesKey points on EdDSA and ECDSA
A few key points are:
- 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.
- ECDSA uses the secp256k1 curve, and EdDSA uses Curve 25519.
- Bitcoin and Ethereum uses ECDSA, while IOTA uses EdDSA.
- 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.
- For improved security, ECDSA supports a 521-bit curve (P521), while EdDSA supports X448.
- 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.
- 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.
- ECDSA is often used to keep compatibility with Bitcoin and Ethereum.
- 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.
- ECDSA and EdDSA typically have equivalent performance and security levels.
RSA Signatures
And what can you say about RSA? It is over 44 years, and still going strong. We still use it to encrypt data, and can still use it to example encryption keys. It has grown rather large (up to 4,096 bit keys) to keep up with the elliptic curve methods (which has equivalent keys sizes of just 256 bits), but it is still going strong, and is often the signature that is used in SSH connections, and for TLS/SSL. In fact, if you look at most of the digital certificates on the Web, the most common type has an RSA public key.
With RSA, we have a key pair of (e,N) for the public key, and (d,N) for the private key. In signatures, we use the decryption key value (d) to encrypt for a signature, and the public key to prove the signature. In this case, we use s as the signing exponent (which would be defined as d for decryption), and v for the verification exponent (which would be defined as e for encryption). Alice initially has two secret prime numbers (p and q), and which she produces a product (the modulus):
N=pq
Next, she selects a verification exponent (v), and which does not share a factor with:
PHI=(p-1)(q-1)
In most cases she will select:
v=65,537
Next she computes the signature exponent (s) with:
s.v=1 mod(p−1)(q−1)
Next she takes a message (D) and sign with:
S=D^s (mod N)
Bob then checks the signature with:
M=S^v (modN)
If M is equal to D, the signature matches.
This works because of Euler’s formula, where:
S^v=D^{sv}=D (mod N)
An example is here:
https://asecuritysite.com/signatures/rsa12_sig
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/
And …. and dark cloud
There’s a dark cloud on the horizon for each of these methods: quantum computers, and which can crack each of the signature methods. So, within a decade, we are likely to see them replaced by lattice methods, such as with Dilithum:
https://asecuritysite.com/pqc/pqc_sig
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.
Asecuritysite is provided free and without adverts. If you want to support its development and get full access to this blog, subscribe here:
