src/cypherpunks.ru/gogost/gost3410/curve.go

   1 // GoGOST -- Pure Go GOST cryptographic functions library
   2 // Copyright (C) 2015-2019 Sergey Matveev <stargrave@stargrave.org>
   3 //
   4 // This program is free software: you can redistribute it and/or modify
   5 // it under the terms of the GNU General Public License as published by
   6 // the Free Software Foundation, either version 3 of the License, or
   7 // (at your option) any later version.
   8 //
   9 // This program is distributed in the hope that it will be useful,
  10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 // GNU General Public License for more details.
  13 //
  14 // You should have received a copy of the GNU General Public License
  15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16
  17 package gost3410
  18
  19 import (
  20         "errors"
  21         "math/big"
  22 )
  23
  24 var (
  25         zero    *big.Int = big.NewInt(0)
  26         bigInt1 *big.Int = big.NewInt(1)
  27         bigInt2 *big.Int = big.NewInt(2)
  28         bigInt3 *big.Int = big.NewInt(3)
  29 )
  30
  31 type Curve struct {
  32         P *big.Int // Characteristic of the underlying prime field
  33         Q *big.Int // Elliptic curve subgroup order
  34
  35         // Equation coefficients of the elliptic curve in canonical form
  36         A *big.Int
  37         B *big.Int
  38
  39         // Basic point X and Y coordinates
  40         X *big.Int
  41         Y *big.Int
  42
  43         // Temporary variable for the add method
  44         t  *big.Int
  45         tx *big.Int
  46         ty *big.Int
  47 }
  48
  49 func NewCurve(p, q, a, b, bx, by []byte) (*Curve, error) {
  50         c := Curve{
  51                 P:  bytes2big(p[:]),
  52                 Q:  bytes2big(q[:]),
  53                 A:  bytes2big(a[:]),
  54                 B:  bytes2big(b[:]),
  55                 Bx: bytes2big(bx[:]),
  56                 By: bytes2big(by[:]),
  57                 t:  big.NewInt(0),
  58                 tx: big.NewInt(0),
  59                 ty: big.NewInt(0),
  60         }
  61         r1 := big.NewInt(0)
  62         r2 := big.NewInt(0)
  63         r1.Mul(c.Y, c.Y)
  64         r1.Mod(r1, c.P)
  65         r2.Mul(c.X, c.X)
  66         r2.Add(r2, c.A)
  67         r2.Mul(r2, c.X)
  68         r2.Add(r2, c.B)
  69         r2.Mod(r2, c.P)
  70         c.pos(r2)
  71         if r1.Cmp(r2) != 0 {
  72                 return nil, errors.New("Invalid curve parameters")
  73         }
  74         }
  75         return &c, nil
  76 }
  77
  78 func (c *Curve) pos(v *big.Int) {
  79         if v.Cmp(zero) < 0 {
  80                 v.Add(v, c.P)
  81         }
  82 }
  83
  84 func (c *Curve) add(p1x, p1y, p2x, p2y *big.Int) {
  85         if p1x.Cmp(p2x) == 0 && p1y.Cmp(p2y) == 0 {
  86                 // double
  87                 c.t.Mul(p1x, p1x)
  88                 c.t.Mul(c.t, bigInt3)
  89                 c.t.Add(c.t, c.A)
  90                 c.tx.Mul(bigInt2, p1y)
  91                 c.tx.ModInverse(c.tx, c.P)
  92                 c.t.Mul(c.t, c.tx)
  93                 c.t.Mod(c.t, c.P)
  94         } else {
  95                 c.tx.Sub(p2x, p1x)
  96                 c.tx.Mod(c.tx, c.P)
  97                 c.pos(c.tx)
  98                 c.ty.Sub(p2y, p1y)
  99                 c.ty.Mod(c.ty, c.P)
 100                 c.pos(c.ty)
 101                 c.t.ModInverse(c.tx, c.P)
 102                 c.t.Mul(c.t, c.ty)
 103                 c.t.Mod(c.t, c.P)
 104         }
 105         c.tx.Mul(c.t, c.t)
 106         c.tx.Sub(c.tx, p1x)
 107         c.tx.Sub(c.tx, p2x)
 108         c.tx.Mod(c.tx, c.P)
 109         c.pos(c.tx)
 110         c.ty.Sub(p1x, c.tx)
 111         c.ty.Mul(c.ty, c.t)
 112         c.ty.Sub(c.ty, p1y)
 113         c.ty.Mod(c.ty, c.P)
 114         c.pos(c.ty)
 115         p1x.Set(c.tx)
 116         p1y.Set(c.ty)
 117 }
 118
 119 func (c *Curve) Exp(degree, xS, yS *big.Int) (*big.Int, *big.Int, error) {
 120         if degree.Cmp(zero) == 0 {
 121                 return nil, nil, errors.New("Bad degree value")
 122         }
 123         dg := big.NewInt(0).Sub(degree, bigInt1)
 124         tx := big.NewInt(0).Set(xS)
 125         ty := big.NewInt(0).Set(yS)
 126         cx := big.NewInt(0).Set(xS)
 127         cy := big.NewInt(0).Set(yS)
 128         for dg.Cmp(zero) != 0 {
 129                 if dg.Bit(0) == 1 {
 130                         c.add(tx, ty, cx, cy)
 131                 }
 132                 dg.Rsh(dg, 1)
 133                 c.add(cx, cy, cx, cy)
 134         }
 135         return tx, ty, nil
 136 }