pygost/gost3410.py

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