From 33abdb1342d4b06c2c3f198116c3eedce6aeab47 Mon Sep 17 00:00:00 2001 From: Sergey Matveev Date: Wed, 17 Jul 2019 18:10:54 +0300 Subject: [PATCH] Coordinates conversion from/to twisted Edwards to Weierstass form --- .../gogost/gost3410/2012_test.go | 27 ++++++ src/cypherpunks.ru/gogost/gost3410/curve.go | 13 ++- src/cypherpunks.ru/gogost/gost3410/edwards.go | 93 +++++++++++++++++++ src/cypherpunks.ru/gogost/gost3410/params.go | 35 +++++++ 4 files changed, 167 insertions(+), 1 deletion(-) create mode 100644 src/cypherpunks.ru/gogost/gost3410/edwards.go diff --git a/src/cypherpunks.ru/gogost/gost3410/2012_test.go b/src/cypherpunks.ru/gogost/gost3410/2012_test.go index 2ff0345..ddfd6ad 100644 --- 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 b251316..6b371a2 100644 --- 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 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 +// +// 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 . + +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 dbf3040..cbe40e6 100644 --- 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 { -- 2.44.0