2 # PyGOST -- Pure Python GOST cryptographic functions library
3 # Copyright (C) 2015-2021 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
57 def __init__(self, p, q, a, b, x, y, cofactor=1, e=None, d=None):
64 self.cofactor = cofactor
67 if not self.contains((x, y)):
68 raise ValueError("Invalid parameters")
73 return point_size(self.p)
76 """Make positive number
82 def contains(self, point):
83 """Is point on the curve?
85 :type point: (long, long)
89 r2 = ((x * x + self.a) * x + self.b) % self.p
90 return r1 == self.pos(r2)
92 def _add(self, p1x, p1y, p2x, p2y):
93 if p1x == p2x and p1y == p2y:
95 t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
97 tx = self.pos(p2x - p1x) % self.p
98 ty = self.pos(p2y - p1y) % self.p
99 t = (ty * modinvert(tx, self.p)) % self.p
100 tx = self.pos(t * t - p1x - p2x) % self.p
101 ty = self.pos(t * (p1x - tx) - p1y) % self.p
104 def exp(self, degree, x=None, y=None):
110 raise ValueError("Bad degree value")
114 tx, ty = self._add(tx, ty, x, y)
116 x, y = self._add(x, y, x, y)
120 """Compute s/t parameters for twisted Edwards curve points conversion
122 if self.e is None or self.d is None:
123 raise ValueError("Non twisted Edwards curve")
124 if self._st is not None:
127 self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
128 (self.e + self.d) * modinvert(6, self.p) % self.p,
134 "GostR3410_2001_ParamSet_cc": GOST3410Curve(
135 p=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003C7")),
136 q=bytes2long(hexdec("5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85")),
137 a=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003c4")),
138 b=bytes2long(hexdec("2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c")),
139 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
140 y=bytes2long(hexdec("a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c")),
142 "id-GostR3410-2001-TestParamSet": GOST3410Curve(
143 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000431")),
144 q=bytes2long(hexdec("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3")),
145 a=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000007")),
146 b=bytes2long(hexdec("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E")),
147 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
148 y=bytes2long(hexdec("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8")),
150 "id-tc26-gost-3410-12-256-paramSetA": GOST3410Curve(
151 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
152 q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
153 a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")),
154 b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
155 x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
156 y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
159 d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
161 "id-tc26-gost-3410-12-256-paramSetB": GOST3410Curve(
162 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
163 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
164 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
165 b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
166 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
167 y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
169 "id-tc26-gost-3410-12-256-paramSetC": GOST3410Curve(
170 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C99")),
171 q=bytes2long(hexdec("800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F")),
172 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C96")),
173 b=bytes2long(hexdec("3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B")),
174 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
175 y=bytes2long(hexdec("3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC")),
177 "id-tc26-gost-3410-12-256-paramSetD": GOST3410Curve(
178 p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
179 q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
180 a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
181 b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
182 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
183 y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
185 "id-tc26-gost-3410-12-512-paramSetTest": GOST3410Curve(
186 p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
187 q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
189 b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
190 x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
191 y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
193 "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
194 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
195 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
196 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
197 b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
198 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
199 y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
201 "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
202 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
203 q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
204 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
205 b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
206 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
207 y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
209 "id-tc26-gost-3410-12-512-paramSetC": GOST3410Curve(
210 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
211 q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
212 a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
213 b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
214 x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
215 y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
218 d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
221 CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
222 CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetC"]
223 CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"] = CURVES["id-tc26-gost-3410-12-256-paramSetD"]
224 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
225 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
226 CURVES["id-tc26-gost-3410-2012-256-paramSetA"] = CURVES["id-tc26-gost-3410-12-256-paramSetA"]
227 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
228 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-tc26-gost-3410-12-256-paramSetC"]
229 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-tc26-gost-3410-12-256-paramSetD"]
230 CURVES["id-tc26-gost-3410-2012-512-paramSetTest"] = CURVES["id-tc26-gost-3410-12-512-paramSetTest"]
231 CURVES["id-tc26-gost-3410-2012-512-paramSetA"] = CURVES["id-tc26-gost-3410-12-512-paramSetA"]
232 CURVES["id-tc26-gost-3410-2012-512-paramSetB"] = CURVES["id-tc26-gost-3410-12-512-paramSetB"]
233 CURVES["id-tc26-gost-3410-2012-512-paramSetC"] = CURVES["id-tc26-gost-3410-12-512-paramSetC"]
234 DEFAULT_CURVE = CURVES["id-tc26-gost-3410-12-256-paramSetB"]
237 def public_key(curve, prv):
238 """Generate public key from the private one
240 :param GOST3410Curve curve: curve to use
241 :param long prv: private key
242 :returns: public key's parts, X and Y
245 return curve.exp(prv)
248 def sign(curve, prv, digest, rand=None):
249 """Calculate signature for provided digest
251 :param GOST3410Curve curve: curve to use
252 :param long prv: private key
253 :param digest: digest for signing
254 :type digest: bytes, 32 or 64 bytes
255 :param rand: optional predefined random data used for k/r generation
256 :type rand: bytes, 32 or 64 bytes
257 :returns: signature, BE(S) || BE(R)
258 :rtype: bytes, 64 or 128 bytes
260 size = curve.point_size
262 e = bytes2long(digest) % q
268 elif len(rand) != size:
269 raise ValueError("rand length != %d" % size)
270 k = bytes2long(rand) % q
283 return long2bytes(s, size) + long2bytes(r, size)
286 def verify(curve, pub, digest, signature):
287 """Verify provided digest with the signature
289 :param GOST3410Curve curve: curve to use
290 :type pub: (long, long)
291 :param digest: digest needed to check
292 :type digest: bytes, 32 or 64 bytes
293 :param signature: signature to verify with
294 :type signature: bytes, 64 or 128 bytes
297 size = curve.point_size
298 if len(signature) != size * 2:
299 raise ValueError("Invalid signature length")
302 s = bytes2long(signature[:size])
303 r = bytes2long(signature[size:])
304 if r <= 0 or r >= q or s <= 0 or s >= q:
306 e = bytes2long(digest) % curve.q
312 p1x, p1y = curve.exp(z1)
313 q1x, q1y = curve.exp(z2, pub[0], pub[1])
317 lm = modinvert(lm, p)
326 # This is not constant time comparison!
330 def prv_unmarshal(prv):
331 """Unmarshal little-endian private key
333 :param bytes prv: serialized private key
336 It is advisable to use :py:func:`pygost.gost3410.prv_marshal` to
337 assure that key i in curve's Q field for better compatibility with
338 some implementations.
340 return bytes2long(prv[::-1])
343 def prv_marshal(curve, prv):
344 """Marshal little-endian private key
346 :param GOST3410Curve curve: curve to use
347 :param long prv: serialized private key
350 Key is in curve's Q field.
352 return long2bytes(prv % curve.q, point_size(prv))[::-1]
355 def pub_marshal(pub):
356 """Marshal public key
358 :type pub: (long, long)
360 :returns: LE(X) || LE(Y)
362 size = point_size(pub[0])
363 return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
366 def pub_unmarshal(pub):
367 """Unmarshal public key
369 :param pub: LE(X) || LE(Y)
375 return (bytes2long(pub[size:]), bytes2long(pub[:size]))
378 def uv2xy(curve, u, v):
379 """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
382 k1 = (s * (1 + v)) % curve.p
383 k2 = curve.pos(1 - v)
384 x = t + k1 * modinvert(k2, curve.p)
385 y = k1 * modinvert(u * k2, curve.p)
386 return x % curve.p, y % curve.p
389 def xy2uv(curve, x, y):
390 """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
393 xmt = curve.pos(x - t)
394 u = xmt * modinvert(y, curve.p)
395 v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
396 return u % curve.p, v % curve.p