pygost/gost3410.py

   1 # coding: utf-8
   2 # PyGOST -- Pure Python GOST cryptographic functions library
   3 # Copyright (C) 2015-2016 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     # pylint: disable=line-too-long
  98     "GostR3410_2012_TC26_ParamSetA": (
  99         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7",
 100         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275",
 101         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4",
 102         "E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760",
 103         "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003",
 104         "7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4",
 105     ),
 106     "GostR3410_2012_TC26_ParamSetB": (
 107         "8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F",
 108         "800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD",
 109         "8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C",
 110         "687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116",
 111         "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002",
 112         "1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD"
 113     ),
 114     # pylint: enable=line-too-long
 115 }
 116 for c, params in CURVE_PARAMS.items():
 117     CURVE_PARAMS[c] = [hexdec(param) for param in params]
 118
 119
 120 class GOST3410Curve(object):
 121     """ GOST 34.10 validated curve
 122
 123     >>> p, q, a, b, x, y = CURVE_PARAMS["GostR3410_2001_TestParamSet"]
 124     >>> curve = GOST3410Curve(p, q, a, b, x, y)
 125     >>> prv = prv_unmarshal(urandom(32))
 126     >>> signature = sign(curve, prv, GOST341194(data).digest())
 127     >>> pub = public_key(curve, prv)
 128     >>> verify(curve, pub, GOST341194(data).digest(), signature)
 129     True
 130     """
 131     def __init__(self, p, q, a, b, x, y):
 132         self.p = bytes2long(p)
 133         self.q = bytes2long(q)
 134         self.a = bytes2long(a)
 135         self.b = bytes2long(b)
 136         self.x = bytes2long(x)
 137         self.y = bytes2long(y)
 138         r1 = self.y * self.y % self.p
 139         r2 = ((self.x * self.x + self.a) * self.x + self.b) % self.p
 140         if r2 < 0:
 141             r2 += self.p
 142         if r1 != r2:
 143             raise ValueError("Invalid parameters")
 144
 145     def _pos(self, v):
 146         if v < 0:
 147             return v + self.p
 148         return v
 149
 150     def _add(self, p1x, p1y, p2x, p2y):
 151         if p1x == p2x and p1y == p2y:
 152             # double
 153             t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
 154         else:
 155             tx = self._pos(p2x - p1x) % self.p
 156             ty = self._pos(p2y - p1y) % self.p
 157             t = (ty * modinvert(tx, self.p)) % self.p
 158         tx = self._pos(t * t - p1x - p2x) % self.p
 159         ty = self._pos(t * (p1x - tx) - p1y) % self.p
 160         return tx, ty
 161
 162     def exp(self, degree, x=None, y=None):
 163         x = x or self.x
 164         y = y or self.y
 165         tx = x
 166         ty = y
 167         degree -= 1
 168         if degree == 0:
 169             raise ValueError("Bad degree value")
 170         while degree != 0:
 171             if degree & 1 == 1:
 172                 tx, ty = self._add(tx, ty, x, y)
 173             degree = degree >> 1
 174             x, y = self._add(x, y, x, y)
 175         return tx, ty
 176
 177
 178 def public_key(curve, prv):
 179     """ Generate public key from the private one
 180
 181     :param GOST3410Curve curve: curve to use
 182     :param long prv: private key
 183     :returns: public key's parts, X and Y
 184     :rtype: (long, long)
 185     """
 186     return curve.exp(prv)
 187
 188
 189 def sign(curve, prv, digest, mode=2001):
 190     """ Calculate signature for provided digest
 191
 192     :param GOST3410Curve curve: curve to use
 193     :param long prv: private key
 194     :param digest: digest for signing
 195     :type digest: bytes, 32 or 64 bytes
 196     :returns: signature
 197     :rtype: bytes, 64 or 128 bytes
 198     """
 199     size = MODE2SIZE[mode]
 200     q = curve.q
 201     e = bytes2long(digest) % q
 202     if e == 0:
 203         e = 1
 204     while True:
 205         k = bytes2long(urandom(size)) % q
 206         if k == 0:
 207             continue
 208         r, _ = curve.exp(k)
 209         r %= q
 210         if r == 0:
 211             continue
 212         d = prv * r
 213         k *= e
 214         s = (d + k) % q
 215         if s == 0:
 216             continue
 217         break
 218     return long2bytes(s, size) + long2bytes(r, size)
 219
 220
 221 def verify(curve, pub, digest, signature, mode=2001):
 222     """ Verify provided digest with the signature
 223
 224     :param GOST3410Curve curve: curve to use
 225     :type pub: (long, long)
 226     :param digest: digest needed to check
 227     :type digest: bytes, 32 or 64 bytes
 228     :param signature: signature to verify with
 229     :type signature: bytes, 64 or 128 bytes
 230     :rtype: bool
 231     """
 232     size = MODE2SIZE[mode]
 233     if len(signature) != size * 2:
 234         raise ValueError("Invalid signature length")
 235     q = curve.q
 236     p = curve.p
 237     s = bytes2long(signature[:size])
 238     r = bytes2long(signature[size:])
 239     if r <= 0 or r >= q or s <= 0 or s >= q:
 240         return False
 241     e = bytes2long(digest) % curve.q
 242     if e == 0:
 243         e = 1
 244     v = modinvert(e, q)
 245     z1 = s * v % q
 246     z2 = q - r * v % q
 247     p1x, p1y = curve.exp(z1)
 248     q1x, q1y = curve.exp(z2, pub[0], pub[1])
 249     lm = q1x - p1x
 250     if lm < 0:
 251         lm += p
 252     lm = modinvert(lm, p)
 253     z1 = q1y - p1y
 254     lm = lm * z1 % p
 255     lm = lm * lm % p
 256     lm = lm - p1x - q1x
 257     lm = lm % p
 258     if lm < 0:
 259         lm += p
 260     lm %= q
 261     # This is not constant time comparison!
 262     return lm == r
 263
 264
 265 def prv_unmarshal(prv):
 266     """Unmarshal private key
 267
 268     :param bytes prv: serialized private key
 269     :rtype: long
 270     """
 271     return bytes2long(prv[::-1])
 272
 273
 274 def pub_marshal(pub, mode=2001):
 275     """Marshal public key
 276
 277     :type pub: (long, long)
 278     :rtype: bytes
 279     """
 280     size = MODE2SIZE[mode]
 281     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 282
 283
 284 def pub_unmarshal(pub, mode=2001):
 285     """Unmarshal public key
 286
 287     :type pub: bytes
 288     :rtype: (long, long)
 289     """
 290     size = MODE2SIZE[mode]
 291     pub = pub[::-1]
 292     return (bytes2long(pub[size:]), bytes2long(pub[:size]))