1 /* $OpenBSD: gostr341001.c,v 1.7 2017/01/29 17:49:23 beck Exp $ */
2 /*
3  * Copyright (c) 2014 Dmitry Eremin-Solenikov <dbaryshkov@gmail.com>
4  * Copyright (c) 2005-2006 Cryptocom LTD
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  *    notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  *    notice, this list of conditions and the following disclaimer in
15  *    the documentation and/or other materials provided with the
16  *    distribution.
17  *
18  * 3. All advertising materials mentioning features or use of this
19  *    software must display the following acknowledgment:
20  *    "This product includes software developed by the OpenSSL Project
21  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
22  *
23  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
24  *    endorse or promote products derived from this software without
25  *    prior written permission. For written permission, please contact
26  *    openssl-core@openssl.org.
27  *
28  * 5. Products derived from this software may not be called "OpenSSL"
29  *    nor may "OpenSSL" appear in their names without prior written
30  *    permission of the OpenSSL Project.
31  *
32  * 6. Redistributions of any form whatsoever must retain the following
33  *    acknowledgment:
34  *    "This product includes software developed by the OpenSSL Project
35  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
36  *
37  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
38  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
39  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
40  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
41  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
42  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
43  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
44  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
45  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
46  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
47  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
48  * OF THE POSSIBILITY OF SUCH DAMAGE.
49  * ====================================================================
50  */
51 
52 #include <string.h>
53 
54 #include <openssl/opensslconf.h>
55 
56 #ifndef OPENSSL_NO_GOST
57 #include <openssl/bn.h>
58 #include <openssl/err.h>
59 #include <openssl/gost.h>
60 
61 #include "bn_lcl.h"
62 #include "gost_locl.h"
63 
64 /* Convert little-endian byte array into bignum */
65 BIGNUM *
66 GOST_le2bn(const unsigned char *buf, size_t len, BIGNUM *bn)
67 {
68 	unsigned char temp[64];
69 	int i;
70 
71 	if (len > 64)
72 		return NULL;
73 
74 	for (i = 0; i < len; i++) {
75 		temp[len - 1 - i] = buf[i];
76 	}
77 
78 	return BN_bin2bn(temp, len, bn);
79 }
80 
81 int
82 GOST_bn2le(BIGNUM *bn, unsigned char *buf, int len)
83 {
84 	unsigned char temp[64];
85 	int i, bytes;
86 
87 	bytes = BN_num_bytes(bn);
88 	if (len > 64 || bytes > len)
89 		return 0;
90 
91 	BN_bn2bin(bn, temp);
92 
93 	for (i = 0; i < bytes; i++) {
94 		buf[bytes - 1 - i] = temp[i];
95 	}
96 
97 	memset(buf + bytes, 0, len - bytes);
98 
99 	return 1;
100 }
101 
102 int
103 gost2001_compute_public(GOST_KEY *ec)
104 {
105 	const EC_GROUP *group = GOST_KEY_get0_group(ec);
106 	EC_POINT *pub_key = NULL;
107 	const BIGNUM *priv_key = NULL;
108 	BN_CTX *ctx = NULL;
109 	int ok = 0;
110 
111 	if (group == NULL) {
112 		GOSTerror(GOST_R_KEY_IS_NOT_INITIALIZED);
113 		return 0;
114 	}
115 	ctx = BN_CTX_new();
116 	if (ctx == NULL) {
117 		GOSTerror(ERR_R_MALLOC_FAILURE);
118 		return 0;
119 	}
120 	BN_CTX_start(ctx);
121 	if ((priv_key = GOST_KEY_get0_private_key(ec)) == NULL)
122 		goto err;
123 
124 	pub_key = EC_POINT_new(group);
125 	if (pub_key == NULL)
126 		goto err;
127 	if (EC_POINT_mul(group, pub_key, priv_key, NULL, NULL, ctx) == 0)
128 		goto err;
129 	if (GOST_KEY_set_public_key(ec, pub_key) == 0)
130 		goto err;
131 	ok = 1;
132 
133 	if (ok == 0) {
134 err:
135 		GOSTerror(ERR_R_EC_LIB);
136 	}
137 	EC_POINT_free(pub_key);
138 	if (ctx != NULL) {
139 		BN_CTX_end(ctx);
140 		BN_CTX_free(ctx);
141 	}
142 	return ok;
143 }
144 
145 ECDSA_SIG *
146 gost2001_do_sign(BIGNUM *md, GOST_KEY *eckey)
147 {
148 	ECDSA_SIG *newsig = NULL;
149 	BIGNUM *order = NULL;
150 	const EC_GROUP *group;
151 	const BIGNUM *priv_key;
152 	BIGNUM *r = NULL, *s = NULL, *X = NULL, *tmp = NULL, *tmp2 = NULL, *k =
153 	    NULL, *e = NULL;
154 	EC_POINT *C = NULL;
155 	BN_CTX *ctx = BN_CTX_new();
156 	int ok = 0;
157 
158 	if (ctx == NULL) {
159 		GOSTerror(ERR_R_MALLOC_FAILURE);
160 		return NULL;
161 	}
162 	BN_CTX_start(ctx);
163 	newsig = ECDSA_SIG_new();
164 	if (newsig == NULL) {
165 		GOSTerror(ERR_R_MALLOC_FAILURE);
166 		goto err;
167 	}
168 	s = newsig->s;
169 	r = newsig->r;
170 	group = GOST_KEY_get0_group(eckey);
171 	if ((order = BN_CTX_get(ctx)) == NULL)
172 		goto err;
173 	if (EC_GROUP_get_order(group, order, ctx) == 0)
174 		goto err;
175 	priv_key = GOST_KEY_get0_private_key(eckey);
176 	if ((e = BN_CTX_get(ctx)) == NULL)
177 		goto err;
178 	if (BN_mod_ct(e, md, order, ctx) == 0)
179 		goto err;
180 	if (BN_is_zero(e))
181 		BN_one(e);
182 	if ((k = BN_CTX_get(ctx)) == NULL)
183 		goto err;
184 	if ((X = BN_CTX_get(ctx)) == NULL)
185 		goto err;
186 	if ((C = EC_POINT_new(group)) == NULL)
187 		goto err;
188 	do {
189 		do {
190 			if (!BN_rand_range(k, order)) {
191 				GOSTerror(GOST_R_RANDOM_NUMBER_GENERATOR_FAILED);
192 				goto err;
193 			}
194 			/*
195 			 * We do not want timing information to leak the length
196 			 * of k, so we compute G*k using an equivalent scalar
197 			 * of fixed bit-length.
198 			 */
199 			if (BN_add(k, k, order) == 0)
200 				goto err;
201 			if (BN_num_bits(k) <= BN_num_bits(order))
202 				if (BN_add(k, k, order) == 0)
203 					goto err;
204 
205 			if (EC_POINT_mul(group, C, k, NULL, NULL, ctx) == 0) {
206 				GOSTerror(ERR_R_EC_LIB);
207 				goto err;
208 			}
209 			if (EC_POINT_get_affine_coordinates_GFp(group, C, X,
210 			    NULL, ctx) == 0) {
211 				GOSTerror(ERR_R_EC_LIB);
212 				goto err;
213 			}
214 			if (BN_nnmod(r, X, order, ctx) == 0)
215 				goto err;
216 		} while (BN_is_zero(r));
217 		/* s = (r*priv_key+k*e) mod order */
218 		if (tmp == NULL) {
219 			if ((tmp = BN_CTX_get(ctx)) == NULL)
220 				goto err;
221 		}
222 		if (BN_mod_mul(tmp, priv_key, r, order, ctx) == 0)
223 			goto err;
224 		if (tmp2 == NULL) {
225 			if ((tmp2 = BN_CTX_get(ctx)) == NULL)
226 				goto err;
227 		}
228 		if (BN_mod_mul(tmp2, k, e, order, ctx) == 0)
229 			goto err;
230 		if (BN_mod_add(s, tmp, tmp2, order, ctx) == 0)
231 			goto err;
232 	} while (BN_is_zero(s));
233 	ok = 1;
234 
235 err:
236 	EC_POINT_free(C);
237 	if (ctx != NULL) {
238 		BN_CTX_end(ctx);
239 		BN_CTX_free(ctx);
240 	}
241 	if (ok == 0) {
242 		ECDSA_SIG_free(newsig);
243 		newsig = NULL;
244 	}
245 	return newsig;
246 }
247 
248 int
249 gost2001_do_verify(BIGNUM *md, ECDSA_SIG *sig, GOST_KEY *ec)
250 {
251 	BN_CTX *ctx = BN_CTX_new();
252 	const EC_GROUP *group = GOST_KEY_get0_group(ec);
253 	BIGNUM *order;
254 	BIGNUM *e = NULL, *R = NULL, *v = NULL, *z1 = NULL, *z2 = NULL;
255 	BIGNUM *X = NULL, *tmp = NULL;
256 	EC_POINT *C = NULL;
257 	const EC_POINT *pub_key = NULL;
258 	int ok = 0;
259 
260 	if (ctx == NULL)
261 		goto err;
262 	BN_CTX_start(ctx);
263 	if ((order = BN_CTX_get(ctx)) == NULL)
264 		goto err;
265 	if ((e = BN_CTX_get(ctx)) == NULL)
266 		goto err;
267 	if ((z1 = BN_CTX_get(ctx)) == NULL)
268 		goto err;
269 	if ((z2 = BN_CTX_get(ctx)) == NULL)
270 		goto err;
271 	if ((tmp = BN_CTX_get(ctx)) == NULL)
272 		goto err;
273 	if ((X = BN_CTX_get(ctx)) == NULL)
274 		goto err;
275 	if ((R = BN_CTX_get(ctx)) == NULL)
276 		goto err;
277 	if ((v = BN_CTX_get(ctx)) == NULL)
278 		goto err;
279 
280 	if (EC_GROUP_get_order(group, order, ctx) == 0)
281 		goto err;
282 	pub_key = GOST_KEY_get0_public_key(ec);
283 	if (BN_is_zero(sig->s) || BN_is_zero(sig->r) ||
284 	    BN_cmp(sig->s, order) >= 1 || BN_cmp(sig->r, order) >= 1) {
285 		GOSTerror(GOST_R_SIGNATURE_PARTS_GREATER_THAN_Q);
286 		goto err;
287 	}
288 
289 	if (BN_mod_ct(e, md, order, ctx) == 0)
290 		goto err;
291 	if (BN_is_zero(e))
292 		BN_one(e);
293 	if ((v = BN_mod_inverse_ct(v, e, order, ctx)) == NULL)
294 		goto err;
295 	if (BN_mod_mul(z1, sig->s, v, order, ctx) == 0)
296 		goto err;
297 	if (BN_sub(tmp, order, sig->r) == 0)
298 		goto err;
299 	if (BN_mod_mul(z2, tmp, v, order, ctx) == 0)
300 		goto err;
301 	if ((C = EC_POINT_new(group)) == NULL)
302 		goto err;
303 	if (EC_POINT_mul(group, C, z1, pub_key, z2, ctx) == 0) {
304 		GOSTerror(ERR_R_EC_LIB);
305 		goto err;
306 	}
307 	if (EC_POINT_get_affine_coordinates_GFp(group, C, X, NULL, ctx) == 0) {
308 		GOSTerror(ERR_R_EC_LIB);
309 		goto err;
310 	}
311 	if (BN_mod_ct(R, X, order, ctx) == 0)
312 		goto err;
313 	if (BN_cmp(R, sig->r) != 0) {
314 		GOSTerror(GOST_R_SIGNATURE_MISMATCH);
315 	} else {
316 		ok = 1;
317 	}
318 err:
319 	EC_POINT_free(C);
320 	if (ctx != NULL) {
321 		BN_CTX_end(ctx);
322 		BN_CTX_free(ctx);
323 	}
324 	return ok;
325 }
326 
327 /* Implementation of CryptoPro VKO 34.10-2001 algorithm */
328 int
329 VKO_compute_key(BIGNUM *X, BIGNUM *Y, const GOST_KEY *pkey, GOST_KEY *priv_key,
330     const BIGNUM *ukm)
331 {
332 	BIGNUM *p = NULL, *order = NULL;
333 	const BIGNUM *key = GOST_KEY_get0_private_key(priv_key);
334 	const EC_GROUP *group = GOST_KEY_get0_group(priv_key);
335 	const EC_POINT *pub_key = GOST_KEY_get0_public_key(pkey);
336 	EC_POINT *pnt;
337 	BN_CTX *ctx = NULL;
338 	int ok = 0;
339 
340 	pnt = EC_POINT_new(group);
341 	if (pnt == NULL)
342 		goto err;
343 	ctx = BN_CTX_new();
344 	if (ctx == NULL)
345 		goto err;
346 	BN_CTX_start(ctx);
347 	if ((p = BN_CTX_get(ctx)) == NULL)
348 		goto err;
349 	if ((order = BN_CTX_get(ctx)) == NULL)
350 		goto err;
351 	if (EC_GROUP_get_order(group, order, ctx) == 0)
352 		goto err;
353 	if (BN_mod_mul(p, key, ukm, order, ctx) == 0)
354 		goto err;
355 	if (EC_POINT_mul(group, pnt, NULL, pub_key, p, ctx) == 0)
356 		goto err;
357 	if (EC_POINT_get_affine_coordinates_GFp(group, pnt, X, Y, ctx) == 0)
358 		goto err;
359 	ok = 1;
360 
361 err:
362 	if (ctx != NULL) {
363 		BN_CTX_end(ctx);
364 		BN_CTX_free(ctx);
365 	}
366 	EC_POINT_free(pnt);
367 	return ok;
368 }
369 
370 int
371 gost2001_keygen(GOST_KEY *ec)
372 {
373 	BIGNUM *order = BN_new(), *d = BN_new();
374 	const EC_GROUP *group = GOST_KEY_get0_group(ec);
375 	int rc = 0;
376 
377 	if (order == NULL || d == NULL)
378 		goto err;
379 	if (EC_GROUP_get_order(group, order, NULL) == 0)
380 		goto err;
381 
382 	do {
383 		if (BN_rand_range(d, order) == 0) {
384 			GOSTerror(GOST_R_RANDOM_NUMBER_GENERATOR_FAILED);
385 			goto err;
386 		}
387 	} while (BN_is_zero(d));
388 
389 	if (GOST_KEY_set_private_key(ec, d) == 0)
390 		goto err;
391 	rc = gost2001_compute_public(ec);
392 
393 err:
394 	BN_free(d);
395 	BN_free(order);
396 	return rc;
397 }
398 #endif
399