1/*
2 * Copyright 1995-2017 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the OpenSSL license (the "License").  You may not use
5 * this file except in compliance with the License.  You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10#include <stdio.h>
11#include "crypto/ctype.h"
12#include <limits.h>
13#include "internal/cryptlib.h"
14#include <openssl/buffer.h>
15#include "bn_local.h"
16
17static const char Hex[] = "0123456789ABCDEF";
18
19/* Must 'OPENSSL_free' the returned data */
20char *BN_bn2hex(const BIGNUM *a)
21{
22    int i, j, v, z = 0;
23    char *buf;
24    char *p;
25
26    if (BN_is_zero(a))
27        return OPENSSL_strdup("0");
28    buf = OPENSSL_malloc(a->top * BN_BYTES * 2 + 2);
29    if (buf == NULL) {
30        BNerr(BN_F_BN_BN2HEX, ERR_R_MALLOC_FAILURE);
31        goto err;
32    }
33    p = buf;
34    if (a->neg)
35        *p++ = '-';
36    for (i = a->top - 1; i >= 0; i--) {
37        for (j = BN_BITS2 - 8; j >= 0; j -= 8) {
38            /* strip leading zeros */
39            v = (int)((a->d[i] >> j) & 0xff);
40            if (z || v != 0) {
41                *p++ = Hex[v >> 4];
42                *p++ = Hex[v & 0x0f];
43                z = 1;
44            }
45        }
46    }
47    *p = '\0';
48 err:
49    return buf;
50}
51
52/* Must 'OPENSSL_free' the returned data */
53char *BN_bn2dec(const BIGNUM *a)
54{
55    int i = 0, num, ok = 0, n, tbytes;
56    char *buf = NULL;
57    char *p;
58    BIGNUM *t = NULL;
59    BN_ULONG *bn_data = NULL, *lp;
60    int bn_data_num;
61
62    /*-
63     * get an upper bound for the length of the decimal integer
64     * num <= (BN_num_bits(a) + 1) * log(2)
65     *     <= 3 * BN_num_bits(a) * 0.101 + log(2) + 1     (rounding error)
66     *     <= 3 * BN_num_bits(a) / 10 + 3 * BN_num_bits / 1000 + 1 + 1
67     */
68    i = BN_num_bits(a) * 3;
69    num = (i / 10 + i / 1000 + 1) + 1;
70    tbytes = num + 3;   /* negative and terminator and one spare? */
71    bn_data_num = num / BN_DEC_NUM + 1;
72    bn_data = OPENSSL_malloc(bn_data_num * sizeof(BN_ULONG));
73    buf = OPENSSL_malloc(tbytes);
74    if (buf == NULL || bn_data == NULL) {
75        BNerr(BN_F_BN_BN2DEC, ERR_R_MALLOC_FAILURE);
76        goto err;
77    }
78    if ((t = BN_dup(a)) == NULL)
79        goto err;
80
81    p = buf;
82    lp = bn_data;
83    if (BN_is_zero(t)) {
84        *p++ = '0';
85        *p++ = '\0';
86    } else {
87        if (BN_is_negative(t))
88            *p++ = '-';
89
90        while (!BN_is_zero(t)) {
91            if (lp - bn_data >= bn_data_num)
92                goto err;
93            *lp = BN_div_word(t, BN_DEC_CONV);
94            if (*lp == (BN_ULONG)-1)
95                goto err;
96            lp++;
97        }
98        lp--;
99        /*
100         * We now have a series of blocks, BN_DEC_NUM chars in length, where
101         * the last one needs truncation. The blocks need to be reversed in
102         * order.
103         */
104        n = BIO_snprintf(p, tbytes - (size_t)(p - buf), BN_DEC_FMT1, *lp);
105        if (n < 0)
106            goto err;
107        p += n;
108        while (lp != bn_data) {
109            lp--;
110            n = BIO_snprintf(p, tbytes - (size_t)(p - buf), BN_DEC_FMT2, *lp);
111            if (n < 0)
112                goto err;
113            p += n;
114        }
115    }
116    ok = 1;
117 err:
118    OPENSSL_free(bn_data);
119    BN_free(t);
120    if (ok)
121        return buf;
122    OPENSSL_free(buf);
123    return NULL;
124}
125
126int BN_hex2bn(BIGNUM **bn, const char *a)
127{
128    BIGNUM *ret = NULL;
129    BN_ULONG l = 0;
130    int neg = 0, h, m, i, j, k, c;
131    int num;
132
133    if (a == NULL || *a == '\0')
134        return 0;
135
136    if (*a == '-') {
137        neg = 1;
138        a++;
139    }
140
141    for (i = 0; i <= INT_MAX / 4 && ossl_isxdigit(a[i]); i++)
142        continue;
143
144    if (i == 0 || i > INT_MAX / 4)
145        goto err;
146
147    num = i + neg;
148    if (bn == NULL)
149        return num;
150
151    /* a is the start of the hex digits, and it is 'i' long */
152    if (*bn == NULL) {
153        if ((ret = BN_new()) == NULL)
154            return 0;
155    } else {
156        ret = *bn;
157        BN_zero(ret);
158    }
159
160    /* i is the number of hex digits */
161    if (bn_expand(ret, i * 4) == NULL)
162        goto err;
163
164    j = i;                      /* least significant 'hex' */
165    m = 0;
166    h = 0;
167    while (j > 0) {
168        m = (BN_BYTES * 2 <= j) ? BN_BYTES * 2 : j;
169        l = 0;
170        for (;;) {
171            c = a[j - m];
172            k = OPENSSL_hexchar2int(c);
173            if (k < 0)
174                k = 0;          /* paranoia */
175            l = (l << 4) | k;
176
177            if (--m <= 0) {
178                ret->d[h++] = l;
179                break;
180            }
181        }
182        j -= BN_BYTES * 2;
183    }
184    ret->top = h;
185    bn_correct_top(ret);
186
187    *bn = ret;
188    bn_check_top(ret);
189    /* Don't set the negative flag if it's zero. */
190    if (ret->top != 0)
191        ret->neg = neg;
192    return num;
193 err:
194    if (*bn == NULL)
195        BN_free(ret);
196    return 0;
197}
198
199int BN_dec2bn(BIGNUM **bn, const char *a)
200{
201    BIGNUM *ret = NULL;
202    BN_ULONG l = 0;
203    int neg = 0, i, j;
204    int num;
205
206    if (a == NULL || *a == '\0')
207        return 0;
208    if (*a == '-') {
209        neg = 1;
210        a++;
211    }
212
213    for (i = 0; i <= INT_MAX / 4 && ossl_isdigit(a[i]); i++)
214        continue;
215
216    if (i == 0 || i > INT_MAX / 4)
217        goto err;
218
219    num = i + neg;
220    if (bn == NULL)
221        return num;
222
223    /*
224     * a is the start of the digits, and it is 'i' long. We chop it into
225     * BN_DEC_NUM digits at a time
226     */
227    if (*bn == NULL) {
228        if ((ret = BN_new()) == NULL)
229            return 0;
230    } else {
231        ret = *bn;
232        BN_zero(ret);
233    }
234
235    /* i is the number of digits, a bit of an over expand */
236    if (bn_expand(ret, i * 4) == NULL)
237        goto err;
238
239    j = BN_DEC_NUM - i % BN_DEC_NUM;
240    if (j == BN_DEC_NUM)
241        j = 0;
242    l = 0;
243    while (--i >= 0) {
244        l *= 10;
245        l += *a - '0';
246        a++;
247        if (++j == BN_DEC_NUM) {
248            if (!BN_mul_word(ret, BN_DEC_CONV)
249                || !BN_add_word(ret, l))
250                goto err;
251            l = 0;
252            j = 0;
253        }
254    }
255
256    bn_correct_top(ret);
257    *bn = ret;
258    bn_check_top(ret);
259    /* Don't set the negative flag if it's zero. */
260    if (ret->top != 0)
261        ret->neg = neg;
262    return num;
263 err:
264    if (*bn == NULL)
265        BN_free(ret);
266    return 0;
267}
268
269int BN_asc2bn(BIGNUM **bn, const char *a)
270{
271    const char *p = a;
272
273    if (*p == '-')
274        p++;
275
276    if (p[0] == '0' && (p[1] == 'X' || p[1] == 'x')) {
277        if (!BN_hex2bn(bn, p + 2))
278            return 0;
279    } else {
280        if (!BN_dec2bn(bn, p))
281            return 0;
282    }
283    /* Don't set the negative flag if it's zero. */
284    if (*a == '-' && (*bn)->top != 0)
285        (*bn)->neg = 1;
286    return 1;
287}
288
289# ifndef OPENSSL_NO_STDIO
290int BN_print_fp(FILE *fp, const BIGNUM *a)
291{
292    BIO *b;
293    int ret;
294
295    if ((b = BIO_new(BIO_s_file())) == NULL)
296        return 0;
297    BIO_set_fp(b, fp, BIO_NOCLOSE);
298    ret = BN_print(b, a);
299    BIO_free(b);
300    return ret;
301}
302# endif
303
304int BN_print(BIO *bp, const BIGNUM *a)
305{
306    int i, j, v, z = 0;
307    int ret = 0;
308
309    if ((a->neg) && BIO_write(bp, "-", 1) != 1)
310        goto end;
311    if (BN_is_zero(a) && BIO_write(bp, "0", 1) != 1)
312        goto end;
313    for (i = a->top - 1; i >= 0; i--) {
314        for (j = BN_BITS2 - 4; j >= 0; j -= 4) {
315            /* strip leading zeros */
316            v = (int)((a->d[i] >> j) & 0x0f);
317            if (z || v != 0) {
318                if (BIO_write(bp, &Hex[v], 1) != 1)
319                    goto end;
320                z = 1;
321            }
322        }
323    }
324    ret = 1;
325 end:
326    return ret;
327}
328
329char *BN_options(void)
330{
331    static int init = 0;
332    static char data[16];
333
334    if (!init) {
335        init++;
336#ifdef BN_LLONG
337        BIO_snprintf(data, sizeof(data), "bn(%zu,%zu)",
338                     sizeof(BN_ULLONG) * 8, sizeof(BN_ULONG) * 8);
339#else
340        BIO_snprintf(data, sizeof(data), "bn(%zu,%zu)",
341                     sizeof(BN_ULONG) * 8, sizeof(BN_ULONG) * 8);
342#endif
343    }
344    return data;
345}
346