/src/boringssl/crypto/bn_extra/convert.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
2 | | * All rights reserved. |
3 | | * |
4 | | * This package is an SSL implementation written |
5 | | * by Eric Young (eay@cryptsoft.com). |
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 (tjh@cryptsoft.com). |
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 (eay@cryptsoft.com)" |
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 (tjh@cryptsoft.com)" |
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 | | |
64 | | #include <openssl/bio.h> |
65 | | #include <openssl/bytestring.h> |
66 | | #include <openssl/err.h> |
67 | | #include <openssl/mem.h> |
68 | | |
69 | | #include "../fipsmodule/bn/internal.h" |
70 | | |
71 | | |
72 | 244 | int BN_bn2cbb_padded(CBB *out, size_t len, const BIGNUM *in) { |
73 | 244 | uint8_t *ptr; |
74 | 244 | return CBB_add_space(out, &ptr, len) && BN_bn2bin_padded(ptr, len, in); |
75 | 244 | } |
76 | | |
77 | | static const char hextable[] = "0123456789abcdef"; |
78 | | |
79 | 1.21k | char *BN_bn2hex(const BIGNUM *bn) { |
80 | 1.21k | int width = bn_minimal_width(bn); |
81 | 1.21k | char *buf = OPENSSL_malloc(1 /* leading '-' */ + 1 /* zero is non-empty */ + |
82 | 1.21k | width * BN_BYTES * 2 + 1 /* trailing NUL */); |
83 | 1.21k | if (buf == NULL) { |
84 | 0 | return NULL; |
85 | 0 | } |
86 | | |
87 | 1.21k | char *p = buf; |
88 | 1.21k | if (bn->neg) { |
89 | 19 | *(p++) = '-'; |
90 | 19 | } |
91 | | |
92 | 1.21k | if (BN_is_zero(bn)) { |
93 | 291 | *(p++) = '0'; |
94 | 291 | } |
95 | | |
96 | 1.21k | int z = 0; |
97 | 30.8k | for (int i = width - 1; i >= 0; i--) { |
98 | 266k | for (int j = BN_BITS2 - 8; j >= 0; j -= 8) { |
99 | | // strip leading zeros |
100 | 237k | int v = ((int)(bn->d[i] >> (long)j)) & 0xff; |
101 | 237k | if (z || v != 0) { |
102 | 233k | *(p++) = hextable[v >> 4]; |
103 | 233k | *(p++) = hextable[v & 0x0f]; |
104 | 233k | z = 1; |
105 | 233k | } |
106 | 237k | } |
107 | 29.6k | } |
108 | 1.21k | *p = '\0'; |
109 | | |
110 | 1.21k | return buf; |
111 | 1.21k | } |
112 | | |
113 | | // decode_hex decodes |in_len| bytes of hex data from |in| and updates |bn|. |
114 | 0 | static int decode_hex(BIGNUM *bn, const char *in, int in_len) { |
115 | 0 | if (in_len > INT_MAX/4) { |
116 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); |
117 | 0 | return 0; |
118 | 0 | } |
119 | | // |in_len| is the number of hex digits. |
120 | 0 | if (!bn_expand(bn, in_len * 4)) { |
121 | 0 | return 0; |
122 | 0 | } |
123 | | |
124 | 0 | int i = 0; |
125 | 0 | while (in_len > 0) { |
126 | | // Decode one |BN_ULONG| at a time. |
127 | 0 | int todo = BN_BYTES * 2; |
128 | 0 | if (todo > in_len) { |
129 | 0 | todo = in_len; |
130 | 0 | } |
131 | |
|
132 | 0 | BN_ULONG word = 0; |
133 | 0 | int j; |
134 | 0 | for (j = todo; j > 0; j--) { |
135 | 0 | uint8_t hex = 0; |
136 | 0 | if (!OPENSSL_fromxdigit(&hex, in[in_len - j])) { |
137 | | // This shouldn't happen. The caller checks |OPENSSL_isxdigit|. |
138 | 0 | assert(0); |
139 | 0 | } |
140 | 0 | word = (word << 4) | hex; |
141 | 0 | } |
142 | | |
143 | 0 | bn->d[i++] = word; |
144 | 0 | in_len -= todo; |
145 | 0 | } |
146 | 0 | assert(i <= bn->dmax); |
147 | 0 | bn->width = i; |
148 | 0 | return 1; |
149 | 0 | } |
150 | | |
151 | | // decode_dec decodes |in_len| bytes of decimal data from |in| and updates |bn|. |
152 | 12.7k | static int decode_dec(BIGNUM *bn, const char *in, int in_len) { |
153 | 12.7k | int i, j; |
154 | 12.7k | BN_ULONG l = 0; |
155 | | |
156 | | // Decode |BN_DEC_NUM| digits at a time. |
157 | 12.7k | j = BN_DEC_NUM - (in_len % BN_DEC_NUM); |
158 | 12.7k | if (j == BN_DEC_NUM) { |
159 | 390 | j = 0; |
160 | 390 | } |
161 | 12.7k | l = 0; |
162 | 3.67M | for (i = 0; i < in_len; i++) { |
163 | 3.65M | l *= 10; |
164 | 3.65M | l += in[i] - '0'; |
165 | 3.65M | if (++j == BN_DEC_NUM) { |
166 | 201k | if (!BN_mul_word(bn, BN_DEC_CONV) || |
167 | 201k | !BN_add_word(bn, l)) { |
168 | 0 | return 0; |
169 | 0 | } |
170 | 201k | l = 0; |
171 | 201k | j = 0; |
172 | 201k | } |
173 | 3.65M | } |
174 | 12.7k | return 1; |
175 | 12.7k | } |
176 | | |
177 | | typedef int (*decode_func) (BIGNUM *bn, const char *in, int in_len); |
178 | | typedef int (*char_test_func) (int c); |
179 | | |
180 | 12.7k | static int bn_x2bn(BIGNUM **outp, const char *in, decode_func decode, char_test_func want_char) { |
181 | 12.7k | BIGNUM *ret = NULL; |
182 | 12.7k | int neg = 0, i; |
183 | 12.7k | int num; |
184 | | |
185 | 12.7k | if (in == NULL || *in == 0) { |
186 | 0 | return 0; |
187 | 0 | } |
188 | | |
189 | 12.7k | if (*in == '-') { |
190 | 17 | neg = 1; |
191 | 17 | in++; |
192 | 17 | } |
193 | | |
194 | 3.67M | for (i = 0; want_char((unsigned char)in[i]) && i + neg < INT_MAX; i++) {} |
195 | | |
196 | 12.7k | num = i + neg; |
197 | 12.7k | if (outp == NULL) { |
198 | 0 | return num; |
199 | 0 | } |
200 | | |
201 | | // in is the start of the hex digits, and it is 'i' long |
202 | 12.7k | if (*outp == NULL) { |
203 | 1.78k | ret = BN_new(); |
204 | 1.78k | if (ret == NULL) { |
205 | 0 | return 0; |
206 | 0 | } |
207 | 10.9k | } else { |
208 | 10.9k | ret = *outp; |
209 | 10.9k | BN_zero(ret); |
210 | 10.9k | } |
211 | | |
212 | 12.7k | if (!decode(ret, in, i)) { |
213 | 0 | goto err; |
214 | 0 | } |
215 | | |
216 | 12.7k | bn_set_minimal_width(ret); |
217 | 12.7k | if (!BN_is_zero(ret)) { |
218 | 9.08k | ret->neg = neg; |
219 | 9.08k | } |
220 | | |
221 | 12.7k | *outp = ret; |
222 | 12.7k | return num; |
223 | | |
224 | 0 | err: |
225 | 0 | if (*outp == NULL) { |
226 | 0 | BN_free(ret); |
227 | 0 | } |
228 | |
|
229 | 0 | return 0; |
230 | 12.7k | } |
231 | | |
232 | 0 | int BN_hex2bn(BIGNUM **outp, const char *in) { |
233 | 0 | return bn_x2bn(outp, in, decode_hex, OPENSSL_isxdigit); |
234 | 0 | } |
235 | | |
236 | 563 | char *BN_bn2dec(const BIGNUM *a) { |
237 | | // It is easier to print strings little-endian, so we assemble it in reverse |
238 | | // and fix at the end. |
239 | 563 | BIGNUM *copy = NULL; |
240 | 563 | CBB cbb; |
241 | 563 | if (!CBB_init(&cbb, 16) || |
242 | 563 | !CBB_add_u8(&cbb, 0 /* trailing NUL */)) { |
243 | 0 | goto err; |
244 | 0 | } |
245 | | |
246 | 563 | if (BN_is_zero(a)) { |
247 | 125 | if (!CBB_add_u8(&cbb, '0')) { |
248 | 0 | goto err; |
249 | 0 | } |
250 | 438 | } else { |
251 | 438 | copy = BN_dup(a); |
252 | 438 | if (copy == NULL) { |
253 | 0 | goto err; |
254 | 0 | } |
255 | | |
256 | 10.3k | while (!BN_is_zero(copy)) { |
257 | 9.91k | BN_ULONG word = BN_div_word(copy, BN_DEC_CONV); |
258 | 9.91k | if (word == (BN_ULONG)-1) { |
259 | 0 | goto err; |
260 | 0 | } |
261 | | |
262 | 9.91k | const int add_leading_zeros = !BN_is_zero(copy); |
263 | 192k | for (int i = 0; i < BN_DEC_NUM && (add_leading_zeros || word != 0); i++) { |
264 | 182k | if (!CBB_add_u8(&cbb, '0' + word % 10)) { |
265 | 0 | goto err; |
266 | 0 | } |
267 | 182k | word /= 10; |
268 | 182k | } |
269 | 9.91k | assert(word == 0); |
270 | 9.91k | } |
271 | 438 | } |
272 | | |
273 | 563 | if (BN_is_negative(a) && |
274 | 563 | !CBB_add_u8(&cbb, '-')) { |
275 | 0 | goto err; |
276 | 0 | } |
277 | | |
278 | 563 | uint8_t *data; |
279 | 563 | size_t len; |
280 | 563 | if (!CBB_finish(&cbb, &data, &len)) { |
281 | 0 | goto err; |
282 | 0 | } |
283 | | |
284 | | // Reverse the buffer. |
285 | 92.2k | for (size_t i = 0; i < len/2; i++) { |
286 | 91.7k | uint8_t tmp = data[i]; |
287 | 91.7k | data[i] = data[len - 1 - i]; |
288 | 91.7k | data[len - 1 - i] = tmp; |
289 | 91.7k | } |
290 | | |
291 | 563 | BN_free(copy); |
292 | 563 | return (char *)data; |
293 | | |
294 | 0 | err: |
295 | 0 | BN_free(copy); |
296 | 0 | CBB_cleanup(&cbb); |
297 | 0 | return NULL; |
298 | 563 | } |
299 | | |
300 | 12.7k | int BN_dec2bn(BIGNUM **outp, const char *in) { |
301 | 12.7k | return bn_x2bn(outp, in, decode_dec, OPENSSL_isdigit); |
302 | 12.7k | } |
303 | | |
304 | 0 | int BN_asc2bn(BIGNUM **outp, const char *in) { |
305 | 0 | const char *const orig_in = in; |
306 | 0 | if (*in == '-') { |
307 | 0 | in++; |
308 | 0 | } |
309 | |
|
310 | 0 | if (in[0] == '0' && (in[1] == 'X' || in[1] == 'x')) { |
311 | 0 | if (!BN_hex2bn(outp, in+2)) { |
312 | 0 | return 0; |
313 | 0 | } |
314 | 0 | } else { |
315 | 0 | if (!BN_dec2bn(outp, in)) { |
316 | 0 | return 0; |
317 | 0 | } |
318 | 0 | } |
319 | | |
320 | 0 | if (*orig_in == '-' && !BN_is_zero(*outp)) { |
321 | 0 | (*outp)->neg = 1; |
322 | 0 | } |
323 | |
|
324 | 0 | return 1; |
325 | 0 | } |
326 | | |
327 | 0 | int BN_print(BIO *bp, const BIGNUM *a) { |
328 | 0 | int i, j, v, z = 0; |
329 | 0 | int ret = 0; |
330 | |
|
331 | 0 | if (a->neg && BIO_write(bp, "-", 1) != 1) { |
332 | 0 | goto end; |
333 | 0 | } |
334 | | |
335 | 0 | if (BN_is_zero(a) && BIO_write(bp, "0", 1) != 1) { |
336 | 0 | goto end; |
337 | 0 | } |
338 | | |
339 | 0 | for (i = bn_minimal_width(a) - 1; i >= 0; i--) { |
340 | 0 | for (j = BN_BITS2 - 4; j >= 0; j -= 4) { |
341 | | // strip leading zeros |
342 | 0 | v = ((int)(a->d[i] >> (long)j)) & 0x0f; |
343 | 0 | if (z || v != 0) { |
344 | 0 | if (BIO_write(bp, &hextable[v], 1) != 1) { |
345 | 0 | goto end; |
346 | 0 | } |
347 | 0 | z = 1; |
348 | 0 | } |
349 | 0 | } |
350 | 0 | } |
351 | 0 | ret = 1; |
352 | |
|
353 | 0 | end: |
354 | 0 | return ret; |
355 | 0 | } |
356 | | |
357 | 0 | int BN_print_fp(FILE *fp, const BIGNUM *a) { |
358 | 0 | BIO *b = BIO_new_fp(fp, BIO_NOCLOSE); |
359 | 0 | if (b == NULL) { |
360 | 0 | return 0; |
361 | 0 | } |
362 | | |
363 | 0 | int ret = BN_print(b, a); |
364 | 0 | BIO_free(b); |
365 | 0 | return ret; |
366 | 0 | } |
367 | | |
368 | | |
369 | 5.03k | size_t BN_bn2mpi(const BIGNUM *in, uint8_t *out) { |
370 | 5.03k | const size_t bits = BN_num_bits(in); |
371 | 5.03k | const size_t bytes = (bits + 7) / 8; |
372 | | // If the number of bits is a multiple of 8, i.e. if the MSB is set, |
373 | | // prefix with a zero byte. |
374 | 5.03k | int extend = 0; |
375 | 5.03k | if (bytes != 0 && (bits & 0x07) == 0) { |
376 | 1.15k | extend = 1; |
377 | 1.15k | } |
378 | | |
379 | 5.03k | const size_t len = bytes + extend; |
380 | 5.03k | if (len < bytes || |
381 | 5.03k | 4 + len < len || |
382 | 5.03k | (len & 0xffffffff) != len) { |
383 | | // If we cannot represent the number then we emit zero as the interface |
384 | | // doesn't allow an error to be signalled. |
385 | 0 | if (out) { |
386 | 0 | OPENSSL_memset(out, 0, 4); |
387 | 0 | } |
388 | 0 | return 4; |
389 | 0 | } |
390 | | |
391 | 5.03k | if (out == NULL) { |
392 | 2.51k | return 4 + len; |
393 | 2.51k | } |
394 | | |
395 | 2.51k | out[0] = len >> 24; |
396 | 2.51k | out[1] = len >> 16; |
397 | 2.51k | out[2] = len >> 8; |
398 | 2.51k | out[3] = len; |
399 | 2.51k | if (extend) { |
400 | 576 | out[4] = 0; |
401 | 576 | } |
402 | 2.51k | BN_bn2bin(in, out + 4 + extend); |
403 | 2.51k | if (in->neg && len > 0) { |
404 | 13 | out[4] |= 0x80; |
405 | 13 | } |
406 | 2.51k | return len + 4; |
407 | 5.03k | } |
408 | | |
409 | 2.51k | BIGNUM *BN_mpi2bn(const uint8_t *in, size_t len, BIGNUM *out) { |
410 | 2.51k | if (len < 4) { |
411 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING); |
412 | 0 | return NULL; |
413 | 0 | } |
414 | 2.51k | const size_t in_len = ((size_t)in[0] << 24) | |
415 | 2.51k | ((size_t)in[1] << 16) | |
416 | 2.51k | ((size_t)in[2] << 8) | |
417 | 2.51k | ((size_t)in[3]); |
418 | 2.51k | if (in_len != len - 4) { |
419 | 0 | OPENSSL_PUT_ERROR(BN, BN_R_BAD_ENCODING); |
420 | 0 | return NULL; |
421 | 0 | } |
422 | | |
423 | 2.51k | int out_is_alloced = 0; |
424 | 2.51k | if (out == NULL) { |
425 | 0 | out = BN_new(); |
426 | 0 | if (out == NULL) { |
427 | 0 | return NULL; |
428 | 0 | } |
429 | 0 | out_is_alloced = 1; |
430 | 0 | } |
431 | | |
432 | 2.51k | if (in_len == 0) { |
433 | 662 | BN_zero(out); |
434 | 662 | return out; |
435 | 662 | } |
436 | | |
437 | 1.85k | in += 4; |
438 | 1.85k | if (BN_bin2bn(in, in_len, out) == NULL) { |
439 | 0 | if (out_is_alloced) { |
440 | 0 | BN_free(out); |
441 | 0 | } |
442 | 0 | return NULL; |
443 | 0 | } |
444 | 1.85k | out->neg = ((*in) & 0x80) != 0; |
445 | 1.85k | if (out->neg) { |
446 | 13 | BN_clear_bit(out, BN_num_bits(out) - 1); |
447 | 13 | } |
448 | 1.85k | return out; |
449 | 1.85k | } |
450 | | |
451 | 6 | int BN_bn2binpad(const BIGNUM *in, uint8_t *out, int len) { |
452 | 6 | if (len < 0 || |
453 | 6 | !BN_bn2bin_padded(out, (size_t)len, in)) { |
454 | 3 | return -1; |
455 | 3 | } |
456 | 3 | return len; |
457 | 6 | } |
458 | | |
459 | 0 | int BN_bn2lebinpad(const BIGNUM *in, uint8_t *out, int len) { |
460 | 0 | if (len < 0 || |
461 | 0 | !BN_bn2le_padded(out, (size_t)len, in)) { |
462 | 0 | return -1; |
463 | 0 | } |
464 | 0 | return len; |
465 | 0 | } |