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 that many other digital signature methods, and is strong for security. One example of EdDSA is Ed25519, and which is based on Curve 25519. It generates a 64-byte signature value of (R,s), and has 32-byte values for the public and the private keys. In this case we will split a private key into a 2-from-3 secret share policy and allocate to a number of parties. Next each of the parties can generate a part of the signature, and then these are aggregated together to produce the overall signature. In this way the private key never has to be rebuild, in order to create a signature for a data object.
Threshold Ed25519 in Golang |
Theory
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.
Threshold Ed25519
We initially each party creates a secret (\(s_i\)) and commits to a public key of [Threshold Signatures Using Ed25519 and Ed448]:
\(A_i = s_i \cdot B\)
and where \(B\) is the base point on the curve. The party also generates a random value \(r_i\) and commits to:
\(R_i = r_i \cdot B\)
Finally each party generates:
\(S_i=r_i + h.s_i \pmod l\)
and where \(q\) is the order of the curve. Each party then commits to (\(A_i, R_i, S_i\)) and sends to the other parties, and waits for a reply of the commitments. With all commitments received, we can rebuild:
\(R = R_1 + R_2 + ... R_n\)
\(S = S_1 + S_2 + ... S_n\)
The public key (\(A\)) is then:
\(A=A_1 + A_2 + ... A_n\)
and which is equal to:
\(A=s_1 \cdot B + s_2 \cdot B + ... s_n \cdot B\)
We then simply verify with:
\(S.B = R + k.A\)
The signature is then \((R,S)\).
With Shamir Secret Sharing, we modify so that each party has a secret key value (\(s_i\)) and multiplied by a Lagrange coefficient \(l_i\) which matches to a given share. We then recontruct with:
\(A_i = s_i l_i \cdot B\)
\(R_i = r_i \cdot B\)
\(S_i = r_i + k.l_i . s_i \pmod p\)
Coding
The following is an outlline of the code:
package main import ( "fmt" "os" "github.com/coinbase/kryptology/pkg/ted25519/ted25519" ) func main() { msg := "Hello 123" argCount := len(os.Args[1:]) if argCount > 0 { msg = os.Args[1] } message := []byte(msg) config := ted25519.ShareConfiguration{T: 2, N: 3} pub, secretShares, _, _ := ted25519.GenerateSharedKey(&config) // Each party generates a nonce and we combine them together into an aggregate one noncePub1, nonceShares1, _, _ := ted25519.GenerateSharedNonce(&config, secretShares[0], pub, message) noncePub2, nonceShares2, _, _ := ted25519.GenerateSharedNonce(&config, secretShares[1], pub, message) noncePub3, nonceShares3, _, _ := ted25519.GenerateSharedNonce(&config, secretShares[2], pub, message) nonceShares := []*ted25519.NonceShare{ nonceShares1[0].Add(nonceShares2[0]).Add(nonceShares3[0]), nonceShares1[1].Add(nonceShares2[1]).Add(nonceShares3[1]), nonceShares1[2].Add(nonceShares2[2]).Add(nonceShares3[2]), } noncePub := ted25519.GeAdd(ted25519.GeAdd(noncePub1, noncePub2), noncePub3) sig1 := ted25519.TSign(message, secretShares[0], pub, nonceShares[0], noncePub) sig2 := ted25519.TSign(message, secretShares[1], pub, nonceShares[1], noncePub) sig3 := ted25519.TSign(message, secretShares[2], pub, nonceShares[2], noncePub) fmt.Printf("Message: %s\n", msg) fmt.Printf("Public key: %x\n", pub.Bytes()) fmt.Printf("\nThreshold Sig1: %x\n", sig1.Bytes()) fmt.Printf("Threshold Sig2: %x\n", sig2.Bytes()) fmt.Printf("Threshold Sig3: %x\n\n", sig3.Bytes()) sig, _ := ted25519.Aggregate([]*ted25519.PartialSignature{sig1, sig3}, &config) fmt.Printf("Rebuild signature with share 1 and 3: %x\n", sig) sig, _ = ted25519.Aggregate([]*ted25519.PartialSignature{sig2, sig3}, &config) fmt.Printf("Rebuild signature with share 2 and 3: %x\n", sig) ok, _ := ted25519.Verify(pub, message, sig) if ok { fmt.Printf("\nSignature verified") } else { fmt.Printf("\nSignature unverified") } }
A sample run with the message of "Hello" is:
Message: Hello Public key: 32f3de6fe91c3120d1ed6536181aaf4a17a3cc414c15cbcaaf7e76734770a723 Threshold Sig1: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6bee19a3df5ec71a880889bc69159794c59c1eb18b816414dc928d30e88c27ff0b Threshold Sig2: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6b36f588b97b9105677d2a9bc7a66a0f63573f83a05007f507b093b96ea8d23604 Threshold Sig3: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6b6ba464f0b2be029ec86871c816386915126055b51faad533cd9942f5c37d6e0c Rebuild signature with share 1 and 3: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6bb96ac7a8279a1d51bd4ae668a5c93a13e2fdde76b2c133b07587a761717cc703 Rebuild signature with share 2 and 3: 795c891047115ee8dd8f41fdd96af61229762c3942e035799611cb2882ef7b6bb96ac7a8279a1d51bd4ae668a5c93a13e2fdde76b2c133b07587a761717cc703 Signature verified
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 as 32 bytes. Overall Ed25519 produces one of the smallest signature sizes, and has a small size of the public and private key.