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, 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")
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")),
171 d=bytes2long(hexdec("0605F6B7C183FA81578BC39CFAD518132B9DF62897009AF7E522C32D6DC7BFFB")),
173 "id-tc26-gost-3410-2012-512-paramSetTest": GOST3410Curve(
174 p=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DF1D852741AF4704A0458047E80E4546D35B8336FAC224DD81664BBF528BE6373")),
175 q=bytes2long(hexdec("4531ACD1FE0023C7550D267B6B2FEE80922B14B2FFB90F04D4EB7C09B5D2D15DA82F2D7ECB1DBAC719905C5EECC423F1D86E25EDBE23C595D644AAF187E6E6DF")),
177 b=bytes2long(hexdec("1CFF0806A31116DA29D8CFA54E57EB748BC5F377E49400FDD788B649ECA1AC4361834013B2AD7322480A89CA58E0CF74BC9E540C2ADD6897FAD0A3084F302ADC")),
178 x=bytes2long(hexdec("24D19CC64572EE30F396BF6EBBFD7A6C5213B3B3D7057CC825F91093A68CD762FD60611262CD838DC6B60AA7EEE804E28BC849977FAC33B4B530F1B120248A9A")),
179 y=bytes2long(hexdec("2BB312A43BD2CE6E0D020613C857ACDDCFBF061E91E5F2C3F32447C259F39B2C83AB156D77F1496BF7EB3351E1EE4E43DC1A18B91B24640B6DBB92CB1ADD371E")),
181 "id-tc26-gost-3410-12-512-paramSetA": GOST3410Curve(
182 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
183 q=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF27E69532F48D89116FF22B8D4E0560609B4B38ABFAD2B85DCACDB1411F10B275")),
184 a=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC4")),
185 b=bytes2long(hexdec("E8C2505DEDFC86DDC1BD0B2B6667F1DA34B82574761CB0E879BD081CFD0B6265EE3CB090F30D27614CB4574010DA90DD862EF9D4EBEE4761503190785A71C760")),
186 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003")),
187 y=bytes2long(hexdec("7503CFE87A836AE3A61B8816E25450E6CE5E1C93ACF1ABC1778064FDCBEFA921DF1626BE4FD036E93D75E6A50E3A41E98028FE5FC235F5B889A589CB5215F2A4")),
189 "id-tc26-gost-3410-12-512-paramSetB": GOST3410Curve(
190 p=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006F")),
191 q=bytes2long(hexdec("800000000000000000000000000000000000000000000000000000000000000149A1EC142565A545ACFDB77BD9D40CFA8B996712101BEA0EC6346C54374F25BD")),
192 a=bytes2long(hexdec("8000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000006C")),
193 b=bytes2long(hexdec("687D1B459DC841457E3E06CF6F5E2517B97C7D614AF138BCBF85DC806C4B289F3E965D2DB1416D217F8B276FAD1AB69C50F78BEE1FA3106EFB8CCBC7C5140116")),
194 x=bytes2long(hexdec("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002")),
195 y=bytes2long(hexdec("1A8F7EDA389B094C2C071E3647A8940F3C123B697578C213BE6DD9E6C8EC7335DCB228FD1EDF4A39152CBCAAF8C0398828041055F94CEEEC7E21340780FE41BD")),
197 "id-tc26-gost-3410-2012-512-paramSetC": GOST3410Curve(
198 p=bytes2long(hexdec("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFDC7")),
199 q=bytes2long(hexdec("3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC98CDBA46506AB004C33A9FF5147502CC8EDA9E7A769A12694623CEF47F023ED")),
200 a=bytes2long(hexdec("DC9203E514A721875485A529D2C722FB187BC8980EB866644DE41C68E143064546E861C0E2C9EDD92ADE71F46FCF50FF2AD97F951FDA9F2A2EB6546F39689BD3")),
201 b=bytes2long(hexdec("B4C4EE28CEBC6C2C8AC12952CF37F16AC7EFB6A9F69F4B57FFDA2E4F0DE5ADE038CBC2FFF719D2C18DE0284B8BFEF3B52B8CC7A5F5BF0A3C8D2319A5312557E1")),
202 x=bytes2long(hexdec("E2E31EDFC23DE7BDEBE241CE593EF5DE2295B7A9CBAEF021D385F7074CEA043AA27272A7AE602BF2A7B9033DB9ED3610C6FB85487EAE97AAC5BC7928C1950148")),
203 y=bytes2long(hexdec("F5CE40D95B5EB899ABBCCFF5911CB8577939804D6527378B8C108C3D2090FF9BE18E2D33E3021ED2EF32D85822423B6304F726AA854BAE07D0396E9A9ADDC40F")),
206 d=bytes2long(hexdec("9E4F5D8C017D8D9F13A5CF3CDF5BFE4DAB402D54198E31EBDE28A0621050439CA6B39E0A515C06B304E2CE43E79E369E91A0CFC2BC2A22B4CA302DBB33EE7550")),
209 CURVES["id-GostR3410-2001-CryptoPro-XchA-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
210 CURVES["id-GostR3410-2001-CryptoPro-XchB-ParamSet"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
211 CURVES["id-tc26-gost-3410-2012-256-paramSetB"] = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
212 CURVES["id-tc26-gost-3410-2012-256-paramSetC"] = CURVES["id-GostR3410-2001-CryptoPro-B-ParamSet"]
213 CURVES["id-tc26-gost-3410-2012-256-paramSetD"] = CURVES["id-GostR3410-2001-CryptoPro-C-ParamSet"]
214 DEFAULT_CURVE = CURVES["id-GostR3410-2001-CryptoPro-A-ParamSet"]
217 def public_key(curve, prv):
218 """ Generate public key from the private one
220 :param GOST3410Curve curve: curve to use
221 :param long prv: private key
222 :returns: public key's parts, X and Y
225 return curve.exp(prv)
228 def sign(curve, prv, digest, rand=None, mode=2001):
229 """ Calculate signature for provided digest
231 :param GOST3410Curve curve: curve to use
232 :param long prv: private key
233 :param digest: digest for signing
234 :type digest: bytes, 32 or 64 bytes
235 :param rand: optional predefined random data used for k/r generation
236 :type rand: bytes, 32 or 64 bytes
237 :returns: signature, BE(S) || BE(R)
238 :rtype: bytes, 64 or 128 bytes
240 size = MODE2SIZE[mode]
242 e = bytes2long(digest) % q
248 elif len(rand) != size:
249 raise ValueError("rand length != %d" % size)
250 k = bytes2long(rand) % q
263 return long2bytes(s, size) + long2bytes(r, size)
266 def verify(curve, pub, digest, signature, mode=2001):
267 """ Verify provided digest with the signature
269 :param GOST3410Curve curve: curve to use
270 :type pub: (long, long)
271 :param digest: digest needed to check
272 :type digest: bytes, 32 or 64 bytes
273 :param signature: signature to verify with
274 :type signature: bytes, 64 or 128 bytes
277 size = MODE2SIZE[mode]
278 if len(signature) != size * 2:
279 raise ValueError("Invalid signature length")
282 s = bytes2long(signature[:size])
283 r = bytes2long(signature[size:])
284 if r <= 0 or r >= q or s <= 0 or s >= q:
286 e = bytes2long(digest) % curve.q
292 p1x, p1y = curve.exp(z1)
293 q1x, q1y = curve.exp(z2, pub[0], pub[1])
297 lm = modinvert(lm, p)
306 # This is not constant time comparison!
310 def prv_unmarshal(prv):
311 """Unmarshal little-endian private key
313 :param bytes prv: serialized private key
316 return bytes2long(prv[::-1])
319 def pub_marshal(pub, mode=2001):
320 """Marshal public key
322 :type pub: (long, long)
324 :returns: LE(X) || LE(Y)
326 size = MODE2SIZE[mode]
327 return (long2bytes(pub[1], size) + long2bytes(pub[0], size))[::-1]
330 def pub_unmarshal(pub, mode=2001):
331 """Unmarshal public key
333 :param pub: LE(X) || LE(Y)
337 size = MODE2SIZE[mode]
339 return (bytes2long(pub[size:]), bytes2long(pub[:size]))
342 def uv2xy(curve, u, v):
343 """Convert twisted Edwards curve U,V coordinates to Weierstrass X,Y
346 k1 = (s * (1 + v)) % curve.p
347 k2 = curve.pos(1 - v)
348 x = t + k1 * modinvert(k2, curve.p)
349 y = k1 * modinvert(u * k2, curve.p)
350 return x % curve.p, y % curve.p
353 def xy2uv(curve, x, y):
354 """Convert Weierstrass X,Y coordinates to twisted Edwards curve U,V
357 xmt = curve.pos(x - t)
358 u = xmt * modinvert(y, curve.p)
359 v = curve.pos(xmt - s) * modinvert(xmt + s, curve.p)
360 return u % curve.p, v % curve.p