1 /* Originally written by Bodo Moeller for the OpenSSL project.
2 * ====================================================================
3 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in
14 * the documentation and/or other materials provided with the
15 * distribution.
16 *
17 * 3. All advertising materials mentioning features or use of this
18 * software must display the following acknowledgment:
19 * "This product includes software developed by the OpenSSL Project
20 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21 *
22 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23 * endorse or promote products derived from this software without
24 * prior written permission. For written permission, please contact
25 * openssl-core@openssl.org.
26 *
27 * 5. Products derived from this software may not be called "OpenSSL"
28 * nor may "OpenSSL" appear in their names without prior written
29 * permission of the OpenSSL Project.
30 *
31 * 6. Redistributions of any form whatsoever must retain the following
32 * acknowledgment:
33 * "This product includes software developed by the OpenSSL Project
34 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35 *
36 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
40 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47 * OF THE POSSIBILITY OF SUCH DAMAGE.
48 * ====================================================================
49 *
50 * This product includes cryptographic software written by Eric Young
51 * (eay@cryptsoft.com). This product includes software written by Tim
52 * Hudson (tjh@cryptsoft.com).
53 *
54 */
55 /* ====================================================================
56 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
57 *
58 * Portions of the attached software ("Contribution") are developed by
59 * SUN MICROSYSTEMS, INC., and are contributed to the OpenSSL project.
60 *
61 * The Contribution is licensed pursuant to the OpenSSL open source
62 * license provided above.
63 *
64 * The elliptic curve binary polynomial software is originally written by
65 * Sheueling Chang Shantz and Douglas Stebila of Sun Microsystems
66 * Laboratories. */
67
68 #include <openssl/ec.h>
69
70 #include <openssl/bn.h>
71 #include <openssl/err.h>
72
73 #include "internal.h"
74
75
ec_GFp_simple_point2oct(const EC_GROUP * group,const EC_POINT * point,point_conversion_form_t form,uint8_t * buf,size_t len,BN_CTX * ctx)76 static size_t ec_GFp_simple_point2oct(const EC_GROUP *group,
77 const EC_POINT *point,
78 point_conversion_form_t form,
79 uint8_t *buf, size_t len, BN_CTX *ctx) {
80 size_t ret;
81 BN_CTX *new_ctx = NULL;
82 int used_ctx = 0;
83 BIGNUM *x, *y;
84 size_t field_len, i;
85
86 if ((form != POINT_CONVERSION_COMPRESSED) &&
87 (form != POINT_CONVERSION_UNCOMPRESSED)) {
88 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_INVALID_FORM);
89 goto err;
90 }
91
92 if (EC_POINT_is_at_infinity(group, point)) {
93 /* encodes to a single 0 octet */
94 if (buf != NULL) {
95 if (len < 1) {
96 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL);
97 return 0;
98 }
99 buf[0] = 0;
100 }
101 return 1;
102 }
103
104
105 /* ret := required output buffer length */
106 field_len = BN_num_bytes(&group->field);
107 ret =
108 (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
109
110 /* if 'buf' is NULL, just return required length */
111 if (buf != NULL) {
112 if (len < ret) {
113 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, EC_R_BUFFER_TOO_SMALL);
114 goto err;
115 }
116
117 if (ctx == NULL) {
118 ctx = new_ctx = BN_CTX_new();
119 if (ctx == NULL) {
120 return 0;
121 }
122 }
123
124 BN_CTX_start(ctx);
125 used_ctx = 1;
126 x = BN_CTX_get(ctx);
127 y = BN_CTX_get(ctx);
128 if (y == NULL) {
129 goto err;
130 }
131
132 if (!EC_POINT_get_affine_coordinates_GFp(group, point, x, y, ctx)) {
133 goto err;
134 }
135
136 if ((form == POINT_CONVERSION_COMPRESSED) &&
137 BN_is_odd(y)) {
138 buf[0] = form + 1;
139 } else {
140 buf[0] = form;
141 }
142 i = 1;
143
144 if (!BN_bn2bin_padded(buf + i, field_len, x)) {
145 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR);
146 goto err;
147 }
148 i += field_len;
149
150 if (form == POINT_CONVERSION_UNCOMPRESSED) {
151 if (!BN_bn2bin_padded(buf + i, field_len, y)) {
152 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR);
153 goto err;
154 }
155 i += field_len;
156 }
157
158 if (i != ret) {
159 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_point2oct, ERR_R_INTERNAL_ERROR);
160 goto err;
161 }
162 }
163
164 if (used_ctx) {
165 BN_CTX_end(ctx);
166 }
167 BN_CTX_free(new_ctx);
168 return ret;
169
170 err:
171 if (used_ctx) {
172 BN_CTX_end(ctx);
173 }
174 BN_CTX_free(new_ctx);
175 return 0;
176 }
177
178
ec_GFp_simple_oct2point(const EC_GROUP * group,EC_POINT * point,const uint8_t * buf,size_t len,BN_CTX * ctx)179 static int ec_GFp_simple_oct2point(const EC_GROUP *group, EC_POINT *point,
180 const uint8_t *buf, size_t len,
181 BN_CTX *ctx) {
182 point_conversion_form_t form;
183 int y_bit;
184 BN_CTX *new_ctx = NULL;
185 BIGNUM *x, *y;
186 size_t field_len, enc_len;
187 int ret = 0;
188
189 if (len == 0) {
190 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_BUFFER_TOO_SMALL);
191 return 0;
192 }
193 form = buf[0];
194 y_bit = form & 1;
195 form = form & ~1U;
196 if ((form != 0) && (form != POINT_CONVERSION_COMPRESSED) &&
197 (form != POINT_CONVERSION_UNCOMPRESSED)) {
198 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
199 return 0;
200 }
201 if ((form == 0 || form == POINT_CONVERSION_UNCOMPRESSED) && y_bit) {
202 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
203 return 0;
204 }
205
206 if (form == 0) {
207 if (len != 1) {
208 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
209 return 0;
210 }
211
212 return EC_POINT_set_to_infinity(group, point);
213 }
214
215 field_len = BN_num_bytes(&group->field);
216 enc_len =
217 (form == POINT_CONVERSION_COMPRESSED) ? 1 + field_len : 1 + 2 * field_len;
218
219 if (len != enc_len) {
220 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
221 return 0;
222 }
223
224 if (ctx == NULL) {
225 ctx = new_ctx = BN_CTX_new();
226 if (ctx == NULL) {
227 return 0;
228 }
229 }
230
231 BN_CTX_start(ctx);
232 x = BN_CTX_get(ctx);
233 y = BN_CTX_get(ctx);
234 if (y == NULL) {
235 goto err;
236 }
237
238 if (!BN_bin2bn(buf + 1, field_len, x)) {
239 goto err;
240 }
241 if (BN_ucmp(x, &group->field) >= 0) {
242 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
243 goto err;
244 }
245
246 if (form == POINT_CONVERSION_COMPRESSED) {
247 if (!EC_POINT_set_compressed_coordinates_GFp(group, point, x, y_bit, ctx)) {
248 goto err;
249 }
250 } else {
251 if (!BN_bin2bn(buf + 1 + field_len, field_len, y)) {
252 goto err;
253 }
254 if (BN_ucmp(y, &group->field) >= 0) {
255 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_INVALID_ENCODING);
256 goto err;
257 }
258
259 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
260 goto err;
261 }
262 }
263
264 /* test required by X9.62 */
265 if (!EC_POINT_is_on_curve(group, point, ctx)) {
266 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_oct2point, EC_R_POINT_IS_NOT_ON_CURVE);
267 goto err;
268 }
269
270 ret = 1;
271
272 err:
273 BN_CTX_end(ctx);
274 BN_CTX_free(new_ctx);
275 return ret;
276 }
277
EC_POINT_oct2point(const EC_GROUP * group,EC_POINT * point,const uint8_t * buf,size_t len,BN_CTX * ctx)278 int EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point,
279 const uint8_t *buf, size_t len, BN_CTX *ctx) {
280 if (group->meth->oct2point == 0 &&
281 !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) {
282 OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point,
283 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
284 return 0;
285 }
286 if (group->meth != point->meth) {
287 OPENSSL_PUT_ERROR(EC, EC_POINT_oct2point, EC_R_INCOMPATIBLE_OBJECTS);
288 return 0;
289 }
290 if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) {
291 return ec_GFp_simple_oct2point(group, point, buf, len, ctx);
292 }
293
294 return group->meth->oct2point(group, point, buf, len, ctx);
295 }
296
EC_POINT_point2oct(const EC_GROUP * group,const EC_POINT * point,point_conversion_form_t form,uint8_t * buf,size_t len,BN_CTX * ctx)297 size_t EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point,
298 point_conversion_form_t form, uint8_t *buf,
299 size_t len, BN_CTX *ctx) {
300 if (group->meth->point2oct == 0 &&
301 !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) {
302 OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct,
303 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
304 return 0;
305 }
306 if (group->meth != point->meth) {
307 OPENSSL_PUT_ERROR(EC, EC_POINT_point2oct, EC_R_INCOMPATIBLE_OBJECTS);
308 return 0;
309 }
310 if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) {
311 return ec_GFp_simple_point2oct(group, point, form, buf, len, ctx);
312 }
313
314 return group->meth->point2oct(group, point, form, buf, len, ctx);
315 }
316
ec_GFp_simple_set_compressed_coordinates(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x_,int y_bit,BN_CTX * ctx)317 int ec_GFp_simple_set_compressed_coordinates(const EC_GROUP *group,
318 EC_POINT *point, const BIGNUM *x_,
319 int y_bit, BN_CTX *ctx) {
320 BN_CTX *new_ctx = NULL;
321 BIGNUM *tmp1, *tmp2, *x, *y;
322 int ret = 0;
323
324 ERR_clear_error();
325
326 if (ctx == NULL) {
327 ctx = new_ctx = BN_CTX_new();
328 if (ctx == NULL) {
329 return 0;
330 }
331 }
332
333 y_bit = (y_bit != 0);
334
335 BN_CTX_start(ctx);
336 tmp1 = BN_CTX_get(ctx);
337 tmp2 = BN_CTX_get(ctx);
338 x = BN_CTX_get(ctx);
339 y = BN_CTX_get(ctx);
340 if (y == NULL) {
341 goto err;
342 }
343
344 /* Recover y. We have a Weierstrass equation
345 * y^2 = x^3 + a*x + b,
346 * so y is one of the square roots of x^3 + a*x + b. */
347
348 /* tmp1 := x^3 */
349 if (!BN_nnmod(x, x_, &group->field, ctx)) {
350 goto err;
351 }
352
353 if (group->meth->field_decode == 0) {
354 /* field_{sqr,mul} work on standard representation */
355 if (!group->meth->field_sqr(group, tmp2, x_, ctx) ||
356 !group->meth->field_mul(group, tmp1, tmp2, x_, ctx)) {
357 goto err;
358 }
359 } else {
360 if (!BN_mod_sqr(tmp2, x_, &group->field, ctx) ||
361 !BN_mod_mul(tmp1, tmp2, x_, &group->field, ctx)) {
362 goto err;
363 }
364 }
365
366 /* tmp1 := tmp1 + a*x */
367 if (group->a_is_minus3) {
368 if (!BN_mod_lshift1_quick(tmp2, x, &group->field) ||
369 !BN_mod_add_quick(tmp2, tmp2, x, &group->field) ||
370 !BN_mod_sub_quick(tmp1, tmp1, tmp2, &group->field)) {
371 goto err;
372 }
373 } else {
374 if (group->meth->field_decode) {
375 if (!group->meth->field_decode(group, tmp2, &group->a, ctx) ||
376 !BN_mod_mul(tmp2, tmp2, x, &group->field, ctx)) {
377 goto err;
378 }
379 } else {
380 /* field_mul works on standard representation */
381 if (!group->meth->field_mul(group, tmp2, &group->a, x, ctx)) {
382 goto err;
383 }
384 }
385
386 if (!BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) {
387 goto err;
388 }
389 }
390
391 /* tmp1 := tmp1 + b */
392 if (group->meth->field_decode) {
393 if (!group->meth->field_decode(group, tmp2, &group->b, ctx) ||
394 !BN_mod_add_quick(tmp1, tmp1, tmp2, &group->field)) {
395 goto err;
396 }
397 } else {
398 if (!BN_mod_add_quick(tmp1, tmp1, &group->b, &group->field)) {
399 goto err;
400 }
401 }
402
403 if (!BN_mod_sqrt(y, tmp1, &group->field, ctx)) {
404 unsigned long err = ERR_peek_last_error();
405
406 if (ERR_GET_LIB(err) == ERR_LIB_BN &&
407 ERR_GET_REASON(err) == BN_R_NOT_A_SQUARE) {
408 ERR_clear_error();
409 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, EC_R_INVALID_COMPRESSED_POINT);
410 } else {
411 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates, ERR_R_BN_LIB);
412 }
413 goto err;
414 }
415
416 if (y_bit != BN_is_odd(y)) {
417 if (BN_is_zero(y)) {
418 int kron;
419
420 kron = BN_kronecker(x, &group->field, ctx);
421 if (kron == -2) {
422 goto err;
423 }
424
425 if (kron == 1) {
426 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates,
427 EC_R_INVALID_COMPRESSION_BIT);
428 } else {
429 /* BN_mod_sqrt() should have cought this error (not a square) */
430 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates,
431 EC_R_INVALID_COMPRESSED_POINT);
432 }
433 goto err;
434 }
435 if (!BN_usub(y, &group->field, y)) {
436 goto err;
437 }
438 }
439 if (y_bit != BN_is_odd(y)) {
440 OPENSSL_PUT_ERROR(EC, ec_GFp_simple_set_compressed_coordinates,
441 ERR_R_INTERNAL_ERROR);
442 goto err;
443 }
444
445 if (!EC_POINT_set_affine_coordinates_GFp(group, point, x, y, ctx)) {
446 goto err;
447 }
448
449 ret = 1;
450
451 err:
452 BN_CTX_end(ctx);
453 BN_CTX_free(new_ctx);
454 return ret;
455 }
456
EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP * group,EC_POINT * point,const BIGNUM * x,int y_bit,BN_CTX * ctx)457 int EC_POINT_set_compressed_coordinates_GFp(const EC_GROUP *group,
458 EC_POINT *point, const BIGNUM *x,
459 int y_bit, BN_CTX *ctx) {
460 if (group->meth->point_set_compressed_coordinates == 0 &&
461 !(group->meth->flags & EC_FLAGS_DEFAULT_OCT)) {
462 OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp,
463 ERR_R_SHOULD_NOT_HAVE_BEEN_CALLED);
464 return 0;
465 }
466 if (group->meth != point->meth) {
467 OPENSSL_PUT_ERROR(EC, EC_POINT_set_compressed_coordinates_GFp,
468 EC_R_INCOMPATIBLE_OBJECTS);
469 return 0;
470 }
471 if (group->meth->flags & EC_FLAGS_DEFAULT_OCT) {
472 return ec_GFp_simple_set_compressed_coordinates(group, point, x, y_bit,
473 ctx);
474 }
475 return group->meth->point_set_compressed_coordinates(group, point, x, y_bit,
476 ctx);
477 }
478