gost3410/curve.go

   1 // GoGOST -- Pure Go GOST cryptographic functions library
   2 // Copyright (C) 2015-2021 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) PointSize() int {
 100         return PointSize(c.P)
 101 }
 102
 103 func (c *Curve) pos(v *big.Int) {
 104         if v.Cmp(zero) < 0 {
 105                 v.Add(v, c.P)
 106         }
 107 }
 108
 109 func (c *Curve) add(p1x, p1y, p2x, p2y *big.Int) {
 110         if p1x.Cmp(p2x) == 0 && p1y.Cmp(p2y) == 0 {
 111                 // double
 112                 c.t.Mul(p1x, p1x)
 113                 c.t.Mul(c.t, bigInt3)
 114                 c.t.Add(c.t, c.A)
 115                 c.tx.Mul(bigInt2, p1y)
 116                 c.tx.ModInverse(c.tx, c.P)
 117                 c.t.Mul(c.t, c.tx)
 118                 c.t.Mod(c.t, c.P)
 119         } else {
 120                 c.tx.Sub(p2x, p1x)
 121                 c.tx.Mod(c.tx, c.P)
 122                 c.pos(c.tx)
 123                 c.ty.Sub(p2y, p1y)
 124                 c.ty.Mod(c.ty, c.P)
 125                 c.pos(c.ty)
 126                 c.t.ModInverse(c.tx, c.P)
 127                 c.t.Mul(c.t, c.ty)
 128                 c.t.Mod(c.t, c.P)
 129         }
 130         c.tx.Mul(c.t, c.t)
 131         c.tx.Sub(c.tx, p1x)
 132         c.tx.Sub(c.tx, p2x)
 133         c.tx.Mod(c.tx, c.P)
 134         c.pos(c.tx)
 135         c.ty.Sub(p1x, c.tx)
 136         c.ty.Mul(c.ty, c.t)
 137         c.ty.Sub(c.ty, p1y)
 138         c.ty.Mod(c.ty, c.P)
 139         c.pos(c.ty)
 140         p1x.Set(c.tx)
 141         p1y.Set(c.ty)
 142 }
 143
 144 func (c *Curve) Exp(degree, xS, yS *big.Int) (*big.Int, *big.Int, error) {
 145         if degree.Cmp(zero) == 0 {
 146                 return nil, nil, errors.New("gogost/gost3410: zero degree value")
 147         }
 148         dg := big.NewInt(0).Sub(degree, bigInt1)
 149         tx := big.NewInt(0).Set(xS)
 150         ty := big.NewInt(0).Set(yS)
 151         cx := big.NewInt(0).Set(xS)
 152         cy := big.NewInt(0).Set(yS)
 153         for dg.Cmp(zero) != 0 {
 154                 if dg.Bit(0) == 1 {
 155                         c.add(tx, ty, cx, cy)
 156                 }
 157                 dg.Rsh(dg, 1)
 158                 c.add(cx, cy, cx, cy)
 159         }
 160         return tx, ty, nil
 161 }