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