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#include "../delocate.h"
67
68
69BIGNUM *BN_new(void) {
70  BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM));
71
72  if (bn == NULL) {
73    OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
74    return NULL;
75  }
76
77  OPENSSL_memset(bn, 0, sizeof(BIGNUM));
78  bn->flags = BN_FLG_MALLOCED;
79
80  return bn;
81}
82
83void BN_init(BIGNUM *bn) {
84  OPENSSL_memset(bn, 0, sizeof(BIGNUM));
85}
86
87void BN_free(BIGNUM *bn) {
88  if (bn == NULL) {
89    return;
90  }
91
92  if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
93    OPENSSL_free(bn->d);
94  }
95
96  if (bn->flags & BN_FLG_MALLOCED) {
97    OPENSSL_free(bn);
98  } else {
99    bn->d = NULL;
100  }
101}
102
103void BN_clear_free(BIGNUM *bn) {
104  char should_free;
105
106  if (bn == NULL) {
107    return;
108  }
109
110  if (bn->d != NULL) {
111    OPENSSL_cleanse(bn->d, bn->dmax * sizeof(bn->d[0]));
112    if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
113      OPENSSL_free(bn->d);
114    }
115  }
116
117  should_free = (bn->flags & BN_FLG_MALLOCED) != 0;
118  OPENSSL_cleanse(bn, sizeof(BIGNUM));
119  if (should_free) {
120    OPENSSL_free(bn);
121  }
122}
123
124BIGNUM *BN_dup(const BIGNUM *src) {
125  BIGNUM *copy;
126
127  if (src == NULL) {
128    return NULL;
129  }
130
131  copy = BN_new();
132  if (copy == NULL) {
133    return NULL;
134  }
135
136  if (!BN_copy(copy, src)) {
137    BN_free(copy);
138    return NULL;
139  }
140
141  return copy;
142}
143
144BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) {
145  if (src == dest) {
146    return dest;
147  }
148
149  if (!bn_wexpand(dest, src->top)) {
150    return NULL;
151  }
152
153  OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->top);
154
155  dest->top = src->top;
156  dest->neg = src->neg;
157  return dest;
158}
159
160void BN_clear(BIGNUM *bn) {
161  if (bn->d != NULL) {
162    OPENSSL_memset(bn->d, 0, bn->dmax * sizeof(bn->d[0]));
163  }
164
165  bn->top = 0;
166  bn->neg = 0;
167}
168
169DEFINE_METHOD_FUNCTION(BIGNUM, BN_value_one) {
170  static const BN_ULONG kOneLimbs[1] = { 1 };
171  out->d = (BN_ULONG*) kOneLimbs;
172  out->top = 1;
173  out->dmax = 1;
174  out->neg = 0;
175  out->flags = BN_FLG_STATIC_DATA;
176}
177
178/* BN_num_bits_word returns the minimum number of bits needed to represent the
179 * value in |l|. */
180unsigned BN_num_bits_word(BN_ULONG l) {
181  static const unsigned char bits[256] = {
182      0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5,
183      5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
184      6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7,
185      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
186      7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
187      7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
188      8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
189      8, 8, 8, 8, 8, 8, 8, 8, 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};
193
194#if defined(OPENSSL_64_BIT)
195  if (l & 0xffffffff00000000L) {
196    if (l & 0xffff000000000000L) {
197      if (l & 0xff00000000000000L) {
198        return (bits[(int)(l >> 56)] + 56);
199      } else {
200        return (bits[(int)(l >> 48)] + 48);
201      }
202    } else {
203      if (l & 0x0000ff0000000000L) {
204        return (bits[(int)(l >> 40)] + 40);
205      } else {
206        return (bits[(int)(l >> 32)] + 32);
207      }
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)) {
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_set_u64(BIGNUM *bn, uint64_t value) {
267#if BN_BITS2 == 64
268  return BN_set_word(bn, value);
269#elif BN_BITS2 == 32
270  if (value <= BN_MASK2) {
271    return BN_set_word(bn, (BN_ULONG)value);
272  }
273
274  if (!bn_wexpand(bn, 2)) {
275    return 0;
276  }
277
278  bn->neg = 0;
279  bn->d[0] = (BN_ULONG)value;
280  bn->d[1] = (BN_ULONG)(value >> 32);
281  bn->top = 2;
282  return 1;
283#else
284#error "BN_BITS2 must be 32 or 64."
285#endif
286}
287
288int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
289  if (!bn_wexpand(bn, num)) {
290    return 0;
291  }
292  OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG));
293  /* |bn_wexpand| verified that |num| isn't too large. */
294  bn->top = (int)num;
295  bn_correct_top(bn);
296  bn->neg = 0;
297  return 1;
298}
299
300int BN_is_negative(const BIGNUM *bn) {
301  return bn->neg != 0;
302}
303
304void BN_set_negative(BIGNUM *bn, int sign) {
305  if (sign && !BN_is_zero(bn)) {
306    bn->neg = 1;
307  } else {
308    bn->neg = 0;
309  }
310}
311
312int bn_wexpand(BIGNUM *bn, size_t words) {
313  BN_ULONG *a;
314
315  if (words <= (size_t)bn->dmax) {
316    return 1;
317  }
318
319  if (words > (INT_MAX / (4 * BN_BITS2))) {
320    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
321    return 0;
322  }
323
324  if (bn->flags & BN_FLG_STATIC_DATA) {
325    OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
326    return 0;
327  }
328
329  a = OPENSSL_malloc(sizeof(BN_ULONG) * words);
330  if (a == NULL) {
331    OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
332    return 0;
333  }
334
335  OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top);
336
337  OPENSSL_free(bn->d);
338  bn->d = a;
339  bn->dmax = (int)words;
340
341  return 1;
342}
343
344int bn_expand(BIGNUM *bn, size_t bits) {
345  if (bits + BN_BITS2 - 1 < bits) {
346    OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
347    return 0;
348  }
349  return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
350}
351
352void bn_correct_top(BIGNUM *bn) {
353  BN_ULONG *ftl;
354  int tmp_top = bn->top;
355
356  if (tmp_top > 0) {
357    for (ftl = &(bn->d[tmp_top - 1]); tmp_top > 0; tmp_top--) {
358      if (*(ftl--)) {
359        break;
360      }
361    }
362    bn->top = tmp_top;
363  }
364
365  if (bn->top == 0) {
366    bn->neg = 0;
367  }
368}
369