1 /* $OpenBSD: ec_convert.c,v 1.14 2025/01/05 16:07:08 tb Exp $ */
2 /*
3 * Originally written by Bodo Moeller for the OpenSSL project.
4 */
5 /* ====================================================================
6 * Copyright (c) 1998-2003 The OpenSSL Project. All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 *
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
18 * distribution.
19 *
20 * 3. All advertising materials mentioning features or use of this
21 * software must display the following acknowledgment:
22 * "This product includes software developed by the OpenSSL Project
23 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
24 *
25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26 * endorse or promote products derived from this software without
27 * prior written permission. For written permission, please contact
28 * openssl-core@openssl.org.
29 *
30 * 5. Products derived from this software may not be called "OpenSSL"
31 * nor may "OpenSSL" appear in their names without prior written
32 * permission of the OpenSSL Project.
33 *
34 * 6. Redistributions of any form whatsoever must retain the following
35 * acknowledgment:
36 * "This product includes software developed by the OpenSSL Project
37 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
38 *
39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50 * OF THE POSSIBILITY OF SUCH DAMAGE.
51 * ====================================================================
52 *
53 * This product includes cryptographic software written by Eric Young
54 * (eay@cryptsoft.com). This product includes software written by Tim
55 * Hudson (tjh@cryptsoft.com).
56 *
57 */
58 /* ====================================================================
59 * Copyright 2002 Sun Microsystems, Inc. ALL RIGHTS RESERVED.
60 * Binary polynomial ECC support in OpenSSL originally developed by
61 * SUN MICROSYSTEMS, INC., and contributed to the OpenSSL project.
62 */
63
64 #include <string.h>
65
66 #include <openssl/asn1.h>
67 #include <openssl/err.h>
68
69 #include "asn1_local.h"
70 #include "ec_local.h"
71
72 /*
73 * Internal handling of the point conversion octet
74 * (see X9.62, section 4.4.2, SEC 1 section 2.3.3)
75 *
76 * Only the last three bits of the leading octet of a point should be set.
77 * Bits 3 and 2 encode the conversion form for all points except the point
78 * at infinity. In compressed and hybrid form bit 1 indicates if the even
79 * or the odd solution of the quadratic equation for y should be used.
80 *
81 * The public point_conversion_t enum lacks the point at infinity, so we
82 * ignore it except at the API boundary.
83 */
84
85 #define EC_POINT_YBIT 0x01
86
87 #define EC_POINT_AT_INFINITY 0x00
88 #define EC_POINT_COMPRESSED 0x02
89 #define EC_POINT_UNCOMPRESSED 0x04
90 #define EC_POINT_HYBRID 0x06
91 #define EC_POINT_CONVERSION_MASK 0x06
92
93 static int
ec_conversion_form_is_valid(uint8_t form)94 ec_conversion_form_is_valid(uint8_t form)
95 {
96 return (form & EC_POINT_CONVERSION_MASK) == form;
97 }
98
99 static int
ec_check_hybrid_ybit_is_consistent(uint8_t form,int ybit,const BIGNUM * y)100 ec_check_hybrid_ybit_is_consistent(uint8_t form, int ybit, const BIGNUM *y)
101 {
102 if (form == EC_POINT_HYBRID && ybit != BN_is_odd(y)) {
103 ECerror(EC_R_INVALID_ENCODING);
104 return 0;
105 }
106
107 return 1;
108 }
109
110 /* Nonzero y-bit only makes sense with compressed or hybrid encoding. */
111 static int
ec_nonzero_ybit_allowed(uint8_t form)112 ec_nonzero_ybit_allowed(uint8_t form)
113 {
114 return form == EC_POINT_COMPRESSED || form == EC_POINT_HYBRID;
115 }
116
117 static int
ec_add_leading_octet_cbb(CBB * cbb,uint8_t form,int ybit)118 ec_add_leading_octet_cbb(CBB *cbb, uint8_t form, int ybit)
119 {
120 if (ec_nonzero_ybit_allowed(form) && ybit != 0)
121 form |= EC_POINT_YBIT;
122
123 return CBB_add_u8(cbb, form);
124 }
125
126 static int
ec_get_leading_octet_cbs(CBS * cbs,uint8_t * out_form,int * out_ybit)127 ec_get_leading_octet_cbs(CBS *cbs, uint8_t *out_form, int *out_ybit)
128 {
129 uint8_t octet;
130
131 if (!CBS_get_u8(cbs, &octet)) {
132 ECerror(EC_R_BUFFER_TOO_SMALL);
133 return 0;
134 }
135
136 *out_ybit = octet & EC_POINT_YBIT;
137 *out_form = octet & ~EC_POINT_YBIT;
138
139 if (!ec_conversion_form_is_valid(*out_form)) {
140 ECerror(EC_R_INVALID_ENCODING);
141 return 0;
142 }
143
144 if (*out_ybit != 0 && !ec_nonzero_ybit_allowed(*out_form)) {
145 ECerror(EC_R_INVALID_ENCODING);
146 return 0;
147 }
148
149 return 1;
150 }
151
152 static int
ec_encoded_length(const EC_GROUP * group,uint8_t form,size_t * out_len)153 ec_encoded_length(const EC_GROUP *group, uint8_t form, size_t *out_len)
154 {
155 switch (form) {
156 case EC_POINT_AT_INFINITY:
157 *out_len = 1;
158 return 1;
159 case EC_POINT_COMPRESSED:
160 *out_len = 1 + BN_num_bytes(group->p);
161 return 1;
162 case EC_POINT_UNCOMPRESSED:
163 case EC_POINT_HYBRID:
164 *out_len = 1 + 2 * BN_num_bytes(group->p);
165 return 1;
166 default:
167 return 0;
168 }
169 }
170
171 static int
ec_field_element_is_valid(const EC_GROUP * group,const BIGNUM * bn)172 ec_field_element_is_valid(const EC_GROUP *group, const BIGNUM *bn)
173 {
174 /* Ensure bn is in the range [0, p). */
175 return !BN_is_negative(bn) && BN_cmp(group->p, bn) > 0;
176 }
177
178 static int
ec_add_field_element_cbb(CBB * cbb,const EC_GROUP * group,const BIGNUM * bn)179 ec_add_field_element_cbb(CBB *cbb, const EC_GROUP *group, const BIGNUM *bn)
180 {
181 uint8_t *buf = NULL;
182 int buf_len = BN_num_bytes(group->p);
183
184 if (!ec_field_element_is_valid(group, bn)) {
185 ECerror(EC_R_BIGNUM_OUT_OF_RANGE);
186 return 0;
187 }
188 if (!CBB_add_space(cbb, &buf, buf_len)) {
189 ECerror(ERR_R_MALLOC_FAILURE);
190 return 0;
191 }
192 if (BN_bn2binpad(bn, buf, buf_len) != buf_len) {
193 ECerror(ERR_R_MALLOC_FAILURE);
194 return 0;
195 }
196
197 return 1;
198 }
199
200 static int
ec_get_field_element_cbs(CBS * cbs,const EC_GROUP * group,BIGNUM * bn)201 ec_get_field_element_cbs(CBS *cbs, const EC_GROUP *group, BIGNUM *bn)
202 {
203 CBS field_element;
204
205 if (!CBS_get_bytes(cbs, &field_element, BN_num_bytes(group->p))) {
206 ECerror(EC_R_INVALID_ENCODING);
207 return 0;
208 }
209 if (!BN_bin2bn(CBS_data(&field_element), CBS_len(&field_element), bn)) {
210 ECerror(ERR_R_MALLOC_FAILURE);
211 return 0;
212 }
213 if (!ec_field_element_is_valid(group, bn)) {
214 ECerror(EC_R_BIGNUM_OUT_OF_RANGE);
215 return 0;
216 }
217
218 return 1;
219 }
220
221 static size_t
ec_point2oct(const EC_GROUP * group,const EC_POINT * point,uint8_t form,unsigned char * buf,size_t len,BN_CTX * ctx)222 ec_point2oct(const EC_GROUP *group, const EC_POINT *point, uint8_t form,
223 unsigned char *buf, size_t len, BN_CTX *ctx)
224 {
225 CBB cbb;
226 BIGNUM *x, *y;
227 size_t encoded_length;
228 size_t ret = 0;
229
230 if (EC_POINT_is_at_infinity(group, point))
231 form = EC_POINT_AT_INFINITY;
232
233 if (!ec_encoded_length(group, form, &encoded_length)) {
234 ECerror(EC_R_INVALID_FORM);
235 return 0;
236 }
237
238 if (buf == NULL)
239 return encoded_length;
240
241 if (len < encoded_length) {
242 ECerror(EC_R_BUFFER_TOO_SMALL);
243 return 0;
244 }
245
246 BN_CTX_start(ctx);
247 if (!CBB_init_fixed(&cbb, buf, len))
248 goto err;
249
250 if (form == EC_POINT_AT_INFINITY) {
251 if (!EC_POINT_is_at_infinity(group, point))
252 goto err;
253 if (!ec_add_leading_octet_cbb(&cbb, form, 0))
254 goto err;
255
256 goto done;
257 }
258
259 if ((x = BN_CTX_get(ctx)) == NULL)
260 goto err;
261 if ((y = BN_CTX_get(ctx)) == NULL)
262 goto err;
263 if (!EC_POINT_get_affine_coordinates(group, point, x, y, ctx))
264 goto err;
265
266 if (!ec_add_leading_octet_cbb(&cbb, form, BN_is_odd(y)))
267 goto err;
268
269 if (form == EC_POINT_COMPRESSED) {
270 if (!ec_add_field_element_cbb(&cbb, group, x))
271 goto err;
272 } else {
273 if (!ec_add_field_element_cbb(&cbb, group, x))
274 goto err;
275 if (!ec_add_field_element_cbb(&cbb, group, y))
276 goto err;
277 }
278
279 done:
280 if (!CBB_finish(&cbb, NULL, &ret))
281 goto err;
282
283 if (ret != encoded_length) {
284 ret = 0;
285 goto err;
286 }
287
288 err:
289 CBB_cleanup(&cbb);
290 BN_CTX_end(ctx);
291
292 return ret;
293 }
294
295 static int
ec_oct2point(const EC_GROUP * group,EC_POINT * point,const unsigned char * buf,size_t len,BN_CTX * ctx)296 ec_oct2point(const EC_GROUP *group, EC_POINT *point,
297 const unsigned char *buf, size_t len, BN_CTX *ctx)
298 {
299 CBS cbs;
300 uint8_t form;
301 int ybit;
302 BIGNUM *x, *y;
303 int ret = 0;
304
305 BN_CTX_start(ctx);
306 CBS_init(&cbs, buf, len);
307
308 if (!ec_get_leading_octet_cbs(&cbs, &form, &ybit))
309 goto err;
310
311 if (form == EC_POINT_AT_INFINITY) {
312 if (!EC_POINT_set_to_infinity(group, point))
313 goto err;
314
315 goto done;
316 }
317
318 if ((x = BN_CTX_get(ctx)) == NULL)
319 goto err;
320 if ((y = BN_CTX_get(ctx)) == NULL)
321 goto err;
322
323 if (form == EC_POINT_COMPRESSED) {
324 if (!ec_get_field_element_cbs(&cbs, group, x))
325 goto err;
326 if (!EC_POINT_set_compressed_coordinates(group, point, x, ybit, ctx))
327 goto err;
328 } else {
329 if (!ec_get_field_element_cbs(&cbs, group, x))
330 goto err;
331 if (!ec_get_field_element_cbs(&cbs, group, y))
332 goto err;
333 if (!ec_check_hybrid_ybit_is_consistent(form, ybit, y))
334 goto err;
335 if (!EC_POINT_set_affine_coordinates(group, point, x, y, ctx))
336 goto err;
337 }
338
339 done:
340 if (CBS_len(&cbs) > 0) {
341 ECerror(EC_R_INVALID_ENCODING);
342 goto err;
343 }
344
345 ret = 1;
346
347 err:
348 BN_CTX_end(ctx);
349
350 return ret;
351 }
352
353 int
ec_point_to_octets(const EC_GROUP * group,const EC_POINT * point,int form,unsigned char ** out_buf,size_t * out_len,BN_CTX * ctx)354 ec_point_to_octets(const EC_GROUP *group, const EC_POINT *point, int form,
355 unsigned char **out_buf, size_t *out_len, BN_CTX *ctx)
356 {
357 unsigned char *buf = NULL;
358 size_t len = 0;
359 int ret = 0;
360
361 *out_len = 0;
362
363 if (out_buf == NULL || *out_buf != NULL)
364 goto err;
365
366 if ((len = EC_POINT_point2oct(group, point, form, NULL, 0, ctx)) == 0)
367 goto err;
368 if ((buf = calloc(1, len)) == NULL)
369 goto err;
370 if (EC_POINT_point2oct(group, point, form, buf, len, ctx) != len)
371 goto err;
372
373 *out_buf = buf;
374 buf = NULL;
375 *out_len = len;
376 len = 0;
377
378 ret = 1;
379
380 err:
381 freezero(buf, len);
382
383 return ret;
384 }
385
386 int
ec_point_from_octets(const EC_GROUP * group,const unsigned char * buf,size_t buf_len,EC_POINT ** out_point,uint8_t * out_form,BN_CTX * ctx)387 ec_point_from_octets(const EC_GROUP *group, const unsigned char *buf, size_t buf_len,
388 EC_POINT **out_point, uint8_t *out_form, BN_CTX *ctx)
389 {
390 EC_POINT *point;
391 int ret = 0;
392
393 if ((point = *out_point) == NULL)
394 point = EC_POINT_new(group);
395 if (point == NULL)
396 goto err;
397
398 if (!EC_POINT_oct2point(group, point, buf, buf_len, ctx))
399 goto err;
400
401 if (out_form != NULL)
402 *out_form = buf[0] & ~EC_POINT_YBIT;
403
404 *out_point = point;
405 point = NULL;
406
407 ret = 1;
408
409 err:
410 if (*out_point != point)
411 EC_POINT_free(point);
412
413 return ret;
414 }
415
416 static int
ec_normalize_form(const EC_GROUP * group,const EC_POINT * point,int form,uint8_t * out_form)417 ec_normalize_form(const EC_GROUP *group, const EC_POINT *point, int form,
418 uint8_t *out_form)
419 {
420 /*
421 * Established behavior is to reject a request for the form 0 for the
422 * point at infinity even if it is valid.
423 */
424 if (form <= 0 || form > UINT8_MAX)
425 return 0;
426 if (!ec_conversion_form_is_valid(form))
427 return 0;
428
429 *out_form = form;
430 if (EC_POINT_is_at_infinity(group, point))
431 *out_form = EC_POINT_AT_INFINITY;
432
433 return 1;
434 }
435
436 size_t
EC_POINT_point2oct(const EC_GROUP * group,const EC_POINT * point,point_conversion_form_t conv_form,unsigned char * buf,size_t len,BN_CTX * ctx_in)437 EC_POINT_point2oct(const EC_GROUP *group, const EC_POINT *point,
438 point_conversion_form_t conv_form, unsigned char *buf, size_t len,
439 BN_CTX *ctx_in)
440 {
441 BN_CTX *ctx = NULL;
442 uint8_t form;
443 size_t ret = 0;
444
445 if (!ec_normalize_form(group, point, conv_form, &form)) {
446 ECerror(EC_R_INVALID_FORM);
447 goto err;
448 }
449
450 if ((ctx = ctx_in) == NULL)
451 ctx = BN_CTX_new();
452 if (ctx == NULL)
453 goto err;
454
455 if (group->meth != point->meth) {
456 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
457 goto err;
458 }
459 ret = ec_point2oct(group, point, form, buf, len, ctx);
460
461 err:
462 if (ctx != ctx_in)
463 BN_CTX_free(ctx);
464
465 return ret;
466 }
467 LCRYPTO_ALIAS(EC_POINT_point2oct);
468
469 int
EC_POINT_oct2point(const EC_GROUP * group,EC_POINT * point,const unsigned char * buf,size_t len,BN_CTX * ctx_in)470 EC_POINT_oct2point(const EC_GROUP *group, EC_POINT *point,
471 const unsigned char *buf, size_t len, BN_CTX *ctx_in)
472 {
473 BN_CTX *ctx;
474 int ret = 0;
475
476 if ((ctx = ctx_in) == NULL)
477 ctx = BN_CTX_new();
478 if (ctx == NULL)
479 goto err;
480
481 if (group->meth != point->meth) {
482 ECerror(EC_R_INCOMPATIBLE_OBJECTS);
483 goto err;
484 }
485 ret = ec_oct2point(group, point, buf, len, ctx);
486
487 err:
488 if (ctx != ctx_in)
489 BN_CTX_free(ctx);
490
491 return ret;
492 }
493 LCRYPTO_ALIAS(EC_POINT_oct2point);
494
495 BIGNUM *
EC_POINT_point2bn(const EC_GROUP * group,const EC_POINT * point,point_conversion_form_t form,BIGNUM * in_bn,BN_CTX * ctx)496 EC_POINT_point2bn(const EC_GROUP *group, const EC_POINT *point,
497 point_conversion_form_t form, BIGNUM *in_bn, BN_CTX *ctx)
498 {
499 BIGNUM *bn = NULL;
500 unsigned char *buf = NULL;
501 size_t buf_len = 0;
502
503 if (!ec_point_to_octets(group, point, form, &buf, &buf_len, ctx))
504 goto err;
505 if ((bn = BN_bin2bn(buf, buf_len, in_bn)) == NULL)
506 goto err;
507
508 err:
509 freezero(buf, buf_len);
510
511 return bn;
512 }
513 LCRYPTO_ALIAS(EC_POINT_point2bn);
514
515 EC_POINT *
EC_POINT_bn2point(const EC_GROUP * group,const BIGNUM * bn,EC_POINT * point,BN_CTX * ctx)516 EC_POINT_bn2point(const EC_GROUP *group,
517 const BIGNUM *bn, EC_POINT *point, BN_CTX *ctx)
518 {
519 unsigned char *buf = NULL;
520 size_t buf_len = 0;
521
522 /* Of course BN_bn2bin() is in no way symmetric to BN_bin2bn()... */
523 if ((buf_len = BN_num_bytes(bn)) == 0)
524 goto err;
525 if ((buf = calloc(1, buf_len)) == NULL)
526 goto err;
527 if (!BN_bn2bin(bn, buf))
528 goto err;
529 if (!ec_point_from_octets(group, buf, buf_len, &point, NULL, ctx))
530 goto err;
531
532 err:
533 freezero(buf, buf_len);
534
535 return point;
536 }
537 LCRYPTO_ALIAS(EC_POINT_bn2point);
538
539 char *
EC_POINT_point2hex(const EC_GROUP * group,const EC_POINT * point,point_conversion_form_t form,BN_CTX * ctx)540 EC_POINT_point2hex(const EC_GROUP *group, const EC_POINT *point,
541 point_conversion_form_t form, BN_CTX *ctx)
542 {
543 BIGNUM *bn;
544 char *hex = NULL;
545
546 if ((bn = EC_POINT_point2bn(group, point, form, NULL, ctx)) == NULL)
547 goto err;
548 if ((hex = BN_bn2hex(bn)) == NULL)
549 goto err;
550
551 err:
552 BN_free(bn);
553
554 return hex;
555 }
556 LCRYPTO_ALIAS(EC_POINT_point2hex);
557
558 EC_POINT *
EC_POINT_hex2point(const EC_GROUP * group,const char * hex,EC_POINT * in_point,BN_CTX * ctx)559 EC_POINT_hex2point(const EC_GROUP *group, const char *hex,
560 EC_POINT *in_point, BN_CTX *ctx)
561 {
562 EC_POINT *point = NULL;
563 BIGNUM *bn = NULL;
564
565 if (BN_hex2bn(&bn, hex) == 0)
566 goto err;
567 if ((point = EC_POINT_bn2point(group, bn, in_point, ctx)) == NULL)
568 goto err;
569
570 err:
571 BN_free(bn);
572
573 return point;
574 }
575 LCRYPTO_ALIAS(EC_POINT_hex2point);
576