2 # PyGOST -- Pure Python GOST cryptographic functions library
3 # Copyright (C) 2015-2023 Sergey Matveev <stargrave@stargrave.org>
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.
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.
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.
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.
23 from os import urandom
25 from pygost.utils import bytes2long
26 from pygost.utils import hexdec
27 from pygost.utils import long2bytes
28 from pygost.utils import modinvert
31 def point_size(point):
32 """Determine is it either 256 or 512 bit point
34 return (512 // 8) if point.bit_length() > 256 else (256 // 8)
37 class GOST3410Curve(object):
38 """GOST 34.10 validated curve
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)
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
51 :param long x, y: the coordinate of the point P (generator of the
52 subgroup of order q) of the elliptic curve in
54 :param long e, d: coefficients of the equation of the elliptic curve in
55 the twisted Edwards form
56 :param str name: human-readable curve name
59 def __init__(self, p, q, a, b, x, y, cofactor=1, e=None, d=None, name=None):
66 self.cofactor = cofactor
69 if not self.contains((x, y)):
70 raise ValueError("Invalid parameters")
76 return point_size(self.p)
79 return "<%s: %s>" % (self.__class__.__name__, self.name)
82 """Make positive number
88 def contains(self, point):
89 """Is point on the curve?
91 :type point: (long, long)
95 r2 = ((x * x + self.a) * x + self.b) % self.p
96 return r1 == self.pos(r2)
98 def _add(self, p1x, p1y, p2x, p2y):
99 if p1x == p2x and p1y == p2y:
101 t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
103 tx = self.pos(p2x - p1x) % self.p
104 ty = self.pos(p2y - p1y) % self.p
105 t = (ty * modinvert(tx, self.p)) % self.p
106 tx = self.pos(t * t - p1x - p2x) % self.p
107 ty = self.pos(t * (p1x - tx) - p1y) % self.p
110 def exp(self, degree, x=None, y=None):
116 raise ValueError("Bad degree value")
120 tx, ty = self._add(tx, ty, x, y)
122 x, y = self._add(x, y, x, y)
126 """Compute s/t parameters for twisted Edwards curve points conversion
128 if self.e is None or self.d is None:
129 raise ValueError("Non twisted Edwards curve")
130 if self._st is not None:
133 self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
134 (self.e + self.d) * modinvert(6, self.p) % self.p,
140 "GostR3410_2001_ParamSet_cc": GOST3410Curve(
141 p=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003C7")),
142 q=bytes2long(hexdec("5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85")),
143 a=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003c4")),
144 b=bytes2long(hexdec("2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c")),
145 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
146 y=bytes2long(hexdec("a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c")),
148 "id-GostR3410-2001-TestParamSet": GOST3410Curve(
149 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000431")),
150 q=bytes2long(hexdec("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3")),
151 a=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000007")),
152 b=bytes2long(hexdec("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E")),
153 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
154 y=bytes2long(hexdec("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8")),
156 "id-tc26-gost-3410-12-256-paramSetA": GOST3410Curve(
157 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
158 q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
159 a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")),
160 b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
161 x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
162 y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
165 d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
167 "id-tc26-gost-3410-12-256-paramSetB": GOST3410Curve(
168 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
169 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
170 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
171 b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
172 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
173 y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
175 "id-tc26-gost-3410-12-256-paramSetC": GOST3410Curve(
176 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C99")),
177 q=bytes2long(hexdec("800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F")),
178 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C96")),
179 b=bytes2long(hexdec("3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B")),
180 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
181 y=bytes2long(hexdec("3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC")),
183 "id-tc26-gost-3410-12-256-paramSetD": GOST3410Curve(
184 p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
185 q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
186 a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
187 b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
188 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
189 y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
191 "id-tc26-gost-3410-12-512-paramSetTest": GOST3410Curve(
192 p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
193 q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
195 b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
196 x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
197 y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
199 "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
200 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
201 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
202 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
203 b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
204 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
205 y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
207 "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
208 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
209 q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
210 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
211 b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
212 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
213 y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
215 "id-tc26-gost-3410-12-512-paramSetC": GOST3410Curve(
216 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
217 q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
218 a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
219 b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
220 x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
221 y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
224 d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
227 CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
228 CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetC"]
229 CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetD"]
230 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
231 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
232 CURVES["id-tc26-gost-3410-2012-256-paramSetA"] = CURVES["id-tc26-gost-3410-12-256-paramSetA"]
233 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
234 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-tc26-gost-3410-12-256-paramSetC"]
235 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-tc26-gost-3410-12-256-paramSetD"]
236 CURVES["id-tc26-gost-3410-2012-512-paramSetTest"] = CURVES["id-tc26-gost-3410-12-512-paramSetTest"]
237 CURVES["id-tc26-gost-3410-2012-512-paramSetA"] = CURVES["id-tc26-gost-3410-12-512-paramSetA"]
238 CURVES["id-tc26-gost-3410-2012-512-paramSetB"] = CURVES["id-tc26-gost-3410-12-512-paramSetB"]
239 CURVES["id-tc26-gost-3410-2012-512-paramSetC"] = CURVES["id-tc26-gost-3410-12-512-paramSetC"]
240 for _name, _curve in CURVES.items():
242 DEFAULT_CURVE = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
245 def public_key(curve, prv, mask=None):
246 """Generate public key from the private one
248 :param GOST3410Curve curve: curve to use
249 :param long prv: private key
250 :returns: public key's parts, X and Y
255 pub = curve.exp(mask, pub[0], pub[1])
259 def sign(curve, prv, digest, rand=None, mask=None):
260 """Calculate signature for provided digest
262 :param GOST3410Curve curve: curve to use
263 :param long prv: private key
264 :param digest: digest for signing
265 :type digest: bytes, 32 or 64 bytes
266 :param rand: optional predefined random data used for k/r generation
267 :type rand: bytes, 32 or 64 bytes
268 :returns: signature, BE(S) || BE(R)
269 :rtype: bytes, 64 or 128 bytes
271 size = curve.point_size
273 e = bytes2long(digest) % q
279 elif len(rand) != size:
280 raise ValueError("rand length != %d" % size)
281 k = bytes2long(rand) % q
286 r, y = curve.exp(mask, x=r, y=y)
299 return long2bytes(s, size) + long2bytes(r, size)
302 def verify(curve, pub, digest, signature):
303 """Verify provided digest with the signature
305 :param GOST3410Curve curve: curve to use
306 :type pub: (long, long)
307 :param digest: digest needed to check
308 :type digest: bytes, 32 or 64 bytes
309 :param signature: signature to verify with
310 :type signature: bytes, 64 or 128 bytes
313 size = curve.point_size
314 if len(signature) != size * 2:
315 raise ValueError("Invalid signature length")
318 s = bytes2long(signature[:size])
319 r = bytes2long(signature[size:])
320 if r <= 0 or r >= q or s <= 0 or s >= q:
322 e = bytes2long(digest) % curve.q
328 p1x, p1y = curve.exp(z1)
329 q1x, q1y = curve.exp(z2, pub[0], pub[1])
333 lm = modinvert(lm, p)
342 # This is not constant time comparison!
346 def prv_unmarshal(prv):
347 """Unmarshal little-endian private key
349 :param bytes prv: serialized private key
352 It is advisable to use :py:func:`pygost.gost3410.prv_marshal` to
353 assure that key i in curve's Q field for better compatibility with
354 some implementations.
356 return bytes2long(prv[::-1])
359 def prv_marshal(curve, prv):
360 """Marshal little-endian private key
362 :param GOST3410Curve curve: curve to use
363 :param long prv: serialized private key
366 Key is in curve's Q field.
368 return long2bytes(prv % curve.q, point_size(prv))[::-1]
371 def pub_marshal(pub):
372 """Marshal public key
374 :type pub: (long, long)
376 :returns: LE(X) || LE(Y)
378 size = point_size(pub[0])
379 return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
382 def pub_unmarshal(pub):
383 """Unmarshal public key
385 :param pub: LE(X) || LE(Y)
391 return (bytes2long(pub[size:]), bytes2long(pub[:size]))
394 def uv2xy(curve, u, v):
395 """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
398 k1 = (s * (1 + v)) % curve.p
399 k2 = curve.pos(1 - v)
400 x = t + k1 * modinvert(k2, curve.p)
401 y = k1 * modinvert(u * k2, curve.p)
402 return x % curve.p, y % curve.p
405 def xy2uv(curve, x, y):
406 """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
409 xmt = curve.pos(x - t)
410 u = xmt * modinvert(y, curve.p)
411 v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
412 return u % curve.p, v % curve.p