Golang SchnorrThe Schnorr signature is used in Bitcoin, and allows an entity to sign for a message with their private key, but then for everyone involved to generate the public key from the signature, and also for it to be veriified. |
Outline
Signatures are at the core of our world of trust. For centuries we have used them as a legal way of proving our identity and our confirmation of something.
But, in this modern world, our usage of wet signatures is flawed, and have very little credibility. Few of us have to sign for things these days, and thus our signature is often difficult to properly verify. Along with this we often just sign the last page of a document, and where a malicious entity could replace all the other pages. Wet signatures, too, are often scanned and added to documents as GIF files, and then converted into PDF format. All these methods have virtually zero credibility.
In a digital age, we thus need to move to methods which are almost 100% certain, and where we create signatures which cannot be forged, and which validate that the contents of a message/document have not been changed. For this we need digital signatures, and one of the most widely used methods is based on elliptic curve cryptography (ECC): ECDSA.
With ECDSA we create a public and a private key, and then sign a message with the private key, and where the public key is then used to check the validity of the signature. For this we generate a private key, and then, through ECDSA, we can produce the associated public key:
In this way, the Bitcoin infrastructure knows that the person with the correct private key has signed the transaction.
But what happens if two or more people sign a document? Can we produce a single signature for them, so that they both bring their signatures together to sign a document?
Let's say two people want to purchase a new car. How do we create a single signature that proves that it has been signed by both people? Also, how can we make sure that if we get them to sign the same document, that the signature is not the same? Well, that is where the Schnorr signature method comes in, and where we can aggregate signers into a single signature.
With the Schnorr signature, we create a signature \((R,s)\) for a hash of the message (\(M\)). 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 \cdot{G}\)
Next we select a random value (\(k\)) to get a signature value of \(R\):
\(R = k \cdot{G}\)
The value of \(s\) is then:
\(s= k - \text{Hash}(M,R)\cdot{x}\)
Our signature of \(M\) is \((s,R)\) and the public key is \(P\).
To check the signature we calculate
\(P \cdot \text{Hash}(M,R) + s \cdot{G}\)
This becomes \(x \cdot{G} \cdot \text{Hash}(M,R) + (k - \text{Hash}(M,R) \cdot{x})\cdot{G}\).
which is:
\(x \cdot{G} \cdot \text{Hash}(M,R) + k \cdot{G} - \text{Hash}(M,R) \cdot x \cdot G = k \cdot G\)
The value of \(k \cdot{G}\) is equal to \(R\), and so if the result is the same as \(R\), the signature checks out.
An outline of the Go code is [code]:
package main import ( "fmt" "flag" "go.dedis.ch/kyber/v3" "go.dedis.ch/kyber/v3/group/edwards25519" ) var curve = edwards25519.NewBlakeSHA256Ed25519() var sha256 = curve.Hash() type Signature struct { r kyber.Point s kyber.Scalar } func Hash(s string) kyber.Scalar { sha256.Reset() sha256.Write([]byte(s)) return curve.Scalar().SetBytes(sha256.Sum(nil)) } // m: Message // x: Private key func Sign(m string, x kyber.Scalar) Signature { // Get the base of the curve. g := curve.Point().Base() // Pick a random k from allowed set. k := curve.Scalar().Pick(curve.RandomStream()) // r = k * G (a.k.a the same operation as r = g^k) r := curve.Point().Mul(k, g) // Hash(m || r) e := Hash(m + r.String()) // s = k - e * x s := curve.Scalar().Sub(k, curve.Scalar().Mul(e, x)) return Signature{r: r, s: s} } // m: Message // S: Signature func PublicKey(m string, S Signature) kyber.Point { // Create a generator. g := curve.Point().Base() // e = Hash(m || r) e := Hash(m + S.r.String()) // y = (r - s * G) * (1 / e) y := curve.Point().Sub(S.r, curve.Point().Mul(S.s, g)) y = curve.Point().Mul(curve.Scalar().Div(curve.Scalar().One(), e), y) return y } // m: Message // s: Signature // y: Public key func Verify(m string, S Signature, y kyber.Point) bool { // Create a generator. g := curve.Point().Base() // e = Hash(m || r) e := Hash(m + S.r.String()) // Attempt to reconstruct 's * G' with a provided signature; s * G = r - e * y sGv := curve.Point().Sub(S.r, curve.Point().Mul(e, y)) // Construct the actual 's * G' sG := curve.Point().Mul(S.s, g) // Equality check; ensure signature and public key outputs to s * G. return sG.Equal(sGv) } func (S Signature) String() string { return fmt.Sprintf("(r=%s, s=%s)", S.r, S.s) } func main() { message := "abc" flag.Parse() // args := flag.Args() // message=args[0] privateKey := curve.Scalar().Pick(curve.RandomStream()) publicKey := curve.Point().Mul(privateKey, curve.Point().Base()) fmt.Printf("Message to sign: %s\n\n", message) fmt.Printf("Private key: %s\n", privateKey) fmt.Printf("Public key: %s\n\n", publicKey) signature := Sign(message, privateKey) fmt.Printf("Signature (r=%s, s=%s)\n\n", signature.r, signature.s) derivedPublicKey := PublicKey(message, signature) fmt.Printf("Derived public key: %s\n\n", derivedPublicKey) fmt.Printf("Checking keys %t\n", publicKey.Equal(derivedPublicKey)) fmt.Printf("Checking signature %t\n\n", Verify(message, signature, publicKey)) }
In this case we integrate cryptography libraries using the Import() statement. These are imported in the src folder using Git with:
go get gopkg.in\dedis\kyber.v2 go get github.com\dedis\fixbuf
The great advantage with Go is that it can be installed in most operating systems, and then can be compiled into an executable version [install]. We first create this code as file called "schnorr.go" and then compile with:
go build schnorr.go
In Microsoft Windows, this then creates an executable file named "schnorr.exe", and which can be run as a stand-alone program, and pass in an argument. A sample run is:
Message to sign: abc Private key: db9f72a4b7c6d76e480640dc9b40789f2ce1860700415c90178df4599c0a9006 Public key: 96f17aa85c9dc5a57ca3103d723990f775eb38a668afb2e43679efec7eca2080 Signature (r=2ae621dabf1c6dc83302c67e951e5da62ff073970f0ce37b531f55e319c56be5, s=6917994e914ff7f1f6fa29861749203f242eae832d1e24e2f13a3e16983dac02) Derived public key: 96f17aa85c9dc5a57ca3103d723990f775eb38a668afb2e43679efec7eca2080 Checking keys true Checking signature true
If we want to run without compiling, we can run:
go run schnorr.go