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
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 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")
75 return point_size(self.p)
78 """Make positive number
84 def _add(self, p1x, p1y, p2x, p2y):
85 if p1x == p2x and p1y == p2y:
87 t = ((3 * p1x * p1x + self.a) * modinvert(2 * p1y, self.p)) % self.p
89 tx = self.pos(p2x - p1x) % self.p
90 ty = self.pos(p2y - p1y) % self.p
91 t = (ty * modinvert(tx, self.p)) % self.p
92 tx = self.pos(t * t - p1x - p2x) % self.p
93 ty = self.pos(t * (p1x - tx) - p1y) % self.p
96 def exp(self, degree, x=None, y=None):
102 raise ValueError("Bad degree value")
106 tx, ty = self._add(tx, ty, x, y)
108 x, y = self._add(x, y, x, y)
112 """Compute s/t parameters for twisted Edwards curve points conversion
114 if self.e is None or self.d is None:
115 raise ValueError("non twisted Edwards curve")
116 if self._st is not None:
119 self.pos(self.e - self.d) * modinvert(4, self.p) % self.p,
120 (self.e + self.d) * modinvert(6, self.p) % self.p,
126 "GostR3410_2001_ParamSet_cc": GOST3410Curve(
127 p=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003C7")),
128 q=bytes2long(hexdec("5fffffffffffffffffffffffffffffff606117a2f4bde428b7458a54b6e87b85")),
129 a=bytes2long(hexdec("C0000000000000000000000000000000000000000000000000000000000003c4")),
130 b=bytes2long(hexdec("2d06B4265ebc749ff7d0f1f1f88232e81632e9088fd44b7787d5e407e955080c")),
131 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
132 y=bytes2long(hexdec("a20e034bf8813ef5c18d01105e726a17eb248b264ae9706f440bedc8ccb6b22c")),
134 "id-GostR3410-2001-TestParamSet": GOST3410Curve(
135 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000431")),
136 q=bytes2long(hexdec("8000000000000000000000000000000150FE8A1892976154C59CFC193ACCF5B3")),
137 a=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000007")),
138 b=bytes2long(hexdec("5FBFF498AA938CE739B8E022FBAFEF40563F6E6A3472FC2A514C0CE9DAE23B7E")),
139 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000002")),
140 y=bytes2long(hexdec("08E2A8A0E65147D4BD6316030E16D19C85C97F0A9CA267122B96ABBCEA7E8FC8")),
142 "id-GostR3410-2001-CryptoPro-A-ParamSet": GOST3410Curve(
143 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
144 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C611070995AD10045841B09B761B893")),
145 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD94")),
146 b=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000a6")),
147 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
148 y=bytes2long(hexdec("8D91E471E0989CDA27DF505A453F2B7635294F2DDF23E3B122ACC99C9E9F1E14")),
150 "id-GostR3410-2001-CryptoPro-B-ParamSet": GOST3410Curve(
151 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C99")),
152 q=bytes2long(hexdec("800000000000000000000000000000015F700CFFF1A624E5E497161BCC8A198F")),
153 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000C96")),
154 b=bytes2long(hexdec("3E1AF419A269A5F866A7D3C25C3DF80AE979259373FF2B182F49D4CE7E1BBC8B")),
155 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000001")),
156 y=bytes2long(hexdec("3FA8124359F96680B83D1C3EB2C070E5C545C9858D03ECFB744BF8D717717EFC")),
158 "id-GostR3410-2001-CryptoPro-C-ParamSet": GOST3410Curve(
159 p=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D759B")),
160 q=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AA582CA3511EDDFB74F02F3A6598980BB9")),
161 a=bytes2long(hexdec("9B9F605F5A858107AB1EC85E6B41C8AACF846E86789051D37998F7B9022D7598")),
162 b=bytes2long(hexdec("000000000000000000000000000000000000000000000000000000000000805a")),
163 x=bytes2long(hexdec("0000000000000000000000000000000000000000000000000000000000000000")),
164 y=bytes2long(hexdec("41ECE55743711A8C3CBF3783CD08C0EE4D4DC440D4641A8F366E550DFDB3BB67")),
166 "id-tc26-gost-3410-2012-256-paramSetA": GOST3410Curve(
167 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFD97")),
168 q=bytes2long(hexdec("400000000000000000000000000000000FD8CDDFC87B6635C115AF556C360C67")),
169 a=bytes2long(hexdec("C2173F1513981673AF4892C23035A27CE25E2013BF95AA33B22C656F277E7335")),
170 b=bytes2long(hexdec("295F9BAE7428ED9CCC20E7C359A9D41A22FCCD9108E17BF7BA9337A6F8AE9513")),
171 x=bytes2long(hexdec("91E38443A5E82C0D880923425712B2BB658B9196932E02C78B2582FE742DAA28")),
172 y=bytes2long(hexdec("32879423AB1A0375895786C4BB46E9565FDE0B5344766740AF268ADB32322E5C")),
175 d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
177 "id-tc26-gost-3410-2012-512-paramSetTest": GOST3410Curve(
178 p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
179 q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
181 b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
182 x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
183 y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
185 "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
186 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
187 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
188 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
189 b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
190 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
191 y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
193 "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
194 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
195 q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
196 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
197 b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
198 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
199 y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
201 "id-tc26-gost-3410-2012-512-paramSetC": GOST3410Curve(
202 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
203 q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
204 a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
205 b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
206 x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
207 y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
210 d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
213 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
214 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
215 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
216 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"]
217 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
218 DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
221 def public_key(curve, prv):
222 """Generate public key from the private one
224 :param GOST3410Curve curve: curve to use
225 :param long prv: private key
226 :returns: public key's parts, X and Y
229 return curve.exp(prv)
232 def sign(curve, prv, digest, rand=None):
233 """Calculate signature for provided digest
235 :param GOST3410Curve curve: curve to use
236 :param long prv: private key
237 :param digest: digest for signing
238 :type digest: bytes, 32 or 64 bytes
239 :param rand: optional predefined random data used for k/r generation
240 :type rand: bytes, 32 or 64 bytes
241 :returns: signature, BE(S) || BE(R)
242 :rtype: bytes, 64 or 128 bytes
244 size = curve.point_size
246 e = bytes2long(digest) % q
252 elif len(rand) != size:
253 raise ValueError("rand length != %d" % size)
254 k = bytes2long(rand) % q
267 return long2bytes(s, size) + long2bytes(r, size)
270 def verify(curve, pub, digest, signature):
271 """Verify provided digest with the signature
273 :param GOST3410Curve curve: curve to use
274 :type pub: (long, long)
275 :param digest: digest needed to check
276 :type digest: bytes, 32 or 64 bytes
277 :param signature: signature to verify with
278 :type signature: bytes, 64 or 128 bytes
281 size = curve.point_size
282 if len(signature) != size * 2:
283 raise ValueError("Invalid signature length")
286 s = bytes2long(signature[:size])
287 r = bytes2long(signature[size:])
288 if r <= 0 or r >= q or s <= 0 or s >= q:
290 e = bytes2long(digest) % curve.q
296 p1x, p1y = curve.exp(z1)
297 q1x, q1y = curve.exp(z2, pub[0], pub[1])
301 lm = modinvert(lm, p)
310 # This is not constant time comparison!
314 def prv_unmarshal(prv):
315 """Unmarshal little-endian private key
317 :param bytes prv: serialized private key
320 return bytes2long(prv[::-1])
323 def pub_marshal(pub):
324 """Marshal public key
326 :type pub: (long, long)
328 :returns: LE(X) || LE(Y)
330 size = point_size(pub[0])
331 return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
334 def pub_unmarshal(pub):
335 """Unmarshal public key
337 :param pub: LE(X) || LE(Y)
343 return (bytes2long(pub[size:]), bytes2long(pub[:size]))
346 def uv2xy(curve, u, v):
347 """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
350 k1 = (s * (1 + v)) % curve.p
351 k2 = curve.pos(1 - v)
352 x = t + k1 * modinvert(k2, curve.p)
353 y = k1 * modinvert(u * k2, curve.p)
354 return x % curve.p, y % curve.p
357 def xy2uv(curve, x, y):
358 """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
361 xmt = curve.pos(x - t)
362 u = xmt * modinvert(y, curve.p)
363 v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
364 return u % curve.p, v % curve.p