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