GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/crypto/../../libssl/src/crypto/bn/bn_lib.c Lines: 249 362 68.8 %
Date: 2016-12-06 Branches: 146 233 62.7 %

Line Branch Exec Source
1
/* $OpenBSD: bn_lib.c,v 1.36 2016/03/15 20:50:22 krw Exp $ */
2
/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
3
 * All rights reserved.
4
 *
5
 * This package is an SSL implementation written
6
 * by Eric Young (eay@cryptsoft.com).
7
 * The implementation was written so as to conform with Netscapes SSL.
8
 *
9
 * This library is free for commercial and non-commercial use as long as
10
 * the following conditions are aheared to.  The following conditions
11
 * apply to all code found in this distribution, be it the RC4, RSA,
12
 * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
13
 * included with this distribution is covered by the same copyright terms
14
 * except that the holder is Tim Hudson (tjh@cryptsoft.com).
15
 *
16
 * Copyright remains Eric Young's, and as such any Copyright notices in
17
 * the code are not to be removed.
18
 * If this package is used in a product, Eric Young should be given attribution
19
 * as the author of the parts of the library used.
20
 * This can be in the form of a textual message at program startup or
21
 * in documentation (online or textual) provided with the package.
22
 *
23
 * Redistribution and use in source and binary forms, with or without
24
 * modification, are permitted provided that the following conditions
25
 * are met:
26
 * 1. Redistributions of source code must retain the copyright
27
 *    notice, this list of conditions and the following disclaimer.
28
 * 2. Redistributions in binary form must reproduce the above copyright
29
 *    notice, this list of conditions and the following disclaimer in the
30
 *    documentation and/or other materials provided with the distribution.
31
 * 3. All advertising materials mentioning features or use of this software
32
 *    must display the following acknowledgement:
33
 *    "This product includes cryptographic software written by
34
 *     Eric Young (eay@cryptsoft.com)"
35
 *    The word 'cryptographic' can be left out if the rouines from the library
36
 *    being used are not cryptographic related :-).
37
 * 4. If you include any Windows specific code (or a derivative thereof) from
38
 *    the apps directory (application code) you must include an acknowledgement:
39
 *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
40
 *
41
 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
42
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
43
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
44
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
45
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
46
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
47
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
48
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
49
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
50
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51
 * SUCH DAMAGE.
52
 *
53
 * The licence and distribution terms for any publically available version or
54
 * derivative of this code cannot be changed.  i.e. this code cannot simply be
55
 * copied and put under another distribution licence
56
 * [including the GNU Public Licence.]
57
 */
58
59
#ifndef BN_DEBUG
60
# undef NDEBUG /* avoid conflicting definitions */
61
# define NDEBUG
62
#endif
63
64
#include <assert.h>
65
#include <limits.h>
66
#include <stdio.h>
67
#include <string.h>
68
69
#include <openssl/opensslconf.h>
70
71
#include <openssl/err.h>
72
73
#include "bn_lcl.h"
74
75
/* This stuff appears to be completely unused, so is deprecated */
76
#ifndef OPENSSL_NO_DEPRECATED
77
/* For a 32 bit machine
78
 * 2 -   4 ==  128
79
 * 3 -   8 ==  256
80
 * 4 -  16 ==  512
81
 * 5 -  32 == 1024
82
 * 6 -  64 == 2048
83
 * 7 - 128 == 4096
84
 * 8 - 256 == 8192
85
 */
86
static int bn_limit_bits = 0;
87
static int bn_limit_num = 8;        /* (1<<bn_limit_bits) */
88
static int bn_limit_bits_low = 0;
89
static int bn_limit_num_low = 8;    /* (1<<bn_limit_bits_low) */
90
static int bn_limit_bits_high = 0;
91
static int bn_limit_num_high = 8;   /* (1<<bn_limit_bits_high) */
92
static int bn_limit_bits_mont = 0;
93
static int bn_limit_num_mont = 8;   /* (1<<bn_limit_bits_mont) */
94
95
void
96
BN_set_params(int mult, int high, int low, int mont)
97
{
98
	if (mult >= 0) {
99
		if (mult > (int)(sizeof(int) * 8) - 1)
100
			mult = sizeof(int) * 8 - 1;
101
		bn_limit_bits = mult;
102
		bn_limit_num = 1 << mult;
103
	}
104
	if (high >= 0) {
105
		if (high > (int)(sizeof(int) * 8) - 1)
106
			high = sizeof(int) * 8 - 1;
107
		bn_limit_bits_high = high;
108
		bn_limit_num_high = 1 << high;
109
	}
110
	if (low >= 0) {
111
		if (low > (int)(sizeof(int) * 8) - 1)
112
			low = sizeof(int) * 8 - 1;
113
		bn_limit_bits_low = low;
114
		bn_limit_num_low = 1 << low;
115
	}
116
	if (mont >= 0) {
117
		if (mont > (int)(sizeof(int) * 8) - 1)
118
			mont = sizeof(int) * 8 - 1;
119
		bn_limit_bits_mont = mont;
120
		bn_limit_num_mont = 1 << mont;
121
	}
122
}
123
124
int
125
BN_get_params(int which)
126
{
127
	if (which == 0)
128
		return (bn_limit_bits);
129
	else if (which == 1)
130
		return (bn_limit_bits_high);
131
	else if (which == 2)
132
		return (bn_limit_bits_low);
133
	else if (which == 3)
134
		return (bn_limit_bits_mont);
135
	else
136
		return (0);
137
}
138
#endif
139
140
const BIGNUM *
141
BN_value_one(void)
142
16448
{
143
	static const BN_ULONG data_one = 1L;
144
	static const BIGNUM const_one = {
145
		(BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA
146
	};
147
148
16448
	return (&const_one);
149
}
150
151
int
152
BN_num_bits_word(BN_ULONG l)
153
3045231
{
154
	static const unsigned char bits[256] = {
155
		0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
156
		5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
157
		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
158
		6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
159
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
160
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
161
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
162
		7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
163
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,  8, 8, 8, 8,
164
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
165
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
166
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
167
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
168
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
169
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
170
		8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
171
	};
172
173
#ifdef _LP64
174
3045231
	if (l & 0xffffffff00000000L) {
175
1911580
		if (l & 0xffff000000000000L) {
176
1452525
			if (l & 0xff00000000000000L) {
177
1252942
				return (bits[(int)(l >> 56)] + 56);
178
			} else
179
199583
				return (bits[(int)(l >> 48)] + 48);
180
		} else {
181
459055
			if (l & 0x0000ff0000000000L) {
182
266553
				return (bits[(int)(l >> 40)] + 40);
183
			} else
184
192502
				return (bits[(int)(l >> 32)] + 32);
185
		}
186
	} else
187
#endif
188
	{
189
1133651
		if (l & 0xffff0000L) {
190
636981
			if (l & 0xff000000L)
191
440079
				return (bits[(int)(l >> 24L)] + 24);
192
			else
193
196902
				return (bits[(int)(l >> 16L)] + 16);
194
		} else {
195
496670
			if (l & 0xff00L)
196
269635
				return (bits[(int)(l >> 8)] + 8);
197
			else
198
227035
				return (bits[(int)(l)]);
199
		}
200
	}
201
}
202
203
int
204
BN_num_bits(const BIGNUM *a)
205
2207909
{
206
2207909
	int i = a->top - 1;
207
208
	bn_check_top(a);
209
210
2207909
	if (BN_is_zero(a))
211
35
		return 0;
212
2207874
	return ((i * BN_BITS2) + BN_num_bits_word(a->d[i]));
213
}
214
215
void
216
BN_clear_free(BIGNUM *a)
217
71539
{
218
	int i;
219
220
71539
	if (a == NULL)
221
612
		return;
222
	bn_check_top(a);
223

70927
	if (a->d != NULL && !(BN_get_flags(a, BN_FLG_STATIC_DATA))) {
224
66794
		explicit_bzero(a->d, a->dmax * sizeof(a->d[0]));
225
66794
		free(a->d);
226
	}
227
70927
	i = BN_get_flags(a, BN_FLG_MALLOCED);
228
70927
	explicit_bzero(a, sizeof(BIGNUM));
229
70927
	if (i)
230
10525
		free(a);
231
}
232
233
void
234
BN_free(BIGNUM *a)
235
30980
{
236
30980
	BN_clear_free(a);
237
30980
}
238
239
void
240
BN_init(BIGNUM *a)
241
69413
{
242
69413
	memset(a, 0, sizeof(BIGNUM));
243
	bn_check_top(a);
244
69413
}
245
246
BIGNUM *
247
BN_new(void)
248
10553
{
249
	BIGNUM *ret;
250
251
10553
	if ((ret = malloc(sizeof(BIGNUM))) == NULL) {
252
		BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE);
253
		return (NULL);
254
	}
255
10553
	ret->flags = BN_FLG_MALLOCED;
256
10553
	ret->top = 0;
257
10553
	ret->neg = 0;
258
10553
	ret->dmax = 0;
259
10553
	ret->d = NULL;
260
	bn_check_top(ret);
261
10553
	return (ret);
262
}
263
264
/* This is used both by bn_expand2() and bn_dup_expand() */
265
/* The caller MUST check that words > b->dmax before calling this */
266
static BN_ULONG *
267
bn_expand_internal(const BIGNUM *b, int words)
268
98334
{
269
98334
	BN_ULONG *A, *a = NULL;
270
	const BN_ULONG *B;
271
	int i;
272
273
	bn_check_top(b);
274
275
98334
	if (words > (INT_MAX/(4*BN_BITS2))) {
276
		BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG);
277
		return NULL;
278
	}
279
98334
	if (BN_get_flags(b, BN_FLG_STATIC_DATA)) {
280
		BNerr(BN_F_BN_EXPAND_INTERNAL,
281
		    BN_R_EXPAND_ON_STATIC_BIGNUM_DATA);
282
		return (NULL);
283
	}
284
98334
	a = A = reallocarray(NULL, words, sizeof(BN_ULONG));
285
98334
	if (A == NULL) {
286
		BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE);
287
		return (NULL);
288
	}
289
#if 1
290
98334
	B = b->d;
291
	/* Check if the previous number needs to be copied */
292
98334
	if (B != NULL) {
293
35593
		for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
294
			/*
295
			 * The fact that the loop is unrolled
296
			 * 4-wise is a tribute to Intel. It's
297
			 * the one that doesn't have enough
298
			 * registers to accommodate more data.
299
			 * I'd unroll it 8-wise otherwise:-)
300
			 *
301
			 *		<appro@fy.chalmers.se>
302
			 */
303
			BN_ULONG a0, a1, a2, a3;
304
4151
			a0 = B[0];
305
4151
			a1 = B[1];
306
4151
			a2 = B[2];
307
4151
			a3 = B[3];
308
4151
			A[0] = a0;
309
4151
			A[1] = a1;
310
4151
			A[2] = a2;
311
4151
			A[3] = a3;
312
		}
313

31442
		switch (b->top & 3) {
314
		case 3:
315
1203
			A[2] = B[2];
316
		case 2:
317
1903
			A[1] = B[1];
318
		case 1:
319
5399
			A[0] = B[0];
320
		}
321
	}
322
323
#else
324
	memset(A, 0, sizeof(BN_ULONG) * words);
325
	memcpy(A, b->d, sizeof(b->d[0]) * b->top);
326
#endif
327
328
98334
	return (a);
329
}
330
331
/* This is an internal function that can be used instead of bn_expand2()
332
 * when there is a need to copy BIGNUMs instead of only expanding the
333
 * data part, while still expanding them.
334
 * Especially useful when needing to expand BIGNUMs that are declared
335
 * 'const' and should therefore not be changed.
336
 * The reason to use this instead of a BN_dup() followed by a bn_expand2()
337
 * is memory allocation overhead.  A BN_dup() followed by a bn_expand2()
338
 * will allocate new memory for the BIGNUM data twice, and free it once,
339
 * while bn_dup_expand() makes sure allocation is made only once.
340
 */
341
342
#ifndef OPENSSL_NO_DEPRECATED
343
BIGNUM *
344
bn_dup_expand(const BIGNUM *b, int words)
345
{
346
	BIGNUM *r = NULL;
347
348
	bn_check_top(b);
349
350
	/* This function does not work if
351
	 *      words <= b->dmax && top < words
352
	 * because BN_dup() does not preserve 'dmax'!
353
	 * (But bn_dup_expand() is not used anywhere yet.)
354
	 */
355
356
	if (words > b->dmax) {
357
		BN_ULONG *a = bn_expand_internal(b, words);
358
359
		if (a) {
360
			r = BN_new();
361
			if (r) {
362
				r->top = b->top;
363
				r->dmax = words;
364
				r->neg = b->neg;
365
				r->d = a;
366
			} else {
367
				/* r == NULL, BN_new failure */
368
				free(a);
369
			}
370
		}
371
		/* If a == NULL, there was an error in allocation in
372
		   bn_expand_internal(), and NULL should be returned */
373
	} else {
374
		r = BN_dup(b);
375
	}
376
377
	bn_check_top(r);
378
	return r;
379
}
380
#endif
381
382
/* This is an internal function that should not be used in applications.
383
 * It ensures that 'b' has enough room for a 'words' word number
384
 * and initialises any unused part of b->d with leading zeros.
385
 * It is mostly used by the various BIGNUM routines. If there is an error,
386
 * NULL is returned. If not, 'b' is returned. */
387
388
BIGNUM *
389
bn_expand2(BIGNUM *b, int words)
390
98334
{
391
	bn_check_top(b);
392
393
98334
	if (words > b->dmax) {
394
98334
		BN_ULONG *a = bn_expand_internal(b, words);
395
98334
		if (!a)
396
			return NULL;
397
98334
		if (b->d) {
398
31442
			explicit_bzero(b->d, b->dmax * sizeof(b->d[0]));
399
31442
			free(b->d);
400
		}
401
98334
		b->d = a;
402
98334
		b->dmax = words;
403
	}
404
405
/* None of this should be necessary because of what b->top means! */
406
#if 0
407
	/* NB: bn_wexpand() calls this only if the BIGNUM really has to grow */
408
	if (b->top < b->dmax) {
409
		int i;
410
		BN_ULONG *A = &(b->d[b->top]);
411
		for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) {
412
			A[0] = 0;
413
			A[1] = 0;
414
			A[2] = 0;
415
			A[3] = 0;
416
			A[4] = 0;
417
			A[5] = 0;
418
			A[6] = 0;
419
			A[7] = 0;
420
		}
421
		for (i = (b->dmax - b->top)&7; i > 0; i--, A++)
422
			A[0] = 0;
423
		assert(A == &(b->d[b->dmax]));
424
	}
425
#endif
426
	bn_check_top(b);
427
98334
	return b;
428
}
429
430
BIGNUM *
431
BN_dup(const BIGNUM *a)
432
215
{
433
	BIGNUM *t;
434
435
215
	if (a == NULL)
436
		return NULL;
437
	bn_check_top(a);
438
439
215
	t = BN_new();
440
215
	if (t == NULL)
441
		return NULL;
442
215
	if (!BN_copy(t, a)) {
443
		BN_free(t);
444
		return NULL;
445
	}
446
	bn_check_top(t);
447
215
	return t;
448
}
449
450
BIGNUM *
451
BN_copy(BIGNUM *a, const BIGNUM *b)
452
567492
{
453
	int i;
454
	BN_ULONG *A;
455
	const BN_ULONG *B;
456
457
	bn_check_top(b);
458
459
567492
	if (a == b)
460
368
		return (a);
461

567124
	if (bn_wexpand(a, b->top) == NULL)
462
		return (NULL);
463
464
#if 1
465
567124
	A = a->d;
466
567124
	B = b->d;
467
1132104
	for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) {
468
		BN_ULONG a0, a1, a2, a3;
469
564980
		a0 = B[0];
470
564980
		a1 = B[1];
471
564980
		a2 = B[2];
472
564980
		a3 = B[3];
473
564980
		A[0] = a0;
474
564980
		A[1] = a1;
475
564980
		A[2] = a2;
476
564980
		A[3] = a3;
477
	}
478

567124
	switch (b->top & 3) {
479
	case 3:
480
144794
		A[2] = B[2];
481
	case 2:
482
193093
		A[1] = B[1];
483
	case 1:
484
351298
		A[0] = B[0];
485
	}
486
#else
487
	memcpy(a->d, b->d, sizeof(b->d[0]) * b->top);
488
#endif
489
490
567124
	a->top = b->top;
491
567124
	a->neg = b->neg;
492
	bn_check_top(a);
493
567124
	return (a);
494
}
495
496
void
497
BN_swap(BIGNUM *a, BIGNUM *b)
498
{
499
	int flags_old_a, flags_old_b;
500
	BN_ULONG *tmp_d;
501
	int tmp_top, tmp_dmax, tmp_neg;
502
503
	bn_check_top(a);
504
	bn_check_top(b);
505
506
	flags_old_a = a->flags;
507
	flags_old_b = b->flags;
508
509
	tmp_d = a->d;
510
	tmp_top = a->top;
511
	tmp_dmax = a->dmax;
512
	tmp_neg = a->neg;
513
514
	a->d = b->d;
515
	a->top = b->top;
516
	a->dmax = b->dmax;
517
	a->neg = b->neg;
518
519
	b->d = tmp_d;
520
	b->top = tmp_top;
521
	b->dmax = tmp_dmax;
522
	b->neg = tmp_neg;
523
524
	a->flags = (flags_old_a & BN_FLG_MALLOCED) |
525
	    (flags_old_b & BN_FLG_STATIC_DATA);
526
	b->flags = (flags_old_b & BN_FLG_MALLOCED) |
527
	    (flags_old_a & BN_FLG_STATIC_DATA);
528
	bn_check_top(a);
529
	bn_check_top(b);
530
}
531
532
void
533
BN_clear(BIGNUM *a)
534
{
535
	bn_check_top(a);
536
	if (a->d != NULL)
537
		memset(a->d, 0, a->dmax * sizeof(a->d[0]));
538
	a->top = 0;
539
	a->neg = 0;
540
}
541
542
BN_ULONG
543
BN_get_word(const BIGNUM *a)
544
{
545
	if (a->top > 1)
546
		return BN_MASK2;
547
	else if (a->top == 1)
548
		return a->d[0];
549
	/* a->top == 0 */
550
	return 0;
551
}
552
553
BIGNUM *
554
bn_expand(BIGNUM *a, int bits)
555
5583034
{
556
5583034
	if (bits > (INT_MAX - BN_BITS2 + 1))
557
		return (NULL);
558
559
5583034
	if (((bits + BN_BITS2 - 1) / BN_BITS2) <= a->dmax)
560
5565159
		return (a);
561
562
17875
	return bn_expand2(a, (bits + BN_BITS2 - 1) / BN_BITS2);
563
}
564
565
int
566
BN_set_word(BIGNUM *a, BN_ULONG w)
567
5582916
{
568
	bn_check_top(a);
569
5582916
	if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL)
570
		return (0);
571
5582916
	a->neg = 0;
572
5582916
	a->d[0] = w;
573
5582916
	a->top = (w ? 1 : 0);
574
	bn_check_top(a);
575
5582916
	return (1);
576
}
577
578
BIGNUM *
579
BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret)
580
11142
{
581
	unsigned int i, m;
582
	unsigned int n;
583
	BN_ULONG l;
584
11142
	BIGNUM *bn = NULL;
585
586
11142
	if (ret == NULL)
587
1794
		ret = bn = BN_new();
588
11142
	if (ret == NULL)
589
		return (NULL);
590
	bn_check_top(ret);
591
11142
	l = 0;
592
11142
	n = len;
593
11142
	if (n == 0) {
594
		ret->top = 0;
595
		return (ret);
596
	}
597
11142
	i = ((n - 1) / BN_BYTES) + 1;
598
11142
	m = ((n - 1) % (BN_BYTES));
599

11142
	if (bn_wexpand(ret, (int)i) == NULL) {
600
		BN_free(bn);
601
		return NULL;
602
	}
603
11142
	ret->top = i;
604
11142
	ret->neg = 0;
605
509409
	while (n--) {
606
487125
		l = (l << 8L) | *(s++);
607
487125
		if (m-- == 0) {
608
64441
			ret->d[--i] = l;
609
64441
			l = 0;
610
64441
			m = BN_BYTES - 1;
611
		}
612
	}
613
	/* need to call this due to clear byte at top if avoiding
614
	 * having the top bit set (-ve number) */
615

11142
	bn_correct_top(ret);
616
11142
	return (ret);
617
}
618
619
/* ignore negative */
620
int
621
BN_bn2bin(const BIGNUM *a, unsigned char *to)
622
1473
{
623
	int n, i;
624
	BN_ULONG l;
625
626
	bn_check_top(a);
627
1473
	n = i=BN_num_bytes(a);
628
53892
	while (i--) {
629
50946
		l = a->d[i / BN_BYTES];
630
50946
		*(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff;
631
	}
632
1473
	return (n);
633
}
634
635
int
636
BN_ucmp(const BIGNUM *a, const BIGNUM *b)
637
3028222
{
638
	int i;
639
	BN_ULONG t1, t2, *ap, *bp;
640
641
	bn_check_top(a);
642
	bn_check_top(b);
643
644
3028222
	i = a->top - b->top;
645
3028222
	if (i != 0)
646
616975
		return (i);
647
2411247
	ap = a->d;
648
2411247
	bp = b->d;
649
2537468
	for (i = a->top - 1; i >= 0; i--) {
650
2516842
		t1 = ap[i];
651
2516842
		t2 = bp[i];
652
2516842
		if (t1 != t2)
653
2390621
			return ((t1 > t2) ? 1 : -1);
654
	}
655
20626
	return (0);
656
}
657
658
int
659
BN_cmp(const BIGNUM *a, const BIGNUM *b)
660
1056999
{
661
	int i;
662
	int gt, lt;
663
	BN_ULONG t1, t2;
664
665
1056999
	if ((a == NULL) || (b == NULL)) {
666
		if (a != NULL)
667
			return (-1);
668
		else if (b != NULL)
669
			return (1);
670
		else
671
			return (0);
672
	}
673
674
	bn_check_top(a);
675
	bn_check_top(b);
676
677
1056999
	if (a->neg != b->neg) {
678
5
		if (a->neg)
679
			return (-1);
680
		else
681
5
			return (1);
682
	}
683
1056994
	if (a->neg == 0) {
684
1056994
		gt = 1;
685
1056994
		lt = -1;
686
	} else {
687
		gt = -1;
688
		lt = 1;
689
	}
690
691
1056994
	if (a->top > b->top)
692
255189
		return (gt);
693
801805
	if (a->top < b->top)
694
487
		return (lt);
695
809868
	for (i = a->top - 1; i >= 0; i--) {
696
807420
		t1 = a->d[i];
697
807420
		t2 = b->d[i];
698
807420
		if (t1 > t2)
699
337721
			return (gt);
700
469699
		if (t1 < t2)
701
461149
			return (lt);
702
	}
703
2448
	return (0);
704
}
705
706
int
707
BN_set_bit(BIGNUM *a, int n)
708
4798
{
709
	int i, j, k;
710
711
4798
	if (n < 0)
712
		return 0;
713
714
4798
	i = n / BN_BITS2;
715
4798
	j = n % BN_BITS2;
716
4798
	if (a->top <= i) {
717

4700
		if (bn_wexpand(a, i + 1) == NULL)
718
			return (0);
719
29313
		for (k = a->top; k < i + 1; k++)
720
24613
			a->d[k] = 0;
721
4700
		a->top = i + 1;
722
	}
723
724
4798
	a->d[i] |= (((BN_ULONG)1) << j);
725
	bn_check_top(a);
726
4798
	return (1);
727
}
728
729
int
730
BN_clear_bit(BIGNUM *a, int n)
731
{
732
	int i, j;
733
734
	bn_check_top(a);
735
	if (n < 0)
736
		return 0;
737
738
	i = n / BN_BITS2;
739
	j = n % BN_BITS2;
740
	if (a->top <= i)
741
		return (0);
742
743
	a->d[i] &= (~(((BN_ULONG)1) << j));
744
	bn_correct_top(a);
745
	return (1);
746
}
747
748
int
749
BN_is_bit_set(const BIGNUM *a, int n)
750
2608470
{
751
	int i, j;
752
753
	bn_check_top(a);
754
2608470
	if (n < 0)
755
1
		return 0;
756
2608469
	i = n / BN_BITS2;
757
2608469
	j = n % BN_BITS2;
758
2608469
	if (a->top <= i)
759
1278
		return 0;
760
2607191
	return (int)(((a->d[i]) >> j) & ((BN_ULONG)1));
761
}
762
763
int
764
BN_mask_bits(BIGNUM *a, int n)
765
212
{
766
	int b, w;
767
768
	bn_check_top(a);
769
212
	if (n < 0)
770
		return 0;
771
772
212
	w = n / BN_BITS2;
773
212
	b = n % BN_BITS2;
774
212
	if (w >= a->top)
775
		return 0;
776
212
	if (b == 0)
777
		a->top = w;
778
	else {
779
212
		a->top = w + 1;
780
212
		a->d[w] &= ~(BN_MASK2 << b);
781
	}
782

212
	bn_correct_top(a);
783
212
	return (1);
784
}
785
786
void
787
BN_set_negative(BIGNUM *a, int b)
788
36879
{
789

36883
	if (b && !BN_is_zero(a))
790
4
		a->neg = 1;
791
	else
792
36875
		a->neg = 0;
793
36879
}
794
795
int
796
bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n)
797
1243
{
798
	int i;
799
	BN_ULONG aa, bb;
800
801
1243
	aa = a[n - 1];
802
1243
	bb = b[n - 1];
803
1243
	if (aa != bb)
804
1239
		return ((aa > bb) ? 1 : -1);
805
18
	for (i = n - 2; i >= 0; i--) {
806
17
		aa = a[i];
807
17
		bb = b[i];
808
17
		if (aa != bb)
809
3
			return ((aa > bb) ? 1 : -1);
810
	}
811
1
	return (0);
812
}
813
814
/* Here follows a specialised variants of bn_cmp_words().  It has the
815
   property of performing the operation on arrays of different sizes.
816
   The sizes of those arrays is expressed through cl, which is the
817
   common length ( basicall, min(len(a),len(b)) ), and dl, which is the
818
   delta between the two lengths, calculated as len(a)-len(b).
819
   All lengths are the number of BN_ULONGs...  */
820
821
int
822
bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl)
823
1764
{
824
	int n, i;
825
826
1764
	n = cl - 1;
827
828
1764
	if (dl < 0) {
829
288
		for (i = dl; i < 0; i++) {
830
287
			if (b[n - i] != 0)
831
271
				return -1; /* a < b */
832
		}
833
	}
834
1493
	if (dl > 0) {
835
280
		for (i = dl; i > 0; i--) {
836
280
			if (a[n + i] != 0)
837
272
				return 1; /* a > b */
838
		}
839
	}
840
1221
	return bn_cmp_words(a, b, cl);
841
}
842
843
/*
844
 * Constant-time conditional swap of a and b.
845
 * a and b are swapped if condition is not 0.  The code assumes that at most one bit of condition is set.
846
 * nwords is the number of words to swap.  The code assumes that at least nwords are allocated in both a and b,
847
 * and that no more than nwords are used by either a or b.
848
 * a and b cannot be the same number
849
 */
850
void
851
BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords)
852
614240
{
853
	BN_ULONG t;
854
	int i;
855
856
	bn_wcheck_size(a, nwords);
857
	bn_wcheck_size(b, nwords);
858
859
	assert(a != b);
860
	assert((condition & (condition - 1)) == 0);
861
	assert(sizeof(BN_ULONG) >= sizeof(int));
862
863
614240
	condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1;
864
865
614240
	t = (a->top^b->top) & condition;
866
614240
	a->top ^= t;
867
614240
	b->top ^= t;
868
869
#define BN_CONSTTIME_SWAP(ind) \
870
	do { \
871
		t = (a->d[ind] ^ b->d[ind]) & condition; \
872
		a->d[ind] ^= t; \
873
		b->d[ind] ^= t; \
874
	} while (0)
875
876
877


614240
	switch (nwords) {
878
	default:
879
		for (i = 10; i < nwords; i++)
880
			BN_CONSTTIME_SWAP(i);
881
		/* Fallthrough */
882
	case 10: BN_CONSTTIME_SWAP(9); /* Fallthrough */
883
99888
	case 9: BN_CONSTTIME_SWAP(8); /* Fallthrough */
884
99888
	case 8: BN_CONSTTIME_SWAP(7); /* Fallthrough */
885
191532
	case 7: BN_CONSTTIME_SWAP(6); /* Fallthrough */
886
236468
	case 6: BN_CONSTTIME_SWAP(5); /* Fallthrough */
887
315764
	case 5: BN_CONSTTIME_SWAP(4); /* Fallthrough */
888
478756
	case 4: BN_CONSTTIME_SWAP(3); /* Fallthrough */
889
612452
	case 3: BN_CONSTTIME_SWAP(2); /* Fallthrough */
890
614240
	case 2: BN_CONSTTIME_SWAP(1); /* Fallthrough */
891
	case 1:
892
614240
		BN_CONSTTIME_SWAP(0);
893
	}
894
#undef BN_CONSTTIME_SWAP
895
614240
}