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