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         // Equation coefficients of the elliptic curve in twisted Edwards form
  40         E *big.Int
  41         D *big.Int
  42
  43         // Basic point X and Y coordinates
  44         X *big.Int
  45         Y *big.Int
  46
  47         // Temporary variable for the add method
  48         t  *big.Int
  49         tx *big.Int
  50         ty *big.Int
  51
  52         // Cached s/t parameters for Edwards curve points conversion
  53         edS *big.Int
  54         edT *big.Int
  55 }
  56
  57 func NewCurve(p, q, a, b, x, y, e, d *big.Int) (*Curve, error) {
  58         c := Curve{
  59                 P:  p,
  60                 Q:  q,
  61                 A:  a,
  62                 B:  b,
  63                 X:  x,
  64                 Y:  y,
  65                 t:  big.NewInt(0),
  66                 tx: big.NewInt(0),
  67                 ty: big.NewInt(0),
  68         }
  69         r1 := big.NewInt(0)
  70         r2 := big.NewInt(0)
  71         r1.Mul(c.Y, c.Y)
  72         r1.Mod(r1, c.P)
  73         r2.Mul(c.X, c.X)
  74         r2.Add(r2, c.A)
  75         r2.Mul(r2, c.X)
  76         r2.Add(r2, c.B)
  77         r2.Mod(r2, c.P)
  78         c.pos(r2)
  79         if r1.Cmp(r2) != 0 {
  80                 return nil, errors.New("Invalid curve parameters")
  81         }
  82         if e != nil && d != nil {
  83                 c.E = e
  84                 c.D = d
  85         }
  86         return &c, nil
  87 }
  88
  89 func (c *Curve) pos(v *big.Int) {
  90         if v.Cmp(zero) < 0 {
  91                 v.Add(v, c.P)
  92         }
  93 }
  94
  95 func (c *Curve) add(p1x, p1y, p2x, p2y *big.Int) {
  96         if p1x.Cmp(p2x) == 0 && p1y.Cmp(p2y) == 0 {
  97                 // double
  98                 c.t.Mul(p1x, p1x)
  99                 c.t.Mul(c.t, bigInt3)
 100                 c.t.Add(c.t, c.A)
 101                 c.tx.Mul(bigInt2, p1y)
 102                 c.tx.ModInverse(c.tx, c.P)
 103                 c.t.Mul(c.t, c.tx)
 104                 c.t.Mod(c.t, c.P)
 105         } else {
 106                 c.tx.Sub(p2x, p1x)
 107                 c.tx.Mod(c.tx, c.P)
 108                 c.pos(c.tx)
 109                 c.ty.Sub(p2y, p1y)
 110                 c.ty.Mod(c.ty, c.P)
 111                 c.pos(c.ty)
 112                 c.t.ModInverse(c.tx, c.P)
 113                 c.t.Mul(c.t, c.ty)
 114                 c.t.Mod(c.t, c.P)
 115         }
 116         c.tx.Mul(c.t, c.t)
 117         c.tx.Sub(c.tx, p1x)
 118         c.tx.Sub(c.tx, p2x)
 119         c.tx.Mod(c.tx, c.P)
 120         c.pos(c.tx)
 121         c.ty.Sub(p1x, c.tx)
 122         c.ty.Mul(c.ty, c.t)
 123         c.ty.Sub(c.ty, p1y)
 124         c.ty.Mod(c.ty, c.P)
 125         c.pos(c.ty)
 126         p1x.Set(c.tx)
 127         p1y.Set(c.ty)
 128 }
 129
 130 func (c *Curve) Exp(degree, xS, yS *big.Int) (*big.Int, *big.Int, error) {
 131         if degree.Cmp(zero) == 0 {
 132                 return nil, nil, errors.New("Bad degree value")
 133         }
 134         dg := big.NewInt(0).Sub(degree, bigInt1)
 135         tx := big.NewInt(0).Set(xS)
 136         ty := big.NewInt(0).Set(yS)
 137         cx := big.NewInt(0).Set(xS)
 138         cy := big.NewInt(0).Set(yS)
 139         for dg.Cmp(zero) != 0 {
 140                 if dg.Bit(0) == 1 {
 141                         c.add(tx, ty, cx, cy)
 142                 }
 143                 dg.Rsh(dg, 1)
 144                 c.add(cx, cy, cx, cy)
 145         }
 146         return tx, ty, nil
 147 }