1 | /*
|
---|
2 | * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved.
|
---|
3 | *
|
---|
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
|
---|
8 | */
|
---|
9 |
|
---|
10 | #include <assert.h>
|
---|
11 | #include <limits.h>
|
---|
12 | #include "internal/cryptlib.h"
|
---|
13 | #include "bn_lcl.h"
|
---|
14 | #include <openssl/opensslconf.h>
|
---|
15 |
|
---|
16 | /* This stuff appears to be completely unused, so is deprecated */
|
---|
17 | #if OPENSSL_API_COMPAT < 0x00908000L
|
---|
18 | /*-
|
---|
19 | * For a 32 bit machine
|
---|
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 | */
|
---|
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) */
|
---|
36 |
|
---|
37 | void BN_set_params(int mult, int high, int low, int mont)
|
---|
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 | }
|
---|
64 |
|
---|
65 | int BN_get_params(int which)
|
---|
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 | }
|
---|
78 | #endif
|
---|
79 |
|
---|
80 | const BIGNUM *BN_value_one(void)
|
---|
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 };
|
---|
85 |
|
---|
86 | return (&const_one);
|
---|
87 | }
|
---|
88 |
|
---|
89 | int BN_num_bits_word(BN_ULONG l)
|
---|
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 | };
|
---|
109 |
|
---|
110 | #if defined(SIXTY_FOUR_BIT_LONG)
|
---|
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
|
---|
124 | #else
|
---|
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
|
---|
140 | #endif
|
---|
141 | {
|
---|
142 | #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
|
---|
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
|
---|
149 | #endif
|
---|
150 | {
|
---|
151 | #if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG)
|
---|
152 | if (l & 0xff00L)
|
---|
153 | return (bits[(int)(l >> 8)] + 8);
|
---|
154 | else
|
---|
155 | #endif
|
---|
156 | return (bits[(int)(l)]);
|
---|
157 | }
|
---|
158 | }
|
---|
159 | }
|
---|
160 |
|
---|
161 | int BN_num_bits(const BIGNUM *a)
|
---|
162 | {
|
---|
163 | int i = a->top - 1;
|
---|
164 | bn_check_top(a);
|
---|
165 |
|
---|
166 | if (BN_is_zero(a))
|
---|
167 | return 0;
|
---|
168 | return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
|
---|
169 | }
|
---|
170 |
|
---|
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 |
|
---|
180 | void BN_clear_free(BIGNUM *a)
|
---|
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]));
|
---|
189 | if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
|
---|
190 | bn_free_d(a);
|
---|
191 | }
|
---|
192 | i = BN_get_flags(a, BN_FLG_MALLOCED);
|
---|
193 | OPENSSL_cleanse(a, sizeof(*a));
|
---|
194 | if (i)
|
---|
195 | OPENSSL_free(a);
|
---|
196 | }
|
---|
197 |
|
---|
198 | void BN_free(BIGNUM *a)
|
---|
199 | {
|
---|
200 | if (a == NULL)
|
---|
201 | return;
|
---|
202 | bn_check_top(a);
|
---|
203 | if (!BN_get_flags(a, BN_FLG_STATIC_DATA))
|
---|
204 | bn_free_d(a);
|
---|
205 | if (a->flags & BN_FLG_MALLOCED)
|
---|
206 | OPENSSL_free(a);
|
---|
207 | else {
|
---|
208 | #if OPENSSL_API_COMPAT < 0x00908000L
|
---|
209 | a->flags |= BN_FLG_FREE;
|
---|
210 | #endif
|
---|
211 | a->d = NULL;
|
---|
212 | }
|
---|
213 | }
|
---|
214 |
|
---|
215 | void bn_init(BIGNUM *a)
|
---|
216 | {
|
---|
217 | static BIGNUM nilbn;
|
---|
218 |
|
---|
219 | *a = nilbn;
|
---|
220 | bn_check_top(a);
|
---|
221 | }
|
---|
222 |
|
---|
223 | BIGNUM *BN_new(void)
|
---|
224 | {
|
---|
225 | BIGNUM *ret;
|
---|
226 |
|
---|
227 | if ((ret = OPENSSL_zalloc(sizeof(*ret))) == NULL) {
|
---|
228 | BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
|
---|
229 | return (NULL);
|
---|
230 | }
|
---|
231 | ret->flags = BN_FLG_MALLOCED;
|
---|
232 | bn_check_top(ret);
|
---|
233 | return (ret);
|
---|
234 | }
|
---|
235 |
|
---|
236 | BIGNUM *BN_secure_new(void)
|
---|
237 | {
|
---|
238 | BIGNUM *ret = BN_new();
|
---|
239 | if (ret != NULL)
|
---|
240 | ret->flags |= BN_FLG_SECURE;
|
---|
241 | return (ret);
|
---|
242 | }
|
---|
243 |
|
---|
244 | /* This is used by bn_expand2() */
|
---|
245 | /* The caller MUST check that words > b->dmax before calling this */
|
---|
246 | static BN_ULONG *bn_expand_internal(const BIGNUM *b, int words)
|
---|
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 | }
|
---|
262 | if (BN_get_flags(b, BN_FLG_SECURE))
|
---|
263 | a = A = OPENSSL_secure_zalloc(words * sizeof(*a));
|
---|
264 | else
|
---|
265 | a = A = OPENSSL_zalloc(words * sizeof(*a));
|
---|
266 | if (A == NULL) {
|
---|
267 | BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
|
---|
268 | return (NULL);
|
---|
269 | }
|
---|
270 |
|
---|
271 | #if 1
|
---|
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
|
---|
280 | * registers to accommodate more data.
|
---|
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 | }
|
---|
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:
|
---|
303 | /* Without the "case 0" some old optimizers got this wrong. */
|
---|
304 | ;
|
---|
305 | }
|
---|
306 | }
|
---|
307 | #else
|
---|
308 | memset(A, 0, sizeof(*A) * words);
|
---|
309 | memcpy(A, b->d, sizeof(b->d[0]) * b->top);
|
---|
310 | #endif
|
---|
311 |
|
---|
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 | */
|
---|
322 |
|
---|
323 | BIGNUM *bn_expand2(BIGNUM *b, int words)
|
---|
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;
|
---|
331 | if (b->d) {
|
---|
332 | OPENSSL_cleanse(b->d, b->dmax * sizeof(b->d[0]));
|
---|
333 | bn_free_d(b);
|
---|
334 | }
|
---|
335 | b->d = a;
|
---|
336 | b->dmax = words;
|
---|
337 | }
|
---|
338 |
|
---|
339 | bn_check_top(b);
|
---|
340 | return b;
|
---|
341 | }
|
---|
342 |
|
---|
343 | BIGNUM *BN_dup(const BIGNUM *a)
|
---|
344 | {
|
---|
345 | BIGNUM *t;
|
---|
346 |
|
---|
347 | if (a == NULL)
|
---|
348 | return NULL;
|
---|
349 | bn_check_top(a);
|
---|
350 |
|
---|
351 | t = BN_get_flags(a, BN_FLG_SECURE) ? BN_secure_new() : BN_new();
|
---|
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 | }
|
---|
361 |
|
---|
362 | BIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b)
|
---|
363 | {
|
---|
364 | int i;
|
---|
365 | BN_ULONG *A;
|
---|
366 | const BN_ULONG *B;
|
---|
367 |
|
---|
368 | bn_check_top(b);
|
---|
369 |
|
---|
370 | if (a == b)
|
---|
371 | return (a);
|
---|
372 | if (bn_wexpand(a, b->top) == NULL)
|
---|
373 | return (NULL);
|
---|
374 |
|
---|
375 | #if 1
|
---|
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 | }
|
---|
399 | #else
|
---|
400 | memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
|
---|
401 | #endif
|
---|
402 |
|
---|
403 | a->top = b->top;
|
---|
404 | a->neg = b->neg;
|
---|
405 | bn_check_top(a);
|
---|
406 | return (a);
|
---|
407 | }
|
---|
408 |
|
---|
409 | void BN_swap(BIGNUM *a, BIGNUM *b)
|
---|
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 | }
|
---|
443 |
|
---|
444 | void BN_clear(BIGNUM *a)
|
---|
445 | {
|
---|
446 | bn_check_top(a);
|
---|
447 | if (a->d != NULL)
|
---|
448 | OPENSSL_cleanse(a->d, sizeof(*a->d) * a->dmax);
|
---|
449 | a->top = 0;
|
---|
450 | a->neg = 0;
|
---|
451 | }
|
---|
452 |
|
---|
453 | BN_ULONG BN_get_word(const BIGNUM *a)
|
---|
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 | }
|
---|
462 |
|
---|
463 | int BN_set_word(BIGNUM *a, BN_ULONG w)
|
---|
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 | }
|
---|
474 |
|
---|
475 | BIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
|
---|
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);
|
---|
487 | /* Skip leading zero's. */
|
---|
488 | for ( ; len > 0 && *s == 0; s++, len--)
|
---|
489 | continue;
|
---|
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) {
|
---|
498 | BN_free(bn);
|
---|
499 | return NULL;
|
---|
500 | }
|
---|
501 | ret->top = i;
|
---|
502 | ret->neg = 0;
|
---|
503 | l = 0;
|
---|
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 | }
|
---|
519 |
|
---|
520 | /* ignore negative */
|
---|
521 | static int bn2binpad(const BIGNUM *a, unsigned char *to, int tolen)
|
---|
522 | {
|
---|
523 | int i;
|
---|
524 | BN_ULONG l;
|
---|
525 |
|
---|
526 | bn_check_top(a);
|
---|
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 | }
|
---|
537 | while (i--) {
|
---|
538 | l = a->d[i / BN_BYTES];
|
---|
539 | *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
|
---|
540 | }
|
---|
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;
|
---|
569 | /* Skip trailing zeroes. */
|
---|
570 | for ( ; len > 0 && s[-1] == 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 | s--;
|
---|
588 | l = (l << 8L) | *s;
|
---|
589 | if (m-- == 0) {
|
---|
590 | ret->d[--i] = l;
|
---|
591 | l = 0;
|
---|
592 | m = BN_BYTES - 1;
|
---|
593 | }
|
---|
594 | }
|
---|
595 | /*
|
---|
596 | * need to call this due to clear byte at top if avoiding having the top
|
---|
597 | * bit set (-ve number)
|
---|
598 | */
|
---|
599 | bn_correct_top(ret);
|
---|
600 | return ret;
|
---|
601 | }
|
---|
602 |
|
---|
603 | int BN_bn2lebinpad(const BIGNUM *a, unsigned char *to, int tolen)
|
---|
604 | {
|
---|
605 | int i;
|
---|
606 | BN_ULONG l;
|
---|
607 | bn_check_top(a);
|
---|
608 | i = BN_num_bytes(a);
|
---|
609 | if (tolen < i)
|
---|
610 | return -1;
|
---|
611 | /* Add trailing zeroes if necessary */
|
---|
612 | if (tolen > i)
|
---|
613 | memset(to + i, 0, tolen - i);
|
---|
614 | to += i;
|
---|
615 | while (i--) {
|
---|
616 | l = a->d[i / BN_BYTES];
|
---|
617 | to--;
|
---|
618 | *to = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
|
---|
619 | }
|
---|
620 | return tolen;
|
---|
621 | }
|
---|
622 |
|
---|
623 | int BN_ucmp(const BIGNUM *a, const BIGNUM *b)
|
---|
624 | {
|
---|
625 | int i;
|
---|
626 | BN_ULONG t1, t2, *ap, *bp;
|
---|
627 |
|
---|
628 | bn_check_top(a);
|
---|
629 | bn_check_top(b);
|
---|
630 |
|
---|
631 | i = a->top - b->top;
|
---|
632 | if (i != 0)
|
---|
633 | return (i);
|
---|
634 | ap = a->d;
|
---|
635 | bp = b->d;
|
---|
636 | for (i = a->top - 1; i >= 0; i--) {
|
---|
637 | t1 = ap[i];
|
---|
638 | t2 = bp[i];
|
---|
639 | if (t1 != t2)
|
---|
640 | return ((t1 > t2) ? 1 : -1);
|
---|
641 | }
|
---|
642 | return (0);
|
---|
643 | }
|
---|
644 |
|
---|
645 | int BN_cmp(const BIGNUM *a, const BIGNUM *b)
|
---|
646 | {
|
---|
647 | int i;
|
---|
648 | int gt, lt;
|
---|
649 | BN_ULONG t1, t2;
|
---|
650 |
|
---|
651 | if ((a == NULL) || (b == NULL)) {
|
---|
652 | if (a != NULL)
|
---|
653 | return (-1);
|
---|
654 | else if (b != NULL)
|
---|
655 | return (1);
|
---|
656 | else
|
---|
657 | return (0);
|
---|
658 | }
|
---|
659 |
|
---|
660 | bn_check_top(a);
|
---|
661 | bn_check_top(b);
|
---|
662 |
|
---|
663 | if (a->neg != b->neg) {
|
---|
664 | if (a->neg)
|
---|
665 | return (-1);
|
---|
666 | else
|
---|
667 | return (1);
|
---|
668 | }
|
---|
669 | if (a->neg == 0) {
|
---|
670 | gt = 1;
|
---|
671 | lt = -1;
|
---|
672 | } else {
|
---|
673 | gt = -1;
|
---|
674 | lt = 1;
|
---|
675 | }
|
---|
676 |
|
---|
677 | if (a->top > b->top)
|
---|
678 | return (gt);
|
---|
679 | if (a->top < b->top)
|
---|
680 | return (lt);
|
---|
681 | for (i = a->top - 1; i >= 0; i--) {
|
---|
682 | t1 = a->d[i];
|
---|
683 | t2 = b->d[i];
|
---|
684 | if (t1 > t2)
|
---|
685 | return (gt);
|
---|
686 | if (t1 < t2)
|
---|
687 | return (lt);
|
---|
688 | }
|
---|
689 | return (0);
|
---|
690 | }
|
---|
691 |
|
---|
692 | int BN_set_bit(BIGNUM *a, int n)
|
---|
693 | {
|
---|
694 | int i, j, k;
|
---|
695 |
|
---|
696 | if (n < 0)
|
---|
697 | return 0;
|
---|
698 |
|
---|
699 | i = n / BN_BITS2;
|
---|
700 | j = n % BN_BITS2;
|
---|
701 | if (a->top <= i) {
|
---|
702 | if (bn_wexpand(a, i + 1) == NULL)
|
---|
703 | return (0);
|
---|
704 | for (k = a->top; k < i + 1; k++)
|
---|
705 | a->d[k] = 0;
|
---|
706 | a->top = i + 1;
|
---|
707 | }
|
---|
708 |
|
---|
709 | a->d[i] |= (((BN_ULONG)1) << j);
|
---|
710 | bn_check_top(a);
|
---|
711 | return (1);
|
---|
712 | }
|
---|
713 |
|
---|
714 | int BN_clear_bit(BIGNUM *a, int n)
|
---|
715 | {
|
---|
716 | int i, j;
|
---|
717 |
|
---|
718 | bn_check_top(a);
|
---|
719 | if (n < 0)
|
---|
720 | return 0;
|
---|
721 |
|
---|
722 | i = n / BN_BITS2;
|
---|
723 | j = n % BN_BITS2;
|
---|
724 | if (a->top <= i)
|
---|
725 | return (0);
|
---|
726 |
|
---|
727 | a->d[i] &= (~(((BN_ULONG)1) << j));
|
---|
728 | bn_correct_top(a);
|
---|
729 | return (1);
|
---|
730 | }
|
---|
731 |
|
---|
732 | int BN_is_bit_set(const BIGNUM *a, int n)
|
---|
733 | {
|
---|
734 | int i, j;
|
---|
735 |
|
---|
736 | bn_check_top(a);
|
---|
737 | if (n < 0)
|
---|
738 | return 0;
|
---|
739 | i = n / BN_BITS2;
|
---|
740 | j = n % BN_BITS2;
|
---|
741 | if (a->top <= i)
|
---|
742 | return 0;
|
---|
743 | return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
|
---|
744 | }
|
---|
745 |
|
---|
746 | int BN_mask_bits(BIGNUM *a, int n)
|
---|
747 | {
|
---|
748 | int b, w;
|
---|
749 |
|
---|
750 | bn_check_top(a);
|
---|
751 | if (n < 0)
|
---|
752 | return 0;
|
---|
753 |
|
---|
754 | w = n / BN_BITS2;
|
---|
755 | b = n % BN_BITS2;
|
---|
756 | if (w >= a->top)
|
---|
757 | return 0;
|
---|
758 | if (b == 0)
|
---|
759 | a->top = w;
|
---|
760 | else {
|
---|
761 | a->top = w + 1;
|
---|
762 | a->d[w] &= ~(BN_MASK2 << b);
|
---|
763 | }
|
---|
764 | bn_correct_top(a);
|
---|
765 | return (1);
|
---|
766 | }
|
---|
767 |
|
---|
768 | void BN_set_negative(BIGNUM *a, int b)
|
---|
769 | {
|
---|
770 | if (b && !BN_is_zero(a))
|
---|
771 | a->neg = 1;
|
---|
772 | else
|
---|
773 | a->neg = 0;
|
---|
774 | }
|
---|
775 |
|
---|
776 | int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
|
---|
777 | {
|
---|
778 | int i;
|
---|
779 | BN_ULONG aa, bb;
|
---|
780 |
|
---|
781 | aa = a[n - 1];
|
---|
782 | bb = b[n - 1];
|
---|
783 | if (aa != bb)
|
---|
784 | return ((aa > bb) ? 1 : -1);
|
---|
785 | for (i = n - 2; i >= 0; i--) {
|
---|
786 | aa = a[i];
|
---|
787 | bb = b[i];
|
---|
788 | if (aa != bb)
|
---|
789 | return ((aa > bb) ? 1 : -1);
|
---|
790 | }
|
---|
791 | return (0);
|
---|
792 | }
|
---|
793 |
|
---|
794 | /*
|
---|
795 | * Here follows a specialised variants of bn_cmp_words(). It has the
|
---|
796 | * capability of performing the operation on arrays of different sizes. The
|
---|
797 | * sizes of those arrays is expressed through cl, which is the common length
|
---|
798 | * ( basically, min(len(a),len(b)) ), and dl, which is the delta between the
|
---|
799 | * two lengths, calculated as len(a)-len(b). All lengths are the number of
|
---|
800 | * BN_ULONGs...
|
---|
801 | */
|
---|
802 |
|
---|
803 | int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
|
---|
804 | {
|
---|
805 | int n, i;
|
---|
806 | n = cl - 1;
|
---|
807 |
|
---|
808 | if (dl < 0) {
|
---|
809 | for (i = dl; i < 0; i++) {
|
---|
810 | if (b[n - i] != 0)
|
---|
811 | return -1; /* a < b */
|
---|
812 | }
|
---|
813 | }
|
---|
814 | if (dl > 0) {
|
---|
815 | for (i = dl; i > 0; i--) {
|
---|
816 | if (a[n + i] != 0)
|
---|
817 | return 1; /* a > b */
|
---|
818 | }
|
---|
819 | }
|
---|
820 | return bn_cmp_words(a, b, cl);
|
---|
821 | }
|
---|
822 |
|
---|
823 | /*
|
---|
824 | * Constant-time conditional swap of a and b.
|
---|
825 | * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set.
|
---|
826 | * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b,
|
---|
827 | * and that no more than nwords are used by either a or b.
|
---|
828 | * a and b cannot be the same number
|
---|
829 | */
|
---|
830 | void BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
|
---|
831 | {
|
---|
832 | BN_ULONG t;
|
---|
833 | int i;
|
---|
834 |
|
---|
835 | bn_wcheck_size(a, nwords);
|
---|
836 | bn_wcheck_size(b, nwords);
|
---|
837 |
|
---|
838 | assert(a != b);
|
---|
839 | assert((condition & (condition - 1)) == 0);
|
---|
840 | assert(sizeof(BN_ULONG) >= sizeof(int));
|
---|
841 |
|
---|
842 | condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
|
---|
843 |
|
---|
844 | t = (a->top ^ b->top) & condition;
|
---|
845 | a->top ^= t;
|
---|
846 | b->top ^= t;
|
---|
847 |
|
---|
848 | #define BN_CONSTTIME_SWAP(ind) \
|
---|
849 | do { \
|
---|
850 | t = (a->d[ind] ^ b->d[ind]) & condition; \
|
---|
851 | a->d[ind] ^= t; \
|
---|
852 | b->d[ind] ^= t; \
|
---|
853 | } while (0)
|
---|
854 |
|
---|
855 | switch (nwords) {
|
---|
856 | default:
|
---|
857 | for (i = 10; i < nwords; i++)
|
---|
858 | BN_CONSTTIME_SWAP(i);
|
---|
859 | /* Fallthrough */
|
---|
860 | case 10:
|
---|
861 | BN_CONSTTIME_SWAP(9); /* Fallthrough */
|
---|
862 | case 9:
|
---|
863 | BN_CONSTTIME_SWAP(8); /* Fallthrough */
|
---|
864 | case 8:
|
---|
865 | BN_CONSTTIME_SWAP(7); /* Fallthrough */
|
---|
866 | case 7:
|
---|
867 | BN_CONSTTIME_SWAP(6); /* Fallthrough */
|
---|
868 | case 6:
|
---|
869 | BN_CONSTTIME_SWAP(5); /* Fallthrough */
|
---|
870 | case 5:
|
---|
871 | BN_CONSTTIME_SWAP(4); /* Fallthrough */
|
---|
872 | case 4:
|
---|
873 | BN_CONSTTIME_SWAP(3); /* Fallthrough */
|
---|
874 | case 3:
|
---|
875 | BN_CONSTTIME_SWAP(2); /* Fallthrough */
|
---|
876 | case 2:
|
---|
877 | BN_CONSTTIME_SWAP(1); /* Fallthrough */
|
---|
878 | case 1:
|
---|
879 | BN_CONSTTIME_SWAP(0);
|
---|
880 | }
|
---|
881 | #undef BN_CONSTTIME_SWAP
|
---|
882 | }
|
---|
883 |
|
---|
884 | /* Bits of security, see SP800-57 */
|
---|
885 |
|
---|
886 | int BN_security_bits(int L, int N)
|
---|
887 | {
|
---|
888 | int secbits, bits;
|
---|
889 | if (L >= 15360)
|
---|
890 | secbits = 256;
|
---|
891 | else if (L >= 7690)
|
---|
892 | secbits = 192;
|
---|
893 | else if (L >= 3072)
|
---|
894 | secbits = 128;
|
---|
895 | else if (L >= 2048)
|
---|
896 | secbits = 112;
|
---|
897 | else if (L >= 1024)
|
---|
898 | secbits = 80;
|
---|
899 | else
|
---|
900 | return 0;
|
---|
901 | if (N == -1)
|
---|
902 | return secbits;
|
---|
903 | bits = N / 2;
|
---|
904 | if (bits < 80)
|
---|
905 | return 0;
|
---|
906 | return bits >= secbits ? secbits : bits;
|
---|
907 | }
|
---|
908 |
|
---|
909 | void BN_zero_ex(BIGNUM *a)
|
---|
910 | {
|
---|
911 | a->top = 0;
|
---|
912 | a->neg = 0;
|
---|
913 | }
|
---|
914 |
|
---|
915 | int BN_abs_is_word(const BIGNUM *a, const BN_ULONG w)
|
---|
916 | {
|
---|
917 | return ((a->top == 1) && (a->d[0] == w)) || ((w == 0) && (a->top == 0));
|
---|
918 | }
|
---|
919 |
|
---|
920 | int BN_is_zero(const BIGNUM *a)
|
---|
921 | {
|
---|
922 | return a->top == 0;
|
---|
923 | }
|
---|
924 |
|
---|
925 | int BN_is_one(const BIGNUM *a)
|
---|
926 | {
|
---|
927 | return BN_abs_is_word(a, 1) && !a->neg;
|
---|
928 | }
|
---|
929 |
|
---|
930 | int BN_is_word(const BIGNUM *a, const BN_ULONG w)
|
---|
931 | {
|
---|
932 | return BN_abs_is_word(a, w) && (!w || !a->neg);
|
---|
933 | }
|
---|
934 |
|
---|
935 | int BN_is_odd(const BIGNUM *a)
|
---|
936 | {
|
---|
937 | return (a->top > 0) && (a->d[0] & 1);
|
---|
938 | }
|
---|
939 |
|
---|
940 | int BN_is_negative(const BIGNUM *a)
|
---|
941 | {
|
---|
942 | return (a->neg != 0);
|
---|
943 | }
|
---|
944 |
|
---|
945 | int BN_to_montgomery(BIGNUM *r, const BIGNUM *a, BN_MONT_CTX *mont,
|
---|
946 | BN_CTX *ctx)
|
---|
947 | {
|
---|
948 | return BN_mod_mul_montgomery(r, a, &(mont->RR), mont, ctx);
|
---|
949 | }
|
---|
950 |
|
---|
951 | void BN_with_flags(BIGNUM *dest, const BIGNUM *b, int flags)
|
---|
952 | {
|
---|
953 | dest->d = b->d;
|
---|
954 | dest->top = b->top;
|
---|
955 | dest->dmax = b->dmax;
|
---|
956 | dest->neg = b->neg;
|
---|
957 | dest->flags = ((dest->flags & BN_FLG_MALLOCED)
|
---|
958 | | (b->flags & ~BN_FLG_MALLOCED)
|
---|
959 | | BN_FLG_STATIC_DATA | flags);
|
---|
960 | }
|
---|
961 |
|
---|
962 | BN_GENCB *BN_GENCB_new(void)
|
---|
963 | {
|
---|
964 | BN_GENCB *ret;
|
---|
965 |
|
---|
966 | if ((ret = OPENSSL_malloc(sizeof(*ret))) == NULL) {
|
---|
967 | BNerr(BN_F_BN_GENCB_NEW, ERR_R_MALLOC_FAILURE);
|
---|
968 | return (NULL);
|
---|
969 | }
|
---|
970 |
|
---|
971 | return ret;
|
---|
972 | }
|
---|
973 |
|
---|
974 | void BN_GENCB_free(BN_GENCB *cb)
|
---|
975 | {
|
---|
976 | if (cb == NULL)
|
---|
977 | return;
|
---|
978 | OPENSSL_free(cb);
|
---|
979 | }
|
---|
980 |
|
---|
981 | void BN_set_flags(BIGNUM *b, int n)
|
---|
982 | {
|
---|
983 | b->flags |= n;
|
---|
984 | }
|
---|
985 |
|
---|
986 | int BN_get_flags(const BIGNUM *b, int n)
|
---|
987 | {
|
---|
988 | return b->flags & n;
|
---|
989 | }
|
---|
990 |
|
---|
991 | /* Populate a BN_GENCB structure with an "old"-style callback */
|
---|
992 | void BN_GENCB_set_old(BN_GENCB *gencb, void (*callback) (int, int, void *),
|
---|
993 | void *cb_arg)
|
---|
994 | {
|
---|
995 | BN_GENCB *tmp_gencb = gencb;
|
---|
996 | tmp_gencb->ver = 1;
|
---|
997 | tmp_gencb->arg = cb_arg;
|
---|
998 | tmp_gencb->cb.cb_1 = callback;
|
---|
999 | }
|
---|
1000 |
|
---|
1001 | /* Populate a BN_GENCB structure with a "new"-style callback */
|
---|
1002 | void BN_GENCB_set(BN_GENCB *gencb, int (*callback) (int, int, BN_GENCB *),
|
---|
1003 | void *cb_arg)
|
---|
1004 | {
|
---|
1005 | BN_GENCB *tmp_gencb = gencb;
|
---|
1006 | tmp_gencb->ver = 2;
|
---|
1007 | tmp_gencb->arg = cb_arg;
|
---|
1008 | tmp_gencb->cb.cb_2 = callback;
|
---|
1009 | }
|
---|
1010 |
|
---|
1011 | void *BN_GENCB_get_arg(BN_GENCB *cb)
|
---|
1012 | {
|
---|
1013 | return cb->arg;
|
---|
1014 | }
|
---|
1015 |
|
---|
1016 | BIGNUM *bn_wexpand(BIGNUM *a, int words)
|
---|
1017 | {
|
---|
1018 | return (words <= a->dmax) ? a : bn_expand2(a, words);
|
---|
1019 | }
|
---|
1020 |
|
---|
1021 | void bn_correct_top(BIGNUM *a)
|
---|
1022 | {
|
---|
1023 | BN_ULONG *ftl;
|
---|
1024 | int tmp_top = a->top;
|
---|
1025 |
|
---|
1026 | if (tmp_top > 0) {
|
---|
1027 | for (ftl = &(a->d[tmp_top]); tmp_top > 0; tmp_top--) {
|
---|
1028 | ftl--;
|
---|
1029 | if (*ftl != 0)
|
---|
1030 | break;
|
---|
1031 | }
|
---|
1032 | a->top = tmp_top;
|
---|
1033 | }
|
---|
1034 | if (a->top == 0)
|
---|
1035 | a->neg = 0;
|
---|
1036 | bn_pollute(a);
|
---|
1037 | }
|
---|