Debian Codegraph @

external/boringssl/crypto/bn/convert.c

raw
1 /* Copyright (C) 1995-1998 Eric Young ([email protected])
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young ([email protected]).
6 * The implementation was written so as to conform with Netscapes SSL.
7 *
8 * This library is free for commercial and non-commercial use as long as
9 * the following conditions are aheared to. The following conditions
10 * apply to all code found in this distribution, be it the RC4, RSA,
11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation
12 * included with this distribution is covered by the same copyright terms
13 * except that the holder is Tim Hudson ([email protected]).
14 *
15 * Copyright remains Eric Young's, and as such any Copyright notices in
16 * the code are not to be removed.
17 * If this package is used in a product, Eric Young should be given attribution
18 * as the author of the parts of the library used.
19 * This can be in the form of a textual message at program startup or
20 * in documentation (online or textual) provided with the package.
21 *
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
24 * are met:
25 * 1. Redistributions of source code must retain the copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 3. All advertising materials mentioning features or use of this software
31 * must display the following acknowledgement:
32 * "This product includes cryptographic software written by
33 * Eric Young ([email protected])"
34 * The word 'cryptographic' can be left out if the rouines from the library
35 * being used are not cryptographic related :-).
36 * 4. If you include any Windows specific code (or a derivative thereof) from
37 * the apps directory (application code) you must include an acknowledgement:
38 * "This product includes software written by Tim Hudson ([email protected])"
39 *
40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50 * SUCH DAMAGE.
51 *
52 * The licence and distribution terms for any publically available version or
53 * derivative of this code cannot be changed. i.e. this code cannot simply be
54 * copied and put under another distribution licence
55 * [including the GNU Public Licence.] */
56
57 #include <openssl/bn.h>
58
59 #include <assert.h>
60 #include <ctype.h>
61 #include <limits.h>
62 #include <stdio.h>
63 #include <string.h>
64
65 #include <openssl/bio.h>
66 #include <openssl/bytestring.h>
67 #include <openssl/err.h>
68 #include <openssl/mem.h>
69
70 #include "internal.h"
71
72 BIGNUM *BN_bin2bn(const uint8_t *in, size_t len, BIGNUM *ret) {
73 size_t num_words;
74 unsigned m;
75 BN_ULONG word = 0;
76 BIGNUM *bn = NULL;
77
78 if (ret == NULL) {
79 ret = bn = BN_new();
80 }
81
82 if (ret == NULL) {
83 return NULL;
84 }
85
86 if (len == 0) {
87 ret->top = 0;
88 return ret;
89 }
90
91 num_words = ((len - 1) / BN_BYTES) + 1;
92 m = (len - 1) % BN_BYTES;
93 if (bn_wexpand(ret, num_words) == NULL) {
94 if (bn) {
95 BN_free(bn);
96 }
97 return NULL;
98 }
99
100 /* |bn_wexpand| must check bounds on |num_words| to write it into
101 * |ret->dmax|. */
102 assert(num_words <= INT_MAX);
103 ret->top = (int)num_words;
104 ret->neg = 0;
105
106 while (len--) {
107 word = (word << 8) | *(in++);
108 if (m-- == 0) {
109 ret->d[--num_words] = word;
110 word = 0;
111 m = BN_BYTES - 1;
112 }
113 }
114
115 /* need to call this due to clear byte at top if avoiding having the top bit
116 * set (-ve number) */
117 bn_correct_top(ret);
118 return ret;
119 }
120
121 size_t BN_bn2bin(const BIGNUM *in, uint8_t *out) {
122 size_t n, i;
123 BN_ULONG l;
124
125 n = i = BN_num_bytes(in);
126 while (i--) {
127 l = in->d[i / BN_BYTES];
128 *(out++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
129 }
130 return n;
131 }
132
133 /* constant_time_select_ulong returns |x| if |v| is 1 and |y| if |v| is 0. Its
134 * behavior is undefined if |v| takes any other value. */
135 static BN_ULONG constant_time_select_ulong(int v, BN_ULONG x, BN_ULONG y) {
136 BN_ULONG mask = v;
137 mask--;
138
139 return (~mask & x) | (mask & y);
140 }
141
142 /* constant_time_le_size_t returns 1 if |x| <= |y| and 0 otherwise. |x| and |y|
143 * must not have their MSBs set. */
144 static int constant_time_le_size_t(size_t x, size_t y) {
145 return ((x - y - 1) >> (sizeof(size_t) * 8 - 1)) & 1;
146 }
147
148 /* read_word_padded returns the |i|'th word of |in|, if it is not out of
149 * bounds. Otherwise, it returns 0. It does so without branches on the size of
150 * |in|, however it necessarily does not have the same memory access pattern. If
151 * the access would be out of bounds, it reads the last word of |in|. |in| must
152 * not be zero. */
153 static BN_ULONG read_word_padded(const BIGNUM *in, size_t i) {
154 /* Read |in->d[i]| if valid. Otherwise, read the last word. */
155 BN_ULONG l = in->d[constant_time_select_ulong(
156 constant_time_le_size_t(in->dmax, i), in->dmax - 1, i)];
157
158 /* Clamp to zero if above |d->top|. */
159 return constant_time_select_ulong(constant_time_le_size_t(in->top, i), 0, l);
160 }
161
162 int BN_bn2bin_padded(uint8_t *out, size_t len, const BIGNUM *in) {
163 size_t i;
164 BN_ULONG l;
165
166 /* Special case for |in| = 0. Just branch as the probability is negligible. */
167 if (BN_is_zero(in)) {
168 memset(out, 0, len);
169 return 1;
170 }
171
172 /* Check if the integer is too big. This case can exit early in non-constant
173 * time. */
174 if ((size_t)in->top > (len + (BN_BYTES - 1)) / BN_BYTES) {
175 return 0;
176 }
177 if ((len % BN_BYTES) != 0) {
178 l = read_word_padded(in, len / BN_BYTES);
179 if (l >> (8 * (len % BN_BYTES)) != 0) {
180 return 0;
181 }
182 }
183
184 /* Write the bytes out one by one. Serialization is done without branching on
185 * the bits of |in| or on |in->top|, but if the routine would otherwise read
186 * out of bounds, the memory access pattern can't be fixed. However, for an
187 * RSA key of size a multiple of the word size, the probability of BN_BYTES
188 * leading zero octets is low.
189 *
190 * See Falko Stenzke, "Manger's Attack revisited", ICICS 2010. */
191 i = len;
192 while (i--) {
193 l = read_word_padded(in, i / BN_BYTES);
194 *(out++) = (uint8_t)(l >> (8 * (i % BN_BYTES))) & 0xff;
195 }
196 return 1;
197 }
198
199 int BN_bn2cbb_padded(CBB *out, size_t len, const BIGNUM *in) {
200 uint8_t *ptr;
201 return CBB_add_space(out, &ptr, len) && BN_bn2bin_padded(ptr, len, in);
202 }
203
204 static const char hextable[] = "0123456789abcdef";
205
206 char *BN_bn2hex(const BIGNUM *bn) {
207 int i, j, v, z = 0;
208 char *buf;
209 char *p;
210
211 buf = OPENSSL_malloc(bn->top * BN_BYTES * 2 + 2);
212 if (buf == NULL) {
213 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
214 return NULL;
215 }
216
217 p = buf;
218 if (bn->neg) {
219 *(p++) = '-';
220 }
221
222 if (BN_is_zero(bn)) {
223 *(p++) = '0';
224 }
225
226 for (i = bn->top - 1; i >= 0; i--) {
227 for (j = BN_BITS2 - 8; j >= 0; j -= 8) {
228 /* strip leading zeros */
229 v = ((int)(bn->d[i] >> (long)j)) & 0xff;
230 if (z || v != 0) {
231 *(p++) = hextable[v >> 4];
232 *(p++) = hextable[v & 0x0f];
233 z = 1;
234 }
235 }
236 }
237 *p = '\0';
238
239 return buf;
240 }
241
242 /* decode_hex decodes |in_len| bytes of hex data from |in| and updates |bn|. */
243 static int decode_hex(BIGNUM *bn, const char *in, int in_len) {
244 if (in_len > INT_MAX/4) {
245 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
246 return 0;
247 }
248 /* |in_len| is the number of hex digits. */
249 if (bn_expand(bn, in_len * 4) == NULL) {
250 return 0;
251 }
252
253 int i = 0;
254 while (in_len > 0) {
255 /* Decode one |BN_ULONG| at a time. */
256 int todo = BN_BYTES * 2;
257 if (todo > in_len) {
258 todo = in_len;
259 }
260
261 BN_ULONG word = 0;
262 int j;
263 for (j = todo; j > 0; j--) {
264 char c = in[in_len - j];
265
266 BN_ULONG hex;
267 if (c >= '0' && c <= '9') {
268 hex = c - '0';
269 } else if (c >= 'a' && c <= 'f') {
270 hex = c - 'a' + 10;
271 } else if (c >= 'A' && c <= 'F') {
272 hex = c - 'A' + 10;
273 } else {
274 hex = 0;
275 /* This shouldn't happen. The caller checks |isxdigit|. */
276 assert(0);
277 }
278 word = (word << 4) | hex;
279 }
280
281 bn->d[i++] = word;
282 in_len -= todo;
283 }
284 assert(i <= bn->dmax);
285 bn->top = i;
286 return 1;
287 }
288
289 /* decode_dec decodes |in_len| bytes of decimal data from |in| and updates |bn|. */
290 static int decode_dec(BIGNUM *bn, const char *in, int in_len) {
291 int i, j;
292 BN_ULONG l = 0;
293
294 /* Decode |BN_DEC_NUM| digits at a time. */
295 j = BN_DEC_NUM - (in_len % BN_DEC_NUM);
296 if (j == BN_DEC_NUM) {
297 j = 0;
298 }
299 l = 0;
300 for (i = 0; i < in_len; i++) {
301 l *= 10;
302 l += in[i] - '0';
303 if (++j == BN_DEC_NUM) {
304 if (!BN_mul_word(bn, BN_DEC_CONV) ||
305 !BN_add_word(bn, l)) {
306 return 0;
307 }
308 l = 0;
309 j = 0;
310 }
311 }
312 return 1;
313 }
314
315 typedef int (*decode_func) (BIGNUM *bn, const char *in, int in_len);
316 typedef int (*char_test_func) (int c);
317
318 static int bn_x2bn(BIGNUM **outp, const char *in, decode_func decode, char_test_func want_char) {
319 BIGNUM *ret = NULL;
320 int neg = 0, i;
321 int num;
322
323 if (in == NULL || *in == 0) {
324 return 0;
325 }
326
327 if (*in == '-') {
328 neg = 1;
329 in++;
330 }
331
332 for (i = 0; want_char((unsigned char)in[i]) && i + neg < INT_MAX; i++) {}
333
334 num = i + neg;
335 if (outp == NULL) {
336 return num;
337 }
338
339 /* in is the start of the hex digits, and it is 'i' long */
340 if (*outp == NULL) {
341 ret = BN_new();
342 if (ret == NULL) {
343 return 0;
344 }
345 } else {
346 ret = *outp;
347 BN_zero(ret);
348 }
349
350 if (!decode(ret, in, i)) {
351 goto err;
352 }
353
354 bn_correct_top(ret);
355 if (!BN_is_zero(ret)) {
356 ret->neg = neg;
357 }
358
359 *outp = ret;
360 return num;
361
362 err:
363 if (*outp == NULL) {
364 BN_free(ret);
365 }
366
367 return 0;
368 }
369
370 int BN_hex2bn(BIGNUM **outp, const char *in) {
371 return bn_x2bn(outp, in, decode_hex, isxdigit);
372 }
373
374 char *BN_bn2dec(const BIGNUM *a) {
375 int i = 0, num, ok = 0;
376 char *buf = NULL;
377 char *p;
378 BIGNUM *t = NULL;
379 BN_ULONG *bn_data = NULL, *lp;
380
381 /* get an upper bound for the length of the decimal integer
382 * num <= (BN_num_bits(a) + 1) * log(2)
383 * <= 3 * BN_num_bits(a) * 0.1001 + log(2) + 1 (rounding error)
384 * <= BN_num_bits(a)/10 + BN_num_bits/1000 + 1 + 1
385 */
386 i = BN_num_bits(a) * 3;
387 num = i / 10 + i / 1000 + 1 + 1;
388 bn_data = OPENSSL_malloc((num / BN_DEC_NUM + 1) * sizeof(BN_ULONG));
389 buf = OPENSSL_malloc(num + 3);
390 if ((buf == NULL) || (bn_data == NULL)) {
391 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
392 goto err;
393 }
394 t = BN_dup(a);
395 if (t == NULL) {
396 goto err;
397 }
398
399 #define BUF_REMAIN (num + 3 - (size_t)(p - buf))
400 p = buf;
401 lp = bn_data;
402 if (BN_is_zero(t)) {
403 *(p++) = '0';
404 *(p++) = '\0';
405 } else {
406 if (BN_is_negative(t)) {
407 *p++ = '-';
408 }
409
410 while (!BN_is_zero(t)) {
411 *lp = BN_div_word(t, BN_DEC_CONV);
412 lp++;
413 }
414 lp--;
415 /* We now have a series of blocks, BN_DEC_NUM chars
416 * in length, where the last one needs truncation.
417 * The blocks need to be reversed in order. */
418 BIO_snprintf(p, BUF_REMAIN, BN_DEC_FMT1, *lp);
419 while (*p) {
420 p++;
421 }
422 while (lp != bn_data) {
423 lp--;
424 BIO_snprintf(p, BUF_REMAIN, BN_DEC_FMT2, *lp);
425 while (*p) {
426 p++;
427 }
428 }
429 }
430 ok = 1;
431
432 err:
433 OPENSSL_free(bn_data);
434 BN_free(t);
435 if (!ok) {
436 OPENSSL_free(buf);
437 buf = NULL;
438 }
439
440 return buf;
441 }
442
443 int BN_dec2bn(BIGNUM **outp, const char *in) {
444 return bn_x2bn(outp, in, decode_dec, isdigit);
445 }
446
447 int BN_asc2bn(BIGNUM **outp, const char *in) {
448 const char *const orig_in = in;
449 if (*in == '-') {
450 in++;
451 }
452
453 if (in[0] == '0' && (in[1] == 'X' || in[1] == 'x')) {
454 if (!BN_hex2bn(outp, in+2)) {
455 return 0;
456 }
457 } else {
458 if (!BN_dec2bn(outp, in)) {
459 return 0;
460 }
461 }
462
463 if (*orig_in == '-' && !BN_is_zero(*outp)) {
464 (*outp)->neg = 1;
465 }
466
467 return 1;
468 }
469
470 int BN_print(BIO *bp, const BIGNUM *a) {
471 int i, j, v, z = 0;
472 int ret = 0;
473
474 if (a->neg && BIO_write(bp, "-", 1) != 1) {
475 goto end;
476 }
477
478 if (BN_is_zero(a) && BIO_write(bp, "0", 1) != 1) {
479 goto end;
480 }
481
482 for (i = a->top - 1; i >= 0; i--) {
483 for (j = BN_BITS2 - 4; j >= 0; j -= 4) {
484 /* strip leading zeros */
485 v = ((int)(a->d[i] >> (long)j)) & 0x0f;
486 if (z || v != 0) {
487 if (BIO_write(bp, &hextable[v], 1) != 1) {
488 goto end;
489 }
490 z = 1;
491 }
492 }
493 }
494 ret = 1;
495
496 end:
497 return ret;
498 }
499
500 int BN_print_fp(FILE *fp, const BIGNUM *a) {
501 BIO *b;
502 int ret;
503
504 b = BIO_new(BIO_s_file());
505 if (b == NULL) {
506 return 0;
507 }
508 BIO_set_fp(b, fp, BIO_NOCLOSE);
509 ret = BN_print(b, a);
510 BIO_free(b);
511
512 return ret;
513 }
514
515 BN_ULONG BN_get_word(const BIGNUM *bn) {
516 switch (bn->top) {
517 case 0:
518 return 0;
519 case 1:
520 return bn->d[0];
521 default:
522 return BN_MASK2;
523 }
524 }
525
526 size_t BN_bn2mpi(const BIGNUM *in, uint8_t *out) {
527 const size_t bits = BN_num_bits(in);
528 const size_t bytes = (bits + 7) / 8;
529 /* If the number of bits is a multiple of 8, i.e. if the MSB is set,
530 * prefix with a zero byte. */
531 int extend = 0;
532 if (bytes != 0 && (bits & 0x07) == 0) {
533 extend = 1;
534 }
535
536 const size_t len = bytes + extend;
537 if (len < bytes ||
538 4 + len < len ||
539 (len & 0xffffffff) != len) {
540 /* If we cannot represent the number then we emit zero as the interface
541 * doesn't allow an error to be signalled. */
542 if (out) {
543 memset(out, 0, 4);
544 }
545 return 4;
546 }
547
548 if (out == NULL) {
549 return 4 + len;
550 }
551
552 out[0] = len >> 24;
553 out[1] = len >> 16;
554 out[2] = len >> 8;
555 out[3] = len;
556 if (extend) {
557 out[4] = 0;
558 }
559 BN_bn2bin(in, out + 4 + extend);
560 if (in->neg && len > 0) {
561 out[4] |= 0x80;
562 }
563 return len + 4;
564 }
565
566 BIGNUM *BN_mpi2bn(const uint8_t *in, size_t len, BIGNUM *out) {
567 if (len < 4) {
568 OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING);
569 return NULL;
570 }
571 const size_t in_len = ((size_t)in[0] << 24) |
572 ((size_t)in[1] << 16) |
573 ((size_t)in[2] << 8) |
574 ((size_t)in[3]);
575 if (in_len != len - 4) {
576 OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING);
577 return NULL;
578 }
579
580 int out_is_alloced = 0;
581 if (out == NULL) {
582 out = BN_new();
583 if (out == NULL) {
584 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
585 return NULL;
586 }
587 out_is_alloced = 1;
588 }
589
590 if (in_len == 0) {
591 BN_zero(out);
592 return out;
593 }
594
595 in += 4;
596 if (BN_bin2bn(in, in_len, out) == NULL) {
597 if (out_is_alloced) {
598 BN_free(out);
599 }
600 return NULL;
601 }
602 out->neg = ((*in) & 0x80) != 0;
603 if (out->neg) {
604 BN_clear_bit(out, BN_num_bits(out) - 1);
605 }
606 return out;
607 }