With digital signatures we take a hash of a message and sign it with a private key, and then use a public key to verify it. Two popular signatures use EdDSA and are Ed25519 and Ed488. Overall Ed25519 gives 128-bit security, while Ed448 gives 256-bit security. We can merge these with the Dilithium post quantum cryptography method. In this case we will use Ed25519, Ed488, Ed25519-Dilithium2 and Ed448-Dilithium3.
Digital Signatures using CIRCL |
Performance evaluation
For ECDSA, RSA, Ed25519 and Ed448 we have:
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) RSA
The following provides an analysis of the PCQ methods for digital signing:
Method Public key size Private key size Signature size Security level ------------------------------------------------------------------------------------------------------ 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 Rainbow Level Ia (Oil-and-Vineger) 161,600 103,648 66 1 (128-bit) Multivariate (UOV) Rainbow Level IIIa 861,400 611,300 164 3 (192-bit) Multivariate (UOV) Rainbow Level Vc 1,885,400 1,375,700 204 5 (256-bit) Multivariate (UOV) 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 Picnic 3 Full 49 73 71,179 3 (192-bit) Symmetric GeMSS 128 352,188 16 33 1 (128-bit) Multivariate (HFEv-) GeMSS 192 1,237,964 24 53 1 (128-bit) Multivariate (HFEv-)
For performance on M4 (ARM Cortex-M4 dev) [1] and measured in CPU operations per second. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Key generation Sign Verify ---------------------------------------------------------------- Crystals Dilithium 2 (Lattice) 36,424 61,312 40,664 Crystals Dilithium 3 50,752 81,792 55,000 Crystals Dilithium 5 67,136 104,408 71,472 Falcon 512 (Lattice) 1,680 2,484 512 Falcon 1024 1,680 2,452 512 Rainbow Level Ia (Oil-and-Vineger) 2,969 4,720 2,732 Rainbow Level IIIa 3,216 3,224 1,440 Rainbow Level Vc 3,736 6,896 4,928 Sphincs SHA256-128f Simple 2,192 2,248 2,544 Sphincs SHA256-192f Simple 3,512 3,640 3,872 Sphincs SHA256-256f Simple 5,600 5,560 5,184
For stack memory size on an ARM Cortex-M4 device [1] and measured in bytes. Note, no Rainbow assessment has been performed in [1], so LUOV (an Oil-and-Vinegar method) has been used to give an indication of performance levels:
Method Memory (Bytes) ------------------------------------------------- Crystals Dilithium 2 (Lattice) 13,948 Crystals Dilithium 3 13,756 Crystals Dilithium 5 13,852 Falcon 512 (Lattice) 117,271 Falcon 1024 157,207 Rainbow Level Ia (Oil-and-Vineger) 404,920 Rainbow Level IIIa 405,412 Rainbow Level Vc 405,730 Sphincs SHA256-128f Simple 4,668 Sphincs SHA256-192f Simple 4,676 Sphincs SHA256-256f Simple 5,084
Ed25519 signing
With Ed25519, Bob first generates a 256-bit random number for his private key (\(priv\)) and then create the public key with:
\(pub = H(priv)[\colon 32] \cdot B\)
and where \(B\) is the base point on the curve, and where \(H()\) is a hash function (SHA-512). In this case we take the lower 32 bytes of the SHA-512 hash. Normally we just define this as the \(y\) co-ordinate of the point. The public key is thus 32 bytes long (256 bits). To compute the signature, we generate:
\(r = H_{int}( H(priv)[32\colon] \: || \: M) \pmod l\)
and where \(H_{int}()\) is a hash function (SHA-512) and converted to an integer value. In this case we take the upper 32 bytes for the calculation. The value of \(l\) is the order of the curve. Then \(M\) is the byte value of the message. With "||" we append the bytes together. We then convert this to a point on the curve with:
\(R=r \cdot B\)
Next, we compute:
\(h=H_{int}(R \: || \: pub \: || \: M) \pmod l\)
and:
\(s=H_{int}(priv))[\colon 32]\)
\(S=(r+h \cdot s) \pmod l\)
The signature is then \((R,S\)). Bob sends \(M\), \(R\), \(S\) and \(pub\) to Alice. Alice then computes:
\(k=H(R \: || \: pub \: || \: M) \pmod l\)
\(P_1=S \cdot B\)
\(P_2=R + k \cdot pub\)
and if \(P_1\) is equal to \(P_2\), the signature verifies. This works because:
\(P_1=S \cdot B = (r + h \cdot s \pmod l) \cdot B = r \cdot B + h \cdot s \cdot B = R + h \cdot pub = P_2\)
Note that \(l\) is the order of the curve (\(l= 2^{252} + 27742317777372353535851937790883648493\)).
The great advantage of using Ed25519 over ECDSA is that we can aggregate signatures and public keys.
Here is an overview of the maths involved:
There are three main modes [RFC 8032] that we can have: Ed25519 (pure EdDSA, as we have defined above), Ed25519Ph (where the message is hashed), and Ed25519Ctx (and where we add a context message):
- Ed25519 (pure Ed25519). \(r = H_{int}( H(priv)[32\colon] \: || \: M) \pmod l\)
- Ed25519Ph (with pre-hash). \(r = H_{int}( H(priv)[32\colon] \: || \: H(M)) \pmod l\). In this case the message will be hashed with SHA-512 before it is used.
- Ed25519Ctx (with context). \(r = H_{int}( H(priv)[32\colon] \: || \: M \: || \: Ctx) \pmod l\) and where \(Ctx\) is a context string.
Coding
The following is an outline of the code:
package main import ( "fmt" "os" "github.com/cloudflare/circl/sign" "github.com/cloudflare/circl/sign/schemes" ) func main() { modename := "Ed25519" m := "Hello" argCount := len(os.Args[1:]) if argCount > 0 { modename = os.Args[1] } if argCount > 1 { m = os.Args[2] } mode := schemes.ByName(modename) pk, sk, _ := mode.GenerateKey() msg := []byte(m) opts := &sign.SignatureOpts{} signature := mode.Sign(sk, msg, opts) fmt.Printf("CIRCL Signatures\n\n") fmt.Printf("Signature method: %s \n", modename) fmt.Printf("Message: %s \n\n", msg) skbin, _ := sk.MarshalBinary() fmt.Printf("Private key: %x [showing first 32 bytes]\n", skbin[:32]) fmt.Printf(" - Private key length: %d\n", len(skbin)) pkbin, _ := sk.MarshalBinary() fmt.Printf("Public key: %x [showing first 32 bytes]\n", pkbin) fmt.Printf(" - Public key length: %d\n", len(pkbin)) fmt.Printf("Signature: %x [showing first 32 bytes]\n", signature[:32]) fmt.Printf(" - Signature length: %d \n", len(signature)) if !mode.Verify(pk, msg, signature, opts) { panic("Signature has NOT been verified!") } else { fmt.Printf("Signature has been verified!") } }
A sample run for Ed25519 is:
CIRCL Signatures Signature method: Ed25519 Message: Hello Private key: 9b5ab3255af6dadc6617d4561920ca1f01e7471887f171a5a18a2fde5776073d [showing first 32 bytes] - Private key length: 64 Public key: 9b5ab3255af6dadc6617d4561920ca1f01e7471887f171a5a18a2fde5776073d [showing first 32 bytes] - Public key length: 64 Signature: 3d97019e0420f43098044280f021fef52d347da25832a4177b5052786f4edfc3 [showing first 32 bytes] - Signature length: 64 Signature has been verified!
A sample run for Ed448 is:
CIRCL Signatures Signature method: Ed448 Message: Hello Private key: e1be32ff5822ef8a44adf5e290e79dbda1db9e6ef6b2857f592cd53b866e8b77 [showing first 32 bytes] - Private key length: 114 Public key: e1be32ff5822ef8a44adf5e290e79dbda1db9e6ef6b2857f592cd53b866e8b77 [showing first 32 bytes] - Public key length: 114 Signature: d76ea76c46841572edd7142f1e3598199d563e0de5a6fd2ff7bdde6de331ee89 [showing first 32 bytes] - Signature length: 114 Signature has been verified!
A sample run for Ed25519-Dilithium2:
CIRCL Signatures Signature method: Ed25519-Dilithium2 Message: Hello Private key: 73649b69fcbaf7ef753bedbebd598fcf7a4cc8bd85dc8ec3c0e564389893e5ec [showing first 32 bytes] - Private key length: 2560 Public key: 73649b69fcbaf7ef753bedbebd598fcf7a4cc8bd85dc8ec3c0e564389893e5ec [showing first 32 bytes] - Public key length: 2560 Signature: c63a0b2c213d47020f1c2283f14531e2647bc402526a476c559a2c81c537aee2 [showing first 32 bytes] - Signature length: 2484 Signature has been verified!
A sample run for Ed448-Dilithium3 :
CIRCL Signatures Signature method: Ed448-Dilithium3 Message: Hello Private key: 8e521eed1cce7b5010e1b88472449f5bb9181142e9751e84f099d8a14f7b0ce3 [showing first 32 bytes] - Private key length: 4057 Public key: 8e521eed1cce7b5010e1b88472449f5bb9181142e9751e84f099d8a14f7b0ce3 [showing first 32 bytes] - Public key length: 4057 Signature: ae6ac74a19dc0842e9abe49522c6617f32b9fb867de6d4b93b553176fed6ee7f [showing first 32 bytes] - Signature length: 3407 Signature has been verified!