]>
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 | { | |
173 | if (BN_get_flags(a,BN_FLG_SECURE)) | |
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 MC |
181 | { |
182 | int i; | |
183 | ||
184 | if (a == NULL) | |
185 | return; | |
186 | bn_check_top(a); | |
187 | if (a->d != NULL) { | |
188 | OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); | |
9f040d6d RS |
189 | if (!BN_get_flags(a, BN_FLG_STATIC_DATA)) |
190 | bn_free_d(a); | |
0f113f3e MC |
191 | } |
192 | i = BN_get_flags(a, BN_FLG_MALLOCED); | |
9f040d6d | 193 | OPENSSL_cleanse(a, sizeof(*a)); |
0f113f3e MC |
194 | if (i) |
195 | OPENSSL_free(a); | |
196 | } | |
d02b48c6 | 197 | |
6b691a5c | 198 | void BN_free(BIGNUM *a) |
0f113f3e MC |
199 | { |
200 | if (a == NULL) | |
201 | return; | |
202 | bn_check_top(a); | |
b548a1f1 | 203 | if (!BN_get_flags(a, BN_FLG_STATIC_DATA)) |
9f040d6d | 204 | bn_free_d(a); |
0f113f3e MC |
205 | if (a->flags & BN_FLG_MALLOCED) |
206 | OPENSSL_free(a); | |
207 | else { | |
98186eb4 | 208 | #if OPENSSL_API_COMPAT < 0x00908000L |
0f113f3e | 209 | a->flags |= BN_FLG_FREE; |
2ae1ea37 | 210 | #endif |
0f113f3e MC |
211 | a->d = NULL; |
212 | } | |
213 | } | |
dfeab068 | 214 | |
d59c7c81 | 215 | void bn_init(BIGNUM *a) |
0f113f3e | 216 | { |
d59c7c81 RS |
217 | static BIGNUM nilbn; |
218 | ||
219 | *a = nilbn; | |
0f113f3e MC |
220 | bn_check_top(a); |
221 | } | |
d02b48c6 | 222 | |
6b691a5c | 223 | BIGNUM *BN_new(void) |
0f113f3e MC |
224 | { |
225 | BIGNUM *ret; | |
226 | ||
64b25758 | 227 | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) { |
0f113f3e MC |
228 | BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); |
229 | return (NULL); | |
230 | } | |
231 | ret->flags = BN_FLG_MALLOCED; | |
0f113f3e MC |
232 | bn_check_top(ret); |
233 | return (ret); | |
234 | } | |
d02b48c6 | 235 | |
74924dcb RS |
236 | BIGNUM *BN_secure_new(void) |
237 | { | |
238 | BIGNUM *ret = BN_new(); | |
90945fa3 | 239 | if (ret != NULL) |
74924dcb RS |
240 | ret->flags |= BN_FLG_SECURE; |
241 | return (ret); | |
242 | } | |
243 | ||
8707e3be | 244 | /* This is used by bn_expand2() */ |
020fc820 | 245 | /* The caller MUST check that words > b->dmax before calling this */ |
6343829a | 246 | static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) |
0f113f3e MC |
247 | { |
248 | BN_ULONG *A, *a = NULL; | |
249 | const BN_ULONG *B; | |
250 | int i; | |
251 | ||
252 | bn_check_top(b); | |
253 | ||
254 | if (words > (INT_MAX / (4 * BN_BITS2))) { | |
255 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); | |
256 | return NULL; | |
257 | } | |
258 | if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { | |
259 | BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); | |
260 | return (NULL); | |
261 | } | |
74924dcb | 262 | if (BN_get_flags(b,BN_FLG_SECURE)) |
d8ca44ba | 263 | a = A = OPENSSL_secure_zalloc(words * sizeof(*a)); |
74924dcb | 264 | else |
d8ca44ba | 265 | a = A = OPENSSL_zalloc(words * sizeof(*a)); |
0f113f3e MC |
266 | if (A == NULL) { |
267 | BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); | |
268 | return (NULL); | |
269 | } | |
f8571ce8 | 270 | |
dfeab068 | 271 | #if 1 |
0f113f3e MC |
272 | B = b->d; |
273 | /* Check if the previous number needs to be copied */ | |
274 | if (B != NULL) { | |
275 | for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { | |
276 | /* | |
277 | * The fact that the loop is unrolled | |
278 | * 4-wise is a tribute to Intel. It's | |
279 | * the one that doesn't have enough | |
0d4fb843 | 280 | * registers to accommodate more data. |
0f113f3e MC |
281 | * I'd unroll it 8-wise otherwise:-) |
282 | * | |
283 | * <appro@fy.chalmers.se> | |
284 | */ | |
285 | BN_ULONG a0, a1, a2, a3; | |
286 | a0 = B[0]; | |
287 | a1 = B[1]; | |
288 | a2 = B[2]; | |
289 | a3 = B[3]; | |
290 | A[0] = a0; | |
291 | A[1] = a1; | |
292 | A[2] = a2; | |
293 | A[3] = a3; | |
294 | } | |
0f113f3e MC |
295 | switch (b->top & 3) { |
296 | case 3: | |
297 | A[2] = B[2]; | |
298 | case 2: | |
299 | A[1] = B[1]; | |
300 | case 1: | |
301 | A[0] = B[0]; | |
302 | case 0: | |
23d38992 | 303 | /* Without the "case 0" some old optimizers got this wrong. */ |
0f113f3e MC |
304 | ; |
305 | } | |
306 | } | |
dfeab068 | 307 | #else |
16f8d4eb | 308 | memset(A, 0, sizeof(*A) * words); |
0f113f3e | 309 | memcpy(A, b->d, sizeof(b->d[0]) * b->top); |
dfeab068 | 310 | #endif |
dfeab068 | 311 | |
0f113f3e MC |
312 | return (a); |
313 | } | |
314 | ||
315 | /* | |
316 | * This is an internal function that should not be used in applications. It | |
317 | * ensures that 'b' has enough room for a 'words' word number and initialises | |
318 | * any unused part of b->d with leading zeros. It is mostly used by the | |
319 | * various BIGNUM routines. If there is an error, NULL is returned. If not, | |
320 | * 'b' is returned. | |
321 | */ | |
020fc820 | 322 | |
6343829a | 323 | BIGNUM *bn_expand2(BIGNUM *b, int words) |
0f113f3e MC |
324 | { |
325 | bn_check_top(b); | |
326 | ||
327 | if (words > b->dmax) { | |
328 | BN_ULONG *a = bn_expand_internal(b, words); | |
329 | if (!a) | |
330 | return NULL; | |
74924dcb | 331 | if (b->d) { |
9f040d6d RS |
332 | OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0])); |
333 | bn_free_d(b); | |
74924dcb | 334 | } |
0f113f3e MC |
335 | b->d = a; |
336 | b->dmax = words; | |
337 | } | |
2bfd2c74 | 338 | |
0f113f3e MC |
339 | bn_check_top(b); |
340 | return b; | |
341 | } | |
d02b48c6 | 342 | |
84c15db5 | 343 | BIGNUM *BN_dup(const BIGNUM *a) |
0f113f3e MC |
344 | { |
345 | BIGNUM *t; | |
346 | ||
347 | if (a == NULL) | |
348 | return NULL; | |
349 | bn_check_top(a); | |
350 | ||
74924dcb | 351 | t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new(); |
0f113f3e MC |
352 | if (t == NULL) |
353 | return NULL; | |
354 | if (!BN_copy(t, a)) { | |
355 | BN_free(t); | |
356 | return NULL; | |
357 | } | |
358 | bn_check_top(t); | |
359 | return t; | |
360 | } | |
d02b48c6 | 361 | |
84c15db5 | 362 | BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
363 | { |
364 | int i; | |
365 | BN_ULONG *A; | |
366 | const BN_ULONG *B; | |
58964a49 | 367 | |
0f113f3e | 368 | bn_check_top(b); |
dfeab068 | 369 | |
0f113f3e MC |
370 | if (a == b) |
371 | return (a); | |
372 | if (bn_wexpand(a, b->top) == NULL) | |
373 | return (NULL); | |
58964a49 RE |
374 | |
375 | #if 1 | |
0f113f3e MC |
376 | A = a->d; |
377 | B = b->d; | |
378 | for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { | |
379 | BN_ULONG a0, a1, a2, a3; | |
380 | a0 = B[0]; | |
381 | a1 = B[1]; | |
382 | a2 = B[2]; | |
383 | a3 = B[3]; | |
384 | A[0] = a0; | |
385 | A[1] = a1; | |
386 | A[2] = a2; | |
387 | A[3] = a3; | |
388 | } | |
389 | /* ultrix cc workaround, see comments in bn_expand_internal */ | |
390 | switch (b->top & 3) { | |
391 | case 3: | |
392 | A[2] = B[2]; | |
393 | case 2: | |
394 | A[1] = B[1]; | |
395 | case 1: | |
396 | A[0] = B[0]; | |
397 | case 0:; | |
398 | } | |
58964a49 | 399 | #else |
0f113f3e | 400 | memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); |
58964a49 RE |
401 | #endif |
402 | ||
0f113f3e MC |
403 | a->top = b->top; |
404 | a->neg = b->neg; | |
405 | bn_check_top(a); | |
406 | return (a); | |
407 | } | |
d02b48c6 | 408 | |
78a0c1f1 | 409 | void BN_swap(BIGNUM *a, BIGNUM *b) |
0f113f3e MC |
410 | { |
411 | int flags_old_a, flags_old_b; | |
412 | BN_ULONG *tmp_d; | |
413 | int tmp_top, tmp_dmax, tmp_neg; | |
414 | ||
415 | bn_check_top(a); | |
416 | bn_check_top(b); | |
417 | ||
418 | flags_old_a = a->flags; | |
419 | flags_old_b = b->flags; | |
420 | ||
421 | tmp_d = a->d; | |
422 | tmp_top = a->top; | |
423 | tmp_dmax = a->dmax; | |
424 | tmp_neg = a->neg; | |
425 | ||
426 | a->d = b->d; | |
427 | a->top = b->top; | |
428 | a->dmax = b->dmax; | |
429 | a->neg = b->neg; | |
430 | ||
431 | b->d = tmp_d; | |
432 | b->top = tmp_top; | |
433 | b->dmax = tmp_dmax; | |
434 | b->neg = tmp_neg; | |
435 | ||
436 | a->flags = | |
437 | (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); | |
438 | b->flags = | |
439 | (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); | |
440 | bn_check_top(a); | |
441 | bn_check_top(b); | |
442 | } | |
78a0c1f1 | 443 | |
6b691a5c | 444 | void BN_clear(BIGNUM *a) |
0f113f3e MC |
445 | { |
446 | bn_check_top(a); | |
447 | if (a->d != NULL) | |
16f8d4eb | 448 | memset(a->d, 0, sizeof(*a->d) * a->dmax); |
0f113f3e MC |
449 | a->top = 0; |
450 | a->neg = 0; | |
451 | } | |
d02b48c6 | 452 | |
020fc820 | 453 | BN_ULONG BN_get_word(const BIGNUM *a) |
0f113f3e MC |
454 | { |
455 | if (a->top > 1) | |
456 | return BN_MASK2; | |
457 | else if (a->top == 1) | |
458 | return a->d[0]; | |
459 | /* a->top == 0 */ | |
460 | return 0; | |
461 | } | |
d02b48c6 | 462 | |
e042540f | 463 | int BN_set_word(BIGNUM *a, BN_ULONG w) |
0f113f3e MC |
464 | { |
465 | bn_check_top(a); | |
466 | if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) | |
467 | return (0); | |
468 | a->neg = 0; | |
469 | a->d[0] = w; | |
470 | a->top = (w ? 1 : 0); | |
471 | bn_check_top(a); | |
472 | return (1); | |
473 | } | |
d02b48c6 | 474 | |
6343829a | 475 | BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) |
0f113f3e MC |
476 | { |
477 | unsigned int i, m; | |
478 | unsigned int n; | |
479 | BN_ULONG l; | |
480 | BIGNUM *bn = NULL; | |
481 | ||
482 | if (ret == NULL) | |
483 | ret = bn = BN_new(); | |
484 | if (ret == NULL) | |
485 | return (NULL); | |
486 | bn_check_top(ret); | |
22dc08d0 | 487 | /* Skip leading zero's. */ |
3c65047d | 488 | for ( ; len > 0 && *s == 0; s++, len--) |
22dc08d0 | 489 | continue; |
0f113f3e MC |
490 | n = len; |
491 | if (n == 0) { | |
492 | ret->top = 0; | |
493 | return (ret); | |
494 | } | |
495 | i = ((n - 1) / BN_BYTES) + 1; | |
496 | m = ((n - 1) % (BN_BYTES)); | |
497 | if (bn_wexpand(ret, (int)i) == NULL) { | |
23a1d5e9 | 498 | BN_free(bn); |
0f113f3e MC |
499 | return NULL; |
500 | } | |
501 | ret->top = i; | |
502 | ret->neg = 0; | |
22dc08d0 | 503 | l = 0; |
0f113f3e MC |
504 | while (n--) { |
505 | l = (l << 8L) | *(s++); | |
506 | if (m-- == 0) { | |
507 | ret->d[--i] = l; | |
508 | l = 0; | |
509 | m = BN_BYTES - 1; | |
510 | } | |
511 | } | |
512 | /* | |
513 | * need to call this due to clear byte at top if avoiding having the top | |
514 | * bit set (-ve number) | |
515 | */ | |
516 | bn_correct_top(ret); | |
517 | return (ret); | |
518 | } | |
d02b48c6 RE |
519 | |
520 | /* ignore negative */ | |
85a4807f | 521 | static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) |
0f113f3e | 522 | { |
85a4807f | 523 | int i; |
0f113f3e MC |
524 | BN_ULONG l; |
525 | ||
526 | bn_check_top(a); | |
85a4807f DSH |
527 | i = BN_num_bytes(a); |
528 | if (tolen == -1) | |
529 | tolen = i; | |
530 | else if (tolen < i) | |
531 | return -1; | |
532 | /* Add leading zeroes if necessary */ | |
533 | if (tolen > i) { | |
534 | memset(to, 0, tolen - i); | |
535 | to += tolen - i; | |
536 | } | |
0f113f3e MC |
537 | while (i--) { |
538 | l = a->d[i / BN_BYTES]; | |
539 | *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; | |
540 | } | |
85a4807f DSH |
541 | return tolen; |
542 | } | |
543 | ||
544 | int BN_bn2binpad(const BIGNUM *a, unsigned char *to, int tolen) | |
545 | { | |
546 | if (tolen < 0) | |
547 | return -1; | |
548 | return bn2binpad(a, to, tolen); | |
549 | } | |
550 | ||
551 | int BN_bn2bin(const BIGNUM *a, unsigned char *to) | |
552 | { | |
553 | return bn2binpad(a, to, -1); | |
554 | } | |
555 | ||
556 | BIGNUM *BN_lebin2bn(const unsigned char *s, int len, BIGNUM *ret) | |
557 | { | |
558 | unsigned int i, m; | |
559 | unsigned int n; | |
560 | BN_ULONG l; | |
561 | BIGNUM *bn = NULL; | |
562 | ||
563 | if (ret == NULL) | |
564 | ret = bn = BN_new(); | |
565 | if (ret == NULL) | |
566 | return (NULL); | |
567 | bn_check_top(ret); | |
568 | s += len - 1; | |
569 | /* Skip trailing zeroes. */ | |
570 | for ( ; len > 0 && *s == 0; s--, len--) | |
571 | continue; | |
572 | n = len; | |
573 | if (n == 0) { | |
574 | ret->top = 0; | |
575 | return ret; | |
576 | } | |
577 | i = ((n - 1) / BN_BYTES) + 1; | |
578 | m = ((n - 1) % (BN_BYTES)); | |
579 | if (bn_wexpand(ret, (int)i) == NULL) { | |
580 | BN_free(bn); | |
581 | return NULL; | |
582 | } | |
583 | ret->top = i; | |
584 | ret->neg = 0; | |
585 | l = 0; | |
586 | while (n--) { | |
587 | l = (l << 8L) | *(s--); | |
588 | if (m-- == 0) { | |
589 | ret->d[--i] = l; | |
590 | l = 0; | |
591 | m = BN_BYTES - 1; | |
592 | } | |
593 | } | |
594 | /* | |
595 | * need to call this due to clear byte at top if avoiding having the top | |
596 | * bit set (-ve number) | |
597 | */ | |
598 | bn_correct_top(ret); | |
599 | return ret; | |
600 | } | |
601 | ||
602 | int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen) | |
603 | { | |
604 | int i; | |
605 | BN_ULONG l; | |
606 | bn_check_top(a); | |
607 | i = BN_num_bytes(a); | |
608 | if (tolen < i) | |
609 | return -1; | |
610 | /* Add trailing zeroes if necessary */ | |
611 | if (tolen > i) | |
612 | memset(to + i, 0, tolen - i); | |
613 | to += i - 1; | |
614 | while (i--) { | |
615 | l = a->d[i / BN_BYTES]; | |
616 | *(to--) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; | |
617 | } | |
618 | return tolen; | |
0f113f3e | 619 | } |
d02b48c6 | 620 | |
84c15db5 | 621 | int BN_ucmp(const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
622 | { |
623 | int i; | |
624 | BN_ULONG t1, t2, *ap, *bp; | |
625 | ||
626 | bn_check_top(a); | |
627 | bn_check_top(b); | |
628 | ||
629 | i = a->top - b->top; | |
630 | if (i != 0) | |
631 | return (i); | |
632 | ap = a->d; | |
633 | bp = b->d; | |
634 | for (i = a->top - 1; i >= 0; i--) { | |
635 | t1 = ap[i]; | |
636 | t2 = bp[i]; | |
637 | if (t1 != t2) | |
638 | return ((t1 > t2) ? 1 : -1); | |
639 | } | |
640 | return (0); | |
641 | } | |
d02b48c6 | 642 | |
84c15db5 | 643 | int BN_cmp(const BIGNUM *a, const BIGNUM *b) |
0f113f3e MC |
644 | { |
645 | int i; | |
646 | int gt, lt; | |
647 | BN_ULONG t1, t2; | |
648 | ||
649 | if ((a == NULL) || (b == NULL)) { | |
650 | if (a != NULL) | |
651 | return (-1); | |
652 | else if (b != NULL) | |
653 | return (1); | |
654 | else | |
655 | return (0); | |
656 | } | |
657 | ||
658 | bn_check_top(a); | |
659 | bn_check_top(b); | |
660 | ||
661 | if (a->neg != b->neg) { | |
662 | if (a->neg) | |
663 | return (-1); | |
664 | else | |
665 | return (1); | |
666 | } | |
667 | if (a->neg == 0) { | |
668 | gt = 1; | |
669 | lt = -1; | |
670 | } else { | |
671 | gt = -1; | |
672 | lt = 1; | |
673 | } | |
674 | ||
675 | if (a->top > b->top) | |
676 | return (gt); | |
677 | if (a->top < b->top) | |
678 | return (lt); | |
679 | for (i = a->top - 1; i >= 0; i--) { | |
680 | t1 = a->d[i]; | |
681 | t2 = b->d[i]; | |
682 | if (t1 > t2) | |
683 | return (gt); | |
684 | if (t1 < t2) | |
685 | return (lt); | |
686 | } | |
687 | return (0); | |
688 | } | |
d02b48c6 | 689 | |
6b691a5c | 690 | int BN_set_bit(BIGNUM *a, int n) |
0f113f3e MC |
691 | { |
692 | int i, j, k; | |
693 | ||
694 | if (n < 0) | |
695 | return 0; | |
696 | ||
697 | i = n / BN_BITS2; | |
698 | j = n % BN_BITS2; | |
699 | if (a->top <= i) { | |
700 | if (bn_wexpand(a, i + 1) == NULL) | |
701 | return (0); | |
702 | for (k = a->top; k < i + 1; k++) | |
703 | a->d[k] = 0; | |
704 | a->top = i + 1; | |
705 | } | |
706 | ||
707 | a->d[i] |= (((BN_ULONG)1) << j); | |
708 | bn_check_top(a); | |
709 | return (1); | |
710 | } | |
d02b48c6 | 711 | |
6b691a5c | 712 | int BN_clear_bit(BIGNUM *a, int n) |
0f113f3e MC |
713 | { |
714 | int i, j; | |
d02b48c6 | 715 | |
0f113f3e MC |
716 | bn_check_top(a); |
717 | if (n < 0) | |
718 | return 0; | |
1a017330 | 719 | |
0f113f3e MC |
720 | i = n / BN_BITS2; |
721 | j = n % BN_BITS2; | |
722 | if (a->top <= i) | |
723 | return (0); | |
d02b48c6 | 724 | |
0f113f3e MC |
725 | a->d[i] &= (~(((BN_ULONG)1) << j)); |
726 | bn_correct_top(a); | |
727 | return (1); | |
728 | } | |
d02b48c6 | 729 | |
84c15db5 | 730 | int BN_is_bit_set(const BIGNUM *a, int n) |
0f113f3e MC |
731 | { |
732 | int i, j; | |
733 | ||
734 | bn_check_top(a); | |
735 | if (n < 0) | |
736 | return 0; | |
737 | i = n / BN_BITS2; | |
738 | j = n % BN_BITS2; | |
739 | if (a->top <= i) | |
740 | return 0; | |
741 | return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); | |
742 | } | |
d02b48c6 | 743 | |
6b691a5c | 744 | int BN_mask_bits(BIGNUM *a, int n) |
0f113f3e MC |
745 | { |
746 | int b, w; | |
747 | ||
748 | bn_check_top(a); | |
749 | if (n < 0) | |
750 | return 0; | |
751 | ||
752 | w = n / BN_BITS2; | |
753 | b = n % BN_BITS2; | |
754 | if (w >= a->top) | |
755 | return 0; | |
756 | if (b == 0) | |
757 | a->top = w; | |
758 | else { | |
759 | a->top = w + 1; | |
760 | a->d[w] &= ~(BN_MASK2 << b); | |
761 | } | |
762 | bn_correct_top(a); | |
763 | return (1); | |
764 | } | |
dfeab068 | 765 | |
ff22e913 | 766 | void BN_set_negative(BIGNUM *a, int b) |
0f113f3e MC |
767 | { |
768 | if (b && !BN_is_zero(a)) | |
769 | a->neg = 1; | |
770 | else | |
771 | a->neg = 0; | |
772 | } | |
ff22e913 | 773 | |
cbd48ba6 | 774 | int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) |
0f113f3e MC |
775 | { |
776 | int i; | |
777 | BN_ULONG aa, bb; | |
778 | ||
779 | aa = a[n - 1]; | |
780 | bb = b[n - 1]; | |
781 | if (aa != bb) | |
782 | return ((aa > bb) ? 1 : -1); | |
783 | for (i = n - 2; i >= 0; i--) { | |
784 | aa = a[i]; | |
785 | bb = b[i]; | |
786 | if (aa != bb) | |
787 | return ((aa > bb) ? 1 : -1); | |
788 | } | |
789 | return (0); | |
790 | } | |
791 | ||
792 | /* | |
793 | * Here follows a specialised variants of bn_cmp_words(). It has the | |
399de496 | 794 | * capability of performing the operation on arrays of different sizes. The |
0f113f3e | 795 | * sizes of those arrays is expressed through cl, which is the common length |
399de496 | 796 | * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the |
0f113f3e MC |
797 | * two lengths, calculated as len(a)-len(b). All lengths are the number of |
798 | * BN_ULONGs... | |
799 | */ | |
800 | ||
801 | int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) | |
802 | { | |
803 | int n, i; | |
804 | n = cl - 1; | |
805 | ||
806 | if (dl < 0) { | |
807 | for (i = dl; i < 0; i++) { | |
808 | if (b[n - i] != 0) | |
809 | return -1; /* a < b */ | |
810 | } | |
811 | } | |
812 | if (dl > 0) { | |
813 | for (i = dl; i > 0; i--) { | |
814 | if (a[n + i] != 0) | |
815 | return 1; /* a > b */ | |
816 | } | |
817 | } | |
818 | return bn_cmp_words(a, b, cl); | |
819 | } | |
820 | ||
821 | /* | |
822 | * Constant-time conditional swap of a and b. | |
f9b6c0ba DSH |
823 | * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. |
824 | * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, | |
825 | * and that no more than nwords are used by either a or b. | |
826 | * a and b cannot be the same number | |
827 | */ | |
828 | void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) | |
0f113f3e MC |
829 | { |
830 | BN_ULONG t; | |
831 | int i; | |
f9b6c0ba | 832 | |
0f113f3e MC |
833 | bn_wcheck_size(a, nwords); |
834 | bn_wcheck_size(b, nwords); | |
f9b6c0ba | 835 | |
0f113f3e MC |
836 | assert(a != b); |
837 | assert((condition & (condition - 1)) == 0); | |
838 | assert(sizeof(BN_ULONG) >= sizeof(int)); | |
f9b6c0ba | 839 | |
0f113f3e | 840 | condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; |
f9b6c0ba | 841 | |
0f113f3e MC |
842 | t = (a->top ^ b->top) & condition; |
843 | a->top ^= t; | |
844 | b->top ^= t; | |
f9b6c0ba DSH |
845 | |
846 | #define BN_CONSTTIME_SWAP(ind) \ | |
0f113f3e MC |
847 | do { \ |
848 | t = (a->d[ind] ^ b->d[ind]) & condition; \ | |
849 | a->d[ind] ^= t; \ | |
850 | b->d[ind] ^= t; \ | |
851 | } while (0) | |
852 | ||
853 | switch (nwords) { | |
854 | default: | |
855 | for (i = 10; i < nwords; i++) | |
856 | BN_CONSTTIME_SWAP(i); | |
857 | /* Fallthrough */ | |
858 | case 10: | |
859 | BN_CONSTTIME_SWAP(9); /* Fallthrough */ | |
860 | case 9: | |
861 | BN_CONSTTIME_SWAP(8); /* Fallthrough */ | |
862 | case 8: | |
863 | BN_CONSTTIME_SWAP(7); /* Fallthrough */ | |
864 | case 7: | |
865 | BN_CONSTTIME_SWAP(6); /* Fallthrough */ | |
866 | case 6: | |
867 | BN_CONSTTIME_SWAP(5); /* Fallthrough */ | |
868 | case 5: | |
869 | BN_CONSTTIME_SWAP(4); /* Fallthrough */ | |
870 | case 4: | |
871 | BN_CONSTTIME_SWAP(3); /* Fallthrough */ | |
872 | case 3: | |
873 | BN_CONSTTIME_SWAP(2); /* Fallthrough */ | |
874 | case 2: | |
875 | BN_CONSTTIME_SWAP(1); /* Fallthrough */ | |
876 | case 1: | |
877 | BN_CONSTTIME_SWAP(0); | |
878 | } | |
f9b6c0ba DSH |
879 | #undef BN_CONSTTIME_SWAP |
880 | } | |
2514fa79 DSH |
881 | |
882 | /* Bits of security, see SP800-57 */ | |
883 | ||
884 | int BN_security_bits(int L, int N) | |
0f113f3e MC |
885 | { |
886 | int secbits, bits; | |
887 | if (L >= 15360) | |
888 | secbits = 256; | |
889 | else if (L >= 7690) | |
890 | secbits = 192; | |
891 | else if (L >= 3072) | |
892 | secbits = 128; | |
893 | else if (L >= 2048) | |
894 | secbits = 112; | |
895 | else if (L >= 1024) | |
896 | secbits = 80; | |
897 | else | |
898 | return 0; | |
899 | if (N == -1) | |
900 | return secbits; | |
901 | bits = N / 2; | |
902 | if (bits < 80) | |
903 | return 0; | |
904 | return bits >= secbits ? secbits : bits; | |
905 | } | |
85bcf27c MC |
906 | |
907 | void BN_zero_ex(BIGNUM *a) | |
0f113f3e MC |
908 | { |
909 | a->top = 0; | |
910 | a->neg = 0; | |
911 | } | |
85bcf27c MC |
912 | |
913 | int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w) | |
0f113f3e MC |
914 | { |
915 | return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0)); | |
916 | } | |
85bcf27c MC |
917 | |
918 | int BN_is_zero(const BIGNUM *a) | |
0f113f3e MC |
919 | { |
920 | return a->top == 0; | |
921 | } | |
85bcf27c MC |
922 | |
923 | int BN_is_one(const BIGNUM *a) | |
0f113f3e MC |
924 | { |
925 | return BN_abs_is_word(a, 1) && !a->neg; | |
926 | } | |
85bcf27c MC |
927 | |
928 | int BN_is_word(const BIGNUM *a, const BN_ULONG w) | |
0f113f3e MC |
929 | { |
930 | return BN_abs_is_word(a, w) && (!w || !a->neg); | |
931 | } | |
85bcf27c MC |
932 | |
933 | int BN_is_odd(const BIGNUM *a) | |
0f113f3e MC |
934 | { |
935 | return (a->top > 0) && (a->d[0] & 1); | |
936 | } | |
85bcf27c MC |
937 | |
938 | int BN_is_negative(const BIGNUM *a) | |
0f113f3e MC |
939 | { |
940 | return (a->neg != 0); | |
941 | } | |
85bcf27c | 942 | |
0f113f3e MC |
943 | int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont, |
944 | BN_CTX *ctx) | |
945 | { | |
946 | return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx); | |
947 | } | |
85bcf27c | 948 | |
fd7d2520 | 949 | void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags) |
0f113f3e MC |
950 | { |
951 | dest->d = b->d; | |
952 | dest->top = b->top; | |
953 | dest->dmax = b->dmax; | |
954 | dest->neg = b->neg; | |
955 | dest->flags = ((dest->flags & BN_FLG_MALLOCED) | |
956 | | (b->flags & ~BN_FLG_MALLOCED) | |
fd7d2520 | 957 | | BN_FLG_STATIC_DATA | flags); |
0f113f3e | 958 | } |
85bcf27c MC |
959 | |
960 | BN_GENCB *BN_GENCB_new(void) | |
0f113f3e MC |
961 | { |
962 | BN_GENCB *ret; | |
85bcf27c | 963 | |
b4faea50 | 964 | if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) { |
0f113f3e MC |
965 | BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE); |
966 | return (NULL); | |
967 | } | |
85bcf27c | 968 | |
0f113f3e MC |
969 | return ret; |
970 | } | |
85bcf27c MC |
971 | |
972 | void BN_GENCB_free(BN_GENCB *cb) | |
0f113f3e MC |
973 | { |
974 | if (cb == NULL) | |
975 | return; | |
976 | OPENSSL_free(cb); | |
977 | } | |
85bcf27c MC |
978 | |
979 | void BN_set_flags(BIGNUM *b, int n) | |
0f113f3e MC |
980 | { |
981 | b->flags |= n; | |
982 | } | |
85bcf27c MC |
983 | |
984 | int BN_get_flags(const BIGNUM *b, int n) | |
0f113f3e MC |
985 | { |
986 | return b->flags & n; | |
987 | } | |
85bcf27c MC |
988 | |
989 | /* Populate a BN_GENCB structure with an "old"-style callback */ | |
0f113f3e MC |
990 | void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *), |
991 | void *cb_arg) | |
992 | { | |
993 | BN_GENCB *tmp_gencb = gencb; | |
994 | tmp_gencb->ver = 1; | |
995 | tmp_gencb->arg = cb_arg; | |
996 | tmp_gencb->cb.cb_1 = callback; | |
997 | } | |
85bcf27c MC |
998 | |
999 | /* Populate a BN_GENCB structure with a "new"-style callback */ | |
0f113f3e MC |
1000 | void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *), |
1001 | void *cb_arg) | |
1002 | { | |
1003 | BN_GENCB *tmp_gencb = gencb; | |
1004 | tmp_gencb->ver = 2; | |
1005 | tmp_gencb->arg = cb_arg; | |
1006 | tmp_gencb->cb.cb_2 = callback; | |
1007 | } | |
85bcf27c MC |
1008 | |
1009 | void *BN_GENCB_get_arg(BN_GENCB *cb) | |
0f113f3e MC |
1010 | { |
1011 | return cb->arg; | |
1012 | } | |
85bcf27c MC |
1013 | |
1014 | BIGNUM *bn_wexpand(BIGNUM *a, int words) | |
0f113f3e MC |
1015 | { |
1016 | return (words <= a->dmax) ? a : bn_expand2(a, words); | |
1017 | } | |
85bcf27c MC |
1018 | |
1019 | void bn_correct_top(BIGNUM *a) | |
0f113f3e MC |
1020 | { |
1021 | BN_ULONG *ftl; | |
1022 | int tmp_top = a->top; | |
1023 | ||
1024 | if (tmp_top > 0) { | |
1025 | for (ftl = &(a->d[tmp_top - 1]); tmp_top > 0; tmp_top--) | |
1026 | if (*(ftl--)) | |
1027 | break; | |
1028 | a->top = tmp_top; | |
1029 | } | |
1030 | bn_pollute(a); | |
1031 | } |