GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/ec/ec2_oct.c Lines: 107 162 66.0 %
Date: 2017-11-13 Branches: 72 142 50.7 %

Line Branch Exec Source
1
/* $OpenBSD: ec2_oct.c,v 1.8 2017/01/29 17:49:23 beck Exp $ */
2
/* ====================================================================
3
 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
4
 *
5
 * The Elliptic Curve Public-Key Crypto Library (ECC Code) included
6
 * herein is developed by SUN MICROSYSTEMS, INC., and is contributed
7
 * to the OpenSSL project.
8
 *
9
 * The ECC Code is licensed pursuant to the OpenSSL open source
10
 * license provided below.
11
 *
12
 * The software is originally written by Sheueling Chang Shantz and
13
 * Douglas Stebila of Sun Microsystems Laboratories.
14
 *
15
 */
16
/* ====================================================================
17
 * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
18
 *
19
 * Redistribution and use in source and binary forms, with or without
20
 * modification, are permitted provided that the following conditions
21
 * are met:
22
 *
23
 * 1. Redistributions of source code must retain the above copyright
24
 *    notice, this list of conditions and the following disclaimer.
25
 *
26
 * 2. Redistributions in binary form must reproduce the above copyright
27
 *    notice, this list of conditions and the following disclaimer in
28
 *    the documentation and/or other materials provided with the
29
 *    distribution.
30
 *
31
 * 3. All advertising materials mentioning features or use of this
32
 *    software must display the following acknowledgment:
33
 *    "This product includes software developed by the OpenSSL Project
34
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
35
 *
36
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
37
 *    endorse or promote products derived from this software without
38
 *    prior written permission. For written permission, please contact
39
 *    openssl-core@openssl.org.
40
 *
41
 * 5. Products derived from this software may not be called "OpenSSL"
42
 *    nor may "OpenSSL" appear in their names without prior written
43
 *    permission of the OpenSSL Project.
44
 *
45
 * 6. Redistributions of any form whatsoever must retain the following
46
 *    acknowledgment:
47
 *    "This product includes software developed by the OpenSSL Project
48
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
49
 *
50
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
51
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
52
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
53
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
54
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
55
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
56
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
57
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
58
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
59
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
60
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
61
 * OF THE POSSIBILITY OF SUCH DAMAGE.
62
 * ====================================================================
63
 *
64
 * This product includes cryptographic software written by Eric Young
65
 * (eay@cryptsoft.com).  This product includes software written by Tim
66
 * Hudson (tjh@cryptsoft.com).
67
 *
68
 */
69
70
#include <openssl/opensslconf.h>
71
72
#include <openssl/err.h>
73
74
#include "ec_lcl.h"
75
76
#ifndef OPENSSL_NO_EC2M
77
78
/* Calculates and sets the affine coordinates of an EC_POINT from the given
79
 * compressed coordinates.  Uses algorithm 2.3.4 of SEC 1.
80
 * Note that the simple implementation only uses affine coordinates.
81
 *
82
 * The method is from the following publication:
83
 *
84
 *     Harper, Menezes, Vanstone:
85
 *     "Public-Key Cryptosystems with Very Small Key Lengths",
86
 *     EUROCRYPT '92, Springer-Verlag LNCS 658,
87
 *     published February 1993
88
 *
89
 * US Patents 6,141,420 and 6,618,483 (Vanstone, Mullin, Agnew) describe
90
 * the same method, but claim no priority date earlier than July 29, 1994
91
 * (and additionally fail to cite the EUROCRYPT '92 publication as prior art).
92
 */
93
int
94
ec_GF2m_simple_set_compressed_coordinates(const EC_GROUP *group, EC_POINT *point,
95
    const BIGNUM *x_, int y_bit, BN_CTX *ctx)
96
{
97
	BN_CTX *new_ctx = NULL;
98
	BIGNUM *tmp, *x, *y, *z;
99
	int ret = 0, z0;
100
101
	/* clear error queue */
102
168
	ERR_clear_error();
103
104
84
	if (ctx == NULL) {
105
		ctx = new_ctx = BN_CTX_new();
106
		if (ctx == NULL)
107
			return 0;
108
	}
109
84
	y_bit = (y_bit != 0) ? 1 : 0;
110
111
84
	BN_CTX_start(ctx);
112
84
	if ((tmp = BN_CTX_get(ctx)) == NULL)
113
		goto err;
114
84
	if ((x = BN_CTX_get(ctx)) == NULL)
115
		goto err;
116
84
	if ((y = BN_CTX_get(ctx)) == NULL)
117
		goto err;
118
84
	if ((z = BN_CTX_get(ctx)) == NULL)
119
		goto err;
120
121
84
	if (!BN_GF2m_mod_arr(x, x_, group->poly))
122
		goto err;
123
84
	if (BN_is_zero(x)) {
124
		if (!BN_GF2m_mod_sqrt_arr(y, &group->b, group->poly, ctx))
125
			goto err;
126
	} else {
127
84
		if (!group->meth->field_sqr(group, tmp, x, ctx))
128
			goto err;
129
84
		if (!group->meth->field_div(group, tmp, &group->b, tmp, ctx))
130
			goto err;
131
84
		if (!BN_GF2m_add(tmp, &group->a, tmp))
132
			goto err;
133
84
		if (!BN_GF2m_add(tmp, x, tmp))
134
			goto err;
135
84
		if (!BN_GF2m_mod_solve_quad_arr(z, tmp, group->poly, ctx)) {
136
			unsigned long err = ERR_peek_last_error();
137
138
			if (ERR_GET_LIB(err) == ERR_LIB_BN &&
139
			    ERR_GET_REASON(err) == BN_R_NO_SOLUTION) {
140
				ERR_clear_error();
141
				ECerror(EC_R_INVALID_COMPRESSED_POINT);
142
			} else
143
				ECerror(ERR_R_BN_LIB);
144
			goto err;
145
		}
146
252
		z0 = (BN_is_odd(z)) ? 1 : 0;
147
84
		if (!group->meth->field_mul(group, y, x, z, ctx))
148
			goto err;
149
84
		if (z0 != y_bit) {
150
51
			if (!BN_GF2m_add(y, y, x))
151
				goto err;
152
		}
153
	}
154
155
84
	if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))
156
		goto err;
157
158
84
	ret = 1;
159
160
err:
161
84
	BN_CTX_end(ctx);
162
84
	BN_CTX_free(new_ctx);
163
84
	return ret;
164
84
}
165
166
167
/* Converts an EC_POINT to an octet string.
168
 * If buf is NULL, the encoded length will be returned.
169
 * If the length len of buf is smaller than required an error will be returned.
170
 */
171
size_t
172
ec_GF2m_simple_point2oct(const EC_GROUP *group, const EC_POINT *point,
173
    point_conversion_form_t form,
174
    unsigned char *buf, size_t len, BN_CTX * ctx)
175
{
176
	size_t ret;
177
	BN_CTX *new_ctx = NULL;
178
	int used_ctx = 0;
179
	BIGNUM *x, *y, *yxi;
180
	size_t field_len, i, skip;
181
182
4374
	if ((form != POINT_CONVERSION_COMPRESSED)
183
4374
	    && (form != POINT_CONVERSION_UNCOMPRESSED)
184
2187
	    && (form != POINT_CONVERSION_HYBRID)) {
185
		ECerror(EC_R_INVALID_FORM);
186
		goto err;
187
	}
188
2187
	if (EC_POINT_is_at_infinity(group, point) > 0) {
189
		/* encodes to a single 0 octet */
190
		if (buf != NULL) {
191
			if (len < 1) {
192
				ECerror(EC_R_BUFFER_TOO_SMALL);
193
				return 0;
194
			}
195
			buf[0] = 0;
196
		}
197
		return 1;
198
	}
199
	/* ret := required output buffer length */
200
2187
	field_len = (EC_GROUP_get_degree(group) + 7) / 8;
201
4374
	ret = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len :
202
2187
	    1 + 2 * field_len;
203
204
	/* if 'buf' is NULL, just return required length */
205
2187
	if (buf != NULL) {
206
1095
		if (len < ret) {
207
			ECerror(EC_R_BUFFER_TOO_SMALL);
208
			goto err;
209
		}
210
1095
		if (ctx == NULL) {
211
924
			ctx = new_ctx = BN_CTX_new();
212
924
			if (ctx == NULL)
213
				return 0;
214
		}
215
1095
		BN_CTX_start(ctx);
216
		used_ctx = 1;
217
1095
		if ((x = BN_CTX_get(ctx)) == NULL)
218
			goto err;
219
1095
		if ((y = BN_CTX_get(ctx)) == NULL)
220
			goto err;
221
1095
		if ((yxi = BN_CTX_get(ctx)) == NULL)
222
			goto err;
223
224
1095
		if (!EC_POINT_get_affine_coordinates_GF2m(group, point, x, y, ctx))
225
			goto err;
226
227
1095
		buf[0] = form;
228

1767
		if ((form != POINT_CONVERSION_UNCOMPRESSED) && !BN_is_zero(x)) {
229
672
			if (!group->meth->field_div(group, yxi, y, x, ctx))
230
				goto err;
231

1344
			if (BN_is_odd(yxi))
232
416
				buf[0]++;
233
		}
234
		i = 1;
235
236
1095
		skip = field_len - BN_num_bytes(x);
237
1095
		if (skip > field_len) {
238
			ECerror(ERR_R_INTERNAL_ERROR);
239
			goto err;
240
		}
241
3980
		while (skip > 0) {
242
895
			buf[i++] = 0;
243
895
			skip--;
244
		}
245
1095
		skip = BN_bn2bin(x, buf + i);
246
1095
		i += skip;
247
1095
		if (i != 1 + field_len) {
248
			ECerror(ERR_R_INTERNAL_ERROR);
249
			goto err;
250
		}
251
2190
		if (form == POINT_CONVERSION_UNCOMPRESSED ||
252
1095
		    form == POINT_CONVERSION_HYBRID) {
253
423
			skip = field_len - BN_num_bytes(y);
254
423
			if (skip > field_len) {
255
				ECerror(ERR_R_INTERNAL_ERROR);
256
				goto err;
257
			}
258
1096
			while (skip > 0) {
259
125
				buf[i++] = 0;
260
125
				skip--;
261
			}
262
423
			skip = BN_bn2bin(y, buf + i);
263
423
			i += skip;
264
423
		}
265
1095
		if (i != ret) {
266
			ECerror(ERR_R_INTERNAL_ERROR);
267
			goto err;
268
		}
269
	}
270
2187
	if (used_ctx)
271
1095
		BN_CTX_end(ctx);
272
2187
	BN_CTX_free(new_ctx);
273
2187
	return ret;
274
275
err:
276
	if (used_ctx)
277
		BN_CTX_end(ctx);
278
	BN_CTX_free(new_ctx);
279
	return 0;
280
2187
}
281
282
283
/* Converts an octet string representation to an EC_POINT.
284
 * Note that the simple implementation only uses affine coordinates.
285
 */
286
int
287
ec_GF2m_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
288
    const unsigned char *buf, size_t len, BN_CTX *ctx)
289
{
290
	point_conversion_form_t form;
291
	int y_bit;
292
	BN_CTX *new_ctx = NULL;
293
	BIGNUM *x, *y, *yxi;
294
	size_t field_len, enc_len;
295
	int ret = 0;
296
297
348
	if (len == 0) {
298
		ECerror(EC_R_BUFFER_TOO_SMALL);
299
		return 0;
300
	}
301
174
	form = buf[0];
302
174
	y_bit = form & 1;
303
174
	form = form & ~1U;
304
522
	if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) &&
305
174
	    (form != POINT_CONVERSION_UNCOMPRESSED) &&
306
174
	    (form != POINT_CONVERSION_HYBRID)) {
307
		ECerror(EC_R_INVALID_ENCODING);
308
		return 0;
309
	}
310
174
	if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
311
		ECerror(EC_R_INVALID_ENCODING);
312
		return 0;
313
	}
314
174
	if (form == 0) {
315
3
		if (len != 1) {
316
			ECerror(EC_R_INVALID_ENCODING);
317
			return 0;
318
		}
319
3
		return EC_POINT_set_to_infinity(group, point);
320
	}
321
171
	field_len = (EC_GROUP_get_degree(group) + 7) / 8;
322
342
	enc_len = (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len :
323
171
	    1 + 2 * field_len;
324
325
171
	if (len != enc_len) {
326
		ECerror(EC_R_INVALID_ENCODING);
327
		return 0;
328
	}
329
171
	if (ctx == NULL) {
330
168
		ctx = new_ctx = BN_CTX_new();
331
168
		if (ctx == NULL)
332
			return 0;
333
	}
334
171
	BN_CTX_start(ctx);
335
171
	if ((x = BN_CTX_get(ctx)) == NULL)
336
		goto err;
337
171
	if ((y = BN_CTX_get(ctx)) == NULL)
338
		goto err;
339
171
	if ((yxi = BN_CTX_get(ctx)) == NULL)
340
		goto err;
341
342
171
	if (!BN_bin2bn(buf + 1, field_len, x))
343
		goto err;
344
171
	if (BN_ucmp(x, &group->field) >= 0) {
345
		ECerror(EC_R_INVALID_ENCODING);
346
		goto err;
347
	}
348
171
	if (form == POINT_CONVERSION_COMPRESSED) {
349
84
		if (!EC_POINT_set_compressed_coordinates_GF2m(group, point, x, y_bit, ctx))
350
			goto err;
351
	} else {
352
87
		if (!BN_bin2bn(buf + 1 + field_len, field_len, y))
353
			goto err;
354
87
		if (BN_ucmp(y, &group->field) >= 0) {
355
			ECerror(EC_R_INVALID_ENCODING);
356
			goto err;
357
		}
358
87
		if (form == POINT_CONVERSION_HYBRID) {
359
			if (!group->meth->field_div(group, yxi, y, x, ctx))
360
				goto err;
361
			if (y_bit != BN_is_odd(yxi)) {
362
				ECerror(EC_R_INVALID_ENCODING);
363
				goto err;
364
			}
365
		}
366
87
		if (!EC_POINT_set_affine_coordinates_GF2m(group, point, x, y, ctx))
367
			goto err;
368
	}
369
370
	/* test required by X9.62 */
371
171
	if (EC_POINT_is_on_curve(group, point, ctx) <= 0) {
372
		ECerror(EC_R_POINT_IS_NOT_ON_CURVE);
373
		goto err;
374
	}
375
171
	ret = 1;
376
377
err:
378
171
	BN_CTX_end(ctx);
379
171
	BN_CTX_free(new_ctx);
380
171
	return ret;
381
174
}
382
#endif