pygost/gost3410.py

   1 # coding: utf-8
   2 # PyGOST -- Pure Python GOST cryptographic functions library
   3 # Copyright (C) 2015-2024 Sergey Matveev <stargrave@stargrave.org>
   4 #
   5 # This program is free software: you can redistribute it and/or modify
   6 # it under the terms of the GNU General Public License as published by
   7 # the Free Software Foundation, version 3 of the License.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16 """GOST R 34.10 public-key signature function.
  17
  18 This is implementation of GOST R 34.10-2001 (:rfc:`5832`), GOST R
  19 34.10-2012 (:rfc:`7091`). The difference between 2001 and 2012 is the
  20 key, digest and signature lengths.
  21 """
  22
  23 from os import urandom
  24
  25 from pygost.utils import bytes2long
  26 from pygost.utils import hexdec
  27 from pygost.utils import long2bytes
  28 from pygost.utils import modinvert
  29
  30
  31 def point_size(point):
  32     """Determine is it either 256 or 512 bit point
  33     """
  34     return (512 // 8) if point.bit_length() > 256 else (256 // 8)
  35
  36
  37 class GOST3410Curve(object):
  38     """GOST 34.10 validated curve
  39
  40     >>> curve = CURVES["id-GostR3410-2001-TestParamSet"]
  41     >>> prv = prv_unmarshal(urandom(32))
  42     >>> signature = sign(curve, prv, GOST341194(data).digest())
  43     >>> pub = public_key(curve, prv)
  44     >>> verify(curve, pub, GOST341194(data).digest(), signature)
  45     True
  46
  47     :param long p: characteristic of the underlying prime field
  48     :param long q: elliptic curve subgroup order
  49     :param long a, b: coefficients of the equation of the elliptic curve in
  50                       the canonical form
  51     :param long x, y: the coordinate of the point P (generator of the
  52                       subgroup of order q) of the elliptic curve in
  53                       the canonical form
  54     :param long e, d: coefficients of the equation of the elliptic curve in
  55                       the twisted Edwards form
  56     :param str name: human-readable curve name
  57     """
  58
  59     def __init__(self, p, q, a, b, x, y, cofactor=1, e=None, d=None, name=None):
  60         self.p = p
  61         self.q = q
  62         self.a = a
  63         self.b = b
  64         self.x = x
  65         self.y = y
  66         self.cofactor = cofactor
  67         self.e = e
  68         self.d = d
  69         if not self.contains((x, y)):
  70             raise ValueError("Invalid parameters")
  71         self._st = None
  72         self.name = name
  73
  74     @property
  75     def point_size(self):
  76         return point_size(self.p)
  77
  78     def __repr__(self):
  79         return "<%s: %s>" % (self.__class__.__name__, self.name)
  80
  81     def pos(self, v):
  82         """Make positive number
  83         """
  84         if v < 0:
  85             return v + self.p
  86         return v
  87
  88     def contains(self, point):
  89         """Is point on the curve?
  90
  91         :type point: (long, long)
  92         """
  93         x, y = point
  94         r1 = y * y % self.p
  95         r2 = ((x * x + self.a) * x + self.b) % self.p
  96         return r1 == self.pos(r2)
  97
  98     def _add(self, p1x, p1y, p2x, p2y):
  99         if p1x == p2x and p1y == p2y:
 100             # double
 101             t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
 102         else:
 103             tx = self.pos(p2x - p1x) % self.p
 104             ty = self.pos(p2y - p1y) % self.p
 105             t = (ty * modinvert(tx, self.p)) % self.p
 106         tx = self.pos(t * t - p1x - p2x) % self.p
 107         ty = self.pos(t * (p1x - tx) - p1y) % self.p
 108         return tx, ty
 109
 110     def exp(self, degree, x=None, y=None):
 111         x = x or self.x
 112         y = y or self.y
 113         tx = x
 114         ty = y
 115         if degree == 0:
 116             raise ValueError("Bad degree value")
 117         degree -= 1
 118         while degree != 0:
 119             if degree & 1 == 1:
 120                 tx, ty = self._add(tx, ty, x, y)
 121             degree = degree >> 1
 122             x, y = self._add(x, y, x, y)
 123         return tx, ty
 124
 125     def st(self):
 126         """Compute s/t parameters for twisted Edwards curve points conversion
 127         """
 128         if self.e is None or self.d is None:
 129             raise ValueError("Non twisted Edwards curve")
 130         if self._st is not None:
 131             return self._st
 132         self._st = (
 133             self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
 134             (self.e + self.d) * modinvert(6, self.p) % self.p,
 135         )
 136         return self._st
 137
 138
 139 CURVES = {
 140     "GostR3410_2001_ParamSet_cc": GOST3410Curve(
 141         p=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003C7")),
 142         q=bytes2long(hexdec("5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85")),
 143         a=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003c4")),
 144         b=bytes2long(hexdec("2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c")),
 145         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 146         y=bytes2long(hexdec("a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c")),
 147     ),
 148     "id-GostR3410-2001-TestParamSet": GOST3410Curve(
 149         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000431")),
 150         q=bytes2long(hexdec("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3")),
 151         a=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000007")),
 152         b=bytes2long(hexdec("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E")),
 153         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 154         y=bytes2long(hexdec("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8")),
 155     ),
 156     "id-tc26-gost-3410-12-256-paramSetA": GOST3410Curve(
 157         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 158         q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
 159         a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")),
 160         b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
 161         x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
 162         y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
 163         cofactor=4,
 164         e=0x01,
 165         d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
 166     ),
 167     "id-tc26-gost-3410-12-256-paramSetB": GOST3410Curve(
 168         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 169         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
 170         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
 171         b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
 172         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 173         y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
 174     ),
 175     "id-tc26-gost-3410-12-256-paramSetC": GOST3410Curve(
 176         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C99")),
 177         q=bytes2long(hexdec("800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F")),
 178         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C96")),
 179         b=bytes2long(hexdec("3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B")),
 180         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 181         y=bytes2long(hexdec("3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC")),
 182     ),
 183     "id-tc26-gost-3410-12-256-paramSetD": GOST3410Curve(
 184         p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
 185         q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
 186         a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
 187         b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
 188         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
 189         y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
 190     ),
 191     "id-tc26-gost-3410-12-512-paramSetTest": GOST3410Curve(
 192         p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
 193         q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
 194         a=7,
 195         b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
 196         x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
 197         y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
 198     ),
 199     "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
 200         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 201         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
 202         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
 203         b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
 204         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
 205         y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
 206     ),
 207     "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
 208         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
 209         q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
 210         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
 211         b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
 212         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
 213         y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
 214     ),
 215     "id-tc26-gost-3410-12-512-paramSetC": GOST3410Curve(
 216         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 217         q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
 218         a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
 219         b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
 220         x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
 221         y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
 222         cofactor=4,
 223         e=0x01,
 224         d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
 225     ),
 226 }
 227 CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
 228 CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetC"]
 229 CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetD"]
 230 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 231 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
 232 CURVES["id-tc26-gost-3410-2012-256-paramSetA"] = CURVES["id-tc26-gost-3410-12-256-paramSetA"]
 233 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
 234 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-tc26-gost-3410-12-256-paramSetC"]
 235 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-tc26-gost-3410-12-256-paramSetD"]
 236 CURVES["id-tc26-gost-3410-2012-512-paramSetTest"] = CURVES["id-tc26-gost-3410-12-512-paramSetTest"]
 237 CURVES["id-tc26-gost-3410-2012-512-paramSetA"] = CURVES["id-tc26-gost-3410-12-512-paramSetA"]
 238 CURVES["id-tc26-gost-3410-2012-512-paramSetB"] = CURVES["id-tc26-gost-3410-12-512-paramSetB"]
 239 CURVES["id-tc26-gost-3410-2012-512-paramSetC"] = CURVES["id-tc26-gost-3410-12-512-paramSetC"]
 240 for _name, _curve in CURVES.items():
 241     _curve.name = _name
 242 DEFAULT_CURVE = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
 243
 244
 245 def public_key(curve, prv, mask=None):
 246     """Generate public key from the private one
 247
 248     :param GOST3410Curve curve: curve to use
 249     :param long prv: private key
 250     :returns: public key's parts, X and Y
 251     :rtype: (long, long)
 252     """
 253     pub = curve.exp(prv)
 254     if mask is not None:
 255         pub = curve.exp(mask, pub[0], pub[1])
 256     return pub
 257
 258
 259 def sign(curve, prv, digest, rand=None, mask=None):
 260     """Calculate signature for provided digest
 261
 262     :param GOST3410Curve curve: curve to use
 263     :param long prv: private key
 264     :param digest: digest for signing
 265     :type digest: bytes, 32 or 64 bytes
 266     :param rand: optional predefined random data used for k/r generation
 267     :type rand: bytes, 32 or 64 bytes
 268     :returns: signature, BE(S) || BE(R)
 269     :rtype: bytes, 64 or 128 bytes
 270     """
 271     size = curve.point_size
 272     q = curve.q
 273     e = bytes2long(digest) % q
 274     if e == 0:
 275         e = 1
 276     while True:
 277         if rand is None:
 278             rand = urandom(size)
 279         elif len(rand) != size:
 280             raise ValueError("rand length != %d" % size)
 281         k = bytes2long(rand) % q
 282         if k == 0:
 283             continue
 284         r, y = curve.exp(k)
 285         if mask is not None:
 286             r, y = curve.exp(mask, x=r, y=y)
 287         r %= q
 288         if r == 0:
 289             continue
 290         d = prv * r
 291         k *= e
 292         s = d + k
 293         if mask is not None:
 294             s *= mask
 295         s %= q
 296         if s == 0:
 297             continue
 298         break
 299     return long2bytes(s, size) + long2bytes(r, size)
 300
 301
 302 def verify(curve, pub, digest, signature):
 303     """Verify provided digest with the signature
 304
 305     :param GOST3410Curve curve: curve to use
 306     :type pub: (long, long)
 307     :param digest: digest needed to check
 308     :type digest: bytes, 32 or 64 bytes
 309     :param signature: signature to verify with
 310     :type signature: bytes, 64 or 128 bytes
 311     :rtype: bool
 312     """
 313     size = curve.point_size
 314     if len(signature) != size * 2:
 315         raise ValueError("Invalid signature length")
 316     q = curve.q
 317     p = curve.p
 318     s = bytes2long(signature[:size])
 319     r = bytes2long(signature[size:])
 320     if r <= 0 or r >= q or s <= 0 or s >= q:
 321         return False
 322     e = bytes2long(digest) % curve.q
 323     if e == 0:
 324         e = 1
 325     v = modinvert(e, q)
 326     z1 = s * v % q
 327     z2 = q - r * v % q
 328     p1x, p1y = curve.exp(z1)
 329     q1x, q1y = curve.exp(z2, pub[0], pub[1])
 330     lm = q1x - p1x
 331     if lm < 0:
 332         lm += p
 333     lm = modinvert(lm, p)
 334     z1 = q1y - p1y
 335     lm = lm * z1 % p
 336     lm = lm * lm % p
 337     lm = lm - p1x - q1x
 338     lm = lm % p
 339     if lm < 0:
 340         lm += p
 341     lm %= q
 342     # This is not constant time comparison!
 343     return lm == r
 344
 345
 346 def prv_unmarshal(prv):
 347     """Unmarshal little-endian private key
 348
 349     :param bytes prv: serialized private key
 350     :rtype: long
 351
 352     It is advisable to use :py:func:`pygost.gost3410.prv_marshal` to
 353     assure that key i in curve's Q field for better compatibility with
 354     some implementations.
 355     """
 356     return bytes2long(prv[::-1])
 357
 358
 359 def prv_marshal(curve, prv):
 360     """Marshal little-endian private key
 361
 362     :param GOST3410Curve curve: curve to use
 363     :param long prv: serialized private key
 364     :rtype: bytes
 365
 366     Key is in curve's Q field.
 367     """
 368     return long2bytes(prv % curve.q, point_size(prv))[::-1]
 369
 370
 371 def pub_marshal(pub):
 372     """Marshal public key
 373
 374     :type pub: (long, long)
 375     :rtype: bytes
 376     :returns: LE(X) || LE(Y)
 377     """
 378     size = point_size(pub[0])
 379     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 380
 381
 382 def pub_unmarshal(pub):
 383     """Unmarshal public key
 384
 385     :param pub: LE(X) || LE(Y)
 386     :type pub: bytes
 387     :rtype: (long, long)
 388     """
 389     size = len(pub) // 2
 390     pub = pub[::-1]
 391     return (bytes2long(pub[size:]), bytes2long(pub[:size]))
 392
 393
 394 def uv2xy(curve, u, v):
 395     """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
 396     """
 397     s, t = curve.st()
 398     k1 = (s * (1 + v)) % curve.p
 399     k2 = curve.pos(1 - v)
 400     x = t + k1 * modinvert(k2, curve.p)
 401     y = k1 * modinvert(u * k2, curve.p)
 402     return x % curve.p, y % curve.p
 403
 404
 405 def xy2uv(curve, x, y):
 406     """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
 407     """
 408     s, t = curve.st()
 409     xmt = curve.pos(x - t)
 410     u = xmt * modinvert(y, curve.p)
 411     v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
 412     return u % curve.p, v % curve.p