1 /* $OpenBSD: bn_convert.c,v 1.23 2024/11/08 14:18:44 jsing 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 #include "crypto_internal.h"
73
74 static int bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs);
75 static int bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs);
76
77 static const char hex_digits[] = "0123456789ABCDEF";
78
79 static int
bn_bn2binpad_internal(const BIGNUM * bn,uint8_t * out,int out_len,int little_endian)80 bn_bn2binpad_internal(const BIGNUM *bn, uint8_t *out, int out_len,
81 int little_endian)
82 {
83 uint8_t mask, v;
84 BN_ULONG w;
85 int i, j;
86 int b, n;
87
88 n = BN_num_bytes(bn);
89
90 if (out_len == -1)
91 out_len = n;
92 if (out_len < n)
93 return -1;
94
95 if (bn->dmax == 0) {
96 explicit_bzero(out, out_len);
97 return out_len;
98 }
99
100 mask = 0;
101 b = BN_BITS2;
102 j = 0;
103
104 for (i = out_len - 1; i >= 0; i--) {
105 if (b == BN_BITS2) {
106 mask = crypto_ct_lt_mask(j, bn->top);
107 w = bn->d[j++ % bn->dmax];
108 b = 0;
109 }
110 out[i] = (w >> b) & mask;
111 b += 8;
112 }
113
114 if (little_endian) {
115 for (i = 0, j = out_len - 1; i < out_len / 2; i++, j--) {
116 v = out[i];
117 out[i] = out[j];
118 out[j] = v;
119 }
120 }
121
122 return out_len;
123 }
124
125 int
BN_bn2bin(const BIGNUM * bn,unsigned char * to)126 BN_bn2bin(const BIGNUM *bn, unsigned char *to)
127 {
128 return bn_bn2binpad_internal(bn, to, -1, 0);
129 }
130 LCRYPTO_ALIAS(BN_bn2bin);
131
132 int
BN_bn2binpad(const BIGNUM * bn,unsigned char * to,int to_len)133 BN_bn2binpad(const BIGNUM *bn, unsigned char *to, int to_len)
134 {
135 if (to_len < 0)
136 return -1;
137
138 return bn_bn2binpad_internal(bn, to, to_len, 0);
139 }
140 LCRYPTO_ALIAS(BN_bn2binpad);
141
142 static int
bn_bin2bn_cbs(BIGNUM ** bnp,CBS * cbs,int lebin)143 bn_bin2bn_cbs(BIGNUM **bnp, CBS *cbs, int lebin)
144 {
145 BIGNUM *bn = NULL;
146 BN_ULONG w;
147 uint8_t v;
148 int b, i;
149
150 if ((bn = *bnp) == NULL)
151 bn = BN_new();
152 if (bn == NULL)
153 goto err;
154 if (!bn_expand_bytes(bn, CBS_len(cbs)))
155 goto err;
156
157 b = 0;
158 i = 0;
159 w = 0;
160
161 while (CBS_len(cbs) > 0) {
162 if (lebin) {
163 if (!CBS_get_u8(cbs, &v))
164 goto err;
165 } else {
166 if (!CBS_get_last_u8(cbs, &v))
167 goto err;
168 }
169
170 w |= (BN_ULONG)v << b;
171 b += 8;
172
173 if (b == BN_BITS2 || CBS_len(cbs) == 0) {
174 b = 0;
175 bn->d[i++] = w;
176 w = 0;
177 }
178 }
179
180 bn->neg = 0;
181 bn->top = i;
182
183 bn_correct_top(bn);
184
185 *bnp = bn;
186
187 return 1;
188
189 err:
190 if (*bnp == NULL)
191 BN_free(bn);
192
193 return 0;
194 }
195
196 BIGNUM *
BN_bin2bn(const unsigned char * d,int len,BIGNUM * bn)197 BN_bin2bn(const unsigned char *d, int len, BIGNUM *bn)
198 {
199 CBS cbs;
200
201 if (len < 0)
202 return NULL;
203
204 CBS_init(&cbs, d, len);
205
206 if (!bn_bin2bn_cbs(&bn, &cbs, 0))
207 return NULL;
208
209 return bn;
210 }
211 LCRYPTO_ALIAS(BN_bin2bn);
212
213 int
BN_bn2lebinpad(const BIGNUM * bn,unsigned char * to,int to_len)214 BN_bn2lebinpad(const BIGNUM *bn, unsigned char *to, int to_len)
215 {
216 if (to_len < 0)
217 return -1;
218
219 return bn_bn2binpad_internal(bn, to, to_len, 1);
220 }
221 LCRYPTO_ALIAS(BN_bn2lebinpad);
222
223 BIGNUM *
BN_lebin2bn(const unsigned char * d,int len,BIGNUM * bn)224 BN_lebin2bn(const unsigned char *d, int len, BIGNUM *bn)
225 {
226 CBS cbs;
227
228 if (len < 0)
229 return NULL;
230
231 CBS_init(&cbs, d, len);
232
233 if (!bn_bin2bn_cbs(&bn, &cbs, 1))
234 return NULL;
235
236 return bn;
237 }
238 LCRYPTO_ALIAS(BN_lebin2bn);
239
240 int
BN_asc2bn(BIGNUM ** bnp,const char * s)241 BN_asc2bn(BIGNUM **bnp, const char *s)
242 {
243 CBS cbs, cbs_hex;
244 size_t s_len;
245 uint8_t v;
246 int neg;
247
248 if (bnp != NULL && *bnp != NULL)
249 BN_zero(*bnp);
250
251 if (s == NULL)
252 return 0;
253 if ((s_len = strlen(s)) == 0)
254 return 0;
255
256 CBS_init(&cbs, s, s_len);
257
258 /* Handle negative sign. */
259 if (!CBS_peek_u8(&cbs, &v))
260 return 0;
261 if ((neg = (v == '-'))) {
262 if (!CBS_skip(&cbs, 1))
263 return 0;
264 }
265
266 /* Try parsing as hexadecimal with a 0x prefix. */
267 CBS_dup(&cbs, &cbs_hex);
268 if (!CBS_get_u8(&cbs_hex, &v))
269 goto decimal;
270 if (v != '0')
271 goto decimal;
272 if (!CBS_get_u8(&cbs_hex, &v))
273 goto decimal;
274 if (v != 'X' && v != 'x')
275 goto decimal;
276 if (bn_hex2bn_cbs(bnp, &cbs_hex) == 0)
277 return 0;
278
279 goto done;
280
281 decimal:
282 if (bn_dec2bn_cbs(bnp, &cbs) == 0)
283 return 0;
284
285 done:
286 if (bnp != NULL && *bnp != NULL)
287 BN_set_negative(*bnp, neg);
288
289 return 1;
290 }
291 LCRYPTO_ALIAS(BN_asc2bn);
292
293 char *
BN_bn2dec(const BIGNUM * bn)294 BN_bn2dec(const BIGNUM *bn)
295 {
296 int started = 0;
297 BIGNUM *tmp = NULL;
298 uint8_t *data = NULL;
299 size_t data_len = 0;
300 uint8_t *s = NULL;
301 size_t s_len;
302 BN_ULONG v, w;
303 uint8_t c;
304 CBB cbb;
305 CBS cbs;
306 int i;
307
308 if (!CBB_init(&cbb, 0))
309 goto err;
310
311 if ((tmp = BN_dup(bn)) == NULL)
312 goto err;
313
314 /*
315 * Divide the BIGNUM by a large multiple of 10, then break the remainder
316 * into decimal digits. This produces a reversed string of digits,
317 * potentially with leading zeroes.
318 */
319 while (!BN_is_zero(tmp)) {
320 if ((w = BN_div_word(tmp, BN_DEC_CONV)) == -1)
321 goto err;
322 for (i = 0; i < BN_DEC_NUM; i++) {
323 v = w % 10;
324 if (!CBB_add_u8(&cbb, '0' + v))
325 goto err;
326 w /= 10;
327 }
328 }
329 if (!CBB_finish(&cbb, &data, &data_len))
330 goto err;
331
332 if (data_len > SIZE_MAX - 3)
333 goto err;
334 if (!CBB_init(&cbb, data_len + 3))
335 goto err;
336
337 if (BN_is_negative(bn)) {
338 if (!CBB_add_u8(&cbb, '-'))
339 goto err;
340 }
341
342 /* Reverse digits and trim leading zeroes. */
343 CBS_init(&cbs, data, data_len);
344 while (CBS_len(&cbs) > 0) {
345 if (!CBS_get_last_u8(&cbs, &c))
346 goto err;
347 if (!started && c == '0')
348 continue;
349 if (!CBB_add_u8(&cbb, c))
350 goto err;
351 started = 1;
352 }
353
354 if (!started) {
355 if (!CBB_add_u8(&cbb, '0'))
356 goto err;
357 }
358 if (!CBB_add_u8(&cbb, '\0'))
359 goto err;
360 if (!CBB_finish(&cbb, &s, &s_len))
361 goto err;
362
363 err:
364 BN_free(tmp);
365 CBB_cleanup(&cbb);
366 freezero(data, data_len);
367
368 return s;
369 }
370 LCRYPTO_ALIAS(BN_bn2dec);
371
372 static int
bn_dec2bn_cbs(BIGNUM ** bnp,CBS * cbs)373 bn_dec2bn_cbs(BIGNUM **bnp, CBS *cbs)
374 {
375 CBS cbs_digits;
376 BIGNUM *bn = NULL;
377 int d, neg, num;
378 size_t digits = 0;
379 BN_ULONG w;
380 uint8_t v;
381
382 /* Handle negative sign. */
383 if (!CBS_peek_u8(cbs, &v))
384 goto err;
385 if ((neg = (v == '-'))) {
386 if (!CBS_skip(cbs, 1))
387 goto err;
388 }
389
390 /* Scan to find last decimal digit. */
391 CBS_dup(cbs, &cbs_digits);
392 while (CBS_len(&cbs_digits) > 0) {
393 if (!CBS_get_u8(&cbs_digits, &v))
394 goto err;
395 if (!isdigit(v))
396 break;
397 digits++;
398 }
399 if (digits > INT_MAX / 4)
400 goto err;
401
402 num = digits + neg;
403
404 if (bnp == NULL)
405 return num;
406
407 if ((bn = *bnp) == NULL)
408 bn = BN_new();
409 if (bn == NULL)
410 goto err;
411 if (!bn_expand_bits(bn, digits * 4))
412 goto err;
413
414 if ((d = digits % BN_DEC_NUM) == 0)
415 d = BN_DEC_NUM;
416
417 w = 0;
418
419 /* Work forwards from most significant digit. */
420 while (digits-- > 0) {
421 if (!CBS_get_u8(cbs, &v))
422 goto err;
423
424 if (v < '0' || v > '9')
425 goto err;
426
427 v -= '0';
428 w = w * 10 + v;
429 d--;
430
431 if (d == 0) {
432 if (!BN_mul_word(bn, BN_DEC_CONV))
433 goto err;
434 if (!BN_add_word(bn, w))
435 goto err;
436
437 d = BN_DEC_NUM;
438 w = 0;
439 }
440 }
441
442 bn_correct_top(bn);
443
444 BN_set_negative(bn, neg);
445
446 *bnp = bn;
447
448 return num;
449
450 err:
451 if (bnp != NULL && *bnp == NULL)
452 BN_free(bn);
453
454 return 0;
455 }
456
457 int
BN_dec2bn(BIGNUM ** bnp,const char * s)458 BN_dec2bn(BIGNUM **bnp, const char *s)
459 {
460 size_t s_len;
461 CBS cbs;
462
463 if (bnp != NULL && *bnp != NULL)
464 BN_zero(*bnp);
465
466 if (s == NULL)
467 return 0;
468 if ((s_len = strlen(s)) == 0)
469 return 0;
470
471 CBS_init(&cbs, s, s_len);
472
473 return bn_dec2bn_cbs(bnp, &cbs);
474 }
475 LCRYPTO_ALIAS(BN_dec2bn);
476
477 static int
bn_bn2hex_internal(const BIGNUM * bn,int include_sign,int nibbles_only,char ** out,size_t * out_len)478 bn_bn2hex_internal(const BIGNUM *bn, int include_sign, int nibbles_only,
479 char **out, size_t *out_len)
480 {
481 int started = 0;
482 uint8_t *s = NULL;
483 size_t s_len = 0;
484 BN_ULONG v, w;
485 int i, j;
486 CBB cbb;
487 CBS cbs;
488 uint8_t nul;
489 int ret = 0;
490
491 *out = NULL;
492 *out_len = 0;
493
494 if (!CBB_init(&cbb, 0))
495 goto err;
496
497 if (BN_is_negative(bn) && include_sign) {
498 if (!CBB_add_u8(&cbb, '-'))
499 goto err;
500 }
501 if (BN_is_zero(bn)) {
502 if (!CBB_add_u8(&cbb, '0'))
503 goto err;
504 }
505 for (i = bn->top - 1; i >= 0; i--) {
506 w = bn->d[i];
507 for (j = BN_BITS2 - 8; j >= 0; j -= 8) {
508 v = (w >> j) & 0xff;
509 if (!started && v == 0)
510 continue;
511 if (started || !nibbles_only || (v >> 4) != 0) {
512 if (!CBB_add_u8(&cbb, hex_digits[v >> 4]))
513 goto err;
514 }
515 if (!CBB_add_u8(&cbb, hex_digits[v & 0xf]))
516 goto err;
517 started = 1;
518 }
519 }
520 if (!CBB_add_u8(&cbb, '\0'))
521 goto err;
522 if (!CBB_finish(&cbb, &s, &s_len))
523 goto err;
524
525 /* The length of a C string does not include the terminating NUL. */
526 CBS_init(&cbs, s, s_len);
527 if (!CBS_get_last_u8(&cbs, &nul))
528 goto err;
529
530 *out = (char *)CBS_data(&cbs);
531 *out_len = CBS_len(&cbs);
532 s = NULL;
533 s_len = 0;
534
535 ret = 1;
536
537 err:
538 CBB_cleanup(&cbb);
539 freezero(s, s_len);
540
541 return ret;
542 }
543
544 int
bn_bn2hex_nosign(const BIGNUM * bn,char ** out,size_t * out_len)545 bn_bn2hex_nosign(const BIGNUM *bn, char **out, size_t *out_len)
546 {
547 return bn_bn2hex_internal(bn, 0, 0, out, out_len);
548 }
549
550 int
bn_bn2hex_nibbles(const BIGNUM * bn,char ** out,size_t * out_len)551 bn_bn2hex_nibbles(const BIGNUM *bn, char **out, size_t *out_len)
552 {
553 return bn_bn2hex_internal(bn, 1, 1, out, out_len);
554 }
555
556 char *
BN_bn2hex(const BIGNUM * bn)557 BN_bn2hex(const BIGNUM *bn)
558 {
559 char *s;
560 size_t s_len;
561
562 if (!bn_bn2hex_internal(bn, 1, 0, &s, &s_len))
563 return NULL;
564
565 return s;
566 }
567 LCRYPTO_ALIAS(BN_bn2hex);
568
569 static int
bn_hex2bn_cbs(BIGNUM ** bnp,CBS * cbs)570 bn_hex2bn_cbs(BIGNUM **bnp, CBS *cbs)
571 {
572 CBS cbs_digits;
573 BIGNUM *bn = NULL;
574 int b, i, neg, num;
575 size_t digits = 0;
576 BN_ULONG w;
577 uint8_t v;
578
579 /* Handle negative sign. */
580 if (!CBS_peek_u8(cbs, &v))
581 goto err;
582 if ((neg = (v == '-'))) {
583 if (!CBS_skip(cbs, 1))
584 goto err;
585 }
586
587 /* Scan to find last hexadecimal digit. */
588 CBS_dup(cbs, &cbs_digits);
589 while (CBS_len(&cbs_digits) > 0) {
590 if (!CBS_get_u8(&cbs_digits, &v))
591 goto err;
592 if (!isxdigit(v))
593 break;
594 digits++;
595 }
596 if (digits > INT_MAX / 4)
597 goto err;
598
599 num = digits + neg;
600
601 if (bnp == NULL)
602 return num;
603
604 if ((bn = *bnp) == NULL)
605 bn = BN_new();
606 if (bn == NULL)
607 goto err;
608 if (!bn_expand_bits(bn, digits * 4))
609 goto err;
610
611 if (!CBS_get_bytes(cbs, cbs, digits))
612 goto err;
613
614 b = 0;
615 i = 0;
616 w = 0;
617
618 /* Work backwards from least significant digit. */
619 while (digits-- > 0) {
620 if (!CBS_get_last_u8(cbs, &v))
621 goto err;
622
623 if (v >= '0' && v <= '9')
624 v -= '0';
625 else if (v >= 'a' && v <= 'f')
626 v -= 'a' - 10;
627 else if (v >= 'A' && v <= 'F')
628 v -= 'A' - 10;
629 else
630 goto err;
631
632 w |= (BN_ULONG)v << b;
633 b += 4;
634
635 if (b == BN_BITS2 || digits == 0) {
636 b = 0;
637 bn->d[i++] = w;
638 w = 0;
639 }
640 }
641
642 bn->top = i;
643 bn_correct_top(bn);
644
645 BN_set_negative(bn, neg);
646
647 *bnp = bn;
648
649 return num;
650
651 err:
652 if (bnp != NULL && *bnp == NULL)
653 BN_free(bn);
654
655 return 0;
656 }
657
658 int
BN_hex2bn(BIGNUM ** bnp,const char * s)659 BN_hex2bn(BIGNUM **bnp, const char *s)
660 {
661 size_t s_len;
662 CBS cbs;
663
664 if (bnp != NULL && *bnp != NULL)
665 BN_zero(*bnp);
666
667 if (s == NULL)
668 return 0;
669 if ((s_len = strlen(s)) == 0)
670 return 0;
671
672 CBS_init(&cbs, s, s_len);
673
674 return bn_hex2bn_cbs(bnp, &cbs);
675 }
676 LCRYPTO_ALIAS(BN_hex2bn);
677
678 int
BN_bn2mpi(const BIGNUM * bn,unsigned char * d)679 BN_bn2mpi(const BIGNUM *bn, unsigned char *d)
680 {
681 uint8_t *out_bin;
682 size_t out_len, out_bin_len;
683 int bits, bytes;
684 int extend;
685 CBB cbb, cbb_bin;
686
687 bits = BN_num_bits(bn);
688 bytes = (bits + 7) / 8;
689 extend = (bits != 0) && (bits % 8 == 0);
690 out_bin_len = extend + bytes;
691 out_len = 4 + out_bin_len;
692
693 if (d == NULL)
694 return out_len;
695
696 if (!CBB_init_fixed(&cbb, d, out_len))
697 goto err;
698 if (!CBB_add_u32_length_prefixed(&cbb, &cbb_bin))
699 goto err;
700 if (!CBB_add_space(&cbb_bin, &out_bin, out_bin_len))
701 goto err;
702 if (BN_bn2binpad(bn, out_bin, out_bin_len) != out_bin_len)
703 goto err;
704 if (!CBB_finish(&cbb, NULL, NULL))
705 goto err;
706
707 if (bn->neg)
708 d[4] |= 0x80;
709
710 return out_len;
711
712 err:
713 CBB_cleanup(&cbb);
714
715 return -1;
716 }
717 LCRYPTO_ALIAS(BN_bn2mpi);
718
719 BIGNUM *
BN_mpi2bn(const unsigned char * d,int n,BIGNUM * bn_in)720 BN_mpi2bn(const unsigned char *d, int n, BIGNUM *bn_in)
721 {
722 BIGNUM *bn = bn_in;
723 uint32_t mpi_len;
724 uint8_t v;
725 int neg = 0;
726 CBS cbs;
727
728 if (n < 0)
729 return NULL;
730
731 CBS_init(&cbs, d, n);
732
733 if (!CBS_get_u32(&cbs, &mpi_len)) {
734 BNerror(BN_R_INVALID_LENGTH);
735 return NULL;
736 }
737 if (CBS_len(&cbs) != mpi_len) {
738 BNerror(BN_R_ENCODING_ERROR);
739 return NULL;
740 }
741 if (CBS_len(&cbs) > 0) {
742 if (!CBS_peek_u8(&cbs, &v))
743 return NULL;
744 neg = (v >> 7) & 1;
745 }
746
747 if (!bn_bin2bn_cbs(&bn, &cbs, 0))
748 return NULL;
749
750 if (neg)
751 BN_clear_bit(bn, BN_num_bits(bn) - 1);
752
753 BN_set_negative(bn, neg);
754
755 return bn;
756 }
757 LCRYPTO_ALIAS(BN_mpi2bn);
758