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 <limits.h>
60#include <string.h>
61
62#include <openssl/err.h>
63#include <openssl/mem.h>
64
65#include "internal.h"
66
67
68BIGNUM *BN_new(void) {
69  BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM));
70
71  if (bn == NULL) {
72    OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
73    return NULL;
74  }
75
76  memset(bn, 0, sizeof(BIGNUM));
77  bn->flags = BN_FLG_MALLOCED;
78
79  return bn;
80}
81
82void BN_init(BIGNUM *bn) {
83  memset(bn, 0, sizeof(BIGNUM));
84}
85
86void BN_free(BIGNUM *bn) {
87  if (bn == NULL) {
88    return;
89  }
90
91  if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
92    OPENSSL_free(bn->d);
93  }
94
95  if (bn->flags & BN_FLG_MALLOCED) {
96    OPENSSL_free(bn);
97  } else {
98    bn->d = NULL;
99  }
100}
101
102void BN_clear_free(BIGNUM *bn) {
103  char should_free;
104
105  if (bn == NULL) {
106    return;
107  }
108
109  if (bn->d != NULL) {
110    OPENSSL_cleanse(bn->d, bn->dmax * sizeof(bn->d[0]));
111    if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
112      OPENSSL_free(bn->d);
113    }
114  }
115
116  should_free = (bn->flags & BN_FLG_MALLOCED) != 0;
117  OPENSSL_cleanse(bn, sizeof(BIGNUM));
118  if (should_free) {
119    OPENSSL_free(bn);
120  }
121}
122
123BIGNUM *BN_dup(const BIGNUM *src) {
124  BIGNUM *copy;
125
126  if (src == NULL) {
127    return NULL;
128  }
129
130  copy = BN_new();
131  if (copy == NULL) {
132    return NULL;
133  }
134
135  if (!BN_copy(copy, src)) {
136    BN_free(copy);
137    return NULL;
138  }
139
140  return copy;
141}
142
143BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) {
144  if (src == dest) {
145    return dest;
146  }
147
148  if (bn_wexpand(dest, src->top) == NULL) {
149    return NULL;
150  }
151
152  memcpy(dest->d, src->d, sizeof(src->d[0]) * src->top);
153
154  dest->top = src->top;
155  dest->neg = src->neg;
156  return dest;
157}
158
159void BN_clear(BIGNUM *bn) {
160  if (bn->d != NULL) {
161    memset(bn->d, 0, bn->dmax * sizeof(bn->d[0]));
162  }
163
164  bn->top = 0;
165  bn->neg = 0;
166}
167
168const BIGNUM *BN_value_one(void) {
169  static const BN_ULONG kOneLimbs[1] = { 1 };
170  static const BIGNUM kOne = STATIC_BIGNUM(kOneLimbs);
171
172  return &kOne;
173}
174
175void BN_with_flags(BIGNUM *out, const BIGNUM *in, int flags) {
176  memcpy(out, in, sizeof(BIGNUM));
177  out->flags &= ~BN_FLG_MALLOCED;
178  out->flags |= BN_FLG_STATIC_DATA | flags;
179}
180
181/* BN_num_bits_word returns the minimum number of bits needed to represent the
182 * value in |l|. */
183unsigned BN_num_bits_word(BN_ULONG l) {
184  static const unsigned char bits[256] = {
185      0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
186      5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
187      6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7,
188      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
189      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
190      7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
191      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
192      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
193      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
194      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
195      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};
196
197#if defined(OPENSSL_64_BIT)
198  if (l & 0xffffffff00000000L) {
199    if (l & 0xffff000000000000L) {
200      if (l & 0xff00000000000000L) {
201        return (bits[(int)(l >> 56)] + 56);
202      } else {
203        return (bits[(int)(l >> 48)] + 48);
204      }
205    } else {
206      if (l & 0x0000ff0000000000L) {
207        return (bits[(int)(l >> 40)] + 40);
208      } else {
209        return (bits[(int)(l >> 32)] + 32);
210      }
211    }
212  } else
213#endif
214  {
215    if (l & 0xffff0000L) {
216      if (l & 0xff000000L) {
217        return (bits[(int)(l >> 24L)] + 24);
218      } else {
219        return (bits[(int)(l >> 16L)] + 16);
220      }
221    } else {
222      if (l & 0xff00L) {
223        return (bits[(int)(l >> 8)] + 8);
224      } else {
225        return (bits[(int)(l)]);
226      }
227    }
228  }
229}
230
231unsigned BN_num_bits(const BIGNUM *bn) {
232  const int max = bn->top - 1;
233
234  if (BN_is_zero(bn)) {
235    return 0;
236  }
237
238  return max*BN_BITS2 + BN_num_bits_word(bn->d[max]);
239}
240
241unsigned BN_num_bytes(const BIGNUM *bn) {
242  return (BN_num_bits(bn) + 7) / 8;
243}
244
245void BN_zero(BIGNUM *bn) {
246  bn->top = bn->neg = 0;
247}
248
249int BN_one(BIGNUM *bn) {
250  return BN_set_word(bn, 1);
251}
252
253int BN_set_word(BIGNUM *bn, BN_ULONG value) {
254  if (value == 0) {
255    BN_zero(bn);
256    return 1;
257  }
258
259  if (bn_wexpand(bn, 1) == NULL) {
260    return 0;
261  }
262
263  bn->neg = 0;
264  bn->d[0] = value;
265  bn->top = 1;
266  return 1;
267}
268
269int BN_is_negative(const BIGNUM *bn) {
270  return bn->neg != 0;
271}
272
273void BN_set_negative(BIGNUM *bn, int sign) {
274  if (sign && !BN_is_zero(bn)) {
275    bn->neg = 1;
276  } else {
277    bn->neg = 0;
278  }
279}
280
281BIGNUM *bn_wexpand(BIGNUM *bn, size_t words) {
282  BN_ULONG *a;
283
284  if (words <= (size_t)bn->dmax) {
285    return bn;
286  }
287
288  if (words > (INT_MAX / (4 * BN_BITS2))) {
289    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
290    return NULL;
291  }
292
293  if (bn->flags & BN_FLG_STATIC_DATA) {
294    OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
295    return NULL;
296  }
297
298  a = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words);
299  if (a == NULL) {
300    OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
301    return NULL;
302  }
303
304  memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top);
305
306  OPENSSL_free(bn->d);
307  bn->d = a;
308  bn->dmax = (int)words;
309
310  return bn;
311}
312
313BIGNUM *bn_expand(BIGNUM *bn, size_t bits) {
314  if (bits + BN_BITS2 - 1 < bits) {
315    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
316    return NULL;
317  }
318  return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
319}
320
321void bn_correct_top(BIGNUM *bn) {
322  BN_ULONG *ftl;
323  int tmp_top = bn->top;
324
325  if (tmp_top > 0) {
326    for (ftl = &(bn->d[tmp_top - 1]); tmp_top > 0; tmp_top--) {
327      if (*(ftl--)) {
328        break;
329      }
330    }
331    bn->top = tmp_top;
332  }
333}
334
335int BN_get_flags(const BIGNUM *bn, int flags) {
336  return bn->flags & flags;
337}
338
339void BN_set_flags(BIGNUM *bn, int flags) {
340  bn->flags |= flags;
341}
342