椭圆曲线加解密及验签原理 Golang 实现

椭圆曲线

$$ y^2=x^3+ax+b $$

运算规则

在椭圆曲线上取两点A，B并作过这两点直线交椭圆曲线为点 C’ 再过 C’ 作垂线交椭圆曲线为点 C 则定义

C=A+B

特殊的若A，B两点重合，则作A点切线，此时定义

C=2A

若取B点为A关于x轴对称的点，并且定义为-A，则此时该直线交曲线为无穷原点处

所以已知x，求xA点并不困难。反之，已知xA点，求x则非常困难。此即为椭圆曲线加密算法背后的数学原理。

椭圆曲线加解密算法原理

椭圆曲线要形成一条光滑的曲线，要求x,y取值均为实数，即实数域上的椭圆曲线。但椭圆曲线加密算法，并非使用实数域，而是使用有限域。按数论定义，有限域GF(p)指给定某个质数p，由0、1、2……p-1共p个元素组成的整数集合中定义的加减乘除运算。

关于有限域 https://baike.baidu.com/item/%E6%9C%89%E9%99%90%E5%9F%9F/4273049?fr=aladdin

定义点 $P(x_p,y_p)\ Q(x_q,y_q)\qquad R(x_r,y_r)=P+Q$ 此时

$\lambda=\frac{y_q-y_p}{x_q-x_p}\ mod\ p \ (p \neq q)$

$x_r=(\lambda ^2 – x_p – x_q)\ mod\ p$

$y_r=(\lambda (x_p – x_r) – y_p )\ mod\ p$

椭圆曲线签名算法原理

设私钥、公钥分别为d、Q，即Q = dG，其中G为G点。

私钥签名：

1、选择随机数r，计算点rG(x, y)。

2、根据随机数r、消息M的哈希h、私钥d，计算s = (h + dx)/r。

3、将消息M、rG和签名s发给接收方。

公钥验证签名：

1、接收方收到消息M、以及签名。

2、根据消息求哈希h。

3、使用发送方公钥K计算：hG/s + xQ/s，并与rG比较，如相等即验签成功。

$ Q=dG \quad s=(h+dx)/r \\ hG/s+xQ/s=\frac{hGr+xQr}{h+dx}=\frac{r(h+xd)G}{h+dx}=rG $

设私钥、公钥分别为k、K，即K = kG，其中G为G点。

公钥加密：

将明文编码到Ep（a,b）上一点M，并产生一个随机数r

计算点C1=M+rK，C2=rG

私钥解密：

C1-kC2=M + rK – k(rG) = M + r(kG) – k(rG) = M

其中k、K分别为私钥、公钥。

Golang实现

Golang 官方库中的函数对应着上面 s = (h + dx)/r

// 生成签名
func signGeneric(priv *PrivateKey, csprng *cipher.StreamReader, c elliptic.Curve, hash []byte) (r, s *big.Int, err error) {
	// SEC 1, Version 2.0, Section 4.1.3
	N := c.Params().N
	if N.Sign() == 0 {
		return nil, nil, errZeroParam
	}
	var k, kInv *big.Int
	for {
		for {
			k, err = randFieldElement(c, *csprng) // 生成随机k
			if err != nil {
				r = nil
				return
			}

			if in, ok := priv.Curve.(invertible); ok {
				kInv = in.Inverse(k)
			} else {
				kInv = fermatInverse(k, N) // N != 0
			}

			r, _ = priv.Curve.ScalarBaseMult(k.Bytes()) // 计算 r=k*G
			r.Mod(r, N)
			if r.Sign() != 0 {
				break
			}
		}

		e := hashToInt(hash, c)
		s = new(big.Int).Mul(priv.D, r) // s=d*k*G
		s.Add(s, e)       // s=d*k*G+e
		s.Mul(s, kInv)    // s=(d*k*G+e)/r
		s.Mod(s, N) // N != 0 // s=(d*k*G+e)/r mod N
		if s.Sign() != 0 {
			break
		}
	}

	return
}

// 验证签名
func verifyGeneric(pub *PublicKey, c elliptic.Curve, hash []byte, r, s *big.Int) bool {
	// SEC 1, Version 2.0, Section 4.1.4
	e := hashToInt(hash, c)
	var w *big.Int
	N := c.Params().N
	if in, ok := c.(invertible); ok {
		w = in.Inverse(s)
	} else {
		w = new(big.Int).ModInverse(s, N) // w=1/s mod N
	}

	u1 := e.Mul(e, w)
	u1.Mod(u1, N) // u1 = e/s mod N
	u2 := w.Mul(r, w) 
	u2.Mod(u2, N) // u2 = r/s mod N

	// Check if implements S1*g + S2*p
	var x, y *big.Int
	if opt, ok := c.(combinedMult); ok {
		x, y = opt.CombinedMult(pub.X, pub.Y, u1.Bytes(), u2.Bytes())
	} else {
		x1, y1 := c.ScalarBaseMult(u1.Bytes())
		x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes())
		x, y = c.Add(x1, y1, x2, y2)
	}

	if x.Sign() == 0 && y.Sign() == 0 {
		return false
	}
	x.Mod(x, N)
	return x.Cmp(r) == 0
}

签名验签例子

package main

import (
	"crypto/ecdsa"
	"crypto/elliptic"
	"crypto/md5"
	"crypto/rand"
	"fmt"
	"hash"
	"io"
	"math/big"
	"os"
)

func main() {
	pubkeyCurve := elliptic.P256()                                 // 定义椭圆曲线 y² = x³ + 7
	privatekey, err := ecdsa.GenerateKey(pubkeyCurve, rand.Reader) // 定义私钥 k

	if err != nil {
		fmt.Println(err)
		os.Exit(1)
	}

	var pubkey ecdsa.PublicKey
	pubkey = privatekey.PublicKey // 公钥K K=kG

	fmt.Println("Private Key :")
	fmt.Printf("%x \n", privatekey)

	fmt.Println("Public Key :")
	fmt.Printf("%x \n", pubkey)

	// hash 签名内容 M
	var h hash.Hash
	h = md5.New()
	r := big.NewInt(0)
	s := big.NewInt(0)

	io.WriteString(h, "Hello World!")
	signhash := h.Sum(nil)
	// 私钥签名
	r, s, serr := ecdsa.Sign(rand.Reader, privatekey, signhash)
	if serr != nil {
		fmt.Println(err)
		os.Exit(1)
	}

	signature := r.Bytes()
	signature = append(signature, s.Bytes()...)

	fmt.Printf("Signature : %x\n", signature)

	// 公钥验证签名
	verifystatus := ecdsa.Verify(&pubkey, signhash, r, s)
	fmt.Println(verifystatus) // should be true

}