pygost/gost3410.py

   1 # coding: utf-8
   2 # PyGOST -- Pure Python GOST cryptographic functions library
   3 # Copyright (C) 2015-2019 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 class GOST3410Curve(object):
  39     """ GOST 34.10 validated curve
  40
  41     >>> curve = CURVES["id-GostR3410-2001-TestParamSet"]
  42     >>> prv = prv_unmarshal(urandom(32))
  43     >>> signature = sign(curve, prv, GOST341194(data).digest())
  44     >>> pub = public_key(curve, prv)
  45     >>> verify(curve, pub, GOST341194(data).digest(), signature)
  46     True
  47     """
  48     def __init__(self, p, q, a, b, x, y):
  49         self.p = p
  50         self.q = q
  51         self.a = a
  52         self.b = b
  53         self.x = x
  54         self.y = y
  55         r1 = self.y * self.y % self.p
  56         r2 = ((self.x * self.x + self.a) * self.x + self.b) % self.p
  57         if r1 != self._pos(r2):
  58             raise ValueError("Invalid parameters")
  59
  60     def _pos(self, v):
  61         if v < 0:
  62             return v + self.p
  63         return v
  64
  65     def _add(self, p1x, p1y, p2x, p2y):
  66         if p1x == p2x and p1y == p2y:
  67             # double
  68             t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
  69         else:
  70             tx = self._pos(p2x - p1x) % self.p
  71             ty = self._pos(p2y - p1y) % self.p
  72             t = (ty * modinvert(tx, self.p)) % self.p
  73         tx = self._pos(t * t - p1x - p2x) % self.p
  74         ty = self._pos(t * (p1x - tx) - p1y) % self.p
  75         return tx, ty
  76
  77     def exp(self, degree, x=None, y=None):
  78         x = x or self.x
  79         y = y or self.y
  80         tx = x
  81         ty = y
  82         if degree == 0:
  83             raise ValueError("Bad degree value")
  84         degree -= 1
  85         while degree != 0:
  86             if degree & 1 == 1:
  87                 tx, ty = self._add(tx, ty, x, y)
  88             degree = degree >> 1
  89             x, y = self._add(x, y, x, y)
  90         return tx, ty
  91
  92
  93 CURVES = {
  94     "GostR3410_2001_ParamSet_cc": GOST3410Curve(
  95         p=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003C7")),
  96         q=bytes2long(hexdec("5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85")),
  97         a=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003c4")),
  98         b=bytes2long(hexdec("2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c")),
  99         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 100         y=bytes2long(hexdec("a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c")),
 101     ),
 102     "id-GostR3410-2001-TestParamSet": GOST3410Curve(
 103         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000431")),
 104         q=bytes2long(hexdec("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3")),
 105         a=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000007")),
 106         b=bytes2long(hexdec("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E")),
 107         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 108         y=bytes2long(hexdec("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8")),
 109     ),
 110     "id-GostR3410-2001-CryptoPro-A-ParamSet": GOST3410Curve(
 111         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 112         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
 113         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
 114         b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
 115         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 116         y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
 117     ),
 118     "id-GostR3410-2001-CryptoPro-B-ParamSet": GOST3410Curve(
 119         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C99")),
 120         q=bytes2long(hexdec("800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F")),
 121         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C96")),
 122         b=bytes2long(hexdec("3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B")),
 123         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 124         y=bytes2long(hexdec("3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC")),
 125     ),
 126     "id-GostR3410-2001-CryptoPro-C-ParamSet": GOST3410Curve(
 127         p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
 128         q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
 129         a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
 130         b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
 131         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
 132         y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
 133     ),
 134     "id-GostR3410-2001-CryptoPro-XchA-ParamSet": GOST3410Curve(
 135         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 136         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
 137         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
 138         b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
 139         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 140         y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
 141     ),
 142     "id-GostR3410-2001-CryptoPro-XchB-ParamSet": GOST3410Curve(
 143         p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
 144         q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
 145         a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
 146         b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
 147         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
 148         y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
 149     ),
 150     "id-tc26-gost-3410-2012-256-paramSetA": GOST3410Curve(
 151         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 152         q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
 153         a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")),
 154         b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
 155         x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
 156         y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
 157     ),
 158     "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
 159         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 160         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
 161         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
 162         b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
 163         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
 164         y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
 165     ),
 166     "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
 167         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
 168         q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
 169         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
 170         b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
 171         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
 172         y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
 173     ),
 174     "id-tc26-gost-3410-2012-512-paramSetC": GOST3410Curve(
 175         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 176         q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
 177         a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
 178         b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
 179         x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
 180         y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
 181     ),
 182 }
 183 DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 184
 185
 186 def public_key(curve, prv):
 187     """ Generate public key from the private one
 188
 189     :param GOST3410Curve curve: curve to use
 190     :param long prv: private key
 191     :returns: public key's parts, X and Y
 192     :rtype: (long, long)
 193     """
 194     return curve.exp(prv)
 195
 196
 197 def sign(curve, prv, digest, mode=2001):
 198     """ Calculate signature for provided digest
 199
 200     :param GOST3410Curve curve: curve to use
 201     :param long prv: private key
 202     :param digest: digest for signing
 203     :type digest: bytes, 32 or 64 bytes
 204     :returns: signature
 205     :rtype: bytes, 64 or 128 bytes
 206     """
 207     size = MODE2SIZE[mode]
 208     q = curve.q
 209     e = bytes2long(digest) % q
 210     if e == 0:
 211         e = 1
 212     while True:
 213         k = bytes2long(urandom(size)) % q
 214         if k == 0:
 215             continue
 216         r, _ = curve.exp(k)
 217         r %= q
 218         if r == 0:
 219             continue
 220         d = prv * r
 221         k *= e
 222         s = (d + k) % q
 223         if s == 0:
 224             continue
 225         break
 226     return long2bytes(s, size) + long2bytes(r, size)
 227
 228
 229 def verify(curve, pub, digest, signature, mode=2001):
 230     """ Verify provided digest with the signature
 231
 232     :param GOST3410Curve curve: curve to use
 233     :type pub: (long, long)
 234     :param digest: digest needed to check
 235     :type digest: bytes, 32 or 64 bytes
 236     :param signature: signature to verify with
 237     :type signature: bytes, 64 or 128 bytes
 238     :rtype: bool
 239     """
 240     size = MODE2SIZE[mode]
 241     if len(signature) != size * 2:
 242         raise ValueError("Invalid signature length")
 243     q = curve.q
 244     p = curve.p
 245     s = bytes2long(signature[:size])
 246     r = bytes2long(signature[size:])
 247     if r <= 0 or r >= q or s <= 0 or s >= q:
 248         return False
 249     e = bytes2long(digest) % curve.q
 250     if e == 0:
 251         e = 1
 252     v = modinvert(e, q)
 253     z1 = s * v % q
 254     z2 = q - r * v % q
 255     p1x, p1y = curve.exp(z1)
 256     q1x, q1y = curve.exp(z2, pub[0], pub[1])
 257     lm = q1x - p1x
 258     if lm < 0:
 259         lm += p
 260     lm = modinvert(lm, p)
 261     z1 = q1y - p1y
 262     lm = lm * z1 % p
 263     lm = lm * lm % p
 264     lm = lm - p1x - q1x
 265     lm = lm % p
 266     if lm < 0:
 267         lm += p
 268     lm %= q
 269     # This is not constant time comparison!
 270     return lm == r
 271
 272
 273 def prv_unmarshal(prv):
 274     """Unmarshal private key
 275
 276     :param bytes prv: serialized private key
 277     :rtype: long
 278     """
 279     return bytes2long(prv[::-1])
 280
 281
 282 def pub_marshal(pub, mode=2001):
 283     """Marshal public key
 284
 285     :type pub: (long, long)
 286     :rtype: bytes
 287     """
 288     size = MODE2SIZE[mode]
 289     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 290
 291
 292 def pub_unmarshal(pub, mode=2001):
 293     """Unmarshal public key
 294
 295     :type pub: bytes
 296     :rtype: (long, long)
 297     """
 298     size = MODE2SIZE[mode]
 299     pub = pub[::-1]
 300     return (bytes2long(pub[size:]), bytes2long(pub[:size]))