pygost/gost3410.py

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