From 312c6b813adbf8a04253e3b1da28e02780c61d07 Mon Sep 17 00:00:00 2001 From: Sergey Matveev Date: Wed, 10 Jul 2019 16:46:26 +0300 Subject: [PATCH] Coordinates conversion from/to twisted Edwards to Weierstass form --- NEWS | 2 + README | 2 + news.texi | 2 + pygost/gost3410.py | 67 ++++++++++++++++++++++++++++---- pygost/stubs/pygost/gost3410.pyi | 22 ++++++++++- pygost/test_gost3410.py | 18 +++++++++ www.texi | 2 + 7 files changed, 107 insertions(+), 8 deletions(-) diff --git a/NEWS b/NEWS index f2292f6..60003b8 100644 --- a/NEWS +++ b/NEWS @@ -1,5 +1,7 @@ 4.0: * 34.10-2012 TC26 twisted Edwards curve related parameters + * Coordinates conversion from twisted Edwards to Weierstrass + form and vice versa * More test vectors * Backward incompatible Sbox and curves parameters renaming, to comply with OIDs identifying them: diff --git a/README b/README index cc24e2f..d703323 100644 --- a/README +++ b/README @@ -12,6 +12,8 @@ GOST is GOvernment STandard of Russian Federation (and Soviet Union). * GOST R 34.10-2001 (RFC 5832) public key signature function * GOST R 34.10-2012 (RFC 7091) public key signature function * various 34.10 curve parameters included +* Coordinates conversion from twisted Edwards to Weierstrass form and + vice versa * VKO GOST R 34.10-2001 key agreement function (RFC 4357) * VKO GOST R 34.10-2012 key agreement function (RFC 7836) * 28147-89 and CryptoPro key wrapping (RFC 4357) diff --git a/news.texi b/news.texi index 9fe78fb..b1bf15c 100644 --- a/news.texi +++ b/news.texi @@ -7,6 +7,8 @@ @item 4.0 @itemize @item 34.10-2012 TC26 twisted Edwards curve related parameters + @item Coordinates conversion from twisted Edwards to Weierstrass + form and vice versa @item More test vectors @item Backward incompatible Sbox and curves parameters renaming, to comply with OIDs identifying them: diff --git a/pygost/gost3410.py b/pygost/gost3410.py index f1baa58..673441c 100644 --- a/pygost/gost3410.py +++ b/pygost/gost3410.py @@ -44,20 +44,35 @@ class GOST3410Curve(object): >>> pub = public_key(curve, prv) >>> verify(curve, pub, GOST341194(data).digest(), signature) True + + :param long p: characteristic of the underlying prime field + :param long q: elliptic curve subgroup order + :param long a, b: coefficients of the equation of the elliptic curve in + the canonical form + :param long x, y: the coordinate of the point P (generator of the + subgroup of order q) of the elliptic curve in + the canonical form + :param long e, d: coefficients of the equation of the elliptic curve in + the twisted Edwards form """ - def __init__(self, p, q, a, b, x, y): + def __init__(self, p, q, a, b, x, y, e=None, d=None): self.p = p self.q = q self.a = a self.b = b self.x = x self.y = y + self.e = e + self.d = d r1 = self.y * self.y % self.p r2 = ((self.x * self.x + self.a) * self.x + self.b) % self.p - if r1 != self._pos(r2): + if r1 != self.pos(r2): raise ValueError("Invalid parameters") + self._st = None - def _pos(self, v): + def pos(self, v): + """Make positive number + """ if v < 0: return v + self.p return v @@ -67,11 +82,11 @@ class GOST3410Curve(object): # double t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p else: - tx = self._pos(p2x - p1x) % self.p - ty = self._pos(p2y - p1y) % self.p + tx = self.pos(p2x - p1x) % self.p + ty = self.pos(p2y - p1y) % self.p t = (ty * modinvert(tx, self.p)) % self.p - tx = self._pos(t * t - p1x - p2x) % self.p - ty = self._pos(t * (p1x - tx) - p1y) % self.p + tx = self.pos(t * t - p1x - p2x) % self.p + ty = self.pos(t * (p1x - tx) - p1y) % self.p return tx, ty def exp(self, degree, x=None, y=None): @@ -89,6 +104,19 @@ class GOST3410Curve(object): x, y = self._add(x, y, x, y) return tx, ty + def st(self): + """Compute s/t parameters for twisted Edwards curve points conversion + """ + if self.e is None or self.d is None: + raise ValueError("non twisted Edwards curve") + if self._st is not None: + return self._st + self._st = ( + self.pos(self.e - self.d) * modinvert(4, self.p) % self.p, + (self.e + self.d) * modinvert(6, self.p) % self.p, + ) + return self._st + CURVES = { "GostR3410_2001_ParamSet_cc": GOST3410Curve( @@ -154,6 +182,8 @@ CURVES = { b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")), x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")), y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")), + e=0x01, + d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")), ), "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve( p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")), @@ -178,6 +208,8 @@ CURVES = { b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")), x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")), y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")), + e=0x01, + d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")), ), } DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"] @@ -298,3 +330,24 @@ def pub_unmarshal(pub, mode=2001): size = MODE2SIZE[mode] pub = pub[::-1] return (bytes2long(pub[size:]), bytes2long(pub[:size])) + + +def uv2xy(curve, u, v): + """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y + """ + s, t = curve.st() + k1 = (s * (1 + v)) % curve.p + k2 = curve.pos(1 - v) + x = t + k1 * modinvert(k2, curve.p) + y = k1 * modinvert(u * k2, curve.p) + return x % curve.p, y % curve.p + + +def xy2uv(curve, x, y): + """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V + """ + s, t = curve.st() + xmt = curve.pos(x - t) + u = xmt * modinvert(y, curve.p) + v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p) + return u % curve.p, v % curve.p diff --git a/pygost/stubs/pygost/gost3410.pyi b/pygost/stubs/pygost/gost3410.pyi index ed59186..f2071cc 100644 --- a/pygost/stubs/pygost/gost3410.pyi +++ b/pygost/stubs/pygost/gost3410.pyi @@ -15,13 +15,27 @@ class GOST3410Curve(object): b = ... # type: int x = ... # type: int y = ... # type: int + e = ... # type: int + d = ... # type: int def __init__( - self, p: bytes, q: bytes, a: bytes, b: bytes, x: bytes, y: bytes + self, + p: int, + q: int, + a: int, + b: int, + x: int, + y: int, + e: int = None, + d: int = None, ) -> None: ... + def pos(self, v: int) -> int: ... + def exp(self, degree: int, x: int=..., y: int=...) -> int: ... + def st(self) -> Tuple[int, int]: ... + def public_key(curve: GOST3410Curve, prv: int) -> PublicKey: ... @@ -45,3 +59,9 @@ def pub_marshal(pub: PublicKey, mode: int=...) -> bytes: ... def pub_unmarshal(pub: bytes, mode: int=...) -> PublicKey: ... + + +def uv2xy(curve: GOST3410Curve, u: int, v: int) -> Tuple[int, int]: ... + + +def xy2uv(curve: GOST3410Curve, x: int, y: int) -> Tuple[int, int]: ... diff --git a/pygost/test_gost3410.py b/pygost/test_gost3410.py index b69afae..681902c 100644 --- a/pygost/test_gost3410.py +++ b/pygost/test_gost3410.py @@ -22,7 +22,9 @@ from pygost.gost3410 import CURVES from pygost.gost3410 import GOST3410Curve from pygost.gost3410 import public_key from pygost.gost3410 import sign +from pygost.gost3410 import uv2xy from pygost.gost3410 import verify +from pygost.gost3410 import xy2uv from pygost.utils import bytes2long from pygost.utils import hexdec from pygost.utils import long2bytes @@ -230,6 +232,22 @@ class Test34102012(TestCase): self.assertNotIn(b"\x00" * 8, s) +class TestUVXYConversion(TestCase): + """Twisted Edwards to Weierstrass coordinates conversion and vice versa + """ + def test_curve1(self): + c = CURVES["id-tc26-gost-3410-2012-256-paramSetA"] + u, v = (0x0D, bytes2long(hexdec("60CA1E32AA475B348488C38FAB07649CE7EF8DBE87F22E81F92B2592DBA300E7"))) + self.assertEqual(uv2xy(c, u, v), (c.x, c.y)) + self.assertEqual(xy2uv(c, c.x, c.y), (u, v)) + + def test_curve2(self): + c = CURVES["id-tc26-gost-3410-2012-512-paramSetC"] + u, v = (0x12, bytes2long(hexdec("469AF79D1FB1F5E16B99592B77A01E2A0FDFB0D01794368D9A56117F7B38669522DD4B650CF789EEBF068C5D139732F0905622C04B2BAAE7600303EE73001A3D"))) + self.assertEqual(uv2xy(c, u, v), (c.x, c.y)) + self.assertEqual(xy2uv(c, c.x, c.y), (u, v)) + + class Test34102012SESPAKE(TestCase): """Test vectors for multiplication from :rfc:`8133` """ diff --git a/www.texi b/www.texi index 5e97287..7f3c0f2 100644 --- a/www.texi +++ b/www.texi @@ -38,6 +38,8 @@ Currently supported algorithms are: (@url{https://tools.ietf.org/html/rfc7091.html, RFC 7091}) public key signature function @item various 34.10 curve parameters included +@item Coordinates conversion from twisted Edwards to Weierstrass + form and vice versa @item VKO GOST R 34.10-2001 key agreement function (@url{https://tools.ietf.org/html/rfc4357.html, RFC 4357}) @item VKO GOST R 34.10-2012 key agreement function -- 2.44.0