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