云社区 博客 博客详情

《区块链与金融大数据整合实战》 —3.6 基于椭圆的加密算法

华章计算机 发表于 2020-02-16 16:53:49 2020-02-16
0
0

【摘要】 本节书摘来自华章计算机《区块链与金融大数据整合实战》 一书中第3章,第3.6节,作者是王静逸 。

3.6  基于椭圆的加密算法

  在区块链的私钥加密算法中,最重要、运用最广泛的就是基于椭圆的对称加密算法。本节就来了解椭圆加密算法的原理和运用方法。

  椭圆加密算法(Elliptic Curve Cryptography,ECC)运用椭圆曲线的数学理论,实现了一种新的非对称加密算法。对比在3.1节中介绍的RSA算法,它具有以下两个优点:

* ECC的密钥长度可以更短;

* 安全系数更高,基于椭圆破解更加困难。160位的ECC相当于1024的RSA,对于2048位的RSA,只需要210位的ECC就可以做到相同加密难度。

  椭圆加密可以使用二元三阶方程来表示,具体如下:

y2=x3+ax+b

  a和b是常规系数,可以归纳方程的二维模型,如图3-14所示。

  椭圆运算有一些特别的运算规则,如下所示。

* 加法运算:在曲线上画一条直线,与椭圆交点为A、B两点,取交点关于X轴对称的点C,C点定义为A+B,椭圆加法就是A+B=C,如图3-15所示。

 image.png

图3-14  椭圆曲线方程二维图

 image.png

图3-15  椭圆方程加法法则C=A+B

* 二倍运算:在椭圆的A点切线上,与椭圆有一个交点,这个交点关于X轴的对称点为B,这个交点定义为A+A,值为2A,椭圆二倍运算为A+A=2A=B,如图3-16所示。

* 正负取反法则:A点关于x轴对称定义的点为-A,这就是椭圆的正负取反运算,如图3-17所示。

 image.png

图3-16  椭圆方程二倍法则A+A=2A=B

 image.png

图3-17  椭圆方程取反法则

* 无穷远法则:取A到-A间的直线,且该直线平行于y轴,则认为这条直线与椭圆相交于无限远的点,如图3-18所示。

 image.png

图3-18  椭圆方程无穷远法则

  基于椭圆曲线的加密形式,需要找到如RSA算法的因素分解和求离散的难题。通过椭圆上的G点和附加计算参数xG求x非常困难,这个就是椭圆加密的原理所在。具体如下:

  (1)设置私钥为k,公钥为K,二者之间的椭圆关系为:K=kG,G表示椭圆的G点。

  (2)对公钥进行加密,得到一个随机数r,消息M通过椭圆方程生成密文C,密文表示方法为点对,具体公式为:C={rG,M+rK},K是公钥。

  (3)对私钥进行解密,具体计算方式为M+rK-k(rG)=M+r(kG)-k(rG)=M。k和K为第(1)步和第(2)步中的私钥与公钥。

  椭圆曲线签名的算法为ECDSA,它的算法流程分为私钥签名和公钥验证签名。

  私钥签名具体流程如下:

  (1)设置私钥为k,公钥为K,二者之间的椭圆关系为K=kG,G表示G点。

  (2)获取随机数r,计算椭圆所在点rG(x,y)

  (3)计算签名公式s=(h+kx)/r,其中,r为随机数,M为消息,h为哈希,k为私钥。

  (4)将消息M、签名{rG,s}发送给使用对象。

  公钥验证签名具体流程如下:

  (1)接收到私钥传来的消息M,签名为{rG=(x,y),s}

  (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

  

  下面来看下以太坊中椭圆加密算法的实现,具体代码示例如下:

  

  //elliptic.go

  

  type Curve t 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)

  }

  

  以上代码中定义了椭圆的几个主要属性,以及本节提到的几个运算法则。具体的功能实现代码如下:

  

  //elliptic.go

  //曲线参数包含椭圆曲线的参数,并提供一个通用的非常数时间曲线的实现

  type CurveParams struct {

      P       *big.Int // the order of the underlying field

      N       *big.Int // the order of the base point

      B       *big.Int // the constant of the curve equation

      Gx, Gy  *big.Int // (x,y) of the base point

      BitSize int      // the size of the underlying field

      Name    string   // the canonical name of the curve

  }

  

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

      return curve

  }

  

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

      // y? = x? - 3x + b

      y2 := new(big.Int).Mul(y, y)

      y2.Mod(y2, curve.P)

  

      x3 := new(big.Int).Mul(x, x)

      x3.Mul(x3, x)

  

      threeX := new(big.Int).Lsh(x, 1)

      threeX.Add(threeX, x)

  

      x3.Sub(x3, threeX)

      x3.Add(x3, curve.B)

      x3.Mod(x3, curve.P)

  

      return x3.Cmp(y2) == 0

  }

  

  // zForAffine返回仿射点(x, y)的雅可比矩阵Z值

  // y = 0,假设它们表示无穷远处的点,因为(0,0)不在这里处理的任何曲线上

  func zForAffine(x, y *big.Int) *big.Int {

      z := new(big.Int)

      if x.Sign() != 0 || y.Sign() != 0 {

          z.SetInt64(1)

      }

      return z

  }

  

  // affineFromJacobian反转了雅可比矩阵变换。参见文件的顶部

  func (curve *CurveParams) affineFromJacobian(x, y, z *big.Int) (xOut, yOut

    *big.Int) {

      if z.Sign() == 0 {

          return new(big.Int), new(big.Int)

      }

  

      zinv := new(big.Int).ModInverse(z, curve.P)

      zinvsq := new(big.Int).Mul(zinv, zinv)

  

      xOut = new(big.Int).Mul(x, zinvsq)

      xOut.Mod(xOut, curve.P)

      zinvsq.Mul(zinvsq, zinv)

      yOut = new(big.Int).Mul(y, zinvsq)

      yOut.Mod(yOut, curve.P)

      return

  }

  

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

      z1 := zForAffine(x1, y1)

      z2 := zForAffine(x2, y2)

      return curve.affineFromJacobian(curve.addJacobian(x1,y1,z1,x2,y2,z2))

  }

  

  // 雅可比矩阵在雅可比矩阵坐标(x1, y1, z1)中取两个点

  // (x2, y2, z2)返回它们的和,也是雅可比矩阵形式

  func (curve *CurveParams) addJacobian(x1, y1, z1, x2, y2, z2 *big.Int)

    (*big.Int, *big.Int, *big.Int) {

      // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html

        #addition-add-2007-bl

      x3, y3, z3 := new(big.Int), new(big.Int), new(big.Int)

      if z1.Sign() == 0 {

          x3.Set(x2)

          y3.Set(y2)

          z3.Set(z2)

          return x3, y3, z3

      }

      if z2.Sign() == 0 {

          x3.Set(x1)

          y3.Set(y1)

          z3.Set(z1)

          return x3, y3, z3

      }

  

      z1z1 := new(big.Int).Mul(z1, z1)

      z1z1.Mod(z1z1, curve.P)

      z2z2 := new(big.Int).Mul(z2, z2)

      z2z2.Mod(z2z2, curve.P)

  

      u1 := new(big.Int).Mul(x1, z2z2)

      u1.Mod(u1, curve.P)

      u2 := new(big.Int).Mul(x2, z1z1)

      u2.Mod(u2, curve.P)

      h := new(big.Int).Sub(u2, u1)

      xEqual := h.Sign() == 0

      if h.Sign() == -1 {

          h.Add(h, curve.P)

      }

      i := new(big.Int).Lsh(h, 1)

      i.Mul(i, i)

      j := new(big.Int).Mul(h, i)

  

      s1 := new(big.Int).Mul(y1, z2)

      s1.Mul(s1, z2z2)

      s1.Mod(s1, curve.P)

      s2 := new(big.Int).Mul(y2, z1)

      s2.Mul(s2, z1z1)

      s2.Mod(s2, curve.P)

      r := new(big.Int).Sub(s2, s1)

      if r.Sign() == -1 {

          r.Add(r, curve.P)

      }

      yEqual := r.Sign() == 0

      if xEqual && yEqual {

          return curve.doubleJacobian(x1, y1, z1)

      }

      r.Lsh(r, 1)

      v := new(big.Int).Mul(u1, i)

  

      x3.Set(r)

      x3.Mul(x3, x3)

      x3.Sub(x3, j)

      x3.Sub(x3, v)

      x3.Sub(x3, v)

      x3.Mod(x3, curve.P)

  

      y3.Set(r)

      v.Sub(v, x3)

      y3.Mul(y3, v)

      s1.Mul(s1, j)

      s1.Lsh(s1, 1)

      y3.Sub(y3, s1)

      y3.Mod(y3, curve.P)

  

      z3.Add(z1, z2)

      z3.Mul(z3, z3)

      z3.Sub(z3, z1z1)

      z3.Sub(z3, z2z2)

      z3.Mul(z3, h)

      z3.Mod(z3, curve.P)

  

      return x3, y3, z3

  }

  

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

      z1 := zForAffine(x1, y1)

      return curve.affineFromJacobian(curve.doubleJacobian(x1, y1, z1))

  }

  

  //双雅可比矩阵在雅可比矩阵(x, y, z)中取一个点

  //返回它的double,也是雅可比矩阵形式

  func (curve *CurveParams) doubleJacobian(x, y, z *big.Int) (*big.Int,

    *big.Int, *big.Int) {

      // See http://hyperelliptic.org/EFD/g1p/auto-shortw-jacobian-3.html

        #doubling-dbl-2001-b

      delta := new(big.Int).Mul(z, z)

      delta.Mod(delta, curve.P)

      gamma := new(big.Int).Mul(y, y)

      gamma.Mod(gamma, curve.P)

      alpha := new(big.Int).Sub(x, delta)

      if alpha.Sign() == -1 {

          alpha.Add(alpha, curve.P)

      }

      alpha2 := new(big.Int).Add(x, delta)

      alpha.Mul(alpha, alpha2)

      alpha2.Set(alpha)

      alpha.Lsh(alpha, 1)

      alpha.Add(alpha, alpha2)

  

      beta := alpha2.Mul(x, gamma)

  

      x3 := new(big.Int).Mul(alpha, alpha)

      beta8 := new(big.Int).Lsh(beta, 3)

      x3.Sub(x3, beta8)

      for x3.Sign() == -1 {

          x3.Add(x3, curve.P)

      }

      x3.Mod(x3, curve.P)

  

      z3 := new(big.Int).Add(y, z)

      z3.Mul(z3, z3)

      z3.Sub(z3, gamma)

      if z3.Sign() == -1 {

          z3.Add(z3, curve.P)

      }

      z3.Sub(z3, delta)

      if z3.Sign() == -1 {

          z3.Add(z3, curve.P)

      }

      z3.Mod(z3, curve.P)

  

      beta.Lsh(beta, 2)

      beta.Sub(beta, x3)

      if beta.Sign() == -1 {

          beta.Add(beta, curve.P)

      }

      y3 := alpha.Mul(alpha, beta)

  

      gamma.Mul(gamma, gamma)

      gamma.Lsh(gamma, 3)

      gamma.Mod(gamma, curve.P)

  

      y3.Sub(y3, gamma)

      if y3.Sign() == -1 {

          y3.Add(y3, curve.P)

      }

      y3.Mod(y3, curve.P)

  

      return x3, y3, z3

  }

  

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

    *big.Int) {

      Bz := new(big.Int).SetInt64(1)

      x, y, z := new(big.Int), new(big.Int), new(big.Int)

  

      for _, byte := range k {

          for bitNum := 0; bitNum < 8; bitNum++ {

              x, y, z = curve.doubleJacobian(x, y, z)

              if byte&0x80 == 0x80 {

                  x, y, z = curve.addJacobian(Bx, By, Bz, x, y, z)

              }

              byte <<= 1

          }

      }

  

      return curve.affineFromJacobian(x, y, z)

  }

  

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

      return curve.ScalarMult(curve.Gx, curve.Gy, k)

  }

  

  var mask = []byte{0xff, 0x1, 0x3, 0x7, 0xf, 0x1f, 0x3f, 0x7f}

  

  // GenerateKey 返回一个公钥/私钥对

  // 私钥是使用给定的读取器生成的,该读取器必须返回随机数据

  func GenerateKey(curve Curve, rand io.Reader) (priv []byte, x, y *big.Int,

    err error) {

      N := curve.Params().N

      bitSize := N.BitLen()

      byteLen := (bitSize + 7) >> 3

      priv = make([]byte, byteLen)

  

      for x == nil {

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

          if err != nil {

              return

          }

          // 我们必须屏蔽掉任何多余的位,以防底层字段不是一个完整的字节数

          priv[0] &= mask[bitSize%8]

          // 这是因为,在测试中rand会返回所有的0,而我们不会想要得到无穷远处的点,

            然后无限循环

          priv[1] ^= 0x42

  

          //如果标量超出了范围,则抽样另一个随机数

          if new(big.Int).SetBytes(priv).Cmp(N) >= 0 {

              continue

          }

  

          x, y = curve.ScalarBaseMult(priv)

      }

      return

  }

  

  // Marshal将一个点转换为ANSI X9.62指定的形式

  func Marshal(curve Curve, x, y *big.Int) []byte {

      byteLen := (curve.Params().BitSize + 7) >> 3

  

      ret := make([]byte, 1+2*byteLen)

      ret[0] = 4 // 未压缩的点

  

      xBytes := x.Bytes()

      copy(ret[1+byteLen-len(xBytes):], xBytes)

      yBytes := y.Bytes()

      copy(ret[1+2*byteLen-len(yBytes):], yBytes)

      return ret

  }

  

  // 仅编组将按编组序列化的点转换为x、y对

  // 如果点不在曲线上,则是一个错误。出错时,x=nil

  func Unmarshal(curve Curve, data []byte) (x, y *big.Int) {

      byteLen := (curve.Params().BitSize + 7) >> 3

      if len(data) != 1+2*byteLen {

          return

      }

      if data[0] != 4 { //未压缩的形式

          return

      }

      x = new(big.Int).SetBytes(data[1 : 1+byteLen])

      y = new(big.Int).SetBytes(data[1+byteLen:])

      if !curve.IsOnCurve(x, y) {

          x, y = nil, nil

      }

      return

  }

  

  var initonce sync.Once

  var p384 *CurveParams

  var p521 *CurveParams

  

  func initAll() {

      initP224()

      initP256()

      initP384()

      initP521()

  }

  

  func initP384() {

      // See FIPS 186-3, section D.2.4

      p384 = &CurveParams{Name: "P-384"}

      p384.P, _ = new(big.Int).SetString("394020061963944792122790401001436

        1380507973927046544666794829340424572177149687032904726608825893800

        1861606973112319", 10)

      p384.N, _ = new(big.Int).SetString("394020061963944792122790401001436

        138050797392704654466679469052796276593991132635693989563081522949

        13554433653942643", 10)

      p384.B, _ = new(big.Int).SetString("b3312fa7e23ee7e4988e056be3f82

        d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef",16)

      p384.Gx, _ = new(big.Int).SetString("aa87ca22be8b05378eb1c71ef320ad

        746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7",16)

      p384.Gy, _ = new(big.Int).SetString("3617de4a96262c6f5d9e98bf9292dc29

        f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f",16)

      p384.BitSize = 384

  }

  

  func initP521() {

      // See FIPS 186-3, section D.2.5

      p521 = &CurveParams{Name: "P-521"}

      p521.P, _ = new(big.Int).SetString("686479766013060971498190079908

        1393217269435300143305409394463459185543183397656052122559640661454

        554977296311391480858037121987999716643812574028291115057151", 10)

      p521.N, _ = new(big.Int).SetString("686479766013060971498190079908

        139321726943530014330540939446345918554318339765539424505774633321

        7197532963996371363321113864768612440380340372808892707005449", 10)

      p521.B, _ = new(big.Int).SetString("051953eb9618e1c9a1f929a21a0b68540

        eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573

        df883d2c34f1ef451fd46b503f00", 16)

      p521.Gx, _ = new(big.Int).SetString("c6858e06b70404e9cd9e3ecb662395

        b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de

        3348b3c1856a429bf97e7e31c2e5bd66", 16)

      p521.Gy, _ = new(big.Int).SetString("11839296a789a3bc0045c8a5fb42

        c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad

        0761353c7086a272c24088be94769fd16650", 16)

      p521.BitSize = 521

  }

  

  //加密操作是使用时间算法实现的

  func P256() Curve {

      initonce.Do(initAll)

      return p256

  }

  

  //加密操作不使用固定时间算法

  func P384() Curve {

      initonce.Do(initAll)

      return p384

  }

  

  //加密操作不使用固定时间算法

  func P521() Curve {

      initonce.Do(initAll)

      return p521

  }

  

  在以太坊中,大量使用椭圆函数进行加密、解密、签名等。以太坊中,每一次的交易都需要用户进行签名才能打包到块中进行共识存储。签名的实现代码具体如下:

  

  //ecdsa.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)

          s.Mul(s, kInv)

          s.Mod(s, N)

          if s.Sign() != 0 {

              break

          }

  

          //签名为{r, s},即{kG, (e+DkG)/k}

      }

  

      return

  }

  

  //验证签名

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

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

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

  

      if r.Sign() <= 0 || s.Sign() <= 0 {

          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

  }


登录后可下载附件,请登录或者注册

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:huaweicloud.bbs@huawei.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
评论文章 //点赞 收藏 0
点赞
分享文章到微博
分享文章到朋友圈

上一篇:《区块链与金融大数据整合实战》 —3.5 公钥与私钥

下一篇:《区块链与金融大数据整合实战》 —3.7 区块链与密码学的“前世今生”

评论 (0)


登录后可评论,请 登录注册

评论