1 /* $OpenBSD: bn_convert.c,v 1.21 2024/04/17 21:55:43 tb Exp $ */
2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3 * All rights reserved.
4 *
5 * This package is an SSL implementation written
6 * by Eric Young (eay@cryptsoft.com).
7 * The implementation was written so as to conform with Netscapes SSL.
8 *
9 * This library is free for commercial and non-commercial use as long as
10 * the following conditions are aheared to. The following conditions
11 * apply to all code found in this distribution, be it the RC4, RSA,
12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
13 * included with this distribution is covered by the same copyright terms
14 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15 *
16 * Copyright remains Eric Young's, and as such any Copyright notices in
17 * the code are not to be removed.
18 * If this package is used in a product, Eric Young should be given attribution
19 * as the author of the parts of the library used.
20 * This can be in the form of a textual message at program startup or
21 * in documentation (online or textual) provided with the package.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
25 * are met:
26 * 1. Redistributions of source code must retain the copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 3. All advertising materials mentioning features or use of this software
32 * must display the following acknowledgement:
33 * "This product includes cryptographic software written by
34 * Eric Young (eay@cryptsoft.com)"
35 * The word 'cryptographic' can be left out if the rouines from the library
36 * being used are not cryptographic related :-).
37 * 4. If you include any Windows specific code (or a derivative thereof) from
38 * the apps directory (application code) you must include an acknowledgement:
39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40 *
41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51 * SUCH DAMAGE.
52 *
53 * The licence and distribution terms for any publically available version or
54 * derivative of this code cannot be changed. i.e. this code cannot simply be
55 * copied and put under another distribution licence
56 * [including the GNU Public Licence.]
57 */
58
59 #include <ctype.h>
60 #include <limits.h>
61 #include <stdio.h>
62 #include <string.h>
63
64 #include <openssl/opensslconf.h>
65
66 #include <openssl/bio.h>
67 #include <openssl/buffer.h>
68 #include <openssl/err.h>
69
70 #include "bn_local.h"
71 #include "bytestring.h"
72
73 static int bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs);
74 static int bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs);
75
76 static const char hex_digits[] = "0123456789ABCDEF";
77
78 typedef enum {
79 big,
80 little,
81 } endianness_t;
82
83 /* ignore negative */
84 static int
bn2binpad(const BIGNUM * a,unsigned char * to,int tolen,endianness_t endianness)85 bn2binpad(const BIGNUM *a, unsigned char *to, int tolen, endianness_t endianness)
86 {
87 int n;
88 size_t i, lasti, j, atop, mask;
89 BN_ULONG l;
90
91 /*
92 * In case |a| is fixed-top, BN_num_bytes can return bogus length,
93 * but it's assumed that fixed-top inputs ought to be "nominated"
94 * even for padded output, so it works out...
95 */
96 n = BN_num_bytes(a);
97 if (tolen == -1)
98 tolen = n;
99 else if (tolen < n) { /* uncommon/unlike case */
100 BIGNUM temp = *a;
101
102 bn_correct_top(&temp);
103
104 n = BN_num_bytes(&temp);
105 if (tolen < n)
106 return -1;
107 }
108
109 /* Swipe through whole available data and don't give away padded zero. */
110 atop = a->dmax * BN_BYTES;
111 if (atop == 0) {
112 explicit_bzero(to, tolen);
113 return tolen;
114 }
115
116 lasti = atop - 1;
117 atop = a->top * BN_BYTES;
118
119 if (endianness == big)
120 to += tolen; /* start from the end of the buffer */
121
122 for (i = 0, j = 0; j < (size_t)tolen; j++) {
123 unsigned char val;
124
125 l = a->d[i / BN_BYTES];
126 mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1));
127 val = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask);
128
129 if (endianness == big)
130 *--to = val;
131 else
132 *to++ = val;
133
134 i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */
135 }
136
137 return tolen;
138 }
139
140 int
BN_bn2bin(const BIGNUM * a,unsigned char * to)141 BN_bn2bin(const BIGNUM *a, unsigned char *to)
142 {
143 return bn2binpad(a, to, -1, big);
144 }
145 LCRYPTO_ALIAS(BN_bn2bin);
146
147 int
BN_bn2binpad(const BIGNUM * a,unsigned char * to,int tolen)148 BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
149 {
150 if (tolen < 0)
151 return -1;
152 return bn2binpad(a, to, tolen, big);
153 }
154 LCRYPTO_ALIAS(BN_bn2binpad);
155
156 static int
bn_bin2bn_cbs(BIGNUM ** bnp,CBS * cbs,int lebin)157 bn_bin2bn_cbs(BIGNUM **bnp, CBS *cbs, int lebin)
158 {
159 BIGNUM *bn = NULL;
160 BN_ULONG w;
161 uint8_t v;
162 int b, i;
163
164 if ((bn = *bnp) == NULL)
165 bn = BN_new();
166 if (bn == NULL)
167 goto err;
168 if (!bn_expand_bytes(bn, CBS_len(cbs)))
169 goto err;
170
171 b = 0;
172 i = 0;
173 w = 0;
174
175 while (CBS_len(cbs) > 0) {
176 if (lebin) {
177 if (!CBS_get_u8(cbs, &v))
178 goto err;
179 } else {
180 if (!CBS_get_last_u8(cbs, &v))
181 goto err;
182 }
183
184 w |= (BN_ULONG)v << b;
185 b += 8;
186
187 if (b == BN_BITS2 || CBS_len(cbs) == 0) {
188 b = 0;
189 bn->d[i++] = w;
190 w = 0;
191 }
192 }
193
194 bn->neg = 0;
195 bn->top = i;
196
197 bn_correct_top(bn);
198
199 *bnp = bn;
200
201 return 1;
202
203 err:
204 if (*bnp == NULL)
205 BN_free(bn);
206
207 return 0;
208 }
209
210 BIGNUM *
BN_bin2bn(const unsigned char * d,int len,BIGNUM * bn)211 BN_bin2bn(const unsigned char *d, int len, BIGNUM *bn)
212 {
213 CBS cbs;
214
215 if (len < 0)
216 return NULL;
217
218 CBS_init(&cbs, d, len);
219
220 if (!bn_bin2bn_cbs(&bn, &cbs, 0))
221 return NULL;
222
223 return bn;
224 }
225 LCRYPTO_ALIAS(BN_bin2bn);
226
227 int
BN_bn2lebinpad(const BIGNUM * a,unsigned char * to,int tolen)228 BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
229 {
230 if (tolen < 0)
231 return -1;
232
233 return bn2binpad(a, to, tolen, little);
234 }
235 LCRYPTO_ALIAS(BN_bn2lebinpad);
236
237 BIGNUM *
BN_lebin2bn(const unsigned char * d,int len,BIGNUM * bn)238 BN_lebin2bn(const unsigned char *d, int len, BIGNUM *bn)
239 {
240 CBS cbs;
241
242 if (len < 0)
243 return NULL;
244
245 CBS_init(&cbs, d, len);
246
247 if (!bn_bin2bn_cbs(&bn, &cbs, 1))
248 return NULL;
249
250 return bn;
251 }
252 LCRYPTO_ALIAS(BN_lebin2bn);
253
254 int
BN_asc2bn(BIGNUM ** bnp,const char * s)255 BN_asc2bn(BIGNUM **bnp, const char *s)
256 {
257 CBS cbs, cbs_hex;
258 size_t s_len;
259 uint8_t v;
260 int neg;
261
262 if (bnp != NULL && *bnp != NULL)
263 BN_zero(*bnp);
264
265 if (s == NULL)
266 return 0;
267 if ((s_len = strlen(s)) == 0)
268 return 0;
269
270 CBS_init(&cbs, s, s_len);
271
272 /* Handle negative sign. */
273 if (!CBS_peek_u8(&cbs, &v))
274 return 0;
275 if ((neg = (v == '-'))) {
276 if (!CBS_skip(&cbs, 1))
277 return 0;
278 }
279
280 /* Try parsing as hexadecimal with a 0x prefix. */
281 CBS_dup(&cbs, &cbs_hex);
282 if (!CBS_get_u8(&cbs_hex, &v))
283 goto decimal;
284 if (v != '0')
285 goto decimal;
286 if (!CBS_get_u8(&cbs_hex, &v))
287 goto decimal;
288 if (v != 'X' && v != 'x')
289 goto decimal;
290 if (bn_hex2bn_cbs(bnp, &cbs_hex) == 0)
291 return 0;
292
293 goto done;
294
295 decimal:
296 if (bn_dec2bn_cbs(bnp, &cbs) == 0)
297 return 0;
298
299 done:
300 if (bnp != NULL && *bnp != NULL)
301 BN_set_negative(*bnp, neg);
302
303 return 1;
304 }
305 LCRYPTO_ALIAS(BN_asc2bn);
306
307 char *
BN_bn2dec(const BIGNUM * bn)308 BN_bn2dec(const BIGNUM *bn)
309 {
310 int started = 0;
311 BIGNUM *tmp = NULL;
312 uint8_t *data = NULL;
313 size_t data_len = 0;
314 uint8_t *s = NULL;
315 size_t s_len;
316 BN_ULONG v, w;
317 uint8_t c;
318 CBB cbb;
319 CBS cbs;
320 int i;
321
322 if (!CBB_init(&cbb, 0))
323 goto err;
324
325 if ((tmp = BN_dup(bn)) == NULL)
326 goto err;
327
328 /*
329 * Divide the BIGNUM by a large multiple of 10, then break the remainder
330 * into decimal digits. This produces a reversed string of digits,
331 * potentially with leading zeroes.
332 */
333 while (!BN_is_zero(tmp)) {
334 if ((w = BN_div_word(tmp, BN_DEC_CONV)) == -1)
335 goto err;
336 for (i = 0; i < BN_DEC_NUM; i++) {
337 v = w % 10;
338 if (!CBB_add_u8(&cbb, '0' + v))
339 goto err;
340 w /= 10;
341 }
342 }
343 if (!CBB_finish(&cbb, &data, &data_len))
344 goto err;
345
346 if (data_len > SIZE_MAX - 3)
347 goto err;
348 if (!CBB_init(&cbb, data_len + 3))
349 goto err;
350
351 if (BN_is_negative(bn)) {
352 if (!CBB_add_u8(&cbb, '-'))
353 goto err;
354 }
355
356 /* Reverse digits and trim leading zeroes. */
357 CBS_init(&cbs, data, data_len);
358 while (CBS_len(&cbs) > 0) {
359 if (!CBS_get_last_u8(&cbs, &c))
360 goto err;
361 if (!started && c == '0')
362 continue;
363 if (!CBB_add_u8(&cbb, c))
364 goto err;
365 started = 1;
366 }
367
368 if (!started) {
369 if (!CBB_add_u8(&cbb, '0'))
370 goto err;
371 }
372 if (!CBB_add_u8(&cbb, '\0'))
373 goto err;
374 if (!CBB_finish(&cbb, &s, &s_len))
375 goto err;
376
377 err:
378 BN_free(tmp);
379 CBB_cleanup(&cbb);
380 freezero(data, data_len);
381
382 return s;
383 }
384 LCRYPTO_ALIAS(BN_bn2dec);
385
386 static int
bn_dec2bn_cbs(BIGNUM ** bnp,CBS * cbs)387 bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs)
388 {
389 CBS cbs_digits;
390 BIGNUM *bn = NULL;
391 int d, neg, num;
392 size_t digits = 0;
393 BN_ULONG w;
394 uint8_t v;
395
396 /* Handle negative sign. */
397 if (!CBS_peek_u8(cbs, &v))
398 goto err;
399 if ((neg = (v == '-'))) {
400 if (!CBS_skip(cbs, 1))
401 goto err;
402 }
403
404 /* Scan to find last decimal digit. */
405 CBS_dup(cbs, &cbs_digits);
406 while (CBS_len(&cbs_digits) > 0) {
407 if (!CBS_get_u8(&cbs_digits, &v))
408 goto err;
409 if (!isdigit(v))
410 break;
411 digits++;
412 }
413 if (digits > INT_MAX / 4)
414 goto err;
415
416 num = digits + neg;
417
418 if (bnp == NULL)
419 return num;
420
421 if ((bn = *bnp) == NULL)
422 bn = BN_new();
423 if (bn == NULL)
424 goto err;
425 if (!bn_expand_bits(bn, digits * 4))
426 goto err;
427
428 if ((d = digits % BN_DEC_NUM) == 0)
429 d = BN_DEC_NUM;
430
431 w = 0;
432
433 /* Work forwards from most significant digit. */
434 while (digits-- > 0) {
435 if (!CBS_get_u8(cbs, &v))
436 goto err;
437
438 if (v < '0' || v > '9')
439 goto err;
440
441 v -= '0';
442 w = w * 10 + v;
443 d--;
444
445 if (d == 0) {
446 if (!BN_mul_word(bn, BN_DEC_CONV))
447 goto err;
448 if (!BN_add_word(bn, w))
449 goto err;
450
451 d = BN_DEC_NUM;
452 w = 0;
453 }
454 }
455
456 bn_correct_top(bn);
457
458 BN_set_negative(bn, neg);
459
460 *bnp = bn;
461
462 return num;
463
464 err:
465 if (bnp != NULL && *bnp == NULL)
466 BN_free(bn);
467
468 return 0;
469 }
470
471 int
BN_dec2bn(BIGNUM ** bnp,const char * s)472 BN_dec2bn(BIGNUM **bnp, const char *s)
473 {
474 size_t s_len;
475 CBS cbs;
476
477 if (bnp != NULL && *bnp != NULL)
478 BN_zero(*bnp);
479
480 if (s == NULL)
481 return 0;
482 if ((s_len = strlen(s)) == 0)
483 return 0;
484
485 CBS_init(&cbs, s, s_len);
486
487 return bn_dec2bn_cbs(bnp, &cbs);
488 }
489 LCRYPTO_ALIAS(BN_dec2bn);
490
491 static int
bn_bn2hex_internal(const BIGNUM * bn,int include_sign,int nibbles_only,char ** out,size_t * out_len)492 bn_bn2hex_internal(const BIGNUM *bn, int include_sign, int nibbles_only,
493 char **out, size_t *out_len)
494 {
495 int started = 0;
496 uint8_t *s = NULL;
497 size_t s_len = 0;
498 BN_ULONG v, w;
499 int i, j;
500 CBB cbb;
501 CBS cbs;
502 uint8_t nul;
503 int ret = 0;
504
505 *out = NULL;
506 *out_len = 0;
507
508 if (!CBB_init(&cbb, 0))
509 goto err;
510
511 if (BN_is_negative(bn) && include_sign) {
512 if (!CBB_add_u8(&cbb, '-'))
513 goto err;
514 }
515 if (BN_is_zero(bn)) {
516 if (!CBB_add_u8(&cbb, '0'))
517 goto err;
518 }
519 for (i = bn->top - 1; i >= 0; i--) {
520 w = bn->d[i];
521 for (j = BN_BITS2 - 8; j >= 0; j -= 8) {
522 v = (w >> j) & 0xff;
523 if (!started && v == 0)
524 continue;
525 if (started || !nibbles_only || (v >> 4) != 0) {
526 if (!CBB_add_u8(&cbb, hex_digits[v >> 4]))
527 goto err;
528 }
529 if (!CBB_add_u8(&cbb, hex_digits[v & 0xf]))
530 goto err;
531 started = 1;
532 }
533 }
534 if (!CBB_add_u8(&cbb, '\0'))
535 goto err;
536 if (!CBB_finish(&cbb, &s, &s_len))
537 goto err;
538
539 /* The length of a C string does not include the terminating NUL. */
540 CBS_init(&cbs, s, s_len);
541 if (!CBS_get_last_u8(&cbs, &nul))
542 goto err;
543
544 *out = (char *)CBS_data(&cbs);
545 *out_len = CBS_len(&cbs);
546 s = NULL;
547 s_len = 0;
548
549 ret = 1;
550
551 err:
552 CBB_cleanup(&cbb);
553 freezero(s, s_len);
554
555 return ret;
556 }
557
558 int
bn_bn2hex_nosign(const BIGNUM * bn,char ** out,size_t * out_len)559 bn_bn2hex_nosign(const BIGNUM *bn, char **out, size_t *out_len)
560 {
561 return bn_bn2hex_internal(bn, 0, 0, out, out_len);
562 }
563
564 int
bn_bn2hex_nibbles(const BIGNUM * bn,char ** out,size_t * out_len)565 bn_bn2hex_nibbles(const BIGNUM *bn, char **out, size_t *out_len)
566 {
567 return bn_bn2hex_internal(bn, 1, 1, out, out_len);
568 }
569
570 char *
BN_bn2hex(const BIGNUM * bn)571 BN_bn2hex(const BIGNUM *bn)
572 {
573 char *s;
574 size_t s_len;
575
576 if (!bn_bn2hex_internal(bn, 1, 0, &s, &s_len))
577 return NULL;
578
579 return s;
580 }
581 LCRYPTO_ALIAS(BN_bn2hex);
582
583 static int
bn_hex2bn_cbs(BIGNUM ** bnp,CBS * cbs)584 bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs)
585 {
586 CBS cbs_digits;
587 BIGNUM *bn = NULL;
588 int b, i, neg, num;
589 size_t digits = 0;
590 BN_ULONG w;
591 uint8_t v;
592
593 /* Handle negative sign. */
594 if (!CBS_peek_u8(cbs, &v))
595 goto err;
596 if ((neg = (v == '-'))) {
597 if (!CBS_skip(cbs, 1))
598 goto err;
599 }
600
601 /* Scan to find last hexadecimal digit. */
602 CBS_dup(cbs, &cbs_digits);
603 while (CBS_len(&cbs_digits) > 0) {
604 if (!CBS_get_u8(&cbs_digits, &v))
605 goto err;
606 if (!isxdigit(v))
607 break;
608 digits++;
609 }
610 if (digits > INT_MAX / 4)
611 goto err;
612
613 num = digits + neg;
614
615 if (bnp == NULL)
616 return num;
617
618 if ((bn = *bnp) == NULL)
619 bn = BN_new();
620 if (bn == NULL)
621 goto err;
622 if (!bn_expand_bits(bn, digits * 4))
623 goto err;
624
625 if (!CBS_get_bytes(cbs, cbs, digits))
626 goto err;
627
628 b = 0;
629 i = 0;
630 w = 0;
631
632 /* Work backwards from least significant digit. */
633 while (digits-- > 0) {
634 if (!CBS_get_last_u8(cbs, &v))
635 goto err;
636
637 if (v >= '0' && v <= '9')
638 v -= '0';
639 else if (v >= 'a' && v <= 'f')
640 v -= 'a' - 10;
641 else if (v >= 'A' && v <= 'F')
642 v -= 'A' - 10;
643 else
644 goto err;
645
646 w |= (BN_ULONG)v << b;
647 b += 4;
648
649 if (b == BN_BITS2 || digits == 0) {
650 b = 0;
651 bn->d[i++] = w;
652 w = 0;
653 }
654 }
655
656 bn->top = i;
657 bn_correct_top(bn);
658
659 BN_set_negative(bn, neg);
660
661 *bnp = bn;
662
663 return num;
664
665 err:
666 if (bnp != NULL && *bnp == NULL)
667 BN_free(bn);
668
669 return 0;
670 }
671
672 int
BN_hex2bn(BIGNUM ** bnp,const char * s)673 BN_hex2bn(BIGNUM **bnp, const char *s)
674 {
675 size_t s_len;
676 CBS cbs;
677
678 if (bnp != NULL && *bnp != NULL)
679 BN_zero(*bnp);
680
681 if (s == NULL)
682 return 0;
683 if ((s_len = strlen(s)) == 0)
684 return 0;
685
686 CBS_init(&cbs, s, s_len);
687
688 return bn_hex2bn_cbs(bnp, &cbs);
689 }
690 LCRYPTO_ALIAS(BN_hex2bn);
691
692 int
BN_bn2mpi(const BIGNUM * a,unsigned char * d)693 BN_bn2mpi(const BIGNUM *a, unsigned char *d)
694 {
695 int bits;
696 int num = 0;
697 int ext = 0;
698 long l;
699
700 bits = BN_num_bits(a);
701 num = (bits + 7) / 8;
702 if (bits > 0) {
703 ext = ((bits & 0x07) == 0);
704 }
705 if (d == NULL)
706 return (num + 4 + ext);
707
708 l = num + ext;
709 d[0] = (unsigned char)(l >> 24) & 0xff;
710 d[1] = (unsigned char)(l >> 16) & 0xff;
711 d[2] = (unsigned char)(l >> 8) & 0xff;
712 d[3] = (unsigned char)(l) & 0xff;
713 if (ext)
714 d[4] = 0;
715 num = BN_bn2bin(a, &(d[4 + ext]));
716 if (a->neg)
717 d[4] |= 0x80;
718 return (num + 4 + ext);
719 }
720 LCRYPTO_ALIAS(BN_bn2mpi);
721
722 BIGNUM *
BN_mpi2bn(const unsigned char * d,int n,BIGNUM * bn_in)723 BN_mpi2bn(const unsigned char *d, int n, BIGNUM *bn_in)
724 {
725 BIGNUM *bn = bn_in;
726 uint32_t mpi_len;
727 uint8_t v;
728 int neg = 0;
729 CBS cbs;
730
731 if (n < 0)
732 return NULL;
733
734 CBS_init(&cbs, d, n);
735
736 if (!CBS_get_u32(&cbs, &mpi_len)) {
737 BNerror(BN_R_INVALID_LENGTH);
738 return NULL;
739 }
740 if (CBS_len(&cbs) != mpi_len) {
741 BNerror(BN_R_ENCODING_ERROR);
742 return NULL;
743 }
744 if (CBS_len(&cbs) > 0) {
745 if (!CBS_peek_u8(&cbs, &v))
746 return NULL;
747 neg = (v >> 7) & 1;
748 }
749
750 if (!bn_bin2bn_cbs(&bn, &cbs, 0))
751 return NULL;
752
753 if (neg)
754 BN_clear_bit(bn, BN_num_bits(bn) - 1);
755
756 BN_set_negative(bn, neg);
757
758 return bn;
759 }
760 LCRYPTO_ALIAS(BN_mpi2bn);
761