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 SIZE_3410_2001 = 32
  33 SIZE_3410_2012 = 64
  34 MODE2SIZE = {
  35     2001: SIZE_3410_2001,
  36     2012: SIZE_3410_2012,
  37 }
  38
  39
  40 DEFAULT_CURVE = "GostR3410_2001_CryptoPro_A_ParamSet"
  41 # Curve parameters are the following: p, q, a, b, x, y
  42 CURVE_PARAMS = {
  43     "GostR3410_2001_ParamSet_cc": (
  44         "C0000000000000000000000000000000000000000000000000000000000003C7",
  45         "5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85",
  46         "C0000000000000000000000000000000000000000000000000000000000003c4",
  47         "2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c",
  48         "0000000000000000000000000000000000000000000000000000000000000002",
  49         "a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c",
  50     ),
  51     "GostR3410_2001_TestParamSet": (
  52         "8000000000000000000000000000000000000000000000000000000000000431",
  53         "8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3",
  54         "0000000000000000000000000000000000000000000000000000000000000007",
  55         "5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E",
  56         "0000000000000000000000000000000000000000000000000000000000000002",
  57         "08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8",
  58     ),
  59     "GostR3410_2001_CryptoPro_A_ParamSet": (
  60         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97",
  61         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893",
  62         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94",
  63         "00000000000000000000000000000000000000000000000000000000000000a6",
  64         "0000000000000000000000000000000000000000000000000000000000000001",
  65         "8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14",
  66     ),
  67     "GostR3410_2001_CryptoPro_B_ParamSet": (
  68         "8000000000000000000000000000000000000000000000000000000000000C99",
  69         "800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F",
  70         "8000000000000000000000000000000000000000000000000000000000000C96",
  71         "3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B",
  72         "0000000000000000000000000000000000000000000000000000000000000001",
  73         "3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC",
  74     ),
  75     "GostR3410_2001_CryptoPro_C_ParamSet": (
  76         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B",
  77         "9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9",
  78         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598",
  79         "000000000000000000000000000000000000000000000000000000000000805a",
  80         "0000000000000000000000000000000000000000000000000000000000000000",
  81         "41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67",
  82     ),
  83     "GostR3410_2001_CryptoPro_XchA_ParamSet": (
  84         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97",
  85         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893",
  86         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94",
  87         "00000000000000000000000000000000000000000000000000000000000000a6",
  88         "0000000000000000000000000000000000000000000000000000000000000001",
  89         "8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14",
  90     ),
  91     "GostR3410_2001_CryptoPro_XchB_ParamSet": (
  92         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B",
  93         "9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9",
  94         "9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598",
  95         "000000000000000000000000000000000000000000000000000000000000805a",
  96         "0000000000000000000000000000000000000000000000000000000000000000",
  97         "41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67",
  98     ),
  99     "GostR3410_2012_TC26_ParamSetA": (
 100         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7",
 101         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275",
 102         "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4",
 103         "E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760",
 104         "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003",
 105         "7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4",
 106     ),
 107     "GostR3410_2012_TC26_ParamSetB": (
 108         "8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F",
 109         "800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD",
 110         "8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C",
 111         "687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116",
 112         "00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002",
 113         "1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD"
 114     ),
 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     >>> priv = bytes2long(urandom(32))
 126     >>> signature = sign(curve, priv, GOST341194(data).digest())
 127     >>> pubX, pubY = public_key(curve, priv)
 128     >>> verify(curve, pubX, pubY, 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, private_key):
 179     """ Generate public key from the private one
 180
 181     :param GOST3410Curve curve: curve to use
 182     :param long private_key: private key
 183     :return: public key's parts, X and Y
 184     :rtype: (long, long)
 185     """
 186     return curve.exp(private_key)
 187
 188
 189 def sign(curve, private_key, digest, size=SIZE_3410_2001):
 190     """ Calculate signature for provided digest
 191
 192     :param GOST3410Curve curve: curve to use
 193     :param long private_key: private key
 194     :param digest: digest for signing
 195     :type digest: bytes, 32 or 64 bytes
 196     :param size: signature size
 197     :type size: 32 (for 34.10-2001) or 64 (for 34.10-2012)
 198     :return: signature
 199     :rtype: bytes, 64 or 128 bytes
 200     """
 201     if len(digest) != size:
 202         raise ValueError("Invalid digest length")
 203     q = curve.q
 204     e = bytes2long(digest) % q
 205     if e == 0:
 206         e = 1
 207     while True:
 208         k = bytes2long(urandom(size)) % q
 209         if k == 0:
 210             continue
 211         r, _ = curve.exp(k)
 212         r %= q
 213         if r == 0:
 214             continue
 215         d = private_key * r
 216         k *= e
 217         s = (d + k) % q
 218         if s == 0:
 219             continue
 220         break
 221     return long2bytes(s, size) + long2bytes(r, size)
 222
 223
 224 def verify(curve, pubkeyX, pubkeyY, digest, signature, size=SIZE_3410_2001):
 225     """ Verify provided digest with the signature
 226
 227     :param GOST3410Curve curve: curve to use
 228     :param long pubkeyX: public key's X
 229     :param long pubkeyY: public key's Y
 230     :param digest: digest needed to check
 231     :type digest: bytes, 32 or 64 bytes
 232     :param signature: signature to verify with
 233     :type signature: bytes, 64 or 128 bytes
 234     :param size: signature size
 235     :type size: 32 (for 34.10-2001) or 64 (for 34.10-2012)
 236     :rtype: bool
 237     """
 238     if len(digest) != size:
 239         raise ValueError("Invalid digest length")
 240     if len(signature) != size * 2:
 241         raise ValueError("Invalid signature length")
 242     q = curve.q
 243     p = curve.p
 244     s = bytes2long(signature[:size])
 245     r = bytes2long(signature[size:])
 246     if r <= 0 or r >= q or s <= 0 or s >= q:
 247         return False
 248     e = bytes2long(digest) % curve.q
 249     if e == 0:
 250         e = 1
 251     v = modinvert(e, q)
 252     z1 = s * v % q
 253     z2 = q - r * v % q
 254     p1x, p1y = curve.exp(z1)
 255     q1x, q1y = curve.exp(z2, pubkeyX, pubkeyY)
 256     lm = q1x - p1x
 257     if lm < 0:
 258         lm += p
 259     lm = modinvert(lm, p)
 260     z1 = q1y - p1y
 261     lm = lm * z1 % p
 262     lm = lm * lm % p
 263     lm = lm - p1x - q1x
 264     lm = lm % p
 265     if lm < 0:
 266         lm += p
 267     lm %= q
 268     # This is not constant time comparison!
 269     return lm == r
 270
 271
 272 def prv_unmarshal(private_key):
 273     """Unmarshal private key
 274
 275     :param bytes private_key: serialized private key
 276     :rtype: long
 277     """
 278     return bytes2long(private_key[::-1])
 279
 280
 281 def pub_marshal(pub, mode=2001):
 282     """Marshal public key
 283
 284     :type pub: (long, long)
 285     :rtype: bytes
 286     """
 287     size = MODE2SIZE[mode]
 288     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 289
 290
 291 def pub_unmarshal(pub, mode=2001):
 292     """Unmarshal public key
 293
 294     :type pub: bytes
 295     :rtype: (long, long)
 296     """
 297     pub = pub[::-1]
 298     size = MODE2SIZE[mode]
 299     return (bytes2long(pub[size:]), bytes2long(pub[:size]))