兄弟连区块链教程区块链信息安全3椭圆曲线加解密及签名算法二

兄弟连区块链教程区块链信息安全3椭圆曲线加解密及签名算法的技术原理二。

# 椭圆曲线加解密及签名算法的技术原理及其Go语言实现

### 椭圆曲线加解密算法原理

建立基于椭圆曲线的加密机制,需要找到类似RSA质因子分解或其他求离散对数这样的难题。

而椭圆曲线上的已知G和xG求x,是非常困难的,此即为椭圆曲线上的的离散对数问题。

此处x即为私钥,xG即为公钥。

椭圆曲线加密算法原理如下:

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

公钥加密:

选择随机数r,将消息M生成密文C,该密文是一个点对,即:

C = ,其中K为公钥

私钥解密:

M + rK - k(rG) = M + r(kG) - k(rG) = M

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

### 椭圆曲线签名算法原理

椭圆曲线签名算法,即ECDSA。

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

私钥签名:

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

* 2、根据随机数r、消息M的哈希h、私钥k,计算s = (h + kx)/r。

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

公钥验证签名:

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

* 2、根据消息求哈希h。

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

原理如下:

hG/s + xK/s = hG/s + x(kG)/s = (h+xk)G/s

= r(h+xk)G / (h+kx) = rG

### Go语言中椭圆曲线的实现

椭圆曲线的接口定义:

```go

type Curve interface {

//获取椭圆曲线参数

Params() *CurveParams

//是否在曲线上

IsOnCurve(x, y *big.Int) bool

//加法

Add(x1, y1, x2, y2 *big.Int) (x, y *big.Int)

//二倍运算

Double(x1, y1 *big.Int) (x, y *big.Int)

//k*(Bx,By)

ScalarMult(x1, y1 *big.Int, k []byte) (x, y *big.Int)

//k*G, G为基点

ScalarBaseMult(k []byte) (x, y *big.Int)

}

//代码位置src/crypto/elliptic/elliptic.go

```

椭圆曲线的接口实现:

```go

type CurveParams struct {

//有限域GF(p)中质数p

P *big.Int

//G点的阶

//如果存在最小正整数n,使得nG=O∞,则n为G点的阶

N *big.Int

//椭圆曲线方程y²= x³-3x+b中常数b

B *big.Int

//G点(x,y)

Gx, Gy *big.Int

//密钥长度

BitSize int

//椭圆曲线名称

Name string

}

func (curve *CurveParams) Params() *CurveParams {

//获取椭圆曲线参数,即curve,代码略

}

func (curve *CurveParams) IsOnCurve(x, y *big.Int) bool {

//是否在曲线y²=x³-3x+b上,代码略

}

func (curve *CurveParams) Add(x1, y1, x2, y2 *big.Int) (*big.Int, *big.Int) {

//加法运算,代码略

}

func (curve *CurveParams) Double(x1, y1 *big.Int) (*big.Int, *big.Int) {

//二倍运算,代码略

}

func (curve *CurveParams) ScalarMult(Bx, By *big.Int, k []byte) (*big.Int, *big.Int) {

//k*(Bx,By),代码略

}

func (curve *CurveParams) ScalarBaseMult(k []byte) (*big.Int, *big.Int) {

//k*G, G为基点,代码略

}

//代码位置src/crypto/elliptic/elliptic.go

```

### Go语言中椭圆曲线签名的实现

Go标准库中实现的椭圆曲线签名原理,与上述理论中基本接近。

相关证明方法已注释在代码中。

```go

//公钥

type PublicKey struct {

elliptic.Curve

X, Y *big.Int

}

//私钥

type PrivateKey struct {

PublicKey //嵌入公钥

D *big.Int //私钥

}

func Sign(rand io.Reader, priv *PrivateKey, hash []byte) (r, s *big.Int, err error) {

entropylen := (priv.Curve.Params().BitSize + 7) / 16

if entropylen > 32 {

entropylen = 32

}

entropy := make([]byte, entropylen)

_, err = io.ReadFull(rand, entropy)

if err != nil {

return

}

md := sha512.New()

md.Write(priv.D.Bytes()) //私钥

md.Write(entropy)

md.Write(hash)

key := md.Sum(nil)[:32]

block, err := aes.NewCipher(key)

if err != nil {

return nil, nil, err

}

csprng := cipher.StreamReader{

R: zeroReader,

S: cipher.NewCTR(block, []byte(aesIV)),

}

c := priv.PublicKey.Curve //椭圆曲线

N := c.Params().N //G点的阶

if N.Sign() == 0 {

return nil, nil, errZeroParam

}

var k, kInv *big.Int

for {

for {

//取随机数k

k, err = randFieldElement(c, csprng)

if err != nil {

r = nil

return

}

//求k在有限域GF(P)的逆,即1/k

if in, ok := priv.Curve.(invertible); ok {

kInv = in.Inverse(k)

} else {

kInv = fermatInverse(k, N) // N != 0

}

//求r = kG

r, _ = priv.Curve.ScalarBaseMult(k.Bytes())

r.Mod(r, N)

if r.Sign() != 0 {

break

}

}

e := hashToInt(hash, c) //e即哈希

s = new(big.Int).Mul(priv.D, r) //Dr,即DkG

s.Add(s, e) //e+DkG

s.Mul(s, kInv) //(e+DkG)/k

s.Mod(s, N) // N != 0

if s.Sign() != 0 {

break

}

//签名为,即

}

return

}

//验证签名

func Verify(pub *PublicKey, hash []byte, r, s *big.Int) bool {

c := pub.Curve //椭圆曲线

N := c.Params().N //G点的阶

if r.Sign()

return false

}

if r.Cmp(N) >= 0 || s.Cmp(N) >= 0 {

return false

}

e := hashToInt(hash, c) //e即哈希

var w *big.Int

//求s在有限域GF(P)的逆,即1/s

if in, ok := c.(invertible); ok {

w = in.Inverse(s)

} else {

w = new(big.Int).ModInverse(s, N)

}

u1 := e.Mul(e, w) //即e/s

u1.Mod(u1, N)

u2 := w.Mul(r, w) //即r/s

u2.Mod(u2, N)

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()) //即eG/s

x2, y2 := c.ScalarMult(pub.X, pub.Y, u2.Bytes()) //即DGr/s

//即eG/s + DGr/s = (e + Dr)G/s

//= (e + Dr)kG / (e + DkG) = (e + Dr)r / (e + Dr) = r

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

}

//代码位置src/crypto/ecdsa/ecdsa.go

```

### 后记

椭圆曲线数字签名算法,因其高安全性,目前已广泛应用在比特币、以太坊、超级账本等区块链项目中。

感谢关注兄弟连区块链教程分享!

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181109A0HESB00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券