gost3410/curve.go

   1 // GoGOST -- Pure Go GOST cryptographic functions library
   2 // Copyright (C) 2015-2024 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         // Cached s/t parameters for Edwards curve points conversion
  52         edS *big.Int
  53         edT *big.Int
  54 }
  55
  56 func NewCurve(p, q, a, b, x, y, e, d, co *big.Int) (*Curve, error) {
  57         c := Curve{
  58                 Name: "unknown",
  59                 P:    p,
  60                 Q:    q,
  61                 A:    a,
  62                 B:    b,
  63                 X:    x,
  64                 Y:    y,
  65         }
  66         if !c.Contains(c.X, c.Y) {
  67                 return nil, errors.New("gogost/gost3410: invalid curve parameters")
  68         }
  69         if e != nil && d != nil {
  70                 c.E = e
  71                 c.D = d
  72         }
  73         if co == nil {
  74                 c.Co = bigInt1
  75         } else {
  76                 c.Co = co
  77         }
  78         return &c, nil
  79 }
  80
  81 // Is point on curve?
  82 func (c *Curve) Contains(x, y *big.Int) bool {
  83         r1 := big.NewInt(0)
  84         r2 := big.NewInt(0)
  85         r1.Mul(y, y)
  86         r1.Mod(r1, c.P)
  87         r2.Mul(x, x)
  88         r2.Add(r2, c.A)
  89         r2.Mul(r2, x)
  90         r2.Add(r2, c.B)
  91         r2.Mod(r2, c.P)
  92         c.pos(r2)
  93         return r1.Cmp(r2) == 0
  94 }
  95
  96 // Get the size of the point's coordinate in bytes.
  97 // 32 for 256-bit curves, 64 for 512-bit ones.
  98 func (c *Curve) PointSize() int {
  99         return pointSize(c.P)
 100 }
 101
 102 func (c *Curve) pos(v *big.Int) {
 103         if v.Cmp(zero) < 0 {
 104                 v.Add(v, c.P)
 105         }
 106 }
 107
 108 func (c *Curve) add(p1x, p1y, p2x, p2y *big.Int) {
 109         var t, tx, ty big.Int
 110         if p1x.Cmp(p2x) == 0 && p1y.Cmp(p2y) == 0 {
 111                 // double
 112                 t.Mul(p1x, p1x)
 113                 t.Mul(&t, bigInt3)
 114                 t.Add(&t, c.A)
 115                 tx.Mul(bigInt2, p1y)
 116                 tx.ModInverse(&tx, c.P)
 117                 t.Mul(&t, &tx)
 118                 t.Mod(&t, c.P)
 119         } else {
 120                 tx.Sub(p2x, p1x)
 121                 tx.Mod(&tx, c.P)
 122                 c.pos(&tx)
 123                 ty.Sub(p2y, p1y)
 124                 ty.Mod(&ty, c.P)
 125                 c.pos(&ty)
 126                 t.ModInverse(&tx, c.P)
 127                 t.Mul(&t, &ty)
 128                 t.Mod(&t, c.P)
 129         }
 130         tx.Mul(&t, &t)
 131         tx.Sub(&tx, p1x)
 132         tx.Sub(&tx, p2x)
 133         tx.Mod(&tx, c.P)
 134         c.pos(&tx)
 135         ty.Sub(p1x, &tx)
 136         ty.Mul(&ty, &t)
 137         ty.Sub(&ty, p1y)
 138         ty.Mod(&ty, c.P)
 139         c.pos(&ty)
 140         p1x.Set(&tx)
 141         p1y.Set(&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 }
 162
 163 func (our *Curve) Equal(their *Curve) bool {
 164         return our.P.Cmp(their.P) == 0 &&
 165                 our.Q.Cmp(their.Q) == 0 &&
 166                 our.A.Cmp(their.A) == 0 &&
 167                 our.B.Cmp(their.B) == 0 &&
 168                 our.X.Cmp(their.X) == 0 &&
 169                 our.Y.Cmp(their.Y) == 0 &&
 170                 ((our.E == nil && their.E == nil) || our.E.Cmp(their.E) == 0) &&
 171                 ((our.D == nil && their.D == nil) || our.D.Cmp(their.D) == 0) &&
 172                 our.Co.Cmp(their.Co) == 0
 173 }
 174
 175 func (c *Curve) String() string {
 176         return c.Name
 177 }