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, cofactor=1, 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.cofactor = cofactor
  65         self.e = e
  66         self.d = d
  67         r1 = self.y * self.y % self.p
  68         r2 = ((self.x * self.x + self.a) * self.x + self.b) % self.p
  69         if r1 != self.pos(r2):
  70             raise ValueError("Invalid parameters")
  71         self._st = None
  72
  73     def pos(self, v):
  74         """Make positive number
  75         """
  76         if v < 0:
  77             return v + self.p
  78         return v
  79
  80     def _add(self, p1x, p1y, p2x, p2y):
  81         if p1x == p2x and p1y == p2y:
  82             # double
  83             t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
  84         else:
  85             tx = self.pos(p2x - p1x) % self.p
  86             ty = self.pos(p2y - p1y) % self.p
  87             t = (ty * modinvert(tx, self.p)) % self.p
  88         tx = self.pos(t * t - p1x - p2x) % self.p
  89         ty = self.pos(t * (p1x - tx) - p1y) % self.p
  90         return tx, ty
  91
  92     def exp(self, degree, x=None, y=None):
  93         x = x or self.x
  94         y = y or self.y
  95         tx = x
  96         ty = y
  97         if degree == 0:
  98             raise ValueError("Bad degree value")
  99         degree -= 1
 100         while degree != 0:
 101             if degree & 1 == 1:
 102                 tx, ty = self._add(tx, ty, x, y)
 103             degree = degree >> 1
 104             x, y = self._add(x, y, x, y)
 105         return tx, ty
 106
 107     def st(self):
 108         """Compute s/t parameters for twisted Edwards curve points conversion
 109         """
 110         if self.e is None or self.d is None:
 111             raise ValueError("non twisted Edwards curve")
 112         if self._st is not None:
 113             return self._st
 114         self._st = (
 115             self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
 116             (self.e + self.d) * modinvert(6, self.p) % self.p,
 117         )
 118         return self._st
 119
 120
 121 CURVES = {
 122     "GostR3410_2001_ParamSet_cc": GOST3410Curve(
 123         p=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003C7")),
 124         q=bytes2long(hexdec("5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85")),
 125         a=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003c4")),
 126         b=bytes2long(hexdec("2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c")),
 127         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 128         y=bytes2long(hexdec("a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c")),
 129     ),
 130     "id-GostR3410-2001-TestParamSet": GOST3410Curve(
 131         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000431")),
 132         q=bytes2long(hexdec("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3")),
 133         a=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000007")),
 134         b=bytes2long(hexdec("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E")),
 135         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
 136         y=bytes2long(hexdec("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8")),
 137     ),
 138     "id-GostR3410-2001-CryptoPro-A-ParamSet": GOST3410Curve(
 139         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 140         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
 141         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
 142         b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
 143         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 144         y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
 145     ),
 146     "id-GostR3410-2001-CryptoPro-B-ParamSet": GOST3410Curve(
 147         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C99")),
 148         q=bytes2long(hexdec("800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F")),
 149         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C96")),
 150         b=bytes2long(hexdec("3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B")),
 151         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
 152         y=bytes2long(hexdec("3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC")),
 153     ),
 154     "id-GostR3410-2001-CryptoPro-C-ParamSet": GOST3410Curve(
 155         p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
 156         q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
 157         a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
 158         b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
 159         x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
 160         y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
 161     ),
 162     "id-tc26-gost-3410-2012-256-paramSetA": GOST3410Curve(
 163         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
 164         q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
 165         a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")),
 166         b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
 167         x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
 168         y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
 169         cofactor=4,
 170         e=0x01,
 171         d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
 172     ),
 173     "id-tc26-gost-3410-2012-512-paramSetTest": GOST3410Curve(
 174         p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
 175         q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
 176         a=7,
 177         b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
 178         x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
 179         y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
 180     ),
 181     "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
 182         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 183         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
 184         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
 185         b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
 186         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
 187         y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
 188     ),
 189     "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
 190         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
 191         q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
 192         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
 193         b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
 194         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
 195         y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
 196     ),
 197     "id-tc26-gost-3410-2012-512-paramSetC": GOST3410Curve(
 198         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 199         q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
 200         a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
 201         b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
 202         x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
 203         y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
 204         cofactor=4,
 205         e=0x01,
 206         d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
 207     ),
 208 }
 209 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 210 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
 211 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 212 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"]
 213 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
 214 DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 215
 216
 217 def public_key(curve, prv):
 218     """ Generate public key from the private one
 219
 220     :param GOST3410Curve curve: curve to use
 221     :param long prv: private key
 222     :returns: public key's parts, X and Y
 223     :rtype: (long, long)
 224     """
 225     return curve.exp(prv)
 226
 227
 228 def sign(curve, prv, digest, rand=None, mode=2001):
 229     """ Calculate signature for provided digest
 230
 231     :param GOST3410Curve curve: curve to use
 232     :param long prv: private key
 233     :param digest: digest for signing
 234     :type digest: bytes, 32 or 64 bytes
 235     :param rand: optional predefined random data used for k/r generation
 236     :type rand: bytes, 32 or 64 bytes
 237     :returns: signature, BE(S) || BE(R)
 238     :rtype: bytes, 64 or 128 bytes
 239     """
 240     size = MODE2SIZE[mode]
 241     q = curve.q
 242     e = bytes2long(digest) % q
 243     if e == 0:
 244         e = 1
 245     while True:
 246         if rand is None:
 247             rand = urandom(size)
 248         elif len(rand) != size:
 249             raise ValueError("rand length != %d" % size)
 250         k = bytes2long(rand) % q
 251         if k == 0:
 252             continue
 253         r, _ = curve.exp(k)
 254         r %= q
 255         if r == 0:
 256             continue
 257         d = prv * r
 258         k *= e
 259         s = (d + k) % q
 260         if s == 0:
 261             continue
 262         break
 263     return long2bytes(s, size) + long2bytes(r, size)
 264
 265
 266 def verify(curve, pub, digest, signature, mode=2001):
 267     """ Verify provided digest with the signature
 268
 269     :param GOST3410Curve curve: curve to use
 270     :type pub: (long, long)
 271     :param digest: digest needed to check
 272     :type digest: bytes, 32 or 64 bytes
 273     :param signature: signature to verify with
 274     :type signature: bytes, 64 or 128 bytes
 275     :rtype: bool
 276     """
 277     size = MODE2SIZE[mode]
 278     if len(signature) != size * 2:
 279         raise ValueError("Invalid signature length")
 280     q = curve.q
 281     p = curve.p
 282     s = bytes2long(signature[:size])
 283     r = bytes2long(signature[size:])
 284     if r <= 0 or r >= q or s <= 0 or s >= q:
 285         return False
 286     e = bytes2long(digest) % curve.q
 287     if e == 0:
 288         e = 1
 289     v = modinvert(e, q)
 290     z1 = s * v % q
 291     z2 = q - r * v % q
 292     p1x, p1y = curve.exp(z1)
 293     q1x, q1y = curve.exp(z2, pub[0], pub[1])
 294     lm = q1x - p1x
 295     if lm < 0:
 296         lm += p
 297     lm = modinvert(lm, p)
 298     z1 = q1y - p1y
 299     lm = lm * z1 % p
 300     lm = lm * lm % p
 301     lm = lm - p1x - q1x
 302     lm = lm % p
 303     if lm < 0:
 304         lm += p
 305     lm %= q
 306     # This is not constant time comparison!
 307     return lm == r
 308
 309
 310 def prv_unmarshal(prv):
 311     """Unmarshal little-endian private key
 312
 313     :param bytes prv: serialized private key
 314     :rtype: long
 315     """
 316     return bytes2long(prv[::-1])
 317
 318
 319 def pub_marshal(pub, mode=2001):
 320     """Marshal public key
 321
 322     :type pub: (long, long)
 323     :rtype: bytes
 324     :returns: LE(X) || LE(Y)
 325     """
 326     size = MODE2SIZE[mode]
 327     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 328
 329
 330 def pub_unmarshal(pub, mode=2001):
 331     """Unmarshal public key
 332
 333     :param pub: LE(X) || LE(Y)
 334     :type pub: bytes
 335     :rtype: (long, long)
 336     """
 337     size = MODE2SIZE[mode]
 338     pub = pub[::-1]
 339     return (bytes2long(pub[size:]), bytes2long(pub[:size]))
 340
 341
 342 def uv2xy(curve, u, v):
 343     """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
 344     """
 345     s, t = curve.st()
 346     k1 = (s * (1 + v)) % curve.p
 347     k2 = curve.pos(1 - v)
 348     x = t + k1 * modinvert(k2, curve.p)
 349     y = k1 * modinvert(u * k2, curve.p)
 350     return x % curve.p, y % curve.p
 351
 352
 353 def xy2uv(curve, x, y):
 354     """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
 355     """
 356     s, t = curve.st()
 357     xmt = curve.pos(x - t)
 358     u = xmt * modinvert(y, curve.p)
 359     v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
 360     return u % curve.p, v % curve.p