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