go实现schnorr签名与验证

schnorr签名用到了椭圆曲线，使用一个椭圆曲线上的点$R$和一个常量$pk$作为私钥，那么公钥为$P=pk*G$

$G$是椭圆曲线的基点。知道$P$和$G$，是无法推出私钥的。签名时，随机选择一个$k$，计算$R=k*G$。

然后使用哈希计算要签名的消息以及$R$的哈希，然后再计算$s=k+hash(R,m)*pk$，发送$(R,s)$作为签名。验证时，计算$s*G=R+hash(R,m)*P$，看左右两边的点横坐标是否相同。因为$G，R，P$都是椭圆曲线上的点，所以需要调用椭圆曲线的加和乘，计算结果也在曲线上，所以也不用考虑取模了。

这里理论上来讲发过去的$(R,s)$应该要是512位的，但是这里的实现因为$R$有$x,y$两个坐标，各256位，还要marshal，变成了65字节，所以不能算作严谨的版本。理论上来说可以只发$x$，验证方可以通过$x$算出$y$来，但是不知道如何实现，只好这样折衷一下多发些字节过去。

package main

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

func main(){
	privkey,pubkey :=keyGeneration()
	msg:=sign([]byte("CSCI468/968 Advanced Network Security, Spring 2020"),privkey)
	verify(msg,pubkey,[]byte("CSCI468/968 Advanced Network Security, Spring 2020"))
}


func sign(msg []byte, privkey ecdsa.PrivateKey) []byte {
	//产生随机数
	k, err := randFieldElement(privkey.Curve, rand.Reader)
	if err!=nil{
		panic(err)
	}
	N:=privkey.Params().N

	
	rx,ry:=privkey.Curve.ScalarBaseMult(k.Bytes())//r=k*g
	r:=elliptic.Marshal(privkey.Curve,rx,ry)//椭圆曲线上的点 65byte

	//计算message和hash c
	hash:=sha256.New()
	hash.Write(msg)
	hash.Write(r)
	//hash结果转int用于计算
	c:=hashToInt(hash.Sum(nil),privkey.Curve)//32bytes
	//a*c
	ac:=new(big.Int)
	ac.Mul(privkey.D,c)//64bytes
	//返回值
	s:=new(big.Int)
	s.Add(k,ac)
	s.Mod(s,N)//32bytes

	var res bytes.Buffer
	res.Write(r)
	res.Write(s.Bytes())
	return res.Bytes()//64bytes
}


//check
func verify(rs []byte, pubkey ecdsa.PublicKey,msg[]byte) {
	r := rs[:65] //r
	rx,ry:=elliptic.Unmarshal(pubkey.Curve,r)

	s := rs[65:] //s
	leftx,_:=pubkey.ScalarBaseMult(s)

	hash := sha256.New()
	hash.Write(msg)
	hash.Write(r)
	c := hashToInt(hash.Sum(nil), pubkey.Curve)
	
	cpx,cpy:=pubkey.ScalarMult(pubkey.X,pubkey.Y,c.Bytes())

	rightx,_:=pubkey.Curve.Add(rx,ry,cpx,cpy)

	if leftx.Cmp(rightx)==0 {
		fmt.Println("verify passed")
	}else{
		fmt.Println("verify failed")
	}

}


func keyGeneration()(ecdsa.PrivateKey, ecdsa.PublicKey){
	privKey ,err :=ecdsa.GenerateKey(elliptic.P256(),rand.Reader)
	if err != nil {
		panic(err)
	}
	pubKey :=privKey.PublicKey
	return *privKey,pubKey
}


var one = new(big.Int).SetInt64(1)

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
	}

	k = new(big.Int).SetBytes(b)
	n := new(big.Int).Sub(params.N, one)
	k.Mod(k, n)
	k.Add(k, one)
	return
}

func hashToInt(hash []byte, c elliptic.Curve) *big.Int {
	orderBits := c.Params().N.BitLen()
	orderBytes := (orderBits + 7) / 8
	if len(hash) > orderBytes {
		hash = hash[:orderBytes]
	}

	ret := new(big.Int).SetBytes(hash)
	excess := len(hash)*8 - orderBits
	if excess > 0 {
		ret.Rsh(ret, uint(excess))
	}
	return ret
}