• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
BN_new(void)69 BIGNUM *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 
BN_init(BIGNUM * bn)83 void BN_init(BIGNUM *bn) {
84   OPENSSL_memset(bn, 0, sizeof(BIGNUM));
85 }
86 
BN_free(BIGNUM * bn)87 void 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 
BN_clear_free(BIGNUM * bn)103 void BN_clear_free(BIGNUM *bn) {
104   char should_free;
105 
106   if (bn == NULL) {
107     return;
108   }
109 
110   if (bn->d != NULL) {
111     if ((bn->flags & BN_FLG_STATIC_DATA) == 0) {
112       OPENSSL_free(bn->d);
113     } else {
114       OPENSSL_cleanse(bn->d, bn->dmax * sizeof(bn->d[0]));
115     }
116   }
117 
118   should_free = (bn->flags & BN_FLG_MALLOCED) != 0;
119   if (should_free) {
120     OPENSSL_free(bn);
121   } else {
122     OPENSSL_cleanse(bn, sizeof(BIGNUM));
123   }
124 }
125 
BN_dup(const BIGNUM * src)126 BIGNUM *BN_dup(const BIGNUM *src) {
127   BIGNUM *copy;
128 
129   if (src == NULL) {
130     return NULL;
131   }
132 
133   copy = BN_new();
134   if (copy == NULL) {
135     return NULL;
136   }
137 
138   if (!BN_copy(copy, src)) {
139     BN_free(copy);
140     return NULL;
141   }
142 
143   return copy;
144 }
145 
BN_copy(BIGNUM * dest,const BIGNUM * src)146 BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) {
147   if (src == dest) {
148     return dest;
149   }
150 
151   if (!bn_wexpand(dest, src->top)) {
152     return NULL;
153   }
154 
155   OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->top);
156 
157   dest->top = src->top;
158   dest->neg = src->neg;
159   return dest;
160 }
161 
BN_clear(BIGNUM * bn)162 void BN_clear(BIGNUM *bn) {
163   if (bn->d != NULL) {
164     OPENSSL_memset(bn->d, 0, bn->dmax * sizeof(bn->d[0]));
165   }
166 
167   bn->top = 0;
168   bn->neg = 0;
169 }
170 
DEFINE_METHOD_FUNCTION(BIGNUM,BN_value_one)171 DEFINE_METHOD_FUNCTION(BIGNUM, BN_value_one) {
172   static const BN_ULONG kOneLimbs[1] = { 1 };
173   out->d = (BN_ULONG*) kOneLimbs;
174   out->top = 1;
175   out->dmax = 1;
176   out->neg = 0;
177   out->flags = BN_FLG_STATIC_DATA;
178 }
179 
180 // BN_num_bits_word returns the minimum number of bits needed to represent the
181 // value in |l|.
BN_num_bits_word(BN_ULONG l)182 unsigned BN_num_bits_word(BN_ULONG l) {
183   // |BN_num_bits| is often called on RSA prime factors. These have public bit
184   // lengths, but all bits beyond the high bit are secret, so count bits in
185   // constant time.
186   BN_ULONG x, mask;
187   int bits = (l != 0);
188 
189 #if BN_BITS2 > 32
190   x = l >> 32;
191   mask = 0u - x;
192   mask = (0u - (mask >> (BN_BITS2 - 1)));
193   bits += 32 & mask;
194   l ^= (x ^ l) & mask;
195 #endif
196 
197   x = l >> 16;
198   mask = 0u - x;
199   mask = (0u - (mask >> (BN_BITS2 - 1)));
200   bits += 16 & mask;
201   l ^= (x ^ l) & mask;
202 
203   x = l >> 8;
204   mask = 0u - x;
205   mask = (0u - (mask >> (BN_BITS2 - 1)));
206   bits += 8 & mask;
207   l ^= (x ^ l) & mask;
208 
209   x = l >> 4;
210   mask = 0u - x;
211   mask = (0u - (mask >> (BN_BITS2 - 1)));
212   bits += 4 & mask;
213   l ^= (x ^ l) & mask;
214 
215   x = l >> 2;
216   mask = 0u - x;
217   mask = (0u - (mask >> (BN_BITS2 - 1)));
218   bits += 2 & mask;
219   l ^= (x ^ l) & mask;
220 
221   x = l >> 1;
222   mask = 0u - x;
223   mask = (0u - (mask >> (BN_BITS2 - 1)));
224   bits += 1 & mask;
225 
226   return bits;
227 }
228 
BN_num_bits(const BIGNUM * bn)229 unsigned BN_num_bits(const BIGNUM *bn) {
230   const int width = bn_minimal_width(bn);
231   if (width == 0) {
232     return 0;
233   }
234 
235   return (width - 1) * BN_BITS2 + BN_num_bits_word(bn->d[width - 1]);
236 }
237 
BN_num_bytes(const BIGNUM * bn)238 unsigned BN_num_bytes(const BIGNUM *bn) {
239   return (BN_num_bits(bn) + 7) / 8;
240 }
241 
BN_zero(BIGNUM * bn)242 void BN_zero(BIGNUM *bn) {
243   bn->top = bn->neg = 0;
244 }
245 
BN_one(BIGNUM * bn)246 int BN_one(BIGNUM *bn) {
247   return BN_set_word(bn, 1);
248 }
249 
BN_set_word(BIGNUM * bn,BN_ULONG value)250 int 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 
BN_set_u64(BIGNUM * bn,uint64_t value)266 int 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 
bn_set_words(BIGNUM * bn,const BN_ULONG * words,size_t num)288 int 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 
bn_fits_in_words(const BIGNUM * bn,size_t num)300 int bn_fits_in_words(const BIGNUM *bn, size_t num) {
301   // All words beyond |num| must be zero.
302   BN_ULONG mask = 0;
303   for (size_t i = num; i < (size_t)bn->top; i++) {
304     mask |= bn->d[i];
305   }
306   return mask == 0;
307 }
308 
bn_copy_words(BN_ULONG * out,size_t num,const BIGNUM * bn)309 int bn_copy_words(BN_ULONG *out, size_t num, const BIGNUM *bn) {
310   if (bn->neg) {
311     OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
312     return 0;
313   }
314 
315   size_t width = (size_t)bn->top;
316   if (width > num) {
317     if (!bn_fits_in_words(bn, num)) {
318       OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
319       return 0;
320     }
321     width = num;
322   }
323 
324   OPENSSL_memset(out, 0, sizeof(BN_ULONG) * num);
325   OPENSSL_memcpy(out, bn->d, sizeof(BN_ULONG) * width);
326   return 1;
327 }
328 
BN_is_negative(const BIGNUM * bn)329 int BN_is_negative(const BIGNUM *bn) {
330   return bn->neg != 0;
331 }
332 
BN_set_negative(BIGNUM * bn,int sign)333 void BN_set_negative(BIGNUM *bn, int sign) {
334   if (sign && !BN_is_zero(bn)) {
335     bn->neg = 1;
336   } else {
337     bn->neg = 0;
338   }
339 }
340 
bn_wexpand(BIGNUM * bn,size_t words)341 int bn_wexpand(BIGNUM *bn, size_t words) {
342   BN_ULONG *a;
343 
344   if (words <= (size_t)bn->dmax) {
345     return 1;
346   }
347 
348   if (words > (INT_MAX / (4 * BN_BITS2))) {
349     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
350     return 0;
351   }
352 
353   if (bn->flags & BN_FLG_STATIC_DATA) {
354     OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
355     return 0;
356   }
357 
358   a = OPENSSL_malloc(sizeof(BN_ULONG) * words);
359   if (a == NULL) {
360     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
361     return 0;
362   }
363 
364   OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top);
365 
366   OPENSSL_free(bn->d);
367   bn->d = a;
368   bn->dmax = (int)words;
369 
370   return 1;
371 }
372 
bn_expand(BIGNUM * bn,size_t bits)373 int bn_expand(BIGNUM *bn, size_t bits) {
374   if (bits + BN_BITS2 - 1 < bits) {
375     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
376     return 0;
377   }
378   return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
379 }
380 
bn_resize_words(BIGNUM * bn,size_t words)381 int bn_resize_words(BIGNUM *bn, size_t words) {
382   if ((size_t)bn->top <= words) {
383     if (!bn_wexpand(bn, words)) {
384       return 0;
385     }
386     OPENSSL_memset(bn->d + bn->top, 0, (words - bn->top) * sizeof(BN_ULONG));
387     bn->top = words;
388     return 1;
389   }
390 
391   // All words beyond the new width must be zero.
392   if (!bn_fits_in_words(bn, words)) {
393     OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
394     return 0;
395   }
396   bn->top = words;
397   return 1;
398 }
399 
bn_minimal_width(const BIGNUM * bn)400 int bn_minimal_width(const BIGNUM *bn) {
401   int ret = bn->top;
402   while (ret > 0 && bn->d[ret - 1] == 0) {
403     ret--;
404   }
405   return ret;
406 }
407 
bn_correct_top(BIGNUM * bn)408 void bn_correct_top(BIGNUM *bn) {
409   bn->top = bn_minimal_width(bn);
410   if (bn->top == 0) {
411     bn->neg = 0;
412   }
413 }
414