2 # PyGOST -- Pure Python GOST cryptographic functions library
3 # Copyright (C) 2015-2020 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
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, e=None, d=None):
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")
73 """Make positive number
79 def _add(self, p1x, p1y, p2x, p2y):
80 if p1x == p2x and p1y == p2y:
82 t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
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
91 def exp(self, degree, x=None, y=None):
97 raise ValueError("Bad degree value")
101 tx, ty = self._add(tx, ty, x, y)
103 x, y = self._add(x, y, x, y)
107 """Compute s/t parameters for twisted Edwards curve points conversion
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:
114 self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
115 (self.e + self.d) * modinvert(6, self.p) % self.p,
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")),
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")),
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")),
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")),
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")),
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")),
169 d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
171 "id-tc26-gost-3410-2012-512-paramSetTest": GOST3410Curve(
172 p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
173 q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
175 b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
176 x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
177 y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
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")),
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")),
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")),
203 d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
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"]
214 def public_key(curve, prv):
215 """ Generate public key from the private one
217 :param GOST3410Curve curve: curve to use
218 :param long prv: private key
219 :returns: public key's parts, X and Y
222 return curve.exp(prv)
225 def sign(curve, prv, digest, rand=None, mode=2001):
226 """ Calculate signature for provided digest
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
235 :rtype: bytes, 64 or 128 bytes
237 size = MODE2SIZE[mode]
239 e = bytes2long(digest) % q
245 elif len(rand) != size:
246 raise ValueError("rand length != %d" % size)
247 k = bytes2long(rand) % q
260 return long2bytes(s, size) + long2bytes(r, size)
263 def verify(curve, pub, digest, signature, mode=2001):
264 """ Verify provided digest with the signature
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
274 size = MODE2SIZE[mode]
275 if len(signature) != size * 2:
276 raise ValueError("Invalid signature length")
279 s = bytes2long(signature[:size])
280 r = bytes2long(signature[size:])
281 if r <= 0 or r >= q or s <= 0 or s >= q:
283 e = bytes2long(digest) % curve.q
289 p1x, p1y = curve.exp(z1)
290 q1x, q1y = curve.exp(z2, pub[0], pub[1])
294 lm = modinvert(lm, p)
303 # This is not constant time comparison!
307 def prv_unmarshal(prv):
308 """Unmarshal private key
310 :param bytes prv: serialized private key
313 return bytes2long(prv[::-1])
316 def pub_marshal(pub, mode=2001):
317 """Marshal public key
319 :type pub: (long, long)
322 size = MODE2SIZE[mode]
323 return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
326 def pub_unmarshal(pub, mode=2001):
327 """Unmarshal public key
332 size = MODE2SIZE[mode]
334 return (bytes2long(pub[size:]), bytes2long(pub[:size]))
337 def uv2xy(curve, u, v):
338 """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
341 k1 = (s * (1 + v)) % curve.p
342 k2 = curve.pos(1 - v)
343 x = t + k1 * modinvert(k2, curve.p)
344 y = k1 * modinvert(u * k2, curve.p)
345 return x % curve.p, y % curve.p
348 def xy2uv(curve, x, y):
349 """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
352 xmt = curve.pos(x - t)
353 u = xmt * modinvert(y, curve.p)
354 v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
355 return u % curve.p, v % curve.p