]>
Commit | Line | Data |
---|---|---|
d02b48c6 | 1 | /* crypto/bn/bn_lib.c */ |
58964a49 | 2 | /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) |
d02b48c6 RE |
3 | * All rights reserved. |
4 | * | |
5 | * This package is an SSL implementation written | |
6 | * by Eric Young (eay@cryptsoft.com). | |
7 | * The implementation was written so as to conform with Netscapes SSL. | |
ae5c8664 | 8 | * |
d02b48c6 RE |
9 | * This library is free for commercial and non-commercial use as long as |
10 | * the following conditions are aheared to. The following conditions | |
11 | * apply to all code found in this distribution, be it the RC4, RSA, | |
12 | * lhash, DES, etc., code; not just the SSL code. The SSL documentation | |
13 | * included with this distribution is covered by the same copyright terms | |
14 | * except that the holder is Tim Hudson (tjh@cryptsoft.com). | |
ae5c8664 | 15 | * |
d02b48c6 RE |
16 | * Copyright remains Eric Young's, and as such any Copyright notices in |
17 | * the code are not to be removed. | |
18 | * If this package is used in a product, Eric Young should be given attribution | |
19 | * as the author of the parts of the library used. | |
20 | * This can be in the form of a textual message at program startup or | |
21 | * in documentation (online or textual) provided with the package. | |
ae5c8664 | 22 | * |
d02b48c6 RE |
23 | * Redistribution and use in source and binary forms, with or without |
24 | * modification, are permitted provided that the following conditions | |
25 | * are met: | |
26 | * 1. Redistributions of source code must retain the copyright | |
27 | * notice, this list of conditions and the following disclaimer. | |
28 | * 2. Redistributions in binary form must reproduce the above copyright | |
29 | * notice, this list of conditions and the following disclaimer in the | |
30 | * documentation and/or other materials provided with the distribution. | |
31 | * 3. All advertising materials mentioning features or use of this software | |
32 | * must display the following acknowledgement: | |
33 | * "This product includes cryptographic software written by | |
34 | * Eric Young (eay@cryptsoft.com)" | |
35 | * The word 'cryptographic' can be left out if the rouines from the library | |
36 | * being used are not cryptographic related :-). | |
ae5c8664 | 37 | * 4. If you include any Windows specific code (or a derivative thereof) from |
d02b48c6 RE |
38 | * the apps directory (application code) you must include an acknowledgement: |
39 | * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" | |
ae5c8664 | 40 | * |
d02b48c6 RE |
41 | * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND |
42 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
43 | * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
44 | * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |
45 | * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
46 | * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
47 | * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
48 | * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
49 | * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
50 | * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
51 | * SUCH DAMAGE. | |
ae5c8664 | 52 | * |
d02b48c6 RE |
53 | * The licence and distribution terms for any publically available version or |
54 | * derivative of this code cannot be changed. i.e. this code cannot simply be | |
55 | * copied and put under another distribution licence | |
56 | * [including the GNU Public Licence.] | |
57 | */ | |
58 | ||
bbb8de09 | 59 | #ifndef BN_DEBUG |
ae5c8664 | 60 | # undef NDEBUG /* avoid conflicting definitions */ |
bbb8de09 BM |
61 | # define NDEBUG |
62 | #endif | |
63 | ||
64 | #include <assert.h> | |
addb309a | 65 | #include <limits.h> |
d02b48c6 RE |
66 | #include <stdio.h> |
67 | #include "cryptlib.h" | |
68 | #include "bn_lcl.h" | |
69 | ||
ae5c8664 | 70 | const char BN_version[] = "Big Number" OPENSSL_VERSION_PTEXT; |
dfeab068 | 71 | |
df11e1e9 GT |
72 | /* This stuff appears to be completely unused, so is deprecated */ |
73 | #ifndef OPENSSL_NO_DEPRECATED | |
6977c7e2 TH |
74 | /*- |
75 | * For a 32 bit machine | |
dfeab068 RE |
76 | * 2 - 4 == 128 |
77 | * 3 - 8 == 256 | |
78 | * 4 - 16 == 512 | |
79 | * 5 - 32 == 1024 | |
80 | * 6 - 64 == 2048 | |
81 | * 7 - 128 == 4096 | |
82 | * 8 - 256 == 8192 | |
83 | */ | |
ae5c8664 MC |
84 | static int bn_limit_bits = 0; |
85 | static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ | |
86 | static int bn_limit_bits_low = 0; | |
87 | static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ | |
88 | static int bn_limit_bits_high = 0; | |
89 | static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ | |
90 | static int bn_limit_bits_mont = 0; | |
91 | static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ | |
dfeab068 | 92 | |
6b691a5c | 93 | void BN_set_params(int mult, int high, int low, int mont) |
ae5c8664 MC |
94 | { |
95 | if (mult >= 0) { | |
96 | if (mult > (int)(sizeof(int) * 8) - 1) | |
97 | mult = sizeof(int) * 8 - 1; | |
98 | bn_limit_bits = mult; | |
99 | bn_limit_num = 1 << mult; | |
100 | } | |
101 | if (high >= 0) { | |
102 | if (high > (int)(sizeof(int) * 8) - 1) | |
103 | high = sizeof(int) * 8 - 1; | |
104 | bn_limit_bits_high = high; | |
105 | bn_limit_num_high = 1 << high; | |
106 | } | |
107 | if (low >= 0) { | |
108 | if (low > (int)(sizeof(int) * 8) - 1) | |
109 | low = sizeof(int) * 8 - 1; | |
110 | bn_limit_bits_low = low; | |
111 | bn_limit_num_low = 1 << low; | |
112 | } | |
113 | if (mont >= 0) { | |
114 | if (mont > (int)(sizeof(int) * 8) - 1) | |
115 | mont = sizeof(int) * 8 - 1; | |
116 | bn_limit_bits_mont = mont; | |
117 | bn_limit_num_mont = 1 << mont; | |
118 | } | |
119 | } | |
dfeab068 | 120 | |
6b691a5c | 121 | int BN_get_params(int which) |
ae5c8664 MC |
122 | { |
123 | if (which == 0) | |
124 | return (bn_limit_bits); | |
125 | else if (which == 1) | |
126 | return (bn_limit_bits_high); | |
127 | else if (which == 2) | |
128 | return (bn_limit_bits_low); | |
129 | else if (which == 3) | |
130 | return (bn_limit_bits_mont); | |
131 | else | |
132 | return (0); | |
133 | } | |
df11e1e9 | 134 | #endif |
d02b48c6 | 135 | |
98499135 | 136 | const BIGNUM *BN_value_one(void) |
ae5c8664 MC |
137 | { |
138 | static const BN_ULONG data_one = 1L; | |
139 | static const BIGNUM const_one = | |
140 | { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; | |
d02b48c6 | 141 | |
ae5c8664 MC |
142 | return (&const_one); |
143 | } | |
d02b48c6 | 144 | |
6b691a5c | 145 | int BN_num_bits_word(BN_ULONG l) |
ae5c8664 | 146 | { |
66509ddb DB |
147 | BN_ULONG x, mask; |
148 | int bits = (l != 0); | |
149 | ||
150 | #if BN_BITS2 > 32 | |
151 | x = l >> 32; | |
152 | mask = (0 - x) & BN_MASK2; | |
153 | mask = (0 - (mask >> (BN_BITS2 - 1))); | |
154 | bits += 32 & mask; | |
155 | l ^= (x ^ l) & mask; | |
d02b48c6 | 156 | #endif |
66509ddb DB |
157 | |
158 | x = l >> 16; | |
159 | mask = (0 - x) & BN_MASK2; | |
160 | mask = (0 - (mask >> (BN_BITS2 - 1))); | |
161 | bits += 16 & mask; | |
162 | l ^= (x ^ l) & mask; | |
163 | ||
164 | x = l >> 8; | |
165 | mask = (0 - x) & BN_MASK2; | |
166 | mask = (0 - (mask >> (BN_BITS2 - 1))); | |
167 | bits += 8 & mask; | |
168 | l ^= (x ^ l) & mask; | |
169 | ||
170 | x = l >> 4; | |
171 | mask = (0 - x) & BN_MASK2; | |
172 | mask = (0 - (mask >> (BN_BITS2 - 1))); | |
173 | bits += 4 & mask; | |
174 | l ^= (x ^ l) & mask; | |
175 | ||
176 | x = l >> 2; | |
177 | mask = (0 - x) & BN_MASK2; | |
178 | mask = (0 - (mask >> (BN_BITS2 - 1))); | |
179 | bits += 2 & mask; | |
180 | l ^= (x ^ l) & mask; | |
181 | ||
182 | x = l >> 1; | |
183 | mask = (0 - x) & BN_MASK2; | |
184 | mask = (0 - (mask >> (BN_BITS2 - 1))); | |
185 | bits += 1 & mask; | |
186 | ||
187 | return bits; | |
ae5c8664 | 188 | } |
d02b48c6 | 189 | |
84c15db5 | 190 | int BN_num_bits(const BIGNUM *a) |
ae5c8664 MC |
191 | { |
192 | int i = a->top - 1; | |
193 | bn_check_top(a); | |
dfeab068 | 194 | |
ae5c8664 MC |
195 | if (BN_is_zero(a)) |
196 | return 0; | |
197 | return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); | |
198 | } | |
d02b48c6 | 199 | |
6b691a5c | 200 | void BN_clear_free(BIGNUM *a) |
ae5c8664 MC |
201 | { |
202 | int i; | |
203 | ||
204 | if (a == NULL) | |
205 | return; | |
206 | bn_check_top(a); | |
207 | if (a->d != NULL) { | |
208 | OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); | |
209 | if (!(BN_get_flags(a, BN_FLG_STATIC_DATA))) | |
210 | OPENSSL_free(a->d); | |
211 | } | |
212 | i = BN_get_flags(a, BN_FLG_MALLOCED); | |
213 | OPENSSL_cleanse(a, sizeof(BIGNUM)); | |
214 | if (i) | |
215 | OPENSSL_free(a); | |
216 | } | |
d02b48c6 | 217 | |
6b691a5c | 218 | void BN_free(BIGNUM *a) |
ae5c8664 MC |
219 | { |
220 | if (a == NULL) | |
221 | return; | |
222 | bn_check_top(a); | |
223 | if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA))) | |
224 | OPENSSL_free(a->d); | |
225 | if (a->flags & BN_FLG_MALLOCED) | |
226 | OPENSSL_free(a); | |
227 | else { | |
29961571 | 228 | #ifndef OPENSSL_NO_DEPRECATED |
ae5c8664 | 229 | a->flags |= BN_FLG_FREE; |
2ae1ea37 | 230 | #endif |
ae5c8664 MC |
231 | a->d = NULL; |
232 | } | |
233 | } | |
dfeab068 | 234 | |
6b691a5c | 235 | void BN_init(BIGNUM *a) |
ae5c8664 MC |
236 | { |
237 | memset(a, 0, sizeof(BIGNUM)); | |
238 | bn_check_top(a); | |
239 | } | |
d02b48c6 | 240 | |
6b691a5c | 241 | BIGNUM *BN_new(void) |
ae5c8664 MC |
242 | { |
243 | BIGNUM *ret; | |
244 | ||
245 | if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) { | |
246 | BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); | |
247 | return (NULL); | |
248 | } | |
249 | ret->flags = BN_FLG_MALLOCED; | |
250 | ret->top = 0; | |
251 | ret->neg = 0; | |
252 | ret->dmax = 0; | |
253 | ret->d = NULL; | |
254 | bn_check_top(ret); | |
255 | return (ret); | |
256 | } | |
d02b48c6 | 257 | |
020fc820 RL |
258 | /* This is used both by bn_expand2() and bn_dup_expand() */ |
259 | /* The caller MUST check that words > b->dmax before calling this */ | |
6343829a | 260 | static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) |
ae5c8664 MC |
261 | { |
262 | BN_ULONG *A, *a = NULL; | |
263 | const BN_ULONG *B; | |
264 | int i; | |
265 | ||
ae5c8664 MC |
266 | if (words > (INT_MAX / (4 * BN_BITS2))) { |
267 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); | |
268 | return NULL; | |
269 | } | |
270 | if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { | |
271 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); | |
272 | return (NULL); | |
273 | } | |
274 | a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); | |
275 | if (A == NULL) { | |
276 | BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); | |
277 | return (NULL); | |
278 | } | |
14b5d0d0 | 279 | #ifdef PURIFY |
ae5c8664 MC |
280 | /* |
281 | * Valgrind complains in BN_consttime_swap because we process the whole | |
282 | * array even if it's not initialised yet. This doesn't matter in that | |
283 | * function - what's important is constant time operation (we're not | |
284 | * actually going to use the data) | |
285 | */ | |
286 | memset(a, 0, sizeof(BN_ULONG) * words); | |
14b5d0d0 MC |
287 | #endif |
288 | ||
dfeab068 | 289 | #if 1 |
ae5c8664 MC |
290 | B = b->d; |
291 | /* Check if the previous number needs to be copied */ | |
292 | if (B != NULL) { | |
293 | for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { | |
294 | /* | |
295 | * The fact that the loop is unrolled | |
296 | * 4-wise is a tribute to Intel. It's | |
297 | * the one that doesn't have enough | |
298 | * registers to accomodate more data. | |
299 | * I'd unroll it 8-wise otherwise:-) | |
300 | * | |
301 | * <appro@fy.chalmers.se> | |
302 | */ | |
303 | BN_ULONG a0, a1, a2, a3; | |
304 | a0 = B[0]; | |
305 | a1 = B[1]; | |
306 | a2 = B[2]; | |
307 | a3 = B[3]; | |
308 | A[0] = a0; | |
309 | A[1] = a1; | |
310 | A[2] = a2; | |
311 | A[3] = a3; | |
312 | } | |
313 | /* | |
314 | * workaround for ultrix cc: without 'case 0', the optimizer does | |
315 | * the switch table by doing a=top&3; a--; goto jump_table[a]; | |
316 | * which fails for top== 0 | |
317 | */ | |
318 | switch (b->top & 3) { | |
319 | case 3: | |
320 | A[2] = B[2]; | |
321 | case 2: | |
322 | A[1] = B[1]; | |
323 | case 1: | |
324 | A[0] = B[0]; | |
325 | case 0: | |
326 | ; | |
327 | } | |
328 | } | |
dfeab068 | 329 | #else |
ae5c8664 MC |
330 | memset(A, 0, sizeof(BN_ULONG) * words); |
331 | memcpy(A, b->d, sizeof(b->d[0]) * b->top); | |
dfeab068 | 332 | #endif |
ae5c8664 MC |
333 | |
334 | return (a); | |
335 | } | |
336 | ||
337 | /* | |
338 | * This is an internal function that can be used instead of bn_expand2() when | |
339 | * there is a need to copy BIGNUMs instead of only expanding the data part, | |
340 | * while still expanding them. Especially useful when needing to expand | |
341 | * BIGNUMs that are declared 'const' and should therefore not be changed. The | |
342 | * reason to use this instead of a BN_dup() followed by a bn_expand2() is | |
343 | * memory allocation overhead. A BN_dup() followed by a bn_expand2() will | |
344 | * allocate new memory for the BIGNUM data twice, and free it once, while | |
345 | * bn_dup_expand() makes sure allocation is made only once. | |
020fc820 RL |
346 | */ |
347 | ||
e042540f | 348 | #ifndef OPENSSL_NO_DEPRECATED |
6343829a | 349 | BIGNUM *bn_dup_expand(const BIGNUM *b, int words) |
ae5c8664 MC |
350 | { |
351 | BIGNUM *r = NULL; | |
352 | ||
353 | bn_check_top(b); | |
354 | ||
355 | /* | |
356 | * This function does not work if words <= b->dmax && top < words because | |
357 | * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used | |
358 | * anywhere yet.) | |
359 | */ | |
360 | ||
361 | if (words > b->dmax) { | |
362 | BN_ULONG *a = bn_expand_internal(b, words); | |
363 | ||
364 | if (a) { | |
365 | r = BN_new(); | |
366 | if (r) { | |
367 | r->top = b->top; | |
368 | r->dmax = words; | |
369 | r->neg = b->neg; | |
370 | r->d = a; | |
371 | } else { | |
372 | /* r == NULL, BN_new failure */ | |
373 | OPENSSL_free(a); | |
374 | } | |
375 | } | |
376 | /* | |
377 | * If a == NULL, there was an error in allocation in | |
378 | * bn_expand_internal(), and NULL should be returned | |
379 | */ | |
380 | } else { | |
381 | r = BN_dup(b); | |
382 | } | |
383 | ||
384 | bn_check_top(r); | |
385 | return r; | |
386 | } | |
e042540f | 387 | #endif |
020fc820 | 388 | |
ae5c8664 MC |
389 | /* |
390 | * This is an internal function that should not be used in applications. It | |
391 | * ensures that 'b' has enough room for a 'words' word number and initialises | |
392 | * any unused part of b->d with leading zeros. It is mostly used by the | |
393 | * various BIGNUM routines. If there is an error, NULL is returned. If not, | |
394 | * 'b' is returned. | |
395 | */ | |
020fc820 | 396 | |
6343829a | 397 | BIGNUM *bn_expand2(BIGNUM *b, int words) |
ae5c8664 | 398 | { |
ae5c8664 MC |
399 | if (words > b->dmax) { |
400 | BN_ULONG *a = bn_expand_internal(b, words); | |
401 | if (!a) | |
402 | return NULL; | |
403 | if (b->d) | |
404 | OPENSSL_free(b->d); | |
405 | b->d = a; | |
406 | b->dmax = words; | |
407 | } | |
2bfd2c74 | 408 | |
e042540f GT |
409 | /* None of this should be necessary because of what b->top means! */ |
410 | #if 0 | |
ae5c8664 MC |
411 | /* |
412 | * NB: bn_wexpand() calls this only if the BIGNUM really has to grow | |
413 | */ | |
414 | if (b->top < b->dmax) { | |
415 | int i; | |
416 | BN_ULONG *A = &(b->d[b->top]); | |
417 | for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) { | |
418 | A[0] = 0; | |
419 | A[1] = 0; | |
420 | A[2] = 0; | |
421 | A[3] = 0; | |
422 | A[4] = 0; | |
423 | A[5] = 0; | |
424 | A[6] = 0; | |
425 | A[7] = 0; | |
426 | } | |
427 | for (i = (b->dmax - b->top) & 7; i > 0; i--, A++) | |
428 | A[0] = 0; | |
429 | assert(A == &(b->d[b->dmax])); | |
430 | } | |
e042540f | 431 | #endif |
ae5c8664 MC |
432 | return b; |
433 | } | |
d02b48c6 | 434 | |
84c15db5 | 435 | BIGNUM *BN_dup(const BIGNUM *a) |
ae5c8664 MC |
436 | { |
437 | BIGNUM *t; | |
438 | ||
439 | if (a == NULL) | |
440 | return NULL; | |
441 | bn_check_top(a); | |
442 | ||
443 | t = BN_new(); | |
444 | if (t == NULL) | |
445 | return NULL; | |
446 | if (!BN_copy(t, a)) { | |
447 | BN_free(t); | |
448 | return NULL; | |
449 | } | |
450 | bn_check_top(t); | |
451 | return t; | |
452 | } | |
d02b48c6 | 453 | |
84c15db5 | 454 | BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) |
ae5c8664 MC |
455 | { |
456 | int i; | |
457 | BN_ULONG *A; | |
458 | const BN_ULONG *B; | |
58964a49 | 459 | |
ae5c8664 | 460 | bn_check_top(b); |
dfeab068 | 461 | |
ae5c8664 MC |
462 | if (a == b) |
463 | return (a); | |
464 | if (bn_wexpand(a, b->top) == NULL) | |
465 | return (NULL); | |
58964a49 RE |
466 | |
467 | #if 1 | |
ae5c8664 MC |
468 | A = a->d; |
469 | B = b->d; | |
470 | for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { | |
471 | BN_ULONG a0, a1, a2, a3; | |
472 | a0 = B[0]; | |
473 | a1 = B[1]; | |
474 | a2 = B[2]; | |
475 | a3 = B[3]; | |
476 | A[0] = a0; | |
477 | A[1] = a1; | |
478 | A[2] = a2; | |
479 | A[3] = a3; | |
480 | } | |
481 | /* ultrix cc workaround, see comments in bn_expand_internal */ | |
482 | switch (b->top & 3) { | |
483 | case 3: | |
484 | A[2] = B[2]; | |
485 | case 2: | |
486 | A[1] = B[1]; | |
487 | case 1: | |
488 | A[0] = B[0]; | |
489 | case 0:; | |
490 | } | |
58964a49 | 491 | #else |
ae5c8664 | 492 | memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); |
58964a49 RE |
493 | #endif |
494 | ||
ae5c8664 | 495 | a->neg = b->neg; |
327b2c01 AP |
496 | a->top = b->top; |
497 | a->flags |= b->flags & BN_FLG_FIXED_TOP; | |
ae5c8664 MC |
498 | bn_check_top(a); |
499 | return (a); | |
500 | } | |
d02b48c6 | 501 | |
98f2e513 | 502 | #define FLAGS_DATA(flags) ((flags) & (BN_FLG_STATIC_DATA \ |
327b2c01 AP |
503 | | BN_FLG_CONSTTIME \ |
504 | | BN_FLG_FIXED_TOP)) | |
98f2e513 BB |
505 | #define FLAGS_STRUCT(flags) ((flags) & (BN_FLG_MALLOCED)) |
506 | ||
78a0c1f1 | 507 | void BN_swap(BIGNUM *a, BIGNUM *b) |
ae5c8664 MC |
508 | { |
509 | int flags_old_a, flags_old_b; | |
510 | BN_ULONG *tmp_d; | |
511 | int tmp_top, tmp_dmax, tmp_neg; | |
512 | ||
513 | bn_check_top(a); | |
514 | bn_check_top(b); | |
515 | ||
516 | flags_old_a = a->flags; | |
517 | flags_old_b = b->flags; | |
518 | ||
519 | tmp_d = a->d; | |
520 | tmp_top = a->top; | |
521 | tmp_dmax = a->dmax; | |
522 | tmp_neg = a->neg; | |
523 | ||
524 | a->d = b->d; | |
525 | a->top = b->top; | |
526 | a->dmax = b->dmax; | |
527 | a->neg = b->neg; | |
528 | ||
529 | b->d = tmp_d; | |
530 | b->top = tmp_top; | |
531 | b->dmax = tmp_dmax; | |
532 | b->neg = tmp_neg; | |
533 | ||
98f2e513 BB |
534 | a->flags = FLAGS_STRUCT(flags_old_a) | FLAGS_DATA(flags_old_b); |
535 | b->flags = FLAGS_STRUCT(flags_old_b) | FLAGS_DATA(flags_old_a); | |
ae5c8664 MC |
536 | bn_check_top(a); |
537 | bn_check_top(b); | |
538 | } | |
78a0c1f1 | 539 | |
6b691a5c | 540 | void BN_clear(BIGNUM *a) |
ae5c8664 MC |
541 | { |
542 | bn_check_top(a); | |
543 | if (a->d != NULL) | |
cb5ebf96 | 544 | OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); |
ae5c8664 MC |
545 | a->top = 0; |
546 | a->neg = 0; | |
327b2c01 | 547 | a->flags &= ~BN_FLG_FIXED_TOP; |
ae5c8664 | 548 | } |
d02b48c6 | 549 | |
020fc820 | 550 | BN_ULONG BN_get_word(const BIGNUM *a) |
ae5c8664 MC |
551 | { |
552 | if (a->top > 1) | |
553 | return BN_MASK2; | |
554 | else if (a->top == 1) | |
555 | return a->d[0]; | |
556 | /* a->top == 0 */ | |
557 | return 0; | |
558 | } | |
d02b48c6 | 559 | |
e042540f | 560 | int BN_set_word(BIGNUM *a, BN_ULONG w) |
ae5c8664 MC |
561 | { |
562 | bn_check_top(a); | |
563 | if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) | |
564 | return (0); | |
565 | a->neg = 0; | |
566 | a->d[0] = w; | |
567 | a->top = (w ? 1 : 0); | |
327b2c01 | 568 | a->flags &= ~BN_FLG_FIXED_TOP; |
ae5c8664 MC |
569 | bn_check_top(a); |
570 | return (1); | |
571 | } | |
d02b48c6 | 572 | |
6343829a | 573 | BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) |
ae5c8664 MC |
574 | { |
575 | unsigned int i, m; | |
576 | unsigned int n; | |
577 | BN_ULONG l; | |
578 | BIGNUM *bn = NULL; | |
579 | ||
580 | if (ret == NULL) | |
581 | ret = bn = BN_new(); | |
582 | if (ret == NULL) | |
583 | return (NULL); | |
584 | bn_check_top(ret); | |
585 | l = 0; | |
586 | n = len; | |
587 | if (n == 0) { | |
588 | ret->top = 0; | |
589 | return (ret); | |
590 | } | |
591 | i = ((n - 1) / BN_BYTES) + 1; | |
592 | m = ((n - 1) % (BN_BYTES)); | |
593 | if (bn_wexpand(ret, (int)i) == NULL) { | |
594 | if (bn) | |
595 | BN_free(bn); | |
596 | return NULL; | |
597 | } | |
598 | ret->top = i; | |
599 | ret->neg = 0; | |
600 | while (n--) { | |
601 | l = (l << 8L) | *(s++); | |
602 | if (m-- == 0) { | |
603 | ret->d[--i] = l; | |
604 | l = 0; | |
605 | m = BN_BYTES - 1; | |
606 | } | |
607 | } | |
608 | /* | |
609 | * need to call this due to clear byte at top if avoiding having the top | |
610 | * bit set (-ve number) | |
611 | */ | |
612 | bn_correct_top(ret); | |
613 | return (ret); | |
614 | } | |
d02b48c6 RE |
615 | |
616 | /* ignore negative */ | |
6412738b AP |
617 | static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) |
618 | { | |
df6b67be | 619 | int n; |
bc251459 | 620 | size_t i, lasti, j, atop, mask; |
6412738b AP |
621 | BN_ULONG l; |
622 | ||
bc251459 AP |
623 | /* |
624 | * In case |a| is fixed-top, BN_num_bytes can return bogus length, | |
625 | * but it's assumed that fixed-top inputs ought to be "nominated" | |
626 | * even for padded output, so it works out... | |
627 | */ | |
df6b67be | 628 | n = BN_num_bytes(a); |
bc251459 | 629 | if (tolen == -1) { |
df6b67be | 630 | tolen = n; |
bc251459 AP |
631 | } else if (tolen < n) { /* uncommon/unlike case */ |
632 | BIGNUM temp = *a; | |
6412738b | 633 | |
bc251459 AP |
634 | bn_correct_top(&temp); |
635 | n = BN_num_bytes(&temp); | |
636 | if (tolen < n) | |
637 | return -1; | |
638 | } | |
639 | ||
640 | /* Swipe through whole available data and don't give away padded zero. */ | |
641 | atop = a->dmax * BN_BYTES; | |
642 | if (atop == 0) { | |
6412738b AP |
643 | OPENSSL_cleanse(to, tolen); |
644 | return tolen; | |
645 | } | |
646 | ||
bc251459 AP |
647 | lasti = atop - 1; |
648 | atop = a->top * BN_BYTES; | |
649 | for (i = 0, j = 0, to += tolen; j < (size_t)tolen; j++) { | |
6412738b | 650 | l = a->d[i / BN_BYTES]; |
bc251459 AP |
651 | mask = 0 - ((j - atop) >> (8 * sizeof(i) - 1)); |
652 | *--to = (unsigned char)(l >> (8 * (i % BN_BYTES)) & mask); | |
653 | i += (i - lasti) >> (8 * sizeof(i) - 1); /* stay on last limb */ | |
6412738b AP |
654 | } |
655 | ||
656 | return tolen; | |
657 | } | |
658 | ||
659 | int bn_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) | |
660 | { | |
661 | if (tolen < 0) | |
662 | return -1; | |
663 | return bn2binpad(a, to, tolen); | |
664 | } | |
665 | ||
8623f693 | 666 | int BN_bn2bin(const BIGNUM *a, unsigned char *to) |
ae5c8664 MC |
667 | { |
668 | int n, i; | |
669 | BN_ULONG l; | |
670 | ||
671 | bn_check_top(a); | |
672 | n = i = BN_num_bytes(a); | |
673 | while (i--) { | |
674 | l = a->d[i / BN_BYTES]; | |
675 | *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; | |
676 | } | |
677 | return (n); | |
678 | } | |
d02b48c6 | 679 | |
84c15db5 | 680 | int BN_ucmp(const BIGNUM *a, const BIGNUM *b) |
ae5c8664 MC |
681 | { |
682 | int i; | |
683 | BN_ULONG t1, t2, *ap, *bp; | |
684 | ||
685 | bn_check_top(a); | |
686 | bn_check_top(b); | |
687 | ||
688 | i = a->top - b->top; | |
689 | if (i != 0) | |
690 | return (i); | |
691 | ap = a->d; | |
692 | bp = b->d; | |
693 | for (i = a->top - 1; i >= 0; i--) { | |
694 | t1 = ap[i]; | |
695 | t2 = bp[i]; | |
696 | if (t1 != t2) | |
697 | return ((t1 > t2) ? 1 : -1); | |
698 | } | |
699 | return (0); | |
700 | } | |
d02b48c6 | 701 | |
84c15db5 | 702 | int BN_cmp(const BIGNUM *a, const BIGNUM *b) |
ae5c8664 MC |
703 | { |
704 | int i; | |
705 | int gt, lt; | |
706 | BN_ULONG t1, t2; | |
707 | ||
708 | if ((a == NULL) || (b == NULL)) { | |
709 | if (a != NULL) | |
710 | return (-1); | |
711 | else if (b != NULL) | |
712 | return (1); | |
713 | else | |
714 | return (0); | |
715 | } | |
716 | ||
717 | bn_check_top(a); | |
718 | bn_check_top(b); | |
719 | ||
720 | if (a->neg != b->neg) { | |
721 | if (a->neg) | |
722 | return (-1); | |
723 | else | |
724 | return (1); | |
725 | } | |
726 | if (a->neg == 0) { | |
727 | gt = 1; | |
728 | lt = -1; | |
729 | } else { | |
730 | gt = -1; | |
731 | lt = 1; | |
732 | } | |
733 | ||
734 | if (a->top > b->top) | |
735 | return (gt); | |
736 | if (a->top < b->top) | |
737 | return (lt); | |
738 | for (i = a->top - 1; i >= 0; i--) { | |
739 | t1 = a->d[i]; | |
740 | t2 = b->d[i]; | |
741 | if (t1 > t2) | |
742 | return (gt); | |
743 | if (t1 < t2) | |
744 | return (lt); | |
745 | } | |
746 | return (0); | |
747 | } | |
d02b48c6 | 748 | |
6b691a5c | 749 | int BN_set_bit(BIGNUM *a, int n) |
ae5c8664 MC |
750 | { |
751 | int i, j, k; | |
752 | ||
753 | if (n < 0) | |
754 | return 0; | |
755 | ||
756 | i = n / BN_BITS2; | |
757 | j = n % BN_BITS2; | |
758 | if (a->top <= i) { | |
759 | if (bn_wexpand(a, i + 1) == NULL) | |
760 | return (0); | |
761 | for (k = a->top; k < i + 1; k++) | |
762 | a->d[k] = 0; | |
763 | a->top = i + 1; | |
327b2c01 | 764 | a->flags &= ~BN_FLG_FIXED_TOP; |
ae5c8664 MC |
765 | } |
766 | ||
767 | a->d[i] |= (((BN_ULONG)1) << j); | |
768 | bn_check_top(a); | |
769 | return (1); | |
770 | } | |
d02b48c6 | 771 | |
6b691a5c | 772 | int BN_clear_bit(BIGNUM *a, int n) |
ae5c8664 MC |
773 | { |
774 | int i, j; | |
d02b48c6 | 775 | |
ae5c8664 MC |
776 | bn_check_top(a); |
777 | if (n < 0) | |
778 | return 0; | |
1a017330 | 779 | |
ae5c8664 MC |
780 | i = n / BN_BITS2; |
781 | j = n % BN_BITS2; | |
782 | if (a->top <= i) | |
783 | return (0); | |
d02b48c6 | 784 | |
ae5c8664 MC |
785 | a->d[i] &= (~(((BN_ULONG)1) << j)); |
786 | bn_correct_top(a); | |
787 | return (1); | |
788 | } | |
d02b48c6 | 789 | |
84c15db5 | 790 | int BN_is_bit_set(const BIGNUM *a, int n) |
ae5c8664 MC |
791 | { |
792 | int i, j; | |
793 | ||
794 | bn_check_top(a); | |
795 | if (n < 0) | |
796 | return 0; | |
797 | i = n / BN_BITS2; | |
798 | j = n % BN_BITS2; | |
799 | if (a->top <= i) | |
800 | return 0; | |
801 | return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); | |
802 | } | |
d02b48c6 | 803 | |
6b691a5c | 804 | int BN_mask_bits(BIGNUM *a, int n) |
ae5c8664 MC |
805 | { |
806 | int b, w; | |
807 | ||
808 | bn_check_top(a); | |
809 | if (n < 0) | |
810 | return 0; | |
811 | ||
812 | w = n / BN_BITS2; | |
813 | b = n % BN_BITS2; | |
814 | if (w >= a->top) | |
815 | return 0; | |
816 | if (b == 0) | |
817 | a->top = w; | |
818 | else { | |
819 | a->top = w + 1; | |
820 | a->d[w] &= ~(BN_MASK2 << b); | |
821 | } | |
822 | bn_correct_top(a); | |
823 | return (1); | |
824 | } | |
dfeab068 | 825 | |
ff22e913 | 826 | void BN_set_negative(BIGNUM *a, int b) |
ae5c8664 MC |
827 | { |
828 | if (b && !BN_is_zero(a)) | |
829 | a->neg = 1; | |
830 | else | |
831 | a->neg = 0; | |
832 | } | |
ff22e913 | 833 | |
cbd48ba6 | 834 | int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) |
ae5c8664 MC |
835 | { |
836 | int i; | |
837 | BN_ULONG aa, bb; | |
838 | ||
b250f2a4 MC |
839 | if (n == 0) |
840 | return 0; | |
841 | ||
ae5c8664 MC |
842 | aa = a[n - 1]; |
843 | bb = b[n - 1]; | |
844 | if (aa != bb) | |
845 | return ((aa > bb) ? 1 : -1); | |
846 | for (i = n - 2; i >= 0; i--) { | |
847 | aa = a[i]; | |
848 | bb = b[i]; | |
849 | if (aa != bb) | |
850 | return ((aa > bb) ? 1 : -1); | |
851 | } | |
852 | return (0); | |
853 | } | |
854 | ||
855 | /* | |
856 | * Here follows a specialised variants of bn_cmp_words(). It has the | |
857 | * property of performing the operation on arrays of different sizes. The | |
858 | * sizes of those arrays is expressed through cl, which is the common length | |
859 | * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the | |
860 | * two lengths, calculated as len(a)-len(b). All lengths are the number of | |
861 | * BN_ULONGs... | |
862 | */ | |
863 | ||
864 | int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) | |
865 | { | |
866 | int n, i; | |
867 | n = cl - 1; | |
868 | ||
869 | if (dl < 0) { | |
870 | for (i = dl; i < 0; i++) { | |
871 | if (b[n - i] != 0) | |
872 | return -1; /* a < b */ | |
873 | } | |
874 | } | |
875 | if (dl > 0) { | |
876 | for (i = dl; i > 0; i--) { | |
877 | if (a[n + i] != 0) | |
878 | return 1; /* a > b */ | |
879 | } | |
880 | } | |
881 | return bn_cmp_words(a, b, cl); | |
882 | } | |
883 | ||
884 | /* | |
885 | * Constant-time conditional swap of a and b. | |
0a9f7780 DSH |
886 | * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. |
887 | * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, | |
888 | * and that no more than nwords are used by either a or b. | |
889 | * a and b cannot be the same number | |
890 | */ | |
891 | void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) | |
ae5c8664 MC |
892 | { |
893 | BN_ULONG t; | |
894 | int i; | |
0a9f7780 | 895 | |
ae5c8664 MC |
896 | bn_wcheck_size(a, nwords); |
897 | bn_wcheck_size(b, nwords); | |
0a9f7780 | 898 | |
ae5c8664 MC |
899 | assert(a != b); |
900 | assert((condition & (condition - 1)) == 0); | |
901 | assert(sizeof(BN_ULONG) >= sizeof(int)); | |
0a9f7780 | 902 | |
ae5c8664 | 903 | condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; |
0a9f7780 | 904 | |
ae5c8664 MC |
905 | t = (a->top ^ b->top) & condition; |
906 | a->top ^= t; | |
907 | b->top ^= t; | |
0a9f7780 | 908 | |
b18162a7 BB |
909 | t = (a->neg ^ b->neg) & condition; |
910 | a->neg ^= t; | |
911 | b->neg ^= t; | |
912 | ||
913 | /*- | |
914 | * BN_FLG_STATIC_DATA: indicates that data may not be written to. Intention | |
915 | * is actually to treat it as it's read-only data, and some (if not most) | |
916 | * of it does reside in read-only segment. In other words observation of | |
917 | * BN_FLG_STATIC_DATA in BN_consttime_swap should be treated as fatal | |
918 | * condition. It would either cause SEGV or effectively cause data | |
919 | * corruption. | |
920 | * | |
921 | * BN_FLG_MALLOCED: refers to BN structure itself, and hence must be | |
922 | * preserved. | |
923 | * | |
924 | * BN_FLG_SECURE: must be preserved, because it determines how x->d was | |
925 | * allocated and hence how to free it. | |
926 | * | |
927 | * BN_FLG_CONSTTIME: sufficient to mask and swap | |
928 | * | |
929 | * BN_FLG_FIXED_TOP: indicates that we haven't called bn_correct_top() on | |
930 | * the data, so the d array may be padded with additional 0 values (i.e. | |
931 | * top could be greater than the minimal value that it could be). We should | |
932 | * be swapping it | |
933 | */ | |
934 | ||
935 | #define BN_CONSTTIME_SWAP_FLAGS (BN_FLG_CONSTTIME | BN_FLG_FIXED_TOP) | |
936 | ||
937 | t = ((a->flags ^ b->flags) & BN_CONSTTIME_SWAP_FLAGS) & condition; | |
938 | a->flags ^= t; | |
939 | b->flags ^= t; | |
940 | ||
0a9f7780 | 941 | #define BN_CONSTTIME_SWAP(ind) \ |
ae5c8664 MC |
942 | do { \ |
943 | t = (a->d[ind] ^ b->d[ind]) & condition; \ | |
944 | a->d[ind] ^= t; \ | |
945 | b->d[ind] ^= t; \ | |
946 | } while (0) | |
947 | ||
948 | switch (nwords) { | |
949 | default: | |
950 | for (i = 10; i < nwords; i++) | |
951 | BN_CONSTTIME_SWAP(i); | |
952 | /* Fallthrough */ | |
953 | case 10: | |
954 | BN_CONSTTIME_SWAP(9); /* Fallthrough */ | |
955 | case 9: | |
956 | BN_CONSTTIME_SWAP(8); /* Fallthrough */ | |
957 | case 8: | |
958 | BN_CONSTTIME_SWAP(7); /* Fallthrough */ | |
959 | case 7: | |
960 | BN_CONSTTIME_SWAP(6); /* Fallthrough */ | |
961 | case 6: | |
962 | BN_CONSTTIME_SWAP(5); /* Fallthrough */ | |
963 | case 5: | |
964 | BN_CONSTTIME_SWAP(4); /* Fallthrough */ | |
965 | case 4: | |
966 | BN_CONSTTIME_SWAP(3); /* Fallthrough */ | |
967 | case 3: | |
968 | BN_CONSTTIME_SWAP(2); /* Fallthrough */ | |
969 | case 2: | |
970 | BN_CONSTTIME_SWAP(1); /* Fallthrough */ | |
971 | case 1: | |
972 | BN_CONSTTIME_SWAP(0); | |
973 | } | |
0a9f7780 DSH |
974 | #undef BN_CONSTTIME_SWAP |
975 | } |