In our Horribly Flawed World of PKI … Go Schnorr

A demo of the method is here.

We live in a world of PKI, and where we distribute public keys through digital certificates. It is a horribly jumbled world, which few people understand. If we were to start again, we would not implement PKI. The world of Bitcoin and blockchain does it much better, and where I can sign something with my private key, and then the signature can be used to derive my public key back again. In this way, I don’t have to distribute my public key, you can find it out from my signature. We can also verify that I am the signer of my message, without needing to put my public key in a trusted certificate. And so we turn to Schnorr signatures, and their implementation in the Go programming language.

Schnorr signatures

With the Schnorr signature, we create a signature (R,s) for a hash of the message (MM). 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⋅G

Next we select a random value (k) to get a signature value of R:

R=k⋅G

The value of s is then:

s=k−Hash(M,R)⋅x

Our signature of M is (s,R) and the public key is P.

To check the signature we calculate

P⋅Hash(M,R)+s⋅G

This becomes x⋅G⋅Hash(M,R)+(k−Hash(M,R)⋅x)⋅G

which is:

x⋅G⋅Hash(M,R)+k⋅G−Hash(M,R)⋅x⋅G=k⋅G

The value of k⋅G is equal to R, and so if the result is the same as R, the signature checks out.

A sample run with the message of “Hello” is (and where “BN” is “Big Number”) [here]:

Message:Hello
Private Key: dce71358bf6d57dffaf8ac422ea972dca65badd2ce21b585803ea3075b7de388
Public key: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27
Signature [s]: BN: 18573f5212373b51022b00cbe12276b8099a351526b3384ccd1f02ad71761ff1
Signature [r]: BN: 3d96504afbe3beec97a753c38d614ec5fa68cf8219df36d7cce891319058d5db
Public key recover: Buffer 03 9d e0 bd 0a e1 b2 1c 64 c7 35 12 31 1c d5 fd 35 42 f1 0a f5 02 9c c7 eb 81 e5 fb cc c8 51 18 27
Signature verified: true

In this case we have 256-bit private key (dce7 … 388), and produce a 512-bit public key (03 96e … 827) — the “03” part identifies that we are using a Bitcoin public key. Thus, if we know the message — and which will be stored on the blockchain in the case of Bitcoin — and the key, we can see that we can recover the public key from the signature.

One of the great advantages of the Schnorr signature is that we can sign more than one message.

Coding with Go

The Go programming language gives us the power of C++, without the complexity. An outline of the Go code to implement the Schnorr signature is [code]:

package main
import (
    "fmt"
    "flag"
    "gopkg.in/dedis/kyber.v2"
    "gopkg.in/dedis/kyber.v2/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

In this case we generate a private key, and then generate the associated public key. Next we calculate the (r,s) signature for the message. After this we can then derive the public key back from the signature. In the end we can check that the keys are the same, and that the signature checks-out.

The demo is here:

Golang Schnorr

Conclusions

Few things are more perfect in the form in computer security than the Schnorr signature. In current digital world is flawed, and we need to build a new one. The Schnorr signature provides us with a way to put the citizen at the core of the Internet.

Oh, how I love the beauty of Elliptic Curve Cryptography!