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

椭圆曲线

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

运算规则

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

C=A+B

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

C=2A

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

D=3A

所以已知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

}
广告 广告位招租
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
小黄脸
上一篇
下一篇