]>
Commit | Line | Data |
---|---|---|
4f22f405 RS |
1 | /* |
2 | * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. | |
d02b48c6 | 3 | * |
4f22f405 RS |
4 | * Licensed under the OpenSSL license (the "License"). You may not use |
5 | * this file except in compliance with the License. You can obtain a copy | |
6 | * in the file LICENSE in the source distribution or at | |
7 | * https://www.openssl.org/source/license.html | |
d02b48c6 RE |
8 | */ |
9 | ||
bbb8de09 | 10 | #include <assert.h> |
addb309a | 11 | #include <limits.h> |
b39fc560 | 12 | #include "internal/cryptlib.h" |
d02b48c6 | 13 | #include "bn_lcl.h" |
98186eb4 | 14 | #include <openssl/opensslconf.h> |
d02b48c6 | 15 | |
df11e1e9 | 16 | /* This stuff appears to be completely unused, so is deprecated */ |
98186eb4 | 17 | #if OPENSSL_API_COMPAT < 0x00908000L |
1d97c843 TH |
18 | /*- |
19 | * For a 32 bit machine | |
dfeab068 RE |
20 | * 2 - 4 == 128 |
21 | * 3 - 8 == 256 | |
22 | * 4 - 16 == 512 | |
23 | * 5 - 32 == 1024 | |
24 | * 6 - 64 == 2048 | |
25 | * 7 - 128 == 4096 | |
26 | * 8 - 256 == 8192 | |
27 | */ | |
0f113f3e MC |
28 | static int bn_limit_bits = 0; |
29 | static int bn_limit_num = 8; /* (1<<bn_limit_bits) */ | |
30 | static int bn_limit_bits_low = 0; | |
31 | static int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ | |
32 | static int bn_limit_bits_high = 0; | |
33 | static int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ | |
34 | static int bn_limit_bits_mont = 0; | |
35 | static int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ | |
dfeab068 | 36 | |
6b691a5c | 37 | void BN_set_params(int mult, int high, int low, int mont) |
0f113f3e MC |
38 | { |
39 | if (mult >= 0) { | |
40 | if (mult > (int)(sizeof(int) * 8) - 1) | |
41 | mult = sizeof(int) * 8 - 1; | |
42 | bn_limit_bits = mult; | |
43 | bn_limit_num = 1 << mult; | |
44 | } | |
45 | if (high >= 0) { | |
46 | if (high > (int)(sizeof(int) * 8) - 1) | |
47 | high = sizeof(int) * 8 - 1; | |
48 | bn_limit_bits_high = high; | |
49 | bn_limit_num_high = 1 << high; | |
50 | } | |
51 | if (low >= 0) { | |
52 | if (low > (int)(sizeof(int) * 8) - 1) | |
53 | low = sizeof(int) * 8 - 1; | |
54 | bn_limit_bits_low = low; | |
55 | bn_limit_num_low = 1 << low; | |
56 | } | |
57 | if (mont >= 0) { | |
58 | if (mont > (int)(sizeof(int) * 8) - 1) | |
59 | mont = sizeof(int) * 8 - 1; | |
60 | bn_limit_bits_mont = mont; | |
61 | bn_limit_num_mont = 1 << mont; | |
62 | } | |
63 | } | |
dfeab068 | 64 | |
6b691a5c | 65 | int BN_get_params(int which) |
0f113f3e MC |
66 | { |
67 | if (which == 0) | |
68 | return (bn_limit_bits); | |
69 | else if (which == 1) | |
70 | return (bn_limit_bits_high); | |
71 | else if (which == 2) | |
72 | return (bn_limit_bits_low); | |
73 | else if (which == 3) | |
74 | return (bn_limit_bits_mont); | |
75 | else | |
76 | return (0); | |
77 | } | |
df11e1e9 | 78 | #endif |
d02b48c6 | 79 | |
98499135 | 80 | const BIGNUM *BN_value_one(void) |
0f113f3e MC |
81 | { |
82 | static const BN_ULONG data_one = 1L; | |
83 | static const BIGNUM const_one = | |
84 | { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; | |
d02b48c6 | 85 | |
0f113f3e MC |
86 | return (&const_one); |
87 | } | |
d02b48c6 | 88 | |
6b691a5c | 89 | int BN_num_bits_word(BN_ULONG l) |
0f113f3e MC |
90 | { |
91 | static const unsigned char bits[256] = { | |
92 | 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, | |
93 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, | |
94 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, | |
95 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, | |
96 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
97 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
98 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
99 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, | |
100 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
101 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
102 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
103 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
104 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
105 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
106 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
107 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, | |
108 | }; | |
d02b48c6 | 109 | |
dfeab068 | 110 | #if defined(SIXTY_FOUR_BIT_LONG) |
0f113f3e MC |
111 | if (l & 0xffffffff00000000L) { |
112 | if (l & 0xffff000000000000L) { | |
113 | if (l & 0xff00000000000000L) { | |
114 | return (bits[(int)(l >> 56)] + 56); | |
115 | } else | |
116 | return (bits[(int)(l >> 48)] + 48); | |
117 | } else { | |
118 | if (l & 0x0000ff0000000000L) { | |
119 | return (bits[(int)(l >> 40)] + 40); | |
120 | } else | |
121 | return (bits[(int)(l >> 32)] + 32); | |
122 | } | |
123 | } else | |
d02b48c6 | 124 | #else |
0f113f3e MC |
125 | # ifdef SIXTY_FOUR_BIT |
126 | if (l & 0xffffffff00000000LL) { | |
127 | if (l & 0xffff000000000000LL) { | |
128 | if (l & 0xff00000000000000LL) { | |
129 | return (bits[(int)(l >> 56)] + 56); | |
130 | } else | |
131 | return (bits[(int)(l >> 48)] + 48); | |
132 | } else { | |
133 | if (l & 0x0000ff0000000000LL) { | |
134 | return (bits[(int)(l >> 40)] + 40); | |
135 | } else | |
136 | return (bits[(int)(l >> 32)] + 32); | |
137 | } | |
138 | } else | |
139 | # endif | |
d02b48c6 | 140 | #endif |
0f113f3e | 141 | { |
d02b48c6 | 142 | #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) |
0f113f3e MC |
143 | if (l & 0xffff0000L) { |
144 | if (l & 0xff000000L) | |
145 | return (bits[(int)(l >> 24L)] + 24); | |
146 | else | |
147 | return (bits[(int)(l >> 16L)] + 16); | |
148 | } else | |
d02b48c6 | 149 | #endif |
0f113f3e | 150 | { |
4a47f556 | 151 | #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) |
0f113f3e MC |
152 | if (l & 0xff00L) |
153 | return (bits[(int)(l >> 8)] + 8); | |
154 | else | |
d02b48c6 | 155 | #endif |
0f113f3e MC |
156 | return (bits[(int)(l)]); |
157 | } | |
158 | } | |
159 | } | |
d02b48c6 | 160 | |
84c15db5 | 161 | int BN_num_bits(const BIGNUM *a) |
0f113f3e MC |
162 | { |
163 | int i = a->top - 1; | |
164 | bn_check_top(a); | |
dfeab068 | 165 | |
0f113f3e MC |
166 | if (BN_is_zero(a)) |
167 | return 0; | |
168 | return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); | |
169 | } | |
d02b48c6 | 170 | |
9f040d6d RS |
171 | static void bn_free_d(BIGNUM *a) |
172 | { | |
700b8145 | 173 | if (BN_get_flags(a, BN_FLG_SECURE)) |
9f040d6d RS |
174 | OPENSSL_secure_free(a->d); |
175 | else | |
176 | OPENSSL_free(a->d); | |
177 | } | |
178 | ||
179 | ||
6b691a5c | 180 | void BN_clear_free(BIGNUM *a) |
0f113f3e | 181 | { |
0f113f3e MC |
182 | if (a == NULL) |
183 | return; | |
5f2d9c4d | 184 | if (a->d != NULL && !BN_get_flags(a, BN_FLG_STATIC_DATA)) { |
0f113f3e | 185 | OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); |
5f2d9c4d | 186 | bn_free_d(a); |
0f113f3e | 187 | } |
5f2d9c4d DSH |
188 | if (BN_get_flags(a, BN_FLG_MALLOCED)) { |
189 | OPENSSL_cleanse(a, sizeof(*a)); | |
0f113f3e | 190 | OPENSSL_free(a); |
5f2d9c4d | 191 | } |
0f113f3e | 192 | } |
d02b48c6 | 193 | |
6b691a5c | 194 | void BN_free(BIGNUM *a) |
0f113f3e MC |
195 | { |
196 | if (a == NULL) | |
197 | return; | |
b548a1f1 | 198 | if (!BN_get_flags(a, BN_FLG_STATIC_DATA)) |
9f040d6d | 199 | bn_free_d(a); |
0f113f3e MC |
200 | if (a->flags & BN_FLG_MALLOCED) |
201 | OPENSSL_free(a); | |
0f113f3e | 202 | } |
dfeab068 | 203 | |
d59c7c81 | 204 | void bn_init(BIGNUM *a) |
0f113f3e | 205 | { |
d59c7c81 RS |
206 | static BIGNUM nilbn; |
207 | ||
208 | *a = nilbn; | |
0f113f3e MC |
209 | bn_check_top(a); |
210 | } | |
d02b48c6 | 211 | |
6b691a5c | 212 | BIGNUM *BN_new(void) |
0f113f3e MC |
213 | { |
214 | BIGNUM *ret; | |
215 | ||
64b25758 | 216 | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { |
0f113f3e MC |
217 | BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); |
218 | return (NULL); | |
219 | } | |
220 | ret->flags = BN_FLG_MALLOCED; | |
0f113f3e MC |
221 | bn_check_top(ret); |
222 | return (ret); | |
223 | } | |
d02b48c6 | 224 | |
74924dcb RS |
225 | BIGNUM *BN_secure_new(void) |
226 | { | |
227 | BIGNUM *ret = BN_new(); | |
90945fa3 | 228 | if (ret != NULL) |
74924dcb RS |
229 | ret->flags |= BN_FLG_SECURE; |
230 | return (ret); | |
231 | } | |
232 | ||
8707e3be | 233 | /* This is used by bn_expand2() */ |
020fc820 | 234 | /* The caller MUST check that words > b->dmax before calling this */ |
6343829a | 235 | static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) |
0f113f3e | 236 | { |
d5aa14dd | 237 | BN_ULONG *a = NULL; |
0f113f3e MC |
238 | |
239 | bn_check_top(b); | |
240 | ||
241 | if (words > (INT_MAX / (4 * BN_BITS2))) { | |
242 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); | |
243 | return NULL; | |
244 | } | |
245 | if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { | |
246 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); | |
247 | return (NULL); | |
248 | } | |
700b8145 | 249 | if (BN_get_flags(b, BN_FLG_SECURE)) |
d5aa14dd | 250 | a = OPENSSL_secure_zalloc(words * sizeof(*a)); |
74924dcb | 251 | else |
d5aa14dd EK |
252 | a = OPENSSL_zalloc(words * sizeof(*a)); |
253 | if (a == NULL) { | |
0f113f3e MC |
254 | BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); |
255 | return (NULL); | |
256 | } | |
f8571ce8 | 257 | |
d5aa14dd | 258 | assert(b->top <= words); |
d0808664 MC |
259 | if (b->top > 0) |
260 | memcpy(a, b->d, sizeof(*a) * b->top); | |
dfeab068 | 261 | |
d5aa14dd | 262 | return a; |
0f113f3e MC |
263 | } |
264 | ||
265 | /* | |
266 | * This is an internal function that should not be used in applications. It | |
267 | * ensures that 'b' has enough room for a 'words' word number and initialises | |
268 | * any unused part of b->d with leading zeros. It is mostly used by the | |
269 | * various BIGNUM routines. If there is an error, NULL is returned. If not, | |
270 | * 'b' is returned. | |
271 | */ | |
020fc820 | 272 | |
6343829a | 273 | BIGNUM *bn_expand2(BIGNUM *b, int words) |
0f113f3e MC |
274 | { |
275 | bn_check_top(b); | |
276 | ||
277 | if (words > b->dmax) { | |
278 | BN_ULONG *a = bn_expand_internal(b, words); | |
279 | if (!a) | |
280 | return NULL; | |
74924dcb | 281 | if (b->d) { |
9f040d6d RS |
282 | OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0])); |
283 | bn_free_d(b); | |
74924dcb | 284 | } |
0f113f3e MC |
285 | b->d = a; |
286 | b->dmax = words; | |
287 | } | |
2bfd2c74 | 288 | |
0f113f3e MC |
289 | bn_check_top(b); |
290 | return b; | |
291 | } | |
d02b48c6 | 292 | |
84c15db5 | 293 | BIGNUM *BN_dup(const BIGNUM *a) |
0f113f3e MC |
294 | { |
295 | BIGNUM *t; | |
296 | ||
297 | if (a == NULL) | |
298 | return NULL; | |
299 | bn_check_top(a); | |
300 | ||
74924dcb | 301 | t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new(); |
0f113f3e MC |
302 | if (t == NULL) |
303 | return NULL; | |
304 | if (!BN_copy(t, a)) { | |
305 | BN_free(t); | |
306 | return NULL; | |
307 | } | |
308 | bn_check_top(t); | |
309 | return t; | |
310 | } | |
d02b48c6 | 311 | |
84c15db5 | 312 | BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) |
0f113f3e | 313 | { |
0f113f3e | 314 | bn_check_top(b); |
dfeab068 | 315 | |
0f113f3e | 316 | if (a == b) |
d5aa14dd | 317 | return a; |
0f113f3e | 318 | if (bn_wexpand(a, b->top) == NULL) |
d5aa14dd | 319 | return NULL; |
58964a49 | 320 | |
d0808664 MC |
321 | if (b->top > 0) |
322 | memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); | |
58964a49 | 323 | |
9f944291 SW |
324 | if (BN_get_flags(b, BN_FLG_CONSTTIME) != 0) |
325 | BN_set_flags(a, BN_FLG_CONSTTIME); | |
326 | ||
0f113f3e MC |
327 | a->top = b->top; |
328 | a->neg = b->neg; | |
329 | bn_check_top(a); | |
d5aa14dd | 330 | return a; |
0f113f3e | 331 | } |
d02b48c6 | 332 | |
78a0c1f1 | 333 | void BN_swap(BIGNUM *a, BIGNUM *b) |
0f113f3e MC |
334 | { |
335 | int flags_old_a, flags_old_b; | |
336 | BN_ULONG *tmp_d; | |
337 | int tmp_top, tmp_dmax, tmp_neg; | |
338 | ||
339 | bn_check_top(a); | |
340 | bn_check_top(b); | |
341 | ||
342 | flags_old_a = a->flags; | |
343 | flags_old_b = b->flags; | |
344 | ||
345 | tmp_d = a->d; | |
346 | tmp_top = a->top; | |
347 | tmp_dmax = a->dmax; | |
348 | tmp_neg = a->neg; | |
349 | ||
350 | a->d = b->d; | |
351 | a->top = b->top; | |
352 | a->dmax = b->dmax; | |
353 | a->neg = b->neg; | |
354 | ||
355 | b->d = tmp_d; | |
356 | b->top = tmp_top; | |
357 | b->dmax = tmp_dmax; | |
358 | b->neg = tmp_neg; | |
359 | ||
360 | a->flags = | |
361 | (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); | |
362 | b->flags = | |
363 | (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); | |
364 | bn_check_top(a); | |
365 | bn_check_top(b); | |
366 | } | |
78a0c1f1 | 367 | |
6b691a5c | 368 | void BN_clear(BIGNUM *a) |
0f113f3e MC |
369 | { |
370 | bn_check_top(a); | |
371 | if (a->d != NULL) | |
3ce2fdab | 372 | OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax); |
0f113f3e MC |
373 | a->top = 0; |
374 | a->neg = 0; | |
375 | } | |
d02b48c6 | 376 | |
020fc820 | 377 | BN_ULONG BN_get_word(const BIGNUM *a) |
0f113f3e MC |
378 | { |
379 | if (a->top > 1) | |
380 | return BN_MASK2; | |
381 | else if (a->top == 1) | |
382 | return a->d[0]; | |
383 | /* a->top == 0 */ | |
384 | return 0; | |
385 | } | |
d02b48c6 | 386 | |
e042540f | 387 | int BN_set_word(BIGNUM *a, BN_ULONG w) |
0f113f3e MC |
388 | { |
389 | bn_check_top(a); | |
390 | if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) | |
391 | return (0); | |
392 | a->neg = 0; | |
393 | a->d[0] = w; | |
394 | a->top = (w ? 1 : 0); | |
395 | bn_check_top(a); | |
208fb891 | 396 | return 1; |
0f113f3e | 397 | } |
d02b48c6 | 398 | |
6343829a | 399 | BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) |
0f113f3e MC |
400 | { |
401 | unsigned int i, m; | |
402 | unsigned int n; | |
403 | BN_ULONG l; | |
404 | BIGNUM *bn = NULL; | |
405 | ||
406 | if (ret == NULL) | |
407 | ret = bn = BN_new(); | |
408 | if (ret == NULL) | |
409 | return (NULL); | |
410 | bn_check_top(ret); | |
22dc08d0 | 411 | /* Skip leading zero's. */ |
3c65047d | 412 | for ( ; len > 0 && *s == 0; s++, len--) |
22dc08d0 | 413 | continue; |
0f113f3e MC |
414 | n = len; |
415 | if (n == 0) { | |
416 | ret->top = 0; | |
417 | return (ret); | |
418 | } | |
419 | i = ((n - 1) / BN_BYTES) + 1; | |
420 | m = ((n - 1) % (BN_BYTES)); | |
421 | if (bn_wexpand(ret, (int)i) == NULL) { | |
23a1d5e9 | 422 | BN_free(bn); |
0f113f3e MC |
423 | return NULL; |
424 | } | |
425 | ret->top = i; | |
426 | ret->neg = 0; | |
22dc08d0 | 427 | l = 0; |
0f113f3e MC |
428 | while (n--) { |
429 | l = (l << 8L) | *(s++); | |
430 | if (m-- == 0) { | |
431 | ret->d[--i] = l; | |
432 | l = 0; | |
433 | m = BN_BYTES - 1; | |
434 | } | |
435 | } | |
436 | /* | |
437 | * need to call this due to clear byte at top if avoiding having the top | |
438 | * bit set (-ve number) | |
439 | */ | |
440 | bn_correct_top(ret); | |
441 | return (ret); | |
442 | } | |
d02b48c6 RE |
443 | |
444 | /* ignore negative */ | |
85a4807f | 445 | static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) |
0f113f3e | 446 | { |
85a4807f | 447 | int i; |
0f113f3e MC |
448 | BN_ULONG l; |
449 | ||
450 | bn_check_top(a); | |
85a4807f DSH |
451 | i = BN_num_bytes(a); |
452 | if (tolen == -1) | |
453 | tolen = i; | |
454 | else if (tolen < i) | |
455 | return -1; | |
456 | /* Add leading zeroes if necessary */ | |
457 | if (tolen > i) { | |
458 | memset(to, 0, tolen - i); | |
459 | to += tolen - i; | |
460 | } | |
0f113f3e MC |
461 | while (i--) { |
462 | l = a->d[i / BN_BYTES]; | |
463 | *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; | |
464 | } | |
85a4807f DSH |
465 | return tolen; |
466 | } | |
467 | ||
468 | int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) | |
469 | { | |
470 | if (tolen < 0) | |
471 | return -1; | |
472 | return bn2binpad(a, to, tolen); | |
473 | } | |
474 | ||
475 | int BN_bn2bin(const BIGNUM *a, unsigned char *to) | |
476 | { | |
477 | return bn2binpad(a, to, -1); | |
478 | } | |
479 | ||
480 | BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) | |
481 | { | |
482 | unsigned int i, m; | |
483 | unsigned int n; | |
484 | BN_ULONG l; | |
485 | BIGNUM *bn = NULL; | |
486 | ||
487 | if (ret == NULL) | |
488 | ret = bn = BN_new(); | |
489 | if (ret == NULL) | |
490 | return (NULL); | |
491 | bn_check_top(ret); | |
f3cf2251 | 492 | s += len; |
85a4807f | 493 | /* Skip trailing zeroes. */ |
f3cf2251 | 494 | for ( ; len > 0 && s[-1] == 0; s--, len--) |
85a4807f DSH |
495 | continue; |
496 | n = len; | |
497 | if (n == 0) { | |
498 | ret->top = 0; | |
499 | return ret; | |
500 | } | |
501 | i = ((n - 1) / BN_BYTES) + 1; | |
502 | m = ((n - 1) % (BN_BYTES)); | |
503 | if (bn_wexpand(ret, (int)i) == NULL) { | |
504 | BN_free(bn); | |
505 | return NULL; | |
506 | } | |
507 | ret->top = i; | |
508 | ret->neg = 0; | |
509 | l = 0; | |
510 | while (n--) { | |
f3cf2251 KR |
511 | s--; |
512 | l = (l << 8L) | *s; | |
85a4807f DSH |
513 | if (m-- == 0) { |
514 | ret->d[--i] = l; | |
515 | l = 0; | |
516 | m = BN_BYTES - 1; | |
517 | } | |
518 | } | |
519 | /* | |
520 | * need to call this due to clear byte at top if avoiding having the top | |
521 | * bit set (-ve number) | |
522 | */ | |
523 | bn_correct_top(ret); | |
524 | return ret; | |
525 | } | |
526 | ||
527 | int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) | |
528 | { | |
529 | int i; | |
530 | BN_ULONG l; | |
531 | bn_check_top(a); | |
532 | i = BN_num_bytes(a); | |
533 | if (tolen < i) | |
534 | return -1; | |
535 | /* Add trailing zeroes if necessary */ | |
536 | if (tolen > i) | |
537 | memset(to + i, 0, tolen - i); | |
f3cf2251 | 538 | to += i; |
85a4807f DSH |
539 | while (i--) { |
540 | l = a->d[i / BN_BYTES]; | |
f3cf2251 KR |
541 | to--; |
542 | *to = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; | |
85a4807f DSH |
543 | } |
544 | return tolen; | |
0f113f3e | 545 | } |
d02b48c6 | 546 | |
84c15db5 | 547 | int BN_ucmp(const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
548 | { |
549 | int i; | |
550 | BN_ULONG t1, t2, *ap, *bp; | |
551 | ||
552 | bn_check_top(a); | |
553 | bn_check_top(b); | |
554 | ||
555 | i = a->top - b->top; | |
556 | if (i != 0) | |
557 | return (i); | |
558 | ap = a->d; | |
559 | bp = b->d; | |
560 | for (i = a->top - 1; i >= 0; i--) { | |
561 | t1 = ap[i]; | |
562 | t2 = bp[i]; | |
563 | if (t1 != t2) | |
564 | return ((t1 > t2) ? 1 : -1); | |
565 | } | |
566 | return (0); | |
567 | } | |
d02b48c6 | 568 | |
84c15db5 | 569 | int BN_cmp(const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
570 | { |
571 | int i; | |
572 | int gt, lt; | |
573 | BN_ULONG t1, t2; | |
574 | ||
575 | if ((a == NULL) || (b == NULL)) { | |
576 | if (a != NULL) | |
577 | return (-1); | |
578 | else if (b != NULL) | |
208fb891 | 579 | return 1; |
0f113f3e MC |
580 | else |
581 | return (0); | |
582 | } | |
583 | ||
584 | bn_check_top(a); | |
585 | bn_check_top(b); | |
586 | ||
587 | if (a->neg != b->neg) { | |
588 | if (a->neg) | |
589 | return (-1); | |
590 | else | |
208fb891 | 591 | return 1; |
0f113f3e MC |
592 | } |
593 | if (a->neg == 0) { | |
594 | gt = 1; | |
595 | lt = -1; | |
596 | } else { | |
597 | gt = -1; | |
598 | lt = 1; | |
599 | } | |
600 | ||
601 | if (a->top > b->top) | |
602 | return (gt); | |
603 | if (a->top < b->top) | |
604 | return (lt); | |
605 | for (i = a->top - 1; i >= 0; i--) { | |
606 | t1 = a->d[i]; | |
607 | t2 = b->d[i]; | |
608 | if (t1 > t2) | |
609 | return (gt); | |
610 | if (t1 < t2) | |
611 | return (lt); | |
612 | } | |
613 | return (0); | |
614 | } | |
d02b48c6 | 615 | |
6b691a5c | 616 | int BN_set_bit(BIGNUM *a, int n) |
0f113f3e MC |
617 | { |
618 | int i, j, k; | |
619 | ||
620 | if (n < 0) | |
621 | return 0; | |
622 | ||
623 | i = n / BN_BITS2; | |
624 | j = n % BN_BITS2; | |
625 | if (a->top <= i) { | |
626 | if (bn_wexpand(a, i + 1) == NULL) | |
627 | return (0); | |
628 | for (k = a->top; k < i + 1; k++) | |
629 | a->d[k] = 0; | |
630 | a->top = i + 1; | |
631 | } | |
632 | ||
633 | a->d[i] |= (((BN_ULONG)1) << j); | |
634 | bn_check_top(a); | |
208fb891 | 635 | return 1; |
0f113f3e | 636 | } |
d02b48c6 | 637 | |
6b691a5c | 638 | int BN_clear_bit(BIGNUM *a, int n) |
0f113f3e MC |
639 | { |
640 | int i, j; | |
d02b48c6 | 641 | |
0f113f3e MC |
642 | bn_check_top(a); |
643 | if (n < 0) | |
644 | return 0; | |
1a017330 | 645 | |
0f113f3e MC |
646 | i = n / BN_BITS2; |
647 | j = n % BN_BITS2; | |
648 | if (a->top <= i) | |
649 | return (0); | |
d02b48c6 | 650 | |
0f113f3e MC |
651 | a->d[i] &= (~(((BN_ULONG)1) << j)); |
652 | bn_correct_top(a); | |
208fb891 | 653 | return 1; |
0f113f3e | 654 | } |
d02b48c6 | 655 | |
84c15db5 | 656 | int BN_is_bit_set(const BIGNUM *a, int n) |
0f113f3e MC |
657 | { |
658 | int i, j; | |
659 | ||
660 | bn_check_top(a); | |
661 | if (n < 0) | |
662 | return 0; | |
663 | i = n / BN_BITS2; | |
664 | j = n % BN_BITS2; | |
665 | if (a->top <= i) | |
666 | return 0; | |
667 | return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); | |
668 | } | |
d02b48c6 | 669 | |
6b691a5c | 670 | int BN_mask_bits(BIGNUM *a, int n) |
0f113f3e MC |
671 | { |
672 | int b, w; | |
673 | ||
674 | bn_check_top(a); | |
675 | if (n < 0) | |
676 | return 0; | |
677 | ||
678 | w = n / BN_BITS2; | |
679 | b = n % BN_BITS2; | |
680 | if (w >= a->top) | |
681 | return 0; | |
682 | if (b == 0) | |
683 | a->top = w; | |
684 | else { | |
685 | a->top = w + 1; | |
686 | a->d[w] &= ~(BN_MASK2 << b); | |
687 | } | |
688 | bn_correct_top(a); | |
208fb891 | 689 | return 1; |
0f113f3e | 690 | } |
dfeab068 | 691 | |
ff22e913 | 692 | void BN_set_negative(BIGNUM *a, int b) |
0f113f3e MC |
693 | { |
694 | if (b && !BN_is_zero(a)) | |
695 | a->neg = 1; | |
696 | else | |
697 | a->neg = 0; | |
698 | } | |
ff22e913 | 699 | |
cbd48ba6 | 700 | int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) |
0f113f3e MC |
701 | { |
702 | int i; | |
703 | BN_ULONG aa, bb; | |
704 | ||
705 | aa = a[n - 1]; | |
706 | bb = b[n - 1]; | |
707 | if (aa != bb) | |
708 | return ((aa > bb) ? 1 : -1); | |
709 | for (i = n - 2; i >= 0; i--) { | |
710 | aa = a[i]; | |
711 | bb = b[i]; | |
712 | if (aa != bb) | |
713 | return ((aa > bb) ? 1 : -1); | |
714 | } | |
715 | return (0); | |
716 | } | |
717 | ||
718 | /* | |
719 | * Here follows a specialised variants of bn_cmp_words(). It has the | |
399de496 | 720 | * capability of performing the operation on arrays of different sizes. The |
0f113f3e | 721 | * sizes of those arrays is expressed through cl, which is the common length |
399de496 | 722 | * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the |
0f113f3e MC |
723 | * two lengths, calculated as len(a)-len(b). All lengths are the number of |
724 | * BN_ULONGs... | |
725 | */ | |
726 | ||
727 | int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) | |
728 | { | |
729 | int n, i; | |
730 | n = cl - 1; | |
731 | ||
732 | if (dl < 0) { | |
733 | for (i = dl; i < 0; i++) { | |
734 | if (b[n - i] != 0) | |
735 | return -1; /* a < b */ | |
736 | } | |
737 | } | |
738 | if (dl > 0) { | |
739 | for (i = dl; i > 0; i--) { | |
740 | if (a[n + i] != 0) | |
741 | return 1; /* a > b */ | |
742 | } | |
743 | } | |
744 | return bn_cmp_words(a, b, cl); | |
745 | } | |
746 | ||
747 | /* | |
748 | * Constant-time conditional swap of a and b. | |
f9b6c0ba DSH |
749 | * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. |
750 | * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, | |
751 | * and that no more than nwords are used by either a or b. | |
752 | * a and b cannot be the same number | |
753 | */ | |
754 | void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) | |
0f113f3e MC |
755 | { |
756 | BN_ULONG t; | |
757 | int i; | |
f9b6c0ba | 758 | |
0f113f3e MC |
759 | bn_wcheck_size(a, nwords); |
760 | bn_wcheck_size(b, nwords); | |
f9b6c0ba | 761 | |
0f113f3e MC |
762 | assert(a != b); |
763 | assert((condition & (condition - 1)) == 0); | |
764 | assert(sizeof(BN_ULONG) >= sizeof(int)); | |
f9b6c0ba | 765 | |
0f113f3e | 766 | condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; |
f9b6c0ba | 767 | |
0f113f3e MC |
768 | t = (a->top ^ b->top) & condition; |
769 | a->top ^= t; | |
770 | b->top ^= t; | |
f9b6c0ba DSH |
771 | |
772 | #define BN_CONSTTIME_SWAP(ind) \ | |
0f113f3e MC |
773 | do { \ |
774 | t = (a->d[ind] ^ b->d[ind]) & condition; \ | |
775 | a->d[ind] ^= t; \ | |
776 | b->d[ind] ^= t; \ | |
777 | } while (0) | |
778 | ||
779 | switch (nwords) { | |
780 | default: | |
781 | for (i = 10; i < nwords; i++) | |
782 | BN_CONSTTIME_SWAP(i); | |
783 | /* Fallthrough */ | |
784 | case 10: | |
785 | BN_CONSTTIME_SWAP(9); /* Fallthrough */ | |
786 | case 9: | |
787 | BN_CONSTTIME_SWAP(8); /* Fallthrough */ | |
788 | case 8: | |
789 | BN_CONSTTIME_SWAP(7); /* Fallthrough */ | |
790 | case 7: | |
791 | BN_CONSTTIME_SWAP(6); /* Fallthrough */ | |
792 | case 6: | |
793 | BN_CONSTTIME_SWAP(5); /* Fallthrough */ | |
794 | case 5: | |
795 | BN_CONSTTIME_SWAP(4); /* Fallthrough */ | |
796 | case 4: | |
797 | BN_CONSTTIME_SWAP(3); /* Fallthrough */ | |
798 | case 3: | |
799 | BN_CONSTTIME_SWAP(2); /* Fallthrough */ | |
800 | case 2: | |
801 | BN_CONSTTIME_SWAP(1); /* Fallthrough */ | |
802 | case 1: | |
803 | BN_CONSTTIME_SWAP(0); | |
804 | } | |
f9b6c0ba DSH |
805 | #undef BN_CONSTTIME_SWAP |
806 | } | |
2514fa79 DSH |
807 | |
808 | /* Bits of security, see SP800-57 */ | |
809 | ||
810 | int BN_security_bits(int L, int N) | |
0f113f3e MC |
811 | { |
812 | int secbits, bits; | |
813 | if (L >= 15360) | |
814 | secbits = 256; | |
815 | else if (L >= 7690) | |
816 | secbits = 192; | |
817 | else if (L >= 3072) | |
818 | secbits = 128; | |
819 | else if (L >= 2048) | |
820 | secbits = 112; | |
821 | else if (L >= 1024) | |
822 | secbits = 80; | |
823 | else | |
824 | return 0; | |
825 | if (N == -1) | |
826 | return secbits; | |
827 | bits = N / 2; | |
828 | if (bits < 80) | |
829 | return 0; | |
830 | return bits >= secbits ? secbits : bits; | |
831 | } | |
85bcf27c MC |
832 | |
833 | void BN_zero_ex(BIGNUM *a) | |
0f113f3e MC |
834 | { |
835 | a->top = 0; | |
836 | a->neg = 0; | |
837 | } | |
85bcf27c MC |
838 | |
839 | int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) | |
0f113f3e MC |
840 | { |
841 | return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0)); | |
842 | } | |
85bcf27c MC |
843 | |
844 | int BN_is_zero(const BIGNUM *a) | |
0f113f3e MC |
845 | { |
846 | return a->top == 0; | |
847 | } | |
85bcf27c MC |
848 | |
849 | int BN_is_one(const BIGNUM *a) | |
0f113f3e MC |
850 | { |
851 | return BN_abs_is_word(a, 1) && !a->neg; | |
852 | } | |
85bcf27c MC |
853 | |
854 | int BN_is_word(const BIGNUM *a, const BN_ULONG w) | |
0f113f3e MC |
855 | { |
856 | return BN_abs_is_word(a, w) && (!w || !a->neg); | |
857 | } | |
85bcf27c MC |
858 | |
859 | int BN_is_odd(const BIGNUM *a) | |
0f113f3e MC |
860 | { |
861 | return (a->top > 0) && (a->d[0] & 1); | |
862 | } | |
85bcf27c MC |
863 | |
864 | int BN_is_negative(const BIGNUM *a) | |
0f113f3e MC |
865 | { |
866 | return (a->neg != 0); | |
867 | } | |
85bcf27c | 868 | |
0f113f3e MC |
869 | int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, |
870 | BN_CTX *ctx) | |
871 | { | |
872 | return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx); | |
873 | } | |
85bcf27c | 874 | |
fd7d2520 | 875 | void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) |
0f113f3e MC |
876 | { |
877 | dest->d = b->d; | |
878 | dest->top = b->top; | |
879 | dest->dmax = b->dmax; | |
880 | dest->neg = b->neg; | |
881 | dest->flags = ((dest->flags & BN_FLG_MALLOCED) | |
882 | | (b->flags & ~BN_FLG_MALLOCED) | |
fd7d2520 | 883 | | BN_FLG_STATIC_DATA | flags); |
0f113f3e | 884 | } |
85bcf27c MC |
885 | |
886 | BN_GENCB *BN_GENCB_new(void) | |
0f113f3e MC |
887 | { |
888 | BN_GENCB *ret; | |
85bcf27c | 889 | |
b4faea50 | 890 | if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) { |
0f113f3e MC |
891 | BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE); |
892 | return (NULL); | |
893 | } | |
85bcf27c | 894 | |
0f113f3e MC |
895 | return ret; |
896 | } | |
85bcf27c MC |
897 | |
898 | void BN_GENCB_free(BN_GENCB *cb) | |
0f113f3e MC |
899 | { |
900 | if (cb == NULL) | |
901 | return; | |
902 | OPENSSL_free(cb); | |
903 | } | |
85bcf27c MC |
904 | |
905 | void BN_set_flags(BIGNUM *b, int n) | |
0f113f3e MC |
906 | { |
907 | b->flags |= n; | |
908 | } | |
85bcf27c MC |
909 | |
910 | int BN_get_flags(const BIGNUM *b, int n) | |
0f113f3e MC |
911 | { |
912 | return b->flags & n; | |
913 | } | |
85bcf27c MC |
914 | |
915 | /* Populate a BN_GENCB structure with an "old"-style callback */ | |
0f113f3e MC |
916 | void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *), |
917 | void *cb_arg) | |
918 | { | |
919 | BN_GENCB *tmp_gencb = gencb; | |
920 | tmp_gencb->ver = 1; | |
921 | tmp_gencb->arg = cb_arg; | |
922 | tmp_gencb->cb.cb_1 = callback; | |
923 | } | |
85bcf27c MC |
924 | |
925 | /* Populate a BN_GENCB structure with a "new"-style callback */ | |
0f113f3e MC |
926 | void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *), |
927 | void *cb_arg) | |
928 | { | |
929 | BN_GENCB *tmp_gencb = gencb; | |
930 | tmp_gencb->ver = 2; | |
931 | tmp_gencb->arg = cb_arg; | |
932 | tmp_gencb->cb.cb_2 = callback; | |
933 | } | |
85bcf27c MC |
934 | |
935 | void *BN_GENCB_get_arg(BN_GENCB *cb) | |
0f113f3e MC |
936 | { |
937 | return cb->arg; | |
938 | } | |
85bcf27c MC |
939 | |
940 | BIGNUM *bn_wexpand(BIGNUM *a, int words) | |
0f113f3e MC |
941 | { |
942 | return (words <= a->dmax) ? a : bn_expand2(a, words); | |
943 | } | |
85bcf27c MC |
944 | |
945 | void bn_correct_top(BIGNUM *a) | |
0f113f3e MC |
946 | { |
947 | BN_ULONG *ftl; | |
948 | int tmp_top = a->top; | |
949 | ||
950 | if (tmp_top > 0) { | |
1544583b KR |
951 | for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) { |
952 | ftl--; | |
953 | if (*ftl != 0) | |
0f113f3e | 954 | break; |
1544583b | 955 | } |
0f113f3e MC |
956 | a->top = tmp_top; |
957 | } | |
01c09f9f RS |
958 | if (a->top == 0) |
959 | a->neg = 0; | |
0f113f3e MC |
960 | bn_pollute(a); |
961 | } |