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