2 # PyGOST -- Pure Python GOST cryptographic functions library
3 # Copyright (C) 2015-2019 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, either version 3 of the License, or
8 # (at your option) any later version.
10 # This program is distributed in the hope that it will be useful,
11 # but WITHOUT ANY WARRANTY; without even the implied warranty of
12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 # GNU General Public License for more details.
15 # You should have received a copy of the GNU General Public License
16 # along with this program. If not, see <http://www.gnu.org/licenses/>.
17 """ GOST R 34.10 public-key signature function.
19 This is implementation of GOST R 34.10-2001 (:rfc:`5832`), GOST R
20 34.10-2012 (:rfc:`7091`). The difference between 2001 and 2012 is the
21 key, digest and signature lengths.
24 from os import urandom
26 from pygost.utils import bytes2long
27 from pygost.utils import hexdec
28 from pygost.utils import long2bytes
29 from pygost.utils import modinvert
38 class GOST3410Curve(object):
39 """ GOST 34.10 validated curve
41 >>> curve = CURVES["id-GostR3410-2001-TestParamSet"]
42 >>> prv = prv_unmarshal(urandom(32))
43 >>> signature = sign(curve, prv, GOST341194(data).digest())
44 >>> pub = public_key(curve, prv)
45 >>> verify(curve, pub, GOST341194(data).digest(), signature)
48 :param long p: characteristic of the underlying prime field
49 :param long q: elliptic curve subgroup order
50 :param long a, b: coefficients of the equation of the elliptic curve in
52 :param long x, y: the coordinate of the point P (generator of the
53 subgroup of order q) of the elliptic curve in
55 :param long e, d: coefficients of the equation of the elliptic curve in
56 the twisted Edwards form
58 def __init__(self, p, q, a, b, x, y, e=None, d=None):
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")
74 """Make positive number
80 def _add(self, p1x, p1y, p2x, p2y):
81 if p1x == p2x and p1y == p2y:
83 t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
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
92 def exp(self, degree, x=None, y=None):
98 raise ValueError("Bad degree value")
102 tx, ty = self._add(tx, ty, x, y)
104 x, y = self._add(x, y, x, y)
108 """Compute s/t parameters for twisted Edwards curve points conversion
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:
115 self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
116 (self.e + self.d) * modinvert(6, self.p) % self.p,
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")),
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")),
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")),
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")),
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")),
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")),
170 d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
172 "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
173 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
174 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
175 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
176 b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
177 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
178 y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
180 "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
181 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
182 q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
183 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
184 b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
185 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
186 y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
188 "id-tc26-gost-3410-2012-512-paramSetC": GOST3410Curve(
189 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
190 q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
191 a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
192 b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
193 x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
194 y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
196 d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
199 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
200 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
201 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
202 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"]
203 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
204 DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
207 def public_key(curve, prv):
208 """ Generate public key from the private one
210 :param GOST3410Curve curve: curve to use
211 :param long prv: private key
212 :returns: public key's parts, X and Y
215 return curve.exp(prv)
218 def sign(curve, prv, digest, mode=2001):
219 """ Calculate signature for provided digest
221 :param GOST3410Curve curve: curve to use
222 :param long prv: private key
223 :param digest: digest for signing
224 :type digest: bytes, 32 or 64 bytes
226 :rtype: bytes, 64 or 128 bytes
228 size = MODE2SIZE[mode]
230 e = bytes2long(digest) % q
234 k = bytes2long(urandom(size)) % q
247 return long2bytes(s, size) + long2bytes(r, size)
250 def verify(curve, pub, digest, signature, mode=2001):
251 """ Verify provided digest with the signature
253 :param GOST3410Curve curve: curve to use
254 :type pub: (long, long)
255 :param digest: digest needed to check
256 :type digest: bytes, 32 or 64 bytes
257 :param signature: signature to verify with
258 :type signature: bytes, 64 or 128 bytes
261 size = MODE2SIZE[mode]
262 if len(signature) != size * 2:
263 raise ValueError("Invalid signature length")
266 s = bytes2long(signature[:size])
267 r = bytes2long(signature[size:])
268 if r <= 0 or r >= q or s <= 0 or s >= q:
270 e = bytes2long(digest) % curve.q
276 p1x, p1y = curve.exp(z1)
277 q1x, q1y = curve.exp(z2, pub[0], pub[1])
281 lm = modinvert(lm, p)
290 # This is not constant time comparison!
294 def prv_unmarshal(prv):
295 """Unmarshal private key
297 :param bytes prv: serialized private key
300 return bytes2long(prv[::-1])
303 def pub_marshal(pub, mode=2001):
304 """Marshal public key
306 :type pub: (long, long)
309 size = MODE2SIZE[mode]
310 return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
313 def pub_unmarshal(pub, mode=2001):
314 """Unmarshal public key
319 size = MODE2SIZE[mode]
321 return (bytes2long(pub[size:]), bytes2long(pub[:size]))
324 def uv2xy(curve, u, v):
325 """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
328 k1 = (s * (1 + v)) % curve.p
329 k2 = curve.pos(1 - v)
330 x = t + k1 * modinvert(k2, curve.p)
331 y = k1 * modinvert(u * k2, curve.p)
332 return x % curve.p, y % curve.p
335 def xy2uv(curve, x, y):
336 """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
339 xmt = curve.pos(x - t)
340 u = xmt * modinvert(y, curve.p)
341 v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
342 return u % curve.p, v % curve.p