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 ++ diff --git a/NEWS b/NEWS index 747adb54f306804fbeda6061bfeda42987dbe8802ea4da3745a2eaee80a3663b..ef5382b518e20530d211ef47b96a4d43e3082a2a9f16df7e7da37f69655a0908 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 7dcdca516858f4039842f4172e69894b2f0f0690765a838a0cb35d037cd4a6e3..9b98a999d661b84fcfe31ce7e699ab4cdce88f4b4205b5bce6d2c07fd9f89b9b 100644 --- a/README +++ b/README @@ -12,6 +12,8 @@ * GOST R 34.11-2012 based PBKDF2 function (Р 50.1.111-2016) * 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 4b9fb785e00730cc83d867b1ee4348a02558857d4dfc3a5d4b312f24bc1b4ba4..e30dbcd83914c297b43ad8f8b4052bbe13f2c48b83e83b4bfd8a28254815ed8d 100644 --- a/news.texi +++ b/news.texi @@ -7,6 +7,8 @@ @anchor{Release 4.0} @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 0d9e0e81ed058b81d8e0d59d1192e20d9c57cf0dd30848e44ada97ce3e2eb0b8..8ebe8411f946174f05d8aacc0fe38f50f90be63853aa2483bbefea2dd1249f90 100644 --- a/pygost/gost3410.py +++ b/pygost/gost3410.py @@ -44,20 +44,35 @@ >>> signature = sign(curve, prv, GOST341194(data).digest()) >>> 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 @@ if p1x == p2x and p1y == p2y: # 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 @@ degree = degree >> 1 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 @@ a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")), 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 @@ a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")), 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 @@ """ 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 09f415235542a945e713c89585c6572b1453f5eae00189d67850e443c6e7de6e..17f598bff82d49781c3caa63adcaa3f9f0bb93dcaba954f9b15bf5b13cf9d432 100644 --- a/pygost/stubs/pygost/gost3410.pyi +++ b/pygost/stubs/pygost/gost3410.pyi @@ -15,12 +15,26 @@ a = ... # type: int 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 18b9190b76b0d224a215e23c9890c0da57db04a214de021d57a55e9c8e46c4fc..5216043e20b39259200a9bd46fda71e6f115df9e45907314a49efa440bc9d979 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 @@ -228,6 +230,22 @@ digest = urandom(64) s = sign(c, prv, digest, mode=2012) self.assertTrue(verify(c, (pubX, pubY), digest, s, mode=2012)) 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): diff --git a/www.texi b/www.texi index a9c496cb0c11c0fe31ff980a1df595fe90985b7ff65b5bf7de59fb89ab6fabc6..0c48547df4a39a882860dacf52fa47af93e982b2d8aee7e2206a5094c12f441a 100644 --- a/www.texi +++ b/www.texi @@ -38,6 +38,8 @@ @item GOST R 34.10-2012 (@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