Having Your Crypto Signature Cake And Eating It: Ed25519 or Dilithium … Why Not Have Both?
A few years ago, the Internet was a wild west for security and trust. Basically, very few Web sites could actually be trusted, as often they just supported HTTP. This meant that users could be spied upon and that they could be easily tricked to visit fake sites. Google Chrome changed all that and pushed forward the usage of digital certificates and digital signing for Web sites (to give HTTPs). For trust, the two main methods used are RSA and ECDSA (with RSA being the most popular signature method for Web sites). Now, virtually every website is trusted, and where their public key has been signed by a trusted digital certificate provider.
But, there’s a big cloud on the horizon … and this one is a quantum cloud. Like it or not, both RSA and ECDSA can be cracked by a quantum computer. Considering the ECDSA is also used in Bitcoin and Ethereum, we have less of a cloud, and more of a storm approaching.
Luckily, NIST has been working on new standards to replace our existing public key methods, and this is typically based on lattice methods. The most likely method to be standardized in the next year or so is CRYSTALS-Dilithium. This will allow us to create a key pair in the same way we do now, and then we can sign messages with the private key, and then prove with the associated public key:
So, should your company support a traditional signature or a post-quantum one? Well, one approach is to go hybrid, and where you contain both the traditional signature and keys and the post-quantum one. While this will obviously increase the data in the signature, it will allow applications to migrate from RSA or ECDSA towards Dilithium.
The Ed25519 signature method is highly popular for new applications and uses Curve 25519 as a base. But, it is based on elliptic curve methods and thus needs to be replaced by a quantum robust method.
CRYSTALS Dilithium uses lattice-based Fiat-Shamir schemes and produces one of the smallest signatures of all the post-quantum methods, and with relatively small public and private key sizes. The three main implementations for the parameters used are: Dilithium 2, Dilithium 3 and Dilithium 5. Overall, Dilithium 2 is equivalent to a 128-bit signature and is perhaps the starting point for an implementation.
Luckily, we have the CIRCL library and which supports hybrid methods. For ECDSA, RSA, Ed25519 and Ed448 we have key and signature sizes of:
Method Public key size (B) Private key size (B) Signature size (B) Security level
------------------------------------------------------------------------------------------------------
Ed25519 32 32 64 1 (128-bit) EdDSA
Ed448 57 57 112 3 (192-bit) EdDSA
ECDSA 64 32 48 1 (128-bit) ECDSA
RSA-2048 256 256 256 1 (128-bit) RSAIt can be seen that Ed25519 has one of the smallest public and private ke sizes (each with 32 bytes), and a fairly small signature size (64 bytes). The following provides an analysis of the PCQ methods for digital signing:
Method Public key size Private key size Signature size Security level
------------------------------------------------------------------------------------------------------
Crystals Dilithium2-X25519 2,560 1,344 2,484 1 (128-bit) Lattice
Crystals Dilithium3-X25519 4,057 2,009 3,407 3 (192-bit) Lattice
Crystals Dilithium 2 (Lattice) 1,312 2,528 2,420 1 (128-bit) Lattice
Crystals Dilithium 3 1,952 4,000 3,293 3 (192-bit) Lattice
Crystals Dilithium 5 2,592 4,864 4,595 5 (256-bit) Lattice
Falcon 512 (Lattice) 897 1,281 690 1 (128-bit) Lattice
Falcon 1024 1,793 2,305 1,330 5 (256-bit) Lattice
Sphincs SHA256-128f Simple 32 64 17,088 1 (128-bit) Hash-based
Sphincs SHA256-192f Simple 48 96 35,664 3 (192-bit) Hash-based
Sphincs SHA256-256f Simple 64 128 49,856 5 (256-bit) Hash-based
We can see that the signature size of X25519 is normally 64 bytes, but this increases to 2,484 bytes for both Dilithium2 and X25519 (and thus Dilithium2 has a signature size of 2,420 bytes. The public key rises from 32 bytes to 2,560 bytes, and the private key from 32 bytes to 1,344 bytes.
The following is an outline of the code [here]:
package main
import (
"fmt"
"os"
"github.com/cloudflare/circl/sign/eddilithium2"
)
func main() {
m := "Hello"
argCount := len(os.Args[1:])
if argCount > 0 {
m = os.Args[1]
}
pk, sk, _ :=eddilithium2.GenerateKey(nil)
msg := []byte(m)
var signature [eddilithium2.SignatureSize]byte
eddilithium2.SignTo(sk, msg,signature[:])
fmt.Printf("PQC Signatures (Ed25519-Dilithium2)\n\n")
fmt.Printf("Message: %s \n\n", msg)
fmt.Printf("Private key: %x [showing first 64 bytes]\n", sk.Bytes()[:64])
fmt.Printf(" - Private key length: %d\n", len(sk.Bytes()))
fmt.Printf("Public key: %x [showing first 64 bytes]\n", pk.Bytes()[:64])
fmt.Printf(" - Public key length: %d\n", len(pk.Bytes()))
fmt.Printf("Signature: %x [showing first 64 bytes]\n", signature[:64])
fmt.Printf(" - Signature length: %d \n", len(signature))
if !eddilithium2.Verify(pk, msg, signature[:]) {
panic("Signature has NOT been verified!")
} else {
fmt.Printf("Signature has been verified!")
}
}A sample run for Ed25519-Dilithium2 is [here]:
PQC Signatures (Ed25519-Dilithium2)
Message: Hello
Private key: daa45043f2a791d980ada155688addc4663d6213f37483df02118edaace5ffc5f86fb44e0caea401646ab1b0ca663abc145a02a54121eed835eabb18b8fe7014 [showing first 64 bytes]
- Private key length: 2560
Public key: daa45043f2a791d980ada155688addc4663d6213f37483df02118edaace5ffc53d1c1b16bc78f4ffe014c74920296913b4b57da2ccae0699de644e349aeec1af [showing first 64 bytes]
- Public key length: 1344
Signature: 1b87ef67f34b472e811da6de8064605e833ca6c68007c1846b36f7bd4c6c231ff55b49c0a7b3a7f63e96c171b6ef4095c1e6e80c2eab53bee4ac9309acc7739f [showing first 64 bytes]
- Signature length: 2484
Signature has been verified!And here is Dilithium3-X25519:
https://asecuritysite.com/circl/circl_dil3
Conclusions
And, so, the days of the short ECDSA signature will be gone with the advent of PQC. Bitcoin and Ethereum have benefited from their small key sizes and signatures, but we need to migrate, so consider the future … and having your crypto cake and eating it.
