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 DEFAULT_CURVE = "GostR3410_2001_CryptoPro_A_ParamSet"
  39 # Curve parameters are the following: p, q, a, b, x, y
  40 CURVE_PARAMS = {
  41     "GostR3410_2001_ParamSet_cc": (
  42         "C0000000000000000000000000000000000000000000000000000000000003C7",
  43         "5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85",
  44         "C0000000000000000000000000000000000000000000000000000000000003c4",
  45         "2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c",
  46         "0000000000000000000000000000000000000000000000000000000000000002",
  47         "a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c",
  48     ),
  49     "GostR3410_2001_TestParamSet": (
  50         "8000000000000000000000000000000000000000000000000000000000000431",
  51         "8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3",
  52         "0000000000000000000000000000000000000000000000000000000000000007",
  53         "5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E",
  54         "0000000000000000000000000000000000000000000000000000000000000002",
  55         "08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8",
  56     ),
  57     "GostR3410_2001_CryptoPro_A_ParamSet": (
  58         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97",
  59         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893",
  60         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94",
  61         "00000000000000000000000000000000000000000000000000000000000000a6",
  62         "0000000000000000000000000000000000000000000000000000000000000001",
  63         "8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14",
  64     ),
  65     "GostR3410_2001_CryptoPro_B_ParamSet": (
  66         "8000000000000000000000000000000000000000000000000000000000000C99",
  67         "800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F",
  68         "8000000000000000000000000000000000000000000000000000000000000C96",
  69         "3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B",
  70         "0000000000000000000000000000000000000000000000000000000000000001",
  71         "3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC",
  72     ),
  73     "GostR3410_2001_CryptoPro_C_ParamSet": (
  74         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B",
  75         "9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9",
  76         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598",
  77         "000000000000000000000000000000000000000000000000000000000000805a",
  78         "0000000000000000000000000000000000000000000000000000000000000000",
  79         "41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67",
  80     ),
  81     "GostR3410_2001_CryptoPro_XchA_ParamSet": (
  82         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97",
  83         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893",
  84         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94",
  85         "00000000000000000000000000000000000000000000000000000000000000a6",
  86         "0000000000000000000000000000000000000000000000000000000000000001",
  87         "8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14",
  88     ),
  89     "GostR3410_2001_CryptoPro_XchB_ParamSet": (
  90         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B",
  91         "9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9",
  92         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598",
  93         "000000000000000000000000000000000000000000000000000000000000805a",
  94         "0000000000000000000000000000000000000000000000000000000000000000",
  95         "41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67",
  96     ),
  97     "GostR3410_2012_TC26_256_ParamSetA": (
  98         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97",
  99         "400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67",
 100         "C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335",
 101         "295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513",
 102         "91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28",
 103         "32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C",
 104     ),
 105     "GostR3410_2012_TC26_ParamSetA": (
 106         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7",
 107         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275",
 108         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4",
 109         "E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760",
 110         "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003",
 111         "7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4",
 112     ),
 113     "GostR3410_2012_TC26_ParamSetB": (
 114         "8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F",
 115         "800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD",
 116         "8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C",
 117         "687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116",
 118         "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002",
 119         "1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD"
 120     ),
 121     "GostR3410_2012_TC26_ParamSetC": (
 122         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7",
 123         "3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED",
 124         "DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3",
 125         "B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1",
 126         "E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148",
 127         "F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F",
 128     ),
 129 }
 130 for c, params in CURVE_PARAMS.items():
 131     CURVE_PARAMS[c] = [hexdec(param) for param in params]
 132
 133
 134 class GOST3410Curve(object):
 135     """ GOST 34.10 validated curve
 136
 137     >>> p, q, a, b, x, y = CURVE_PARAMS["GostR3410_2001_TestParamSet"]
 138     >>> curve = GOST3410Curve(p, q, a, b, x, y)
 139     >>> prv = prv_unmarshal(urandom(32))
 140     >>> signature = sign(curve, prv, GOST341194(data).digest())
 141     >>> pub = public_key(curve, prv)
 142     >>> verify(curve, pub, GOST341194(data).digest(), signature)
 143     True
 144     """
 145     def __init__(self, p, q, a, b, x, y):
 146         self.p = bytes2long(p)
 147         self.q = bytes2long(q)
 148         self.a = bytes2long(a)
 149         self.b = bytes2long(b)
 150         self.x = bytes2long(x)
 151         self.y = bytes2long(y)
 152         r1 = self.y * self.y % self.p
 153         r2 = ((self.x * self.x + self.a) * self.x + self.b) % self.p
 154         if r2 < 0:
 155             r2 += self.p
 156         if r1 != r2:
 157             raise ValueError("Invalid parameters")
 158
 159     def _pos(self, v):
 160         if v < 0:
 161             return v + self.p
 162         return v
 163
 164     def _add(self, p1x, p1y, p2x, p2y):
 165         if p1x == p2x and p1y == p2y:
 166             # double
 167             t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
 168         else:
 169             tx = self._pos(p2x - p1x) % self.p
 170             ty = self._pos(p2y - p1y) % self.p
 171             t = (ty * modinvert(tx, self.p)) % self.p
 172         tx = self._pos(t * t - p1x - p2x) % self.p
 173         ty = self._pos(t * (p1x - tx) - p1y) % self.p
 174         return tx, ty
 175
 176     def exp(self, degree, x=None, y=None):
 177         x = x or self.x
 178         y = y or self.y
 179         tx = x
 180         ty = y
 181         if degree == 0:
 182             raise ValueError("Bad degree value")
 183         degree -= 1
 184         while degree != 0:
 185             if degree & 1 == 1:
 186                 tx, ty = self._add(tx, ty, x, y)
 187             degree = degree >> 1
 188             x, y = self._add(x, y, x, y)
 189         return tx, ty
 190
 191
 192 def public_key(curve, prv):
 193     """ Generate public key from the private one
 194
 195     :param GOST3410Curve curve: curve to use
 196     :param long prv: private key
 197     :returns: public key's parts, X and Y
 198     :rtype: (long, long)
 199     """
 200     return curve.exp(prv)
 201
 202
 203 def sign(curve, prv, digest, mode=2001):
 204     """ Calculate signature for provided digest
 205
 206     :param GOST3410Curve curve: curve to use
 207     :param long prv: private key
 208     :param digest: digest for signing
 209     :type digest: bytes, 32 or 64 bytes
 210     :returns: signature
 211     :rtype: bytes, 64 or 128 bytes
 212     """
 213     size = MODE2SIZE[mode]
 214     q = curve.q
 215     e = bytes2long(digest) % q
 216     if e == 0:
 217         e = 1
 218     while True:
 219         k = bytes2long(urandom(size)) % q
 220         if k == 0:
 221             continue
 222         r, _ = curve.exp(k)
 223         r %= q
 224         if r == 0:
 225             continue
 226         d = prv * r
 227         k *= e
 228         s = (d + k) % q
 229         if s == 0:
 230             continue
 231         break
 232     return long2bytes(s, size) + long2bytes(r, size)
 233
 234
 235 def verify(curve, pub, digest, signature, mode=2001):
 236     """ Verify provided digest with the signature
 237
 238     :param GOST3410Curve curve: curve to use
 239     :type pub: (long, long)
 240     :param digest: digest needed to check
 241     :type digest: bytes, 32 or 64 bytes
 242     :param signature: signature to verify with
 243     :type signature: bytes, 64 or 128 bytes
 244     :rtype: bool
 245     """
 246     size = MODE2SIZE[mode]
 247     if len(signature) != size * 2:
 248         raise ValueError("Invalid signature length")
 249     q = curve.q
 250     p = curve.p
 251     s = bytes2long(signature[:size])
 252     r = bytes2long(signature[size:])
 253     if r <= 0 or r >= q or s <= 0 or s >= q:
 254         return False
 255     e = bytes2long(digest) % curve.q
 256     if e == 0:
 257         e = 1
 258     v = modinvert(e, q)
 259     z1 = s * v % q
 260     z2 = q - r * v % q
 261     p1x, p1y = curve.exp(z1)
 262     q1x, q1y = curve.exp(z2, pub[0], pub[1])
 263     lm = q1x - p1x
 264     if lm < 0:
 265         lm += p
 266     lm = modinvert(lm, p)
 267     z1 = q1y - p1y
 268     lm = lm * z1 % p
 269     lm = lm * lm % p
 270     lm = lm - p1x - q1x
 271     lm = lm % p
 272     if lm < 0:
 273         lm += p
 274     lm %= q
 275     # This is not constant time comparison!
 276     return lm == r
 277
 278
 279 def prv_unmarshal(prv):
 280     """Unmarshal private key
 281
 282     :param bytes prv: serialized private key
 283     :rtype: long
 284     """
 285     return bytes2long(prv[::-1])
 286
 287
 288 def pub_marshal(pub, mode=2001):
 289     """Marshal public key
 290
 291     :type pub: (long, long)
 292     :rtype: bytes
 293     """
 294     size = MODE2SIZE[mode]
 295     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 296
 297
 298 def pub_unmarshal(pub, mode=2001):
 299     """Unmarshal public key
 300
 301     :type pub: bytes
 302     :rtype: (long, long)
 303     """
 304     size = MODE2SIZE[mode]
 305     pub = pub[::-1]
 306     return (bytes2long(pub[size:]), bytes2long(pub[:size]))