gost3410/curve.go

   1 // GoGOST -- Pure Go GOST cryptographic functions library
   2 // Copyright (C) 2015-2020 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, version 3 of the License.
   7 //
   8 // This program is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 // GNU General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU General Public License
  14 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
  15
  16 package gost3410
  17
  18 import (
  19         "errors"
  20         "math/big"
  21 )
  22
  23 var (
  24         zero    *big.Int = big.NewInt(0)
  25         bigInt1 *big.Int = big.NewInt(1)
  26         bigInt2 *big.Int = big.NewInt(2)
  27         bigInt3 *big.Int = big.NewInt(3)
  28         bigInt4 *big.Int = big.NewInt(4)
  29 )
  30
  31 type Curve struct {
  32         Name string // Just simple identifier
  33
  34         P *big.Int // Characteristic of the underlying prime field
  35         Q *big.Int // Elliptic curve subgroup order
  36
  37         Co *big.Int // Cofactor
  38
  39         // Equation coefficients of the elliptic curve in canonical form
  40         A *big.Int
  41         B *big.Int
  42
  43         // Equation coefficients of the elliptic curve in twisted Edwards form
  44         E *big.Int
  45         D *big.Int
  46
  47         // Basic point X and Y coordinates
  48         X *big.Int
  49         Y *big.Int
  50
  51         // Temporary variable for the add method
  52         t  *big.Int
  53         tx *big.Int
  54         ty *big.Int
  55
  56         // Cached s/t parameters for Edwards curve points conversion
  57         edS *big.Int
  58         edT *big.Int
  59 }
  60
  61 func NewCurve(p, q, a, b, x, y, e, d, co *big.Int) (*Curve, error) {
  62         c := Curve{
  63                 Name: "unknown",
  64                 P:    p,
  65                 Q:    q,
  66                 A:    a,
  67                 B:    b,
  68                 X:    x,
  69                 Y:    y,
  70                 t:    big.NewInt(0),
  71                 tx:   big.NewInt(0),
  72                 ty:   big.NewInt(0),
  73         }
  74         r1 := big.NewInt(0)
  75         r2 := big.NewInt(0)
  76         r1.Mul(c.Y, c.Y)
  77         r1.Mod(r1, c.P)
  78         r2.Mul(c.X, c.X)
  79         r2.Add(r2, c.A)
  80         r2.Mul(r2, c.X)
  81         r2.Add(r2, c.B)
  82         r2.Mod(r2, c.P)
  83         c.pos(r2)
  84         if r1.Cmp(r2) != 0 {
  85                 return nil, errors.New("gogost/gost3410: invalid curve parameters")
  86         }
  87         if e != nil && d != nil {
  88                 c.E = e
  89                 c.D = d
  90         }
  91         if co == nil {
  92                 c.Co = bigInt1
  93         } else {
  94                 c.Co = co
  95         }
  96         return &c, nil
  97 }
  98
  99 func (c *Curve) pos(v *big.Int) {
 100         if v.Cmp(zero) < 0 {
 101                 v.Add(v, c.P)
 102         }
 103 }
 104
 105 func (c *Curve) add(p1x, p1y, p2x, p2y *big.Int) {
 106         if p1x.Cmp(p2x) == 0 && p1y.Cmp(p2y) == 0 {
 107                 // double
 108                 c.t.Mul(p1x, p1x)
 109                 c.t.Mul(c.t, bigInt3)
 110                 c.t.Add(c.t, c.A)
 111                 c.tx.Mul(bigInt2, p1y)
 112                 c.tx.ModInverse(c.tx, c.P)
 113                 c.t.Mul(c.t, c.tx)
 114                 c.t.Mod(c.t, c.P)
 115         } else {
 116                 c.tx.Sub(p2x, p1x)
 117                 c.tx.Mod(c.tx, c.P)
 118                 c.pos(c.tx)
 119                 c.ty.Sub(p2y, p1y)
 120                 c.ty.Mod(c.ty, c.P)
 121                 c.pos(c.ty)
 122                 c.t.ModInverse(c.tx, c.P)
 123                 c.t.Mul(c.t, c.ty)
 124                 c.t.Mod(c.t, c.P)
 125         }
 126         c.tx.Mul(c.t, c.t)
 127         c.tx.Sub(c.tx, p1x)
 128         c.tx.Sub(c.tx, p2x)
 129         c.tx.Mod(c.tx, c.P)
 130         c.pos(c.tx)
 131         c.ty.Sub(p1x, c.tx)
 132         c.ty.Mul(c.ty, c.t)
 133         c.ty.Sub(c.ty, p1y)
 134         c.ty.Mod(c.ty, c.P)
 135         c.pos(c.ty)
 136         p1x.Set(c.tx)
 137         p1y.Set(c.ty)
 138 }
 139
 140 func (c *Curve) Exp(degree, xS, yS *big.Int) (*big.Int, *big.Int, error) {
 141         if degree.Cmp(zero) == 0 {
 142                 return nil, nil, errors.New("gogost/gost3410: zero degree value")
 143         }
 144         dg := big.NewInt(0).Sub(degree, bigInt1)
 145         tx := big.NewInt(0).Set(xS)
 146         ty := big.NewInt(0).Set(yS)
 147         cx := big.NewInt(0).Set(xS)
 148         cy := big.NewInt(0).Set(yS)
 149         for dg.Cmp(zero) != 0 {
 150                 if dg.Bit(0) == 1 {
 151                         c.add(tx, ty, cx, cy)
 152                 }
 153                 dg.Rsh(dg, 1)
 154                 c.add(cx, cy, cx, cy)
 155         }
 156         return tx, ty, nil
 157 }