GCC Code Coverage Report
Directory: ./ Exec Total Coverage
File: lib/libcrypto/bn/bn_nist.c Lines: 0 405 0.0 %
Date: 2017-11-07 Branches: 0 142 0.0 %

Line Branch Exec Source
1
/* $OpenBSD: bn_nist.c,v 1.18 2016/07/18 01:04:52 bcook Exp $ */
2
/*
3
 * Written by Nils Larsch for the OpenSSL project
4
 */
5
/* ====================================================================
6
 * Copyright (c) 1998-2005 The OpenSSL Project.  All rights reserved.
7
 *
8
 * Redistribution and use in source and binary forms, with or without
9
 * modification, are permitted provided that the following conditions
10
 * are met:
11
 *
12
 * 1. Redistributions of source code must retain the above copyright
13
 *    notice, this list of conditions and the following disclaimer.
14
 *
15
 * 2. Redistributions in binary form must reproduce the above copyright
16
 *    notice, this list of conditions and the following disclaimer in
17
 *    the documentation and/or other materials provided with the
18
 *    distribution.
19
 *
20
 * 3. All advertising materials mentioning features or use of this
21
 *    software must display the following acknowledgment:
22
 *    "This product includes software developed by the OpenSSL Project
23
 *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
24
 *
25
 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26
 *    endorse or promote products derived from this software without
27
 *    prior written permission. For written permission, please contact
28
 *    openssl-core@openssl.org.
29
 *
30
 * 5. Products derived from this software may not be called "OpenSSL"
31
 *    nor may "OpenSSL" appear in their names without prior written
32
 *    permission of the OpenSSL Project.
33
 *
34
 * 6. Redistributions of any form whatsoever must retain the following
35
 *    acknowledgment:
36
 *    "This product includes software developed by the OpenSSL Project
37
 *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
38
 *
39
 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40
 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
43
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50
 * OF THE POSSIBILITY OF SUCH DAMAGE.
51
 * ====================================================================
52
 *
53
 * This product includes cryptographic software written by Eric Young
54
 * (eay@cryptsoft.com).  This product includes software written by Tim
55
 * Hudson (tjh@cryptsoft.com).
56
 *
57
 */
58
59
#include <machine/endian.h>
60
61
#include <stdint.h>
62
#include <string.h>
63
64
#include "bn_lcl.h"
65
66
#define BN_NIST_192_TOP	(192+BN_BITS2-1)/BN_BITS2
67
#define BN_NIST_224_TOP	(224+BN_BITS2-1)/BN_BITS2
68
#define BN_NIST_256_TOP	(256+BN_BITS2-1)/BN_BITS2
69
#define BN_NIST_384_TOP	(384+BN_BITS2-1)/BN_BITS2
70
#define BN_NIST_521_TOP	(521+BN_BITS2-1)/BN_BITS2
71
72
/* pre-computed tables are "carry-less" values of modulus*(i+1) */
73
#if BN_BITS2 == 64
74
static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
75
	{0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
76
	{0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
77
	{0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
78
};
79
static const BN_ULONG _nist_p_192_sqr[] = {
80
	0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
81
	0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
82
};
83
static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
84
	{
85
		0x0000000000000001ULL, 0xFFFFFFFF00000000ULL,
86
		0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL
87
	},
88
	{
89
		0x0000000000000002ULL, 0xFFFFFFFE00000000ULL,
90
		0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL
91
	} /* this one is "carry-full" */
92
};
93
static const BN_ULONG _nist_p_224_sqr[] = {
94
	0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
95
	0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
96
	0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
97
	0xFFFFFFFFFFFFFFFFULL
98
};
99
static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
100
	{
101
		0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL,
102
		0x0000000000000000ULL, 0xFFFFFFFF00000001ULL
103
	},
104
	{
105
		0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL,
106
		0x0000000000000000ULL, 0xFFFFFFFE00000002ULL
107
	},
108
	{
109
		0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL,
110
		0x0000000000000000ULL, 0xFFFFFFFD00000003ULL
111
	},
112
	{
113
		0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL,
114
		0x0000000000000000ULL, 0xFFFFFFFC00000004ULL
115
	},
116
	{
117
		0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL,
118
		0x0000000000000000ULL, 0xFFFFFFFB00000005ULL
119
	},
120
};
121
static const BN_ULONG _nist_p_256_sqr[] = {
122
	0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
123
	0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
124
	0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
125
	0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
126
};
127
static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
128
	{
129
		0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL,
130
		0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL,
131
		0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
132
	},
133
	{
134
		0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL,
135
		0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL,
136
		0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
137
	},
138
	{
139
		0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL,
140
		0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL,
141
		0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
142
	},
143
	{
144
		0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL,
145
		0xFFFFFFFFFFFFFFFBULL, 0xFFFFFFFFFFFFFFFFULL,
146
		0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
147
	},
148
	{
149
		0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL,
150
		0xFFFFFFFFFFFFFFFAULL, 0xFFFFFFFFFFFFFFFFULL,
151
		0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
152
	},
153
};
154
static const BN_ULONG _nist_p_384_sqr[] = {
155
	0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL,
156
	0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL,
157
	0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
158
	0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
159
};
160
static const BN_ULONG _nist_p_521[] = {
161
	0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
162
	0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
163
	0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0x00000000000001FFULL
164
};
165
static const BN_ULONG _nist_p_521_sqr[] = {
166
	0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
167
	0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
168
	0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL,
169
	0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
170
	0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
171
	0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL
172
};
173
#elif BN_BITS2 == 32
174
static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
175
	{
176
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
177
		0xFFFFFFFF, 0xFFFFFFFF
178
	},
179
	{
180
		0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF,
181
		0xFFFFFFFF, 0xFFFFFFFF
182
	},
183
	{
184
		0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF,
185
		0xFFFFFFFF, 0xFFFFFFFF
186
	}
187
};
188
static const BN_ULONG _nist_p_192_sqr[] = {
189
	0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
190
	0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
191
};
192
static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
193
	{
194
		0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF,
195
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
196
	},
197
	{
198
		0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE,
199
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
200
	}
201
};
202
static const BN_ULONG _nist_p_224_sqr[] = {
203
	0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
204
	0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002,
205
	0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
206
	0xFFFFFFFF, 0xFFFFFFFF
207
};
208
static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
209
	{
210
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000,
211
		0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF
212
	},
213
	{
214
		0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001,
215
		0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE
216
	},
217
	{
218
		0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002,
219
		0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD
220
	},
221
	{
222
		0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003,
223
		0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC
224
	},
225
	{
226
		0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004,
227
		0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB
228
	},
229
};
230
static const BN_ULONG _nist_p_256_sqr[] = {
231
	0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
232
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001,
233
	0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001,
234
	0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE
235
};
236
static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
237
	{
238
		0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF,
239
		0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
240
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
241
	},
242
	{
243
		0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE,
244
		0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
245
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
246
	},
247
	{
248
		0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD,
249
		0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
250
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
251
	},
252
	{
253
		0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC,
254
		0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
255
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
256
	},
257
	{
258
		0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB,
259
		0xFFFFFFFA, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
260
		0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
261
	},
262
};
263
static const BN_ULONG _nist_p_384_sqr[] = {
264
	0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE,
265
	0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000,
266
	0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
267
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
268
};
269
static const BN_ULONG _nist_p_521[] = {
270
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
271
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
272
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
273
	0xFFFFFFFF, 0x000001FF
274
};
275
static const BN_ULONG _nist_p_521_sqr[] = {
276
	0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
277
	0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
278
	0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF,
279
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
280
	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
281
	0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF
282
};
283
#else
284
#error "unsupported BN_BITS2"
285
#endif
286
287
static const BIGNUM _bignum_nist_p_192 = {
288
	(BN_ULONG *)_nist_p_192[0],
289
	BN_NIST_192_TOP,
290
	BN_NIST_192_TOP,
291
	0,
292
	BN_FLG_STATIC_DATA
293
};
294
295
static const BIGNUM _bignum_nist_p_224 = {
296
	(BN_ULONG *)_nist_p_224[0],
297
	BN_NIST_224_TOP,
298
	BN_NIST_224_TOP,
299
	0,
300
	BN_FLG_STATIC_DATA
301
};
302
303
static const BIGNUM _bignum_nist_p_256 = {
304
	(BN_ULONG *)_nist_p_256[0],
305
	BN_NIST_256_TOP,
306
	BN_NIST_256_TOP,
307
	0,
308
	BN_FLG_STATIC_DATA
309
};
310
311
static const BIGNUM _bignum_nist_p_384 = {
312
	(BN_ULONG *)_nist_p_384[0],
313
	BN_NIST_384_TOP,
314
	BN_NIST_384_TOP,
315
	0,
316
	BN_FLG_STATIC_DATA
317
};
318
319
static const BIGNUM _bignum_nist_p_521 = {
320
	(BN_ULONG *)_nist_p_521,
321
	BN_NIST_521_TOP,
322
	BN_NIST_521_TOP,
323
	0,
324
	BN_FLG_STATIC_DATA
325
};
326
327
328
const BIGNUM *
329
BN_get0_nist_prime_192(void)
330
{
331
	return &_bignum_nist_p_192;
332
}
333
334
const BIGNUM *
335
BN_get0_nist_prime_224(void)
336
{
337
	return &_bignum_nist_p_224;
338
}
339
340
const BIGNUM *
341
BN_get0_nist_prime_256(void)
342
{
343
	return &_bignum_nist_p_256;
344
}
345
346
const BIGNUM *
347
BN_get0_nist_prime_384(void)
348
{
349
	return &_bignum_nist_p_384;
350
}
351
352
const BIGNUM *
353
BN_get0_nist_prime_521(void)
354
{
355
	return &_bignum_nist_p_521;
356
}
357
358
static void
359
nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max)
360
{
361
	int i;
362
363
#ifdef BN_DEBUG
364
	OPENSSL_assert(top <= max);
365
#endif
366
	for (i = 0; i < top; i++)
367
		dst[i] = src[i];
368
	for (; i < max; i++)
369
		dst[i] = 0;
370
}
371
372
static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
373
{
374
	int i;
375
376
	for (i = 0; i < top; i++)
377
		dst[i] = src[i];
378
}
379
380
#if BN_BITS2 == 64
381
#define bn_cp_64(to, n, from, m)	(to)[n] = (m>=0)?((from)[m]):0;
382
#define bn_64_set_0(to, n)		(to)[n] = (BN_ULONG)0;
383
/*
384
 * two following macros are implemented under assumption that they
385
 * are called in a sequence with *ascending* n, i.e. as they are...
386
 */
387
#define bn_cp_32_naked(to, n, from, m)	(((n)&1)?(to[(n)/2]|=((m)&1)?(from[(m)/2]&BN_MASK2h):(from[(m)/2]<<32))\
388
						:(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
389
#define bn_32_set_0(to, n)		(((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
390
#define bn_cp_32(to,n,from,m)		((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
391
# if BYTE_ORDER == LITTLE_ENDIAN
392
#  if defined(_LP64)
393
#   define NIST_INT64 long
394
#  else
395
#   define NIST_INT64 long long
396
#  endif
397
# endif
398
#else
399
#define bn_cp_64(to, n, from, m) \
400
	{ \
401
	bn_cp_32(to, (n)*2, from, (m)*2); \
402
	bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
403
	}
404
#define bn_64_set_0(to, n) \
405
	{ \
406
	bn_32_set_0(to, (n)*2); \
407
	bn_32_set_0(to, (n)*2+1); \
408
	}
409
#define bn_cp_32(to, n, from, m)	(to)[n] = (m>=0)?((from)[m]):0;
410
#define bn_32_set_0(to, n)		(to)[n] = (BN_ULONG)0;
411
# if defined(BN_LLONG)
412
#  define NIST_INT64 long long
413
# endif
414
#endif /* BN_BITS2 != 64 */
415
416
#define nist_set_192(to, from, a1, a2, a3) \
417
	{ \
418
	bn_cp_64(to, 0, from, (a3) - 3) \
419
	bn_cp_64(to, 1, from, (a2) - 3) \
420
	bn_cp_64(to, 2, from, (a1) - 3) \
421
	}
422
423
int
424
BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, BN_CTX *ctx)
425
{
426
	int top = a->top, i;
427
	int carry;
428
	BN_ULONG *r_d, *a_d = a->d;
429
	union {
430
		BN_ULONG bn[BN_NIST_192_TOP];
431
		unsigned int ui[BN_NIST_192_TOP *
432
		    sizeof(BN_ULONG) / sizeof(unsigned int)];
433
	} buf;
434
	BN_ULONG c_d[BN_NIST_192_TOP], *res;
435
	uintptr_t mask;
436
	static const BIGNUM _bignum_nist_p_192_sqr = {
437
		(BN_ULONG *)_nist_p_192_sqr,
438
		sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
439
		sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
440
		0,
441
		BN_FLG_STATIC_DATA
442
	};
443
444
	field = &_bignum_nist_p_192; /* just to make sure */
445
446
	if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
447
		return BN_nnmod(r, a, field, ctx);
448
449
	i = BN_ucmp(field, a);
450
	if (i == 0) {
451
		BN_zero(r);
452
		return 1;
453
	} else if (i > 0)
454
		return (r == a) ? 1 : (BN_copy(r , a) != NULL);
455
456
	if (r != a) {
457
		if (!bn_wexpand(r, BN_NIST_192_TOP))
458
			return 0;
459
		r_d = r->d;
460
		nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
461
	} else
462
		r_d = a_d;
463
464
	nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
465
	    BN_NIST_192_TOP);
466
467
#if defined(NIST_INT64)
468
	{
469
		NIST_INT64 acc;	/* accumulator */
470
		unsigned int *rp = (unsigned int *)r_d;
471
		const unsigned int *bp = (const unsigned int *)buf.ui;
472
473
		acc = rp[0];
474
		acc += bp[3 * 2 - 6];
475
		acc += bp[5 * 2 - 6];
476
		rp[0] = (unsigned int)acc;
477
		acc >>= 32;
478
479
		acc += rp[1];
480
		acc += bp[3 * 2 - 5];
481
		acc += bp[5 * 2 - 5];
482
		rp[1] = (unsigned int)acc;
483
		acc >>= 32;
484
485
		acc += rp[2];
486
		acc += bp[3 * 2 - 6];
487
		acc += bp[4 * 2 - 6];
488
		acc += bp[5 * 2 - 6];
489
		rp[2] = (unsigned int)acc;
490
		acc >>= 32;
491
492
		acc += rp[3];
493
		acc += bp[3 * 2 - 5];
494
		acc += bp[4 * 2 - 5];
495
		acc += bp[5 * 2 - 5];
496
		rp[3] = (unsigned int)acc;
497
		acc >>= 32;
498
499
		acc += rp[4];
500
		acc += bp[4 * 2 - 6];
501
		acc += bp[5 * 2 - 6];
502
		rp[4] = (unsigned int)acc;
503
		acc >>= 32;
504
505
		acc += rp[5];
506
		acc += bp[4 * 2 - 5];
507
		acc += bp[5 * 2 - 5];
508
		rp[5] = (unsigned int)acc;
509
510
		carry = (int)(acc >> 32);
511
	}
512
#else
513
	{
514
		BN_ULONG t_d[BN_NIST_192_TOP] = {0};
515
516
		nist_set_192(t_d, buf.bn, 0, 3, 3);
517
		carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
518
		nist_set_192(t_d, buf.bn, 4, 4, 0);
519
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
520
		nist_set_192(t_d, buf.bn, 5, 5, 5)
521
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
522
	}
523
#endif
524
	if (carry > 0)
525
		carry = (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
526
		    BN_NIST_192_TOP);
527
	else
528
		carry = 1;
529
530
	/*
531
	 * we need 'if (carry==0 || result>=modulus) result-=modulus;'
532
	 * as comparison implies subtraction, we can write
533
	 * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
534
	 * this is what happens below, but without explicit if:-) a.
535
	 */
536
	mask = 0 - (uintptr_t)bn_sub_words(c_d, r_d, _nist_p_192[0],
537
	    BN_NIST_192_TOP);
538
	mask &= 0 - (uintptr_t)carry;
539
	res = c_d;
540
	res = (BN_ULONG *)(((uintptr_t)res & ~mask) | ((uintptr_t)r_d & mask));
541
	nist_cp_bn(r_d, res, BN_NIST_192_TOP);
542
	r->top = BN_NIST_192_TOP;
543
	bn_correct_top(r);
544
545
	return 1;
546
}
547
548
typedef BN_ULONG (*bn_addsub_f)(BN_ULONG *, const BN_ULONG *,
549
    const BN_ULONG *, int);
550
551
#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
552
	{ \
553
	bn_cp_32(to, 0, from, (a7) - 7) \
554
	bn_cp_32(to, 1, from, (a6) - 7) \
555
	bn_cp_32(to, 2, from, (a5) - 7) \
556
	bn_cp_32(to, 3, from, (a4) - 7) \
557
	bn_cp_32(to, 4, from, (a3) - 7) \
558
	bn_cp_32(to, 5, from, (a2) - 7) \
559
	bn_cp_32(to, 6, from, (a1) - 7) \
560
	}
561
562
int
563
BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, BN_CTX *ctx)
564
{
565
	int top = a->top, i;
566
	int carry;
567
	BN_ULONG *r_d, *a_d = a->d;
568
	union {
569
		BN_ULONG bn[BN_NIST_224_TOP];
570
		unsigned int ui[BN_NIST_224_TOP *
571
		    sizeof(BN_ULONG) / sizeof(unsigned int)];
572
	} buf;
573
	BN_ULONG c_d[BN_NIST_224_TOP], *res;
574
	uintptr_t mask;
575
	union {
576
		bn_addsub_f f;
577
		uintptr_t p;
578
	} u;
579
	static const BIGNUM _bignum_nist_p_224_sqr = {
580
		(BN_ULONG *)_nist_p_224_sqr,
581
		sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
582
		sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
583
		0,
584
		BN_FLG_STATIC_DATA
585
	};
586
587
	field = &_bignum_nist_p_224; /* just to make sure */
588
589
	if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
590
		return BN_nnmod(r, a, field, ctx);
591
592
	i = BN_ucmp(field, a);
593
	if (i == 0) {
594
		BN_zero(r);
595
		return 1;
596
	} else if (i > 0)
597
		return (r == a) ? 1 : (BN_copy(r, a) != NULL);
598
599
	if (r != a) {
600
		if (!bn_wexpand(r, BN_NIST_224_TOP))
601
			return 0;
602
		r_d = r->d;
603
		nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
604
	} else
605
		r_d = a_d;
606
607
	memset(&buf, 0, sizeof(buf));
608
609
#if BN_BITS2==64
610
	/* copy upper 256 bits of 448 bit number ... */
611
	nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
612
	    top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
613
	/* ... and right shift by 32 to obtain upper 224 bits */
614
	nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
615
	/* truncate lower part to 224 bits too */
616
	r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
617
#else
618
	nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP,
619
	    top - BN_NIST_224_TOP, BN_NIST_224_TOP);
620
#endif
621
622
#if defined(NIST_INT64) && BN_BITS2!=64
623
	{
624
		NIST_INT64 acc;	/* accumulator */
625
		unsigned int *rp = (unsigned int *)r_d;
626
		const unsigned int *bp = (const unsigned int *)buf.ui;
627
628
		acc = rp[0];
629
		acc -= bp[7 - 7];
630
		acc -= bp[11 - 7];
631
		rp[0] = (unsigned int)acc;
632
		acc >>= 32;
633
634
		acc += rp[1];
635
		acc -= bp[8 - 7];
636
		acc -= bp[12 - 7];
637
		rp[1] = (unsigned int)acc;
638
		acc >>= 32;
639
640
		acc += rp[2];
641
		acc -= bp[9 - 7];
642
		acc -= bp[13 - 7];
643
		rp[2] = (unsigned int)acc;
644
		acc >>= 32;
645
646
		acc += rp[3];
647
		acc += bp[7 - 7];
648
		acc += bp[11 - 7];
649
		acc -= bp[10 - 7];
650
		rp[3] = (unsigned int)acc;
651
		acc >>= 32;
652
653
		acc += rp[4];
654
		acc += bp[8 - 7];
655
		acc += bp[12 - 7];
656
		acc -= bp[11 - 7];
657
		rp[4] = (unsigned int)acc;
658
		acc >>= 32;
659
660
		acc += rp[5];
661
		acc += bp[9 - 7];
662
		acc += bp[13 - 7];
663
		acc -= bp[12 - 7];
664
		rp[5] = (unsigned int)acc;
665
		acc >>= 32;
666
667
		acc += rp[6];
668
		acc += bp[10 - 7];
669
		acc -= bp[13 - 7];
670
		rp[6] = (unsigned int)acc;
671
672
		carry = (int)(acc >> 32);
673
# if BN_BITS2==64
674
		rp[7] = carry;
675
# endif
676
	}
677
#else
678
	{
679
		BN_ULONG t_d[BN_NIST_224_TOP] = {0};
680
681
		nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
682
		carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
683
		nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
684
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
685
		nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
686
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
687
		nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
688
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
689
690
#if BN_BITS2==64
691
		carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
692
#endif
693
	}
694
#endif
695
	u.f = bn_sub_words;
696
	if (carry > 0) {
697
		carry = (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
698
		    BN_NIST_224_TOP);
699
#if BN_BITS2==64
700
		carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
701
#endif
702
	} else if (carry < 0) {
703
		/* it's a bit more complicated logic in this case.
704
		 * if bn_add_words yields no carry, then result
705
		 * has to be adjusted by unconditionally *adding*
706
		 * the modulus. but if it does, then result has
707
		 * to be compared to the modulus and conditionally
708
		 * adjusted by *subtracting* the latter. */
709
		carry = (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
710
		    BN_NIST_224_TOP);
711
		mask = 0 - (uintptr_t)carry;
712
		u.p = ((uintptr_t)bn_sub_words & mask) |
713
		    ((uintptr_t)bn_add_words & ~mask);
714
	} else
715
		carry = 1;
716
717
	/* otherwise it's effectively same as in BN_nist_mod_192... */
718
	mask = 0 - (uintptr_t)(*u.f)(c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
719
	mask &= 0 - (uintptr_t)carry;
720
	res = c_d;
721
	res = (BN_ULONG *)(((uintptr_t)res & ~mask) | ((uintptr_t)r_d & mask));
722
	nist_cp_bn(r_d, res, BN_NIST_224_TOP);
723
	r->top = BN_NIST_224_TOP;
724
	bn_correct_top(r);
725
726
	return 1;
727
}
728
729
#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
730
	{ \
731
	bn_cp_32(to, 0, from, (a8) - 8) \
732
	bn_cp_32(to, 1, from, (a7) - 8) \
733
	bn_cp_32(to, 2, from, (a6) - 8) \
734
	bn_cp_32(to, 3, from, (a5) - 8) \
735
	bn_cp_32(to, 4, from, (a4) - 8) \
736
	bn_cp_32(to, 5, from, (a3) - 8) \
737
	bn_cp_32(to, 6, from, (a2) - 8) \
738
	bn_cp_32(to, 7, from, (a1) - 8) \
739
	}
740
741
int
742
BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, BN_CTX *ctx)
743
{
744
	int i, top = a->top;
745
	int carry = 0;
746
	BN_ULONG *a_d = a->d, *r_d;
747
	union {
748
		BN_ULONG bn[BN_NIST_256_TOP];
749
		unsigned int ui[BN_NIST_256_TOP *
750
		    sizeof(BN_ULONG) / sizeof(unsigned int)];
751
	} buf;
752
	BN_ULONG c_d[BN_NIST_256_TOP] = {0}, *res;
753
	uintptr_t mask;
754
	union {
755
		bn_addsub_f f;
756
		uintptr_t p;
757
	} u;
758
	static const BIGNUM _bignum_nist_p_256_sqr = {
759
		(BN_ULONG *)_nist_p_256_sqr,
760
		sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
761
		sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
762
		0,
763
		BN_FLG_STATIC_DATA
764
	};
765
766
	field = &_bignum_nist_p_256; /* just to make sure */
767
768
	if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
769
		return BN_nnmod(r, a, field, ctx);
770
771
	i = BN_ucmp(field, a);
772
	if (i == 0) {
773
		BN_zero(r);
774
		return 1;
775
	} else if (i > 0)
776
		return (r == a) ? 1 : (BN_copy(r, a) != NULL);
777
778
	if (r != a) {
779
		if (!bn_wexpand(r, BN_NIST_256_TOP))
780
			return 0;
781
		r_d = r->d;
782
		nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
783
	} else
784
		r_d = a_d;
785
786
	nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP,
787
	    top - BN_NIST_256_TOP, BN_NIST_256_TOP);
788
789
#if defined(NIST_INT64)
790
	{
791
		NIST_INT64 acc;	/* accumulator */
792
		unsigned int *rp = (unsigned int *)r_d;
793
		const unsigned int *bp = (const unsigned int *)buf.ui;
794
795
		acc = rp[0];
796
		acc += bp[8 - 8];
797
		acc += bp[9 - 8];
798
		acc -= bp[11 - 8];
799
		acc -= bp[12 - 8];
800
		acc -= bp[13 - 8];
801
		acc -= bp[14 - 8];
802
		rp[0] = (unsigned int)acc;
803
		acc >>= 32;
804
805
		acc += rp[1];
806
		acc += bp[9 - 8];
807
		acc += bp[10 - 8];
808
		acc -= bp[12 - 8];
809
		acc -= bp[13 - 8];
810
		acc -= bp[14 - 8];
811
		acc -= bp[15 - 8];
812
		rp[1] = (unsigned int)acc;
813
		acc >>= 32;
814
815
		acc += rp[2];
816
		acc += bp[10 - 8];
817
		acc += bp[11 - 8];
818
		acc -= bp[13 - 8];
819
		acc -= bp[14 - 8];
820
		acc -= bp[15 - 8];
821
		rp[2] = (unsigned int)acc;
822
		acc >>= 32;
823
824
		acc += rp[3];
825
		acc += bp[11 - 8];
826
		acc += bp[11 - 8];
827
		acc += bp[12 - 8];
828
		acc += bp[12 - 8];
829
		acc += bp[13 - 8];
830
		acc -= bp[15 - 8];
831
		acc -= bp[8 - 8];
832
		acc -= bp[9 - 8];
833
		rp[3] = (unsigned int)acc;
834
		acc >>= 32;
835
836
		acc += rp[4];
837
		acc += bp[12 - 8];
838
		acc += bp[12 - 8];
839
		acc += bp[13 - 8];
840
		acc += bp[13 - 8];
841
		acc += bp[14 - 8];
842
		acc -= bp[9 - 8];
843
		acc -= bp[10 - 8];
844
		rp[4] = (unsigned int)acc;
845
		acc >>= 32;
846
847
		acc += rp[5];
848
		acc += bp[13 - 8];
849
		acc += bp[13 - 8];
850
		acc += bp[14 - 8];
851
		acc += bp[14 - 8];
852
		acc += bp[15 - 8];
853
		acc -= bp[10 - 8];
854
		acc -= bp[11 - 8];
855
		rp[5] = (unsigned int)acc;
856
		acc >>= 32;
857
858
		acc += rp[6];
859
		acc += bp[14 - 8];
860
		acc += bp[14 - 8];
861
		acc += bp[15 - 8];
862
		acc += bp[15 - 8];
863
		acc += bp[14 - 8];
864
		acc += bp[13 - 8];
865
		acc -= bp[8 - 8];
866
		acc -= bp[9 - 8];
867
		rp[6] = (unsigned int)acc;
868
		acc >>= 32;
869
870
		acc += rp[7];
871
		acc += bp[15 - 8];
872
		acc += bp[15 - 8];
873
		acc += bp[15 - 8];
874
		acc += bp[8 - 8];
875
		acc -= bp[10 - 8];
876
		acc -= bp[11 - 8];
877
		acc -= bp[12 - 8];
878
		acc -= bp[13 - 8];
879
		rp[7] = (unsigned int)acc;
880
881
		carry = (int)(acc >> 32);
882
	}
883
#else
884
	{
885
		BN_ULONG t_d[BN_NIST_256_TOP] = {0};
886
887
		/*S1*/
888
		nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
889
		/*S2*/
890
		nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
891
		carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
892
		/* left shift */
893
		{
894
			BN_ULONG *ap, t, c;
895
			ap = t_d;
896
			c = 0;
897
			for (i = BN_NIST_256_TOP; i != 0; --i) {
898
				t = *ap;
899
				*(ap++) = ((t << 1) | c) & BN_MASK2;
900
				c = (t & BN_TBIT) ? 1 : 0;
901
			}
902
			carry <<= 1;
903
			carry |= c;
904
		}
905
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
906
		/*S3*/
907
		nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
908
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
909
		/*S4*/
910
		nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
911
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
912
		/*D1*/
913
		nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
914
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
915
		/*D2*/
916
		nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
917
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
918
		/*D3*/
919
		nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
920
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
921
		/*D4*/
922
		nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
923
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
924
925
	}
926
#endif
927
	/* see BN_nist_mod_224 for explanation */
928
	u.f = bn_sub_words;
929
	if (carry > 0)
930
		carry = (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
931
		    BN_NIST_256_TOP);
932
	else if (carry < 0) {
933
		carry = (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
934
		    BN_NIST_256_TOP);
935
		mask = 0 - (uintptr_t)carry;
936
		u.p = ((uintptr_t)bn_sub_words & mask) |
937
		    ((uintptr_t)bn_add_words & ~mask);
938
	} else
939
		carry = 1;
940
941
	mask = 0 - (uintptr_t)(*u.f)(c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
942
	mask &= 0 - (uintptr_t)carry;
943
	res = c_d;
944
	res = (BN_ULONG *)(((uintptr_t)res & ~mask) | ((uintptr_t)r_d & mask));
945
	nist_cp_bn(r_d, res, BN_NIST_256_TOP);
946
	r->top = BN_NIST_256_TOP;
947
	bn_correct_top(r);
948
949
	return 1;
950
}
951
952
#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
953
	{ \
954
	bn_cp_32(to, 0, from,  (a12) - 12) \
955
	bn_cp_32(to, 1, from,  (a11) - 12) \
956
	bn_cp_32(to, 2, from,  (a10) - 12) \
957
	bn_cp_32(to, 3, from,  (a9) - 12)  \
958
	bn_cp_32(to, 4, from,  (a8) - 12)  \
959
	bn_cp_32(to, 5, from,  (a7) - 12)  \
960
	bn_cp_32(to, 6, from,  (a6) - 12)  \
961
	bn_cp_32(to, 7, from,  (a5) - 12)  \
962
	bn_cp_32(to, 8, from,  (a4) - 12)  \
963
	bn_cp_32(to, 9, from,  (a3) - 12)  \
964
	bn_cp_32(to, 10, from, (a2) - 12)  \
965
	bn_cp_32(to, 11, from, (a1) - 12)  \
966
	}
967
968
int
969
BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, BN_CTX *ctx)
970
{
971
	int i, top = a->top;
972
	int carry = 0;
973
	BN_ULONG *r_d, *a_d = a->d;
974
	union {
975
		BN_ULONG bn[BN_NIST_384_TOP];
976
		unsigned int ui[BN_NIST_384_TOP *
977
		    sizeof(BN_ULONG) / sizeof(unsigned int)];
978
	} buf;
979
	BN_ULONG c_d[BN_NIST_384_TOP], *res;
980
	uintptr_t mask;
981
	union {
982
		bn_addsub_f f;
983
		uintptr_t p;
984
	} u;
985
	static const BIGNUM _bignum_nist_p_384_sqr = {
986
		(BN_ULONG *)_nist_p_384_sqr,
987
		sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
988
		sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
989
		0,
990
		BN_FLG_STATIC_DATA
991
	};
992
993
	field = &_bignum_nist_p_384; /* just to make sure */
994
995
	if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
996
		return BN_nnmod(r, a, field, ctx);
997
998
	i = BN_ucmp(field, a);
999
	if (i == 0) {
1000
		BN_zero(r);
1001
		return 1;
1002
	} else if (i > 0)
1003
		return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1004
1005
	if (r != a) {
1006
		if (!bn_wexpand(r, BN_NIST_384_TOP))
1007
			return 0;
1008
		r_d = r->d;
1009
		nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
1010
	} else
1011
		r_d = a_d;
1012
1013
	nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP,
1014
	    top - BN_NIST_384_TOP, BN_NIST_384_TOP);
1015
1016
#if defined(NIST_INT64)
1017
	{
1018
		NIST_INT64 acc;	/* accumulator */
1019
		unsigned int *rp = (unsigned int *)r_d;
1020
		const unsigned int *bp = (const unsigned int *)buf.ui;
1021
1022
		acc = rp[0];
1023
		acc += bp[12 - 12];
1024
		acc += bp[21 - 12];
1025
		acc += bp[20 - 12];
1026
		acc -= bp[23 - 12];
1027
		rp[0] = (unsigned int)acc;
1028
		acc >>= 32;
1029
1030
		acc += rp[1];
1031
		acc += bp[13 - 12];
1032
		acc += bp[22 - 12];
1033
		acc += bp[23 - 12];
1034
		acc -= bp[12 - 12];
1035
		acc -= bp[20 - 12];
1036
		rp[1] = (unsigned int)acc;
1037
		acc >>= 32;
1038
1039
		acc += rp[2];
1040
		acc += bp[14 - 12];
1041
		acc += bp[23 - 12];
1042
		acc -= bp[13 - 12];
1043
		acc -= bp[21 - 12];
1044
		rp[2] = (unsigned int)acc;
1045
		acc >>= 32;
1046
1047
		acc += rp[3];
1048
		acc += bp[15 - 12];
1049
		acc += bp[12 - 12];
1050
		acc += bp[20 - 12];
1051
		acc += bp[21 - 12];
1052
		acc -= bp[14 - 12];
1053
		acc -= bp[22 - 12];
1054
		acc -= bp[23 - 12];
1055
		rp[3] = (unsigned int)acc;
1056
		acc >>= 32;
1057
1058
		acc += rp[4];
1059
		acc += bp[21 - 12];
1060
		acc += bp[21 - 12];
1061
		acc += bp[16 - 12];
1062
		acc += bp[13 - 12];
1063
		acc += bp[12 - 12];
1064
		acc += bp[20 - 12];
1065
		acc += bp[22 - 12];
1066
		acc -= bp[15 - 12];
1067
		acc -= bp[23 - 12];
1068
		acc -= bp[23 - 12];
1069
		rp[4] = (unsigned int)acc;
1070
		acc >>= 32;
1071
1072
		acc += rp[5];
1073
		acc += bp[22 - 12];
1074
		acc += bp[22 - 12];
1075
		acc += bp[17 - 12];
1076
		acc += bp[14 - 12];
1077
		acc += bp[13 - 12];
1078
		acc += bp[21 - 12];
1079
		acc += bp[23 - 12];
1080
		acc -= bp[16 - 12];
1081
		rp[5] = (unsigned int)acc;
1082
		acc >>= 32;
1083
1084
		acc += rp[6];
1085
		acc += bp[23 - 12];
1086
		acc += bp[23 - 12];
1087
		acc += bp[18 - 12];
1088
		acc += bp[15 - 12];
1089
		acc += bp[14 - 12];
1090
		acc += bp[22 - 12];
1091
		acc -= bp[17 - 12];
1092
		rp[6] = (unsigned int)acc;
1093
		acc >>= 32;
1094
1095
		acc += rp[7];
1096
		acc += bp[19 - 12];
1097
		acc += bp[16 - 12];
1098
		acc += bp[15 - 12];
1099
		acc += bp[23 - 12];
1100
		acc -= bp[18 - 12];
1101
		rp[7] = (unsigned int)acc;
1102
		acc >>= 32;
1103
1104
		acc += rp[8];
1105
		acc += bp[20 - 12];
1106
		acc += bp[17 - 12];
1107
		acc += bp[16 - 12];
1108
		acc -= bp[19 - 12];
1109
		rp[8] = (unsigned int)acc;
1110
		acc >>= 32;
1111
1112
		acc += rp[9];
1113
		acc += bp[21 - 12];
1114
		acc += bp[18 - 12];
1115
		acc += bp[17 - 12];
1116
		acc -= bp[20 - 12];
1117
		rp[9] = (unsigned int)acc;
1118
		acc >>= 32;
1119
1120
		acc += rp[10];
1121
		acc += bp[22 - 12];
1122
		acc += bp[19 - 12];
1123
		acc += bp[18 - 12];
1124
		acc -= bp[21 - 12];
1125
		rp[10] = (unsigned int)acc;
1126
		acc >>= 32;
1127
1128
		acc += rp[11];
1129
		acc += bp[23 - 12];
1130
		acc += bp[20 - 12];
1131
		acc += bp[19 - 12];
1132
		acc -= bp[22 - 12];
1133
		rp[11] = (unsigned int)acc;
1134
1135
		carry = (int)(acc >> 32);
1136
	}
1137
#else
1138
	{
1139
		BN_ULONG t_d[BN_NIST_384_TOP] = {0};
1140
1141
		/*S1*/
1142
		nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4,
1143
		    21 - 4);
1144
		/* left shift */
1145
		{
1146
			BN_ULONG *ap, t, c;
1147
			ap = t_d;
1148
			c = 0;
1149
			for (i = 3; i != 0; --i) {
1150
				t= *ap;
1151
				*(ap++) = ((t << 1)|c) & BN_MASK2;
1152
				c = (t & BN_TBIT) ? 1 : 0;
1153
			}
1154
			*ap = c;
1155
		}
1156
		carry = (int)bn_add_words(r_d + (128 / BN_BITS2),
1157
		    r_d + (128 / BN_BITS2), t_d, BN_NIST_256_TOP);
1158
		/*S2 */
1159
		carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
1160
		/*S3*/
1161
		nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12,
1162
		    23, 22, 21);
1163
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1164
		/*S4*/
1165
		nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20,
1166
		    0, 23, 0);
1167
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1168
		/*S5*/
1169
		nist_set_384(t_d, buf.bn, 0,0, 0,0, 23, 22, 21, 20, 0,0, 0, 0);
1170
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1171
		/*S6*/
1172
		nist_set_384(t_d, buf.bn, 0,0, 0,0, 0,0, 23, 22, 21, 0,0, 20);
1173
		carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1174
		/*D1*/
1175
		nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14,
1176
		    13, 12, 23);
1177
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1178
		/*D2*/
1179
		nist_set_384(t_d, buf.bn, 0,0, 0,0, 0,0, 0,23, 22, 21, 20, 0);
1180
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1181
		/*D3*/
1182
		nist_set_384(t_d, buf.bn, 0,0, 0,0, 0,0, 0,23, 23, 0,0, 0);
1183
		carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1184
1185
	}
1186
#endif
1187
	/* see BN_nist_mod_224 for explanation */
1188
	u.f = bn_sub_words;
1189
	if (carry > 0)
1190
		carry = (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
1191
		    BN_NIST_384_TOP);
1192
	else if (carry < 0) {
1193
		carry = (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
1194
		    BN_NIST_384_TOP);
1195
		mask = 0 - (uintptr_t)carry;
1196
		u.p = ((uintptr_t)bn_sub_words & mask) |
1197
		    ((uintptr_t)bn_add_words & ~mask);
1198
	} else
1199
		carry = 1;
1200
1201
	mask = 0 - (uintptr_t)(*u.f)(c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
1202
	mask &= 0 - (uintptr_t)carry;
1203
	res = c_d;
1204
	res = (BN_ULONG *)(((uintptr_t)res & ~mask) | ((uintptr_t)r_d & mask));
1205
	nist_cp_bn(r_d, res, BN_NIST_384_TOP);
1206
	r->top = BN_NIST_384_TOP;
1207
	bn_correct_top(r);
1208
1209
	return 1;
1210
}
1211
1212
#define BN_NIST_521_RSHIFT	(521%BN_BITS2)
1213
#define BN_NIST_521_LSHIFT	(BN_BITS2-BN_NIST_521_RSHIFT)
1214
#define BN_NIST_521_TOP_MASK	((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
1215
1216
int
1217
BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, BN_CTX *ctx)
1218
{
1219
	int top = a->top, i;
1220
	BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
1221
	uintptr_t mask;
1222
	static const BIGNUM _bignum_nist_p_521_sqr = {
1223
		(BN_ULONG *)_nist_p_521_sqr,
1224
		sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
1225
		sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
1226
		0,
1227
		BN_FLG_STATIC_DATA
1228
	};
1229
1230
	field = &_bignum_nist_p_521; /* just to make sure */
1231
1232
	if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
1233
		return BN_nnmod(r, a, field, ctx);
1234
1235
	i = BN_ucmp(field, a);
1236
	if (i == 0) {
1237
		BN_zero(r);
1238
		return 1;
1239
	} else if (i > 0)
1240
		return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1241
1242
	if (r != a) {
1243
		if (!bn_wexpand(r, BN_NIST_521_TOP))
1244
			return 0;
1245
		r_d = r->d;
1246
		nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
1247
	} else
1248
		r_d = a_d;
1249
1250
	/* upper 521 bits, copy ... */
1251
	nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
1252
	    top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
1253
	/* ... and right shift */
1254
	for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
1255
		tmp = val >> BN_NIST_521_RSHIFT;
1256
		val = t_d[i + 1];
1257
		t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
1258
	}
1259
	t_d[i] = val >> BN_NIST_521_RSHIFT;
1260
	/* lower 521 bits */
1261
	r_d[i] &= BN_NIST_521_TOP_MASK;
1262
1263
	bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
1264
	mask = 0 - (uintptr_t)bn_sub_words(t_d, r_d, _nist_p_521,
1265
	    BN_NIST_521_TOP);
1266
	res = t_d;
1267
	res = (BN_ULONG *)(((uintptr_t)res & ~mask) | ((uintptr_t)r_d & mask));
1268
	nist_cp_bn(r_d, res, BN_NIST_521_TOP);
1269
	r->top = BN_NIST_521_TOP;
1270
	bn_correct_top(r);
1271
1272
	return 1;
1273
}