Schnorr签名的Go实现

2020-03-18
#密码学

算法解析

1
2
3
4
5
6
7
8
# Sign (x)
generate a, t = a·G
c = H(m,t)
z = a+xc
sig = (t,z)

# Verify (Y = x·G)
accept if z·G = t+c·Y

Go实现

这里用的是 P256 曲线与 SHA256 哈希函数，GenerateKey()方法参考了ECDSA。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/* Schnorr Signature in Golang 
 * Xiaolin Zhang, 2020-03-26
 */ 
package schnorr

import (
    "crypto/elliptic"
    "crypto/rand"
    "crypto/sha256"
    "fmt"
    "io"
    "math/big"
)

type PublicKey struct {
    elliptic.Curve
    X, Y *big.Int
}
type PrivateKey struct {
    PublicKey
    D *big.Int
} 
type Signature struct {
    t PublicKey // t is a point
    z *big.Int
} 

func main () {
    msg := "You know nothing, Jon Snow"
    sk,_ := GenerateKey(elliptic.P256(),rand.Reader)

    sig,_ := Sign(rand.Reader,sk,[]byte(msg))
    result := Verify(sig, sk.PublicKey, []byte(msg))
	
    fmt.Println("     Secret Key: ", sk.D)
    fmt.Println("Signing Message: ", msg)
    fmt.Println(" Signing Result: ", result) 
}

func GenerateKey(c elliptic.Curve, rand io.Reader) (*PrivateKey, error) {
    k, err := randFieldElement(c, rand)
    if err != nil {
        return nil, err
    }
    priv := new(PrivateKey)
    priv.PublicKey.Curve = c
    priv.D = k
    priv.PublicKey.X, priv.PublicKey.Y = c.ScalarBaseMult(k.Bytes())
    return priv, nil
}

// returns a random element of the field underlying the given
func randFieldElement(c elliptic.Curve, rand io.Reader) (k *big.Int, err error) {
    params := c.Params()
    b := make([]byte, params.BitSize/8+8)
    _, err = io.ReadFull(rand, b)
    if err != nil {
        return
    }
    one := new(big.Int).SetInt64(1)
    k = new(big.Int).SetBytes(b)
    n := new(big.Int).Sub(params.N, one)
    k.Mod(k, n)
    k.Add(k, one)
    return
}

func Sign(rand io.Reader, priv *PrivateKey, msg []byte) (sig Signature, err error) {
    c := priv.PublicKey.Curve
    a,_ := GenerateKey(c,rand)
    sig.t = a.PublicKey
    // c = Hash(msg||t)
    concatMsg := append(msg, sig.t.X.Bytes()...)
    hash := sha256.Sum256(concatMsg)
    hashInt := new(big.Int).SetBytes(hash[:])
    // z = a+sk*c
    z := hashInt.Mul(priv.D, hashInt)
    sig.z = z.Add(a.D,z)
    return
}

func Verify(sig Signature1, pk PublicKey, msg []byte) string {
    c := pk.Curve
    // c = Hash(msg||t)
    concatMsg := append(msg, sig.t.X.Bytes()...)
    hash := sha256.Sum256(concatMsg)
    // z*G = t+c*pk
    left,_:= c.ScalarBaseMult(sig.z.Bytes())
    ux,uy := c.ScalarMult(pk.X, pk.Y, hash[:])
    right,_ := c.Add(sig.t.X,sig.t.Y,ux,uy)
    // 0:equal, 1:>, -1:<1
    if left.Cmp(right)==0 {
        return "Accepted"
    }
    return "Denied"
}

签名结果