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 with PEM |
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/pki" "github.com/cloudflare/circl/sign" "github.com/cloudflare/circl/sign/schemes" ) func slice(a []byte, length int) string { s := "" len1 := length if len(a) < length { len1 = len(a) } for i := 0; i < len1; i++ { s = s + (string(a[i])) } return (s) } 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] } scheme := schemes.ByName(modename) pk, sk, _ := scheme.GenerateKey() packedPk, _ := pki.MarshalPEMPublicKey(pk) packedSk, _ := pki.MarshalPEMPrivateKey(sk) fmt.Printf("Message: %s\n", m) fmt.Printf("Scheme: %s\n", scheme.Name()) p, _ := pk.MarshalBinary() fmt.Printf("Public Key (first 100 bytes): %x, Length: %d\n", slice(p, 100), len(p)) p, _ = sk.MarshalBinary() fmt.Printf("Secret Key (first 1000 bytes): %x, Length: %d\n", slice(p, 100), len(p)) fmt.Printf("\nPublic Key (PEM) - first 400 bytes:\n%s\n", slice(packedPk, 400)) fmt.Printf("\nPrivate Key (PEM) - first 400 bytes:\n%s\n", slice(packedSk, 400)) opts := &sign.SignatureOpts{} msg := []byte(m) sig := scheme.Sign(sk, msg, opts) fmt.Printf("\nSignature (first 100 bytes): %x, Length: %d\n", slice(sig, 100), len(sig)) }
A sample run for Ed25519 is:
Message: Hello Scheme: Ed25519 Public Key (first 100 bytes): 093dc2a6044c290a642e1ac292173369c2aec28b5dc28e39c38cc3895800375759c38e6bc39fc3b962c2a6, Length: 32 Secret Key (first 1000 bytes): c293c2ae3ac3b97b781a4367c383c28064172bc29b20c29dc29212c2bc1ec3bf39c2a70100c389204f7a62c3b1093dc2a6044c290a642e1ac292173369c2aec28b5dc28e39c38cc3895800375759c38e6bc39fc3b962c2a6, Length: 64 Public Key (PEM) - first 400 bytes: -----BEGIN PUBLIC KEY----- MCowBQYDK2VwAyEACT2mBEwpCmQuGpIXM2mui12OOczJWAA3V1nOa9/5YqY= -----END PUBLIC KEY----- Private Key (PEM) - first 400 bytes: -----BEGIN Ed25519 PRIVATE KEY----- ME4CAQAwBQYDK2VwBEIEQJOuOvl7eBpDZ8OAZBcrmyCdkhK8Hv85pwEAySBPemLx CT2mBEwpCmQuGpIXM2mui12OOczJWAA3V1nOa9/5YqY= -----END Ed25519 PRIVATE KEY----- Signature (first 100 bytes): c28dc38876c2bb4f4f60c3a3c39ec2a4c2a1c288795c762141c28f4f39c2a80bc389c289c29c1dc29079c2a2127a724fc2b8c2bac28dc29c4836375d2cc2a7c39400c28579c3b6c38c0d213c3cc397c3890ac38622c299205815c28203, Length: 64
A sample run for Ed448 is:
Message: Hello Scheme: Ed448 Public Key (first 100 bytes): c393c2abc397c396c2abc3a0682e58c3855f79c2bf7cc2a3194cc39561c392c3bd1bc28dc391c38a09c3924dc2a2c3b9c39657c39f4312615a15c2bf56c2b5c2be7cc2b667221469382f0ac297c3a7c286c3ba0fc280, Length: 57 Secret Key (first 1000 bytes): 52c2aa7f563b07c2ba57c390c39cc3acc2b2c3b2c3a5640646c395c29fc3a70f32c390c2a7c38fc3bbc38ac38ec293515cc293c28bc28b4f03c2a7c2be74355ec3ba26c3bf67c3a77074c3af34c39ac29c1d3811c28f06c393c2abc397c396c2abc3a0682e58c3855f79c2bf7cc2a3194cc39561c392c3bd1bc28dc391c38a09c3924dc2a2c3b9c39657c39f4312615a15c2bf56c2b5c2be7c, Length: 114 Public Key (PEM) - first 400 bytes: -----BEGIN PUBLIC KEY----- MEMwBQYDK2VxAzoA06vX1qvgaC5YxV95v3yjGUzVYdL9G43RygnSTaL51lffQxJh WhW/VrW+fLZnIhRpOC8Kl+eG+g+A -----END PUBLIC KEY----- Private Key (PEM) - first 400 bytes: -----BEGIN Ed448 PRIVATE KEY----- MIGAAgEAMAUGAytlcQR0BHJSqn9WOwe6V9Dc7LLy5WQGRtWf5w8y0KfP+8rOk1Fc k4uLTwOnvnQ1Xvom/2fncHTvNNqcHTgRjwbTq9fWq+BoLljFX3m/fKMZTNVh0v0b jdHKCdJNovnWV99DEmFaFb9Wtb58tmciFGk4LwqX54b6D4A= -----END Ed448 PRIVATE KEY----- Signature (first 100 bytes): 4ac38cc29e78c287c3a4c381c2b0c2b630c2aa6a1d1c28c389c297c2ba6c7d52c2a3c29a16c2b25034c2bdc39cc28a1ec3b9c3a1c386c3a77553c3a7c2812a7cc3a6c39612c3bfc2bf73c2940774c2a0c290c2b834c3b371c280c3ae682cc293c390514469c28ec3be61600dc2807e22c3ad0dc2b61b17c3ab75c3984fc3bbc2b6386752c3bb0e3ac39b3ec3bec3830bc2a0584513c281, Length: 114
A sample run for Ed25519-Dilithium2:
Message: Hello Scheme: Ed25519-Dilithium2 Public Key (first 100 bytes): c28631c2b4c3bec28a57c3b7c38ec286c3a441c2a87ec28208c29f64c38dc29c5d31073655c2b5c38cc38ec298550ec3aac286c293c2bd4fc3aac28fc29cc392c28437c389c382c287752dc281030bc2b4c3b17724c29fc2a8c2974d21c394391b5cc297c3adc3a1c280c2ac542256c3ae1802c3a93ec291337cc39e027d6dc3a5c28003c3b0c38ac38965520ac29dc3ad32c39a250738c286c38f, Length: 1344 Secret Key (first 1000 bytes): c28631c2b4c3bec28a57c3b7c38ec286c3a441c2a87ec28208c29f64c38dc29c5d31073655c2b5c38cc38ec298550ec3aac28654140f43c3a9c3bcc288c2a1c2b0c3bd70c289c38e2771c2b1c397c2ae0dc39573c38fc39dc3b96109c39bc291c3bb3a03c2aec3aac3813c200dc3aec2986ac3b11f4869046d53c2bfc29ec29bc29665c3afc29fc28dc2ac63c3acc29c293dc2b1c3be27c29cc286c28161, Length: 2560 Public Key (PEM) - first 400 bytes: -----BEGIN PUBLIC KEY----- MIIFUzAMBgorBgEEAYLaSy0JA4IFQQCGMbT+ilf3zobkQah+ggifZM2cXTEHNlW1 zM6YVQ7qhpO9T+qPnNKEN8nCh3UtgQMLtPF3JJ+ol00h1DkbXJft4YCsVCJW7hgC 6T6RM3zeAn1t5YAD8MrJZVIKne0y2iUHOIbP6T07e9EyXgi+vD/MhjhgyWC4fu7w jpQf8xJaHDbbDNdm/YcxWp/OOiLHoOZa55Y1NbzX3Ny/eo6JSFVWlmTQCR1KVfcc 94HDlGzfSj27w/N5aT2uVyEM5ycqqpcoWuoxAsSC+/A77nSnNcskbNrs/TFLLK/q W+a5JMgQ7KA+ha/lCoM6i48SlgwwFNPLeZVf1AnCp7PUEOP0 Private Key (PEM) - first 400 bytes: -----BEGIN Ed25519-Dilithium2 PRIVATE KEY----- MIIKGQIBADAMBgorBgEEAYLaSy0JBIIKBASCCgCGMbT+ilf3zobkQah+ggifZM2c XTEHNlW1zM6YVQ7qhlQUD0Pp/IihsP1wic4ncbHXrg3Vc8/d+WEJ25H7OgOu6sE8 IA3umGrxH0hpBG1Tv56blmXvn42sY+ycKT2x/iechoFhAmyRRihKBg3MKAoUJGaT FmaKlGHcQmQkh4TgJE7RAFFASIHBsgUhMnFCQmoEsyiaiAFbBGZJBghEQAYTAQkT KWrkQJGERAgjsmXcoixkBkgKNUjKpowkQyIctA2LiDHaxk2DsiwJxGFMmDEIiDBE Ni2hxoDiCGALyIWYlm2DlkUJQQ5D Signature (first 100 bytes): c3b57ec297c292c39c1a562bc29942c2bac29b1656c2a518c2ab1d171f5dc3a33dc2b9c28e2cc2bb2200c2945ac28654c281005cc281c284c2be406cc39d023ac2bf6956c3b34b4dc2926d40c39ac287c2b5c2832e79c383c380031243c2a34335636dc3aac2937f4b51c284c385c3bec292c2b2c2a06cc3ab1bc38917c29bc29ec2b8314c5fc2a2c38dc39bc2a2c2ba3ac39cc2813c, Length: 2484
A sample run for Ed448-Dilithium3 :
Message: Hello Scheme: Ed448-Dilithium3 Public Key (first 100 bytes): c2b2c3b508c28d38c392c39cc38c5bc39bc2bc5bc2961dc3bc557ac3b7c29e522fc38bc390c38dc39d6fc3b3c2b4610366c29ec29b533a18c2986f67c2871b51c2bbc28263c3a967c2b3c387c2adc39468c29fc297206b7dc39b12c291c3b5c2af31061ac3a50bc39bc3b5022fc39dc2a70c1d11c29e7dc2afc380c2b1c2a30356c39561c393c29165c3b600c3b5c3b916091c22c2a61775, Length: 2009 Secret Key (first 1000 bytes): c2b2c3b508c28d38c392c39cc38c5bc39bc2bc5bc2961dc3bc557ac3b7c29e522fc38bc390c38dc39d6fc3b3c2b4610366c29e642b565744c3ae76c292291e4613c3b8c295c38a322f1d6c5b16c391452fc28dc3820910c3980b576bc3bfc2abc2805220c2901d0c416ec283c28a12c3a86634c3ad0216c2a6c28cc2b86850c3885ac390c39ac38b04c3bd1146657802, Length: 4057 Public Key (PEM) - first 400 bytes: -----BEGIN PUBLIC KEY----- MIIH7DAMBgorBgEEAYLaSy0KA4IH2gCy9QiNONLczFvbvFuWHfxVeveeUi/L0M3d b/O0YQNmnptTOhiYb2eHG1G7gmPpZ7PHrdRon5cga33bEpH1rzEGGuUL2/UCL92n DB0Rnn2vwLGjA1bVYdORZfYA9fkWCRwiphd1sophqc+0b/g4T+FlS0ZrDwlcFeph vjkPfLHIpRov3H6snGuujz/XBamVTJaF3V/mubq70i2KpVWzKIjgDb6AcnJUP6Yo yKpYXLXsoD3JCNYP78s1iKPMSh1wJFJdsaZPPrbszEa4gCLVUDdPEC1im9xhi6oD V/gZ4//07cAa0qqXSjDxzqtzDvIimk0jEQVdDYUjiK2Cs9I7 Private Key (PEM) - first 400 bytes: -----BEGIN Ed448-Dilithium3 PRIVATE KEY----- MIIP8gIBADAMBgorBgEEAYLaSy0KBIIP3QSCD9my9QiNONLczFvbvFuWHfxVevee Ui/L0M3db/O0YQNmnmQrVldE7naSKR5GE/iVyjIvHWxbFtFFL43CCRDYC1dr/6uA UiCQHQxBboOKEuhmNO0CFqaMuGhQyFrQ2ssE/RFGZXgCUVeIiERFIEA2cBEDNgdD dTFnUmFjhFg2MiaFV0OHcEFAZyKDIxYkhyhGUkBSQCBjJ1FIJGUQBCADJwRnIYAY BVMFVggSdxBBY2ZHdQOAZUJXGGUxWDaHR0F3USZiUlVkZBMSFkEVRFFxZBgkeFhi IydxNRh4hHFAEnRWWBiAVQMxhxUmFI Signature (first 100 bytes): 6bc2a3c39b1271c2a0c3bbc2932778c3ac1bc2acc3876473c2a93372c29a410fc3b051c29112c3ab66c3a6c3ae74690fc3a1c285c28c65235d4a22c3bc4b7010c38127c3acc2bb1bc395123602c3a3475ac3a82ec381c3b6c29919c29442c29dc2a2c383c2b66417c380c397c391041fc39378c3ae2f1c5fc292c2b7c3817cc39c4e13c3897fc3ac7b45c289c294c29e2a4430, Length: 3407