Coordinates conversion from/to twisted Edwards to Weierstass form

diff --git a/src/cypherpunks.ru/gogost/gost3410/2012_test.go b/src/cypherpunks.ru/gogost/gost3410/2012_test.go
index 2ff03455ff1c0939294b086d0d84258cb06dd5b2..ddfd6ad240c38ed64921aa3170ebcb3abd4ee7ab 100644 (file)
--- a/src/cypherpunks.ru/gogost/gost3410/2012_test.go
+++ b/src/cypherpunks.ru/gogost/gost3410/2012_test.go
@@ -150,6 +150,8 @@ func TestGCL3Vectors(t *testing.T) {
                bytes2big(b),
                bytes2big(x),
                bytes2big(y),
+               nil,
+               nil,
        )
        if err != nil {
                t.FailNow()
@@ -379,6 +381,31 @@ func TestSESPAKE(t *testing.T) {
                }
        }
 }
+
+// Twisted Edwards to Weierstrass coordinates conversion and vice versa
+func TestUVXYConversion(t *testing.T) {
+       f := func(c *Curve, uRaw, vRaw []byte) {
+               u := bytes2big(uRaw)
+               v := bytes2big(vRaw)
+               x, y := UV2XY(c, u, v)
+               if x.Cmp(c.X) != 0 {
+                       t.FailNow()
+               }
+               if y.Cmp(c.Y) != 0 {
+                       t.FailNow()
+               }
+               uGot, vGot := XY2UV(c, c.X, c.Y)
+               if u.Cmp(uGot) != 0 {
+                       t.FailNow()
+               }
+               if v.Cmp(vGot) != 0 {
+                       t.FailNow()
+               }
+       }
+       raw, _ := hex.DecodeString("60CA1E32AA475B348488C38FAB07649CE7EF8DBE87F22E81F92B2592DBA300E7")
+       f(CurveIdtc26gost34102012256paramSetA(), []byte{0x0D}, raw)
+       raw, _ = hex.DecodeString("469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B38669522DD4B650CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D")
+       f(CurveIdtc26gost34102012512paramSetC(), []byte{0x12}, raw)
 }
 
 func BenchmarkSign2012(b *testing.B) {

diff --git a/src/cypherpunks.ru/gogost/gost3410/curve.go b/src/cypherpunks.ru/gogost/gost3410/curve.go
index b25131636f3605fdea75c2adeef6dfc3a88219ea..6b371a2bdc21fc28db22481fa3978cab9eb97d21 100644 (file)
--- a/src/cypherpunks.ru/gogost/gost3410/curve.go
+++ b/src/cypherpunks.ru/gogost/gost3410/curve.go
@@ -36,6 +36,10 @@ type Curve struct {
        A *big.Int
        B *big.Int
 
+       // Equation coefficients of the elliptic curve in twisted Edwards form
+       E *big.Int
+       D *big.Int
+
        // Basic point X and Y coordinates
        X *big.Int
        Y *big.Int
@@ -44,9 +48,13 @@ type Curve struct {
        t  *big.Int
        tx *big.Int
        ty *big.Int
+
+       // Cached s/t parameters for Edwards curve points conversion
+       edS *big.Int
+       edT *big.Int
 }
 
-func NewCurve(p, q, a, b, x, y *big.Int) (*Curve, error) {
+func NewCurve(p, q, a, b, x, y, e, d *big.Int) (*Curve, error) {
        c := Curve{
                P:  p,
                Q:  q,
@@ -71,6 +79,9 @@ func NewCurve(p, q, a, b, x, y *big.Int) (*Curve, error) {
        if r1.Cmp(r2) != 0 {
                return nil, errors.New("Invalid curve parameters")
        }
+       if e != nil && d != nil {
+               c.E = e
+               c.D = d
        }
        return &c, nil
 }

diff --git a/src/cypherpunks.ru/gogost/gost3410/edwards.go b/src/cypherpunks.ru/gogost/gost3410/edwards.go
new file mode 100644 (file)
index 0000000..d303a61
--- /dev/null
+++ b/src/cypherpunks.ru/gogost/gost3410/edwards.go
@@ -0,0 +1,93 @@
+// GoGOST -- Pure Go GOST cryptographic functions library
+// Copyright (C) 2015-2019 Sergey Matveev <stargrave@stargrave.org>
+//
+// This program is free software: you can redistribute it and/or modify
+// it under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+//
+// This program is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+//
+// You should have received a copy of the GNU General Public License
+// along with this program.  If not, see <http://www.gnu.org/licenses/>.
+
+package gost3410
+
+import (
+       "math/big"
+)
+
+func (c *Curve) IsEdwards() bool {
+       return c.E != nil
+}
+
+func (c *Curve) EdwardsST() (*big.Int, *big.Int) {
+       if c.edS != nil {
+               return c.edS, c.edT
+       }
+       c.edS = big.NewInt(0)
+       c.edS.Set(c.E)
+       c.edS.Sub(c.edS, c.D)
+       c.pos(c.edS)
+       c.t.SetUint64(4)
+       c.t.ModInverse(c.t, c.P)
+       c.edS.Mul(c.edS, c.t)
+       c.edS.Mod(c.edS, c.P)
+       c.edT = big.NewInt(0)
+       c.edT.Set(c.E)
+       c.edT.Add(c.edT, c.D)
+       c.t.SetUint64(6)
+       c.t.ModInverse(c.t, c.P)
+       c.edT.Mul(c.edT, c.t)
+       c.edT.Mod(c.edT, c.P)
+       return c.edS, c.edT
+}
+
+// Convert Weierstrass X,Y coordinates to twisted Edwards U,V
+func XY2UV(curve *Curve, x, y *big.Int) (*big.Int, *big.Int) {
+       if !curve.IsEdwards() {
+               panic("non twisted Edwards curve")
+       }
+       edS, edT := curve.EdwardsST()
+       curve.t.Sub(x, edT)
+       curve.pos(curve.t)
+       u := big.NewInt(0)
+       u.ModInverse(y, curve.P)
+       u.Mul(u, curve.t)
+       u.Mod(u, curve.P)
+       v := big.NewInt(0).Set(curve.t)
+       v.Sub(v, edS)
+       curve.pos(v)
+       curve.t.Add(curve.t, edS)
+       curve.t.ModInverse(curve.t, curve.P)
+       v.Mul(v, curve.t)
+       v.Mod(v, curve.P)
+       return u, v
+}
+
+// Convert twisted Edwards U,V coordinates to Weierstrass X,Y
+func UV2XY(curve *Curve, u, v *big.Int) (*big.Int, *big.Int) {
+       if !curve.IsEdwards() {
+               panic("non twisted Edwards curve")
+       }
+       edS, edT := curve.EdwardsST()
+       curve.tx.Add(bigInt1, v)
+       curve.tx.Mul(curve.tx, edS)
+       curve.tx.Mod(curve.tx, curve.P)
+       curve.ty.Sub(bigInt1, v)
+       curve.pos(curve.ty)
+       x := big.NewInt(0)
+       x.ModInverse(curve.ty, curve.P)
+       x.Mul(x, curve.tx)
+       x.Add(x, edT)
+       x.Mod(x, curve.P)
+       y := big.NewInt(0)
+       y.Mul(u, curve.ty)
+       y.ModInverse(y, curve.P)
+       y.Mul(y, curve.tx)
+       y.Mod(y, curve.P)
+       return x, y
+}

diff --git a/src/cypherpunks.ru/gogost/gost3410/params.go b/src/cypherpunks.ru/gogost/gost3410/params.go
index dbf3040de980edb13b8da32824fec761ab5aad26..cbe40e6f117150ac05ca6f27dc7404c3ca857af5 100644 (file)
--- a/src/cypherpunks.ru/gogost/gost3410/params.go
+++ b/src/cypherpunks.ru/gogost/gost3410/params.go
@@ -60,6 +60,8 @@ var (
                                0xeb, 0x24, 0x8b, 0x26, 0x4a, 0xe9, 0x70, 0x6f,
                                0x44, 0x0b, 0xed, 0xc8, 0xcc, 0xb6, 0xb2, 0x2c,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -105,6 +107,8 @@ var (
                                0x85, 0xC9, 0x7F, 0x0A, 0x9C, 0xA2, 0x67, 0x12,
                                0x2B, 0x96, 0xAB, 0xBC, 0xEA, 0x7E, 0x8F, 0xC8,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -150,6 +154,8 @@ var (
                                0x35, 0x29, 0x4F, 0x2D, 0xDF, 0x23, 0xE3, 0xB1,
                                0x22, 0xAC, 0xC9, 0x9C, 0x9E, 0x9F, 0x1E, 0x14,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -195,6 +201,8 @@ var (
                                0xC5, 0x45, 0xC9, 0x85, 0x8D, 0x03, 0xEC, 0xFB,
                                0x74, 0x4B, 0xF8, 0xD7, 0x17, 0x71, 0x7E, 0xFC,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -240,6 +248,8 @@ var (
                                0x4D, 0x4D, 0xC4, 0x40, 0xD4, 0x64, 0x1A, 0x8F,
                                0x36, 0x6E, 0x55, 0x0D, 0xFD, 0xB3, 0xBB, 0x67,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -285,6 +295,8 @@ var (
                                0x35, 0x29, 0x4F, 0x2D, 0xDF, 0x23, 0xE3, 0xB1,
                                0x22, 0xAC, 0xC9, 0x9C, 0x9E, 0x9F, 0x1E, 0x14,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -330,6 +342,8 @@ var (
                                0x4D, 0x4D, 0xC4, 0x40, 0xD4, 0x64, 0x1A, 0x8F,
                                0x36, 0x6E, 0x55, 0x0D, 0xFD, 0xB3, 0xBB, 0x67,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -375,6 +389,13 @@ var (
                                0x5F, 0xDE, 0x0B, 0x53, 0x44, 0x76, 0x67, 0x40,
                                0xAF, 0x26, 0x8A, 0xDB, 0x32, 0x32, 0x2E, 0x5C,
                        }),
+                       bigInt1,
+                       bytes2big([]byte{
+                               0x06, 0x05, 0xF6, 0xB7, 0xC1, 0x83, 0xFA, 0x81,
+                               0x57, 0x8B, 0xC3, 0x9C, 0xFA, 0xD5, 0x18, 0x13,
+                               0x2B, 0x9D, 0xF6, 0x28, 0x97, 0x00, 0x9A, 0xF7,
+                               0xE5, 0x22, 0xC3, 0x2D, 0x6D, 0xC7, 0xBF, 0xFB,
+                       }),
                )
                if err != nil {
                        panic(err)
@@ -444,6 +465,8 @@ var (
                                0x80, 0x28, 0xFE, 0x5F, 0xC2, 0x35, 0xF5, 0xB8,
                                0x89, 0xA5, 0x89, 0xCB, 0x52, 0x15, 0xF2, 0xA4,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -513,6 +536,8 @@ var (
                                0x28, 0x04, 0x10, 0x55, 0xF9, 0x4C, 0xEE, 0xEC,
                                0x7E, 0x21, 0x34, 0x07, 0x80, 0xFE, 0x41, 0xBD,
                        }),
+                       nil,
+                       nil,
                )
                if err != nil {
                        panic(err)
@@ -582,6 +607,16 @@ var (
                                0x04, 0xF7, 0x26, 0xAA, 0x85, 0x4B, 0xAE, 0x07,
                                0xD0, 0x39, 0x6E, 0x9A, 0x9A, 0xDD, 0xC4, 0x0F,
                        }),
+                       bigInt1,
+                       bytes2big([]byte{
+                               0x9E, 0x4F, 0x5D, 0x8C, 0x01, 0x7D, 0x8D, 0x9F,
+                               0x13, 0xA5, 0xCF, 0x3C, 0xDF, 0x5B, 0xFE, 0x4D,
+                               0xAB, 0x40, 0x2D, 0x54, 0x19, 0x8E, 0x31, 0xEB,
+                               0xDE, 0x28, 0xA0, 0x62, 0x10, 0x50, 0x43, 0x9C,
+                               0xA6, 0xB3, 0x9E, 0x0A, 0x51, 0x5C, 0x06, 0xB3,
+                               0x04, 0xE2, 0xCE, 0x43, 0xE7, 0x9E, 0x36, 0x9E,
+                               0x91, 0xA0, 0xCF, 0xC2, 0xBC, 0x2A, 0x22, 0xB4,
+                               0xCA, 0x30, 0x2D, 0xBB, 0x33, 0xEE, 0x75, 0x50,
                        }),
                )
                if err != nil {