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     "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     >>> priv = bytes2long(urandom(32))
 124     >>> signature = sign(curve, priv, GOST341194(data).digest())
 125     >>> pubX, pubY = public_key(curve, priv)
 126     >>> verify(curve, pubX, pubY, 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         degree -= 1
 166         if degree == 0:
 167             raise ValueError("Bad degree value")
 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, private_key):
 177     """ Generate public key from the private one
 178
 179     :param GOST3410Curve curve: curve to use
 180     :param long private_key: private key
 181     :return: public key's parts, X and Y
 182     :rtype: (long, long)
 183     """
 184     return curve.exp(private_key)
 185
 186
 187 def sign(curve, private_key, digest, mode=2001):
 188     """ Calculate signature for provided digest
 189
 190     :param GOST3410Curve curve: curve to use
 191     :param long private_key: private key
 192     :param digest: digest for signing
 193     :type digest: bytes, 32 or 64 bytes
 194     :return: 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 = private_key * 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, pubkeyX, pubkeyY, digest, signature, mode=2001):
 220     """ Verify provided digest with the signature
 221
 222     :param GOST3410Curve curve: curve to use
 223     :param long pubkeyX: public key's X
 224     :param long pubkeyY: public key's Y
 225     :param digest: digest needed to check
 226     :type digest: bytes, 32 or 64 bytes
 227     :param signature: signature to verify with
 228     :type signature: bytes, 64 or 128 bytes
 229     :rtype: bool
 230     """
 231     size = MODE2SIZE[mode]
 232     if len(signature) != size * 2:
 233         raise ValueError("Invalid signature length")
 234     q = curve.q
 235     p = curve.p
 236     s = bytes2long(signature[:size])
 237     r = bytes2long(signature[size:])
 238     if r <= 0 or r >= q or s <= 0 or s >= q:
 239         return False
 240     e = bytes2long(digest) % curve.q
 241     if e == 0:
 242         e = 1
 243     v = modinvert(e, q)
 244     z1 = s * v % q
 245     z2 = q - r * v % q
 246     p1x, p1y = curve.exp(z1)
 247     q1x, q1y = curve.exp(z2, pubkeyX, pubkeyY)
 248     lm = q1x - p1x
 249     if lm < 0:
 250         lm += p
 251     lm = modinvert(lm, p)
 252     z1 = q1y - p1y
 253     lm = lm * z1 % p
 254     lm = lm * lm % p
 255     lm = lm - p1x - q1x
 256     lm = lm % p
 257     if lm < 0:
 258         lm += p
 259     lm %= q
 260     # This is not constant time comparison!
 261     return lm == r
 262
 263
 264 def prv_unmarshal(private_key):
 265     """Unmarshal private key
 266
 267     :param bytes private_key: serialized private key
 268     :rtype: long
 269     """
 270     return bytes2long(private_key[::-1])
 271
 272
 273 def pub_marshal(pub, mode=2001):
 274     """Marshal public key
 275
 276     :type pub: (long, long)
 277     :rtype: bytes
 278     """
 279     size = MODE2SIZE[mode]
 280     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 281
 282
 283 def pub_unmarshal(pub, mode=2001):
 284     """Unmarshal public key
 285
 286     :type pub: bytes
 287     :rtype: (long, long)
 288     """
 289     size = MODE2SIZE[mode]
 290     pub = pub[::-1]
 291     return (bytes2long(pub[size:]), bytes2long(pub[:size]))