pygost/gost3410.py

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