pygost/gost3410.py

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