pygost/gost3410.py

   1 # coding: utf-8
   2 # PyGOST -- Pure Python GOST cryptographic functions library
   3 # Copyright (C) 2015-2020 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, version 3 of the License.
   8 #
   9 # This program is distributed in the hope that it will be useful,
  10 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 # GNU General Public License for more details.
  13 #
  14 # You should have received a copy of the GNU General Public License
  15 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  16 """ GOST R 34.10 public-key signature function.
  17
  18 This is implementation of GOST R 34.10-2001 (:rfc:`5832`), GOST R
  19 34.10-2012 (:rfc:`7091`). The difference between 2001 and 2012 is the
  20 key, digest and signature lengths.
  21 """
  22
  23 from os import urandom
  24
  25 from pygost.utils import bytes2long
  26 from pygost.utils import hexdec
  27 from pygost.utils import long2bytes
  28 from pygost.utils import modinvert
  29
  30
  31 MODE2SIZE = {
  32     2001: 32,
  33     2012: 64,
  34 }
  35
  36
  37 class GOST3410Curve(object):
  38     """ GOST 34.10 validated curve
  39
  40     >>> curve = CURVES["id-GostR3410-2001-TestParamSet"]
  41     >>> prv = prv_unmarshal(urandom(32))
  42     >>> signature = sign(curve, prv, GOST341194(data).digest())
  43     >>> pub = public_key(curve, prv)
  44     >>> verify(curve, pub, GOST341194(data).digest(), signature)
  45     True
  46
  47     :param long p: characteristic of the underlying prime field
  48     :param long q: elliptic curve subgroup order
  49     :param long a, b: coefficients of the equation of the elliptic curve in
  50                       the canonical form
  51     :param long x, y: the coordinate of the point P (generator of the
  52                       subgroup of order q) of the elliptic curve in
  53                       the canonical form
  54     :param long e, d: coefficients of the equation of the elliptic curve in
  55                       the twisted Edwards form
  56     """
  57     def __init__(self, p, q, a, b, x, y, e=None, d=None):
  58         self.p = p
  59         self.q = q
  60         self.a = a
  61         self.b = b
  62         self.x = x
  63         self.y = y
  64         self.e = e
  65         self.d = d
  66         r1 = self.y * self.y % self.p
  67         r2 = ((self.x * self.x + self.a) * self.x + self.b) % self.p
  68         if r1 != self.pos(r2):
  69             raise ValueError("Invalid parameters")
  70         self._st = None
  71
  72     def pos(self, v):
  73         """Make positive number
  74         """
  75         if v < 0:
  76             return v + self.p
  77         return v
  78
  79     def _add(self, p1x, p1y, p2x, p2y):
  80         if p1x == p2x and p1y == p2y:
  81             # double
  82             t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
  83         else:
  84             tx = self.pos(p2x - p1x) % self.p
  85             ty = self.pos(p2y - p1y) % self.p
  86             t = (ty * modinvert(tx, self.p)) % self.p
  87         tx = self.pos(t * t - p1x - p2x) % self.p
  88         ty = self.pos(t * (p1x - tx) - p1y) % self.p
  89         return tx, ty
  90
  91     def exp(self, degree, x=None, y=None):
  92         x = x or self.x
  93         y = y or self.y
  94         tx = x
  95         ty = y
  96         if degree == 0:
  97             raise ValueError("Bad degree value")
  98         degree -= 1
  99         while degree != 0:
 100             if degree & 1 == 1:
 101                 tx, ty = self._add(tx, ty, x, y)
 102             degree = degree >> 1
 103             x, y = self._add(x, y, x, y)
 104         return tx, ty
 105
 106     def st(self):
 107         """Compute s/t parameters for twisted Edwards curve points conversion
 108         """
 109         if self.e is None or self.d is None:
 110             raise ValueError("non twisted Edwards curve")
 111         if self._st is not None:
 112             return self._st
 113         self._st = (
 114             self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
 115             (self.e + self.d) * modinvert(6, self.p) % self.p,
 116         )
 117         return self._st
 118
 119
 120 CURVES = {
 121     "GostR3410_2001_ParamSet_cc": GOST3410Curve(
 122         p=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003C7")),
 123         q=bytes2long(hexdec("5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85")),
 124         a=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003c4")),
 125         b=bytes2long(hexdec("2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c")),
 126         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 127         y=bytes2long(hexdec("a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c")),
 128     ),
 129     "id-GostR3410-2001-TestParamSet": GOST3410Curve(
 130         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000431")),
 131         q=bytes2long(hexdec("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3")),
 132         a=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000007")),
 133         b=bytes2long(hexdec("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E")),
 134         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 135         y=bytes2long(hexdec("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8")),
 136     ),
 137     "id-GostR3410-2001-CryptoPro-A-ParamSet": GOST3410Curve(
 138         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 139         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
 140         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
 141         b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
 142         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 143         y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
 144     ),
 145     "id-GostR3410-2001-CryptoPro-B-ParamSet": GOST3410Curve(
 146         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C99")),
 147         q=bytes2long(hexdec("800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F")),
 148         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C96")),
 149         b=bytes2long(hexdec("3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B")),
 150         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 151         y=bytes2long(hexdec("3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC")),
 152     ),
 153     "id-GostR3410-2001-CryptoPro-C-ParamSet": GOST3410Curve(
 154         p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
 155         q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
 156         a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
 157         b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
 158         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
 159         y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
 160     ),
 161     "id-tc26-gost-3410-2012-256-paramSetA": GOST3410Curve(
 162         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 163         q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
 164         a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")),
 165         b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
 166         x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
 167         y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
 168         e=0x01,
 169         d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
 170     ),
 171     "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
 172         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 173         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
 174         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
 175         b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
 176         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
 177         y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
 178     ),
 179     "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
 180         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
 181         q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
 182         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
 183         b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
 184         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
 185         y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
 186     ),
 187     "id-tc26-gost-3410-2012-512-paramSetC": GOST3410Curve(
 188         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 189         q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
 190         a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
 191         b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
 192         x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
 193         y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
 194         e=0x01,
 195         d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
 196     ),
 197 }
 198 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 199 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
 200 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 201 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"]
 202 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
 203 DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 204
 205
 206 def public_key(curve, prv):
 207     """ Generate public key from the private one
 208
 209     :param GOST3410Curve curve: curve to use
 210     :param long prv: private key
 211     :returns: public key's parts, X and Y
 212     :rtype: (long, long)
 213     """
 214     return curve.exp(prv)
 215
 216
 217 def sign(curve, prv, digest, rand=None, mode=2001):
 218     """ Calculate signature for provided digest
 219
 220     :param GOST3410Curve curve: curve to use
 221     :param long prv: private key
 222     :param digest: digest for signing
 223     :type digest: bytes, 32 or 64 bytes
 224     :param rand: optional predefined random data used for k/r generation
 225     :type rand: bytes, 32 or 64 bytes
 226     :returns: signature
 227     :rtype: bytes, 64 or 128 bytes
 228     """
 229     size = MODE2SIZE[mode]
 230     q = curve.q
 231     e = bytes2long(digest) % q
 232     if e == 0:
 233         e = 1
 234     while True:
 235         if rand is None:
 236             rand = urandom(size)
 237         elif len(rand) != size:
 238             raise ValueError("rand length != %d" % size)
 239         k = bytes2long(rand) % q
 240         if k == 0:
 241             continue
 242         r, _ = curve.exp(k)
 243         r %= q
 244         if r == 0:
 245             continue
 246         d = prv * r
 247         k *= e
 248         s = (d + k) % q
 249         if s == 0:
 250             continue
 251         break
 252     return long2bytes(s, size) + long2bytes(r, size)
 253
 254
 255 def verify(curve, pub, digest, signature, mode=2001):
 256     """ Verify provided digest with the signature
 257
 258     :param GOST3410Curve curve: curve to use
 259     :type pub: (long, long)
 260     :param digest: digest needed to check
 261     :type digest: bytes, 32 or 64 bytes
 262     :param signature: signature to verify with
 263     :type signature: bytes, 64 or 128 bytes
 264     :rtype: bool
 265     """
 266     size = MODE2SIZE[mode]
 267     if len(signature) != size * 2:
 268         raise ValueError("Invalid signature length")
 269     q = curve.q
 270     p = curve.p
 271     s = bytes2long(signature[:size])
 272     r = bytes2long(signature[size:])
 273     if r <= 0 or r >= q or s <= 0 or s >= q:
 274         return False
 275     e = bytes2long(digest) % curve.q
 276     if e == 0:
 277         e = 1
 278     v = modinvert(e, q)
 279     z1 = s * v % q
 280     z2 = q - r * v % q
 281     p1x, p1y = curve.exp(z1)
 282     q1x, q1y = curve.exp(z2, pub[0], pub[1])
 283     lm = q1x - p1x
 284     if lm < 0:
 285         lm += p
 286     lm = modinvert(lm, p)
 287     z1 = q1y - p1y
 288     lm = lm * z1 % p
 289     lm = lm * lm % p
 290     lm = lm - p1x - q1x
 291     lm = lm % p
 292     if lm < 0:
 293         lm += p
 294     lm %= q
 295     # This is not constant time comparison!
 296     return lm == r
 297
 298
 299 def prv_unmarshal(prv):
 300     """Unmarshal private key
 301
 302     :param bytes prv: serialized private key
 303     :rtype: long
 304     """
 305     return bytes2long(prv[::-1])
 306
 307
 308 def pub_marshal(pub, mode=2001):
 309     """Marshal public key
 310
 311     :type pub: (long, long)
 312     :rtype: bytes
 313     """
 314     size = MODE2SIZE[mode]
 315     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 316
 317
 318 def pub_unmarshal(pub, mode=2001):
 319     """Unmarshal public key
 320
 321     :type pub: bytes
 322     :rtype: (long, long)
 323     """
 324     size = MODE2SIZE[mode]
 325     pub = pub[::-1]
 326     return (bytes2long(pub[size:]), bytes2long(pub[:size]))
 327
 328
 329 def uv2xy(curve, u, v):
 330     """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
 331     """
 332     s, t = curve.st()
 333     k1 = (s * (1 + v)) % curve.p
 334     k2 = curve.pos(1 - v)
 335     x = t + k1 * modinvert(k2, curve.p)
 336     y = k1 * modinvert(u * k2, curve.p)
 337     return x % curve.p, y % curve.p
 338
 339
 340 def xy2uv(curve, x, y):
 341     """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
 342     """
 343     s, t = curve.st()
 344     xmt = curve.pos(x - t)
 345     u = xmt * modinvert(y, curve.p)
 346     v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
 347     return u % curve.p, v % curve.p