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-2012-512-paramSetTest": GOST3410Curve(
 172         p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
 173         q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
 174         a=7,
 175         b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
 176         x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
 177         y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
 178     ),
 179     "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
 180         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 181         q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
 182         a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
 183         b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
 184         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
 185         y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
 186     ),
 187     "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
 188         p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
 189         q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
 190         a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
 191         b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
 192         x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
 193         y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
 194     ),
 195     "id-tc26-gost-3410-2012-512-paramSetC": GOST3410Curve(
 196         p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
 197         q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
 198         a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
 199         b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
 200         x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
 201         y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
 202         e=0x01,
 203         d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
 204     ),
 205 }
 206 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 207 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
 208 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 209 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"]
 210 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
 211 DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
 212
 213
 214 def public_key(curve, prv):
 215     """ Generate public key from the private one
 216
 217     :param GOST3410Curve curve: curve to use
 218     :param long prv: private key
 219     :returns: public key's parts, X and Y
 220     :rtype: (long, long)
 221     """
 222     return curve.exp(prv)
 223
 224
 225 def sign(curve, prv, digest, rand=None, mode=2001):
 226     """ Calculate signature for provided digest
 227
 228     :param GOST3410Curve curve: curve to use
 229     :param long prv: private key
 230     :param digest: digest for signing
 231     :type digest: bytes, 32 or 64 bytes
 232     :param rand: optional predefined random data used for k/r generation
 233     :type rand: bytes, 32 or 64 bytes
 234     :returns: signature, BE(S) || BE(R)
 235     :rtype: bytes, 64 or 128 bytes
 236     """
 237     size = MODE2SIZE[mode]
 238     q = curve.q
 239     e = bytes2long(digest) % q
 240     if e == 0:
 241         e = 1
 242     while True:
 243         if rand is None:
 244             rand = urandom(size)
 245         elif len(rand) != size:
 246             raise ValueError("rand length != %d" % size)
 247         k = bytes2long(rand) % q
 248         if k == 0:
 249             continue
 250         r, _ = curve.exp(k)
 251         r %= q
 252         if r == 0:
 253             continue
 254         d = prv * r
 255         k *= e
 256         s = (d + k) % q
 257         if s == 0:
 258             continue
 259         break
 260     return long2bytes(s, size) + long2bytes(r, size)
 261
 262
 263 def verify(curve, pub, digest, signature, mode=2001):
 264     """ Verify provided digest with the signature
 265
 266     :param GOST3410Curve curve: curve to use
 267     :type pub: (long, long)
 268     :param digest: digest needed to check
 269     :type digest: bytes, 32 or 64 bytes
 270     :param signature: signature to verify with
 271     :type signature: bytes, 64 or 128 bytes
 272     :rtype: bool
 273     """
 274     size = MODE2SIZE[mode]
 275     if len(signature) != size * 2:
 276         raise ValueError("Invalid signature length")
 277     q = curve.q
 278     p = curve.p
 279     s = bytes2long(signature[:size])
 280     r = bytes2long(signature[size:])
 281     if r <= 0 or r >= q or s <= 0 or s >= q:
 282         return False
 283     e = bytes2long(digest) % curve.q
 284     if e == 0:
 285         e = 1
 286     v = modinvert(e, q)
 287     z1 = s * v % q
 288     z2 = q - r * v % q
 289     p1x, p1y = curve.exp(z1)
 290     q1x, q1y = curve.exp(z2, pub[0], pub[1])
 291     lm = q1x - p1x
 292     if lm < 0:
 293         lm += p
 294     lm = modinvert(lm, p)
 295     z1 = q1y - p1y
 296     lm = lm * z1 % p
 297     lm = lm * lm % p
 298     lm = lm - p1x - q1x
 299     lm = lm % p
 300     if lm < 0:
 301         lm += p
 302     lm %= q
 303     # This is not constant time comparison!
 304     return lm == r
 305
 306
 307 def prv_unmarshal(prv):
 308     """Unmarshal little-endian private key
 309
 310     :param bytes prv: serialized private key
 311     :rtype: long
 312     """
 313     return bytes2long(prv[::-1])
 314
 315
 316 def pub_marshal(pub, mode=2001):
 317     """Marshal public key
 318
 319     :type pub: (long, long)
 320     :rtype: bytes
 321     :returns: LE(X) || LE(Y)
 322     """
 323     size = MODE2SIZE[mode]
 324     return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
 325
 326
 327 def pub_unmarshal(pub, mode=2001):
 328     """Unmarshal public key
 329
 330     :param pub: LE(X) || LE(Y)
 331     :type pub: bytes
 332     :rtype: (long, long)
 333     """
 334     size = MODE2SIZE[mode]
 335     pub = pub[::-1]
 336     return (bytes2long(pub[size:]), bytes2long(pub[:size]))
 337
 338
 339 def uv2xy(curve, u, v):
 340     """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
 341     """
 342     s, t = curve.st()
 343     k1 = (s * (1 + v)) % curve.p
 344     k2 = curve.pos(1 - v)
 345     x = t + k1 * modinvert(k2, curve.p)
 346     y = k1 * modinvert(u * k2, curve.p)
 347     return x % curve.p, y % curve.p
 348
 349
 350 def xy2uv(curve, x, y):
 351     """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
 352     """
 353     s, t = curve.st()
 354     xmt = curve.pos(x - t)
 355     u = xmt * modinvert(y, curve.p)
 356     v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
 357     return u % curve.p, v % curve.p