Debian Codegraph @

external/boringssl/crypto/bn/bn.c

raw
1 /* Copyright (C) 1995-1998 Eric Young ([email protected])
2 * All rights reserved.
3 *
4 * This package is an SSL implementation written
5 * by Eric Young ([email protected]).
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 ([email protected]).
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 ([email protected])"
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 ([email protected])"
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
68 BIGNUM *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
82 void BN_init(BIGNUM *bn) {
83 memset(bn, 0, sizeof(BIGNUM));
84 }
85
86 void 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
102 void 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
123 BIGNUM *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
143 BIGNUM *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
159 void 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
168 const 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
175 void 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|. */
183 unsigned 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
231 unsigned 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
241 unsigned BN_num_bytes(const BIGNUM *bn) {
242 return (BN_num_bits(bn) + 7) / 8;
243 }
244
245 void BN_zero(BIGNUM *bn) {
246 bn->top = bn->neg = 0;
247 }
248
249 int BN_one(BIGNUM *bn) {
250 return BN_set_word(bn, 1);
251 }
252
253 int 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
269 int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) {
270 if (bn_wexpand(bn, num) == NULL) {
271 return 0;
272 }
273 memmove(bn->d, words, num * sizeof(BN_ULONG));
274 /* |bn_wexpand| verified that |num| isn't too large. */
275 bn->top = (int)num;
276 bn_correct_top(bn);
277 bn->neg = 0;
278 return 1;
279 }
280
281 int BN_is_negative(const BIGNUM *bn) {
282 return bn->neg != 0;
283 }
284
285 void BN_set_negative(BIGNUM *bn, int sign) {
286 if (sign && !BN_is_zero(bn)) {
287 bn->neg = 1;
288 } else {
289 bn->neg = 0;
290 }
291 }
292
293 BIGNUM *bn_wexpand(BIGNUM *bn, size_t words) {
294 BN_ULONG *a;
295
296 if (words <= (size_t)bn->dmax) {
297 return bn;
298 }
299
300 if (words > (INT_MAX / (4 * BN_BITS2))) {
301 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
302 return NULL;
303 }
304
305 if (bn->flags & BN_FLG_STATIC_DATA) {
306 OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
307 return NULL;
308 }
309
310 a = OPENSSL_malloc(sizeof(BN_ULONG) * words);
311 if (a == NULL) {
312 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
313 return NULL;
314 }
315
316 memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top);
317
318 OPENSSL_free(bn->d);
319 bn->d = a;
320 bn->dmax = (int)words;
321
322 return bn;
323 }
324
325 BIGNUM *bn_expand(BIGNUM *bn, size_t bits) {
326 if (bits + BN_BITS2 - 1 < bits) {
327 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG);
328 return NULL;
329 }
330 return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2);
331 }
332
333 void bn_correct_top(BIGNUM *bn) {
334 BN_ULONG *ftl;
335 int tmp_top = bn->top;
336
337 if (tmp_top > 0) {
338 for (ftl = &(bn->d[tmp_top - 1]); tmp_top > 0; tmp_top--) {
339 if (*(ftl--)) {
340 break;
341 }
342 }
343 bn->top = tmp_top;
344 }
345 }
346
347 int BN_get_flags(const BIGNUM *bn, int flags) {
348 return bn->flags & flags;
349 }
350
351 void BN_set_flags(BIGNUM *bn, int flags) {
352 bn->flags |= flags;
353 }