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