summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorSergey Matveev <stargrave@stargrave.org>2019-07-10 16:46:26 +0300
committerSergey Matveev <stargrave@stargrave.org>2019-07-12 22:50:07 +0300
commit312c6b813adbf8a04253e3b1da28e02780c61d07 (patch)
treea18c171dc88143c81437dba70f3ee20333d8341c
parent0f9eff2c693f021fd502d5a4f2b98ccc0d3e13c5 (diff)
downloadpygost-312c6b813adbf8a04253e3b1da28e02780c61d07.tar.xz
Coordinates conversion from/to twisted Edwards to Weierstass form4.0
-rw-r--r--NEWS2
-rw-r--r--README2
-rw-r--r--news.texi2
-rw-r--r--pygost/gost3410.py67
-rw-r--r--pygost/stubs/pygost/gost3410.pyi22
-rw-r--r--pygost/test_gost3410.py18
-rw-r--r--www.texi2
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