椭圆曲线
$$ 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
}
