2 * Copyright 2002-2016 The OpenSSL Project Authors. All Rights Reserved.
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
11 #include "internal/cryptlib.h"
13 #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
14 #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
15 #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
16 #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
17 #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
19 /* pre-computed tables are "carry-less" values of modulus*(i+1) */
21 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
22 {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
23 {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
24 {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
27 static const BN_ULONG _nist_p_192_sqr[] = {
28 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
29 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
32 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
33 {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL,
34 0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL},
35 {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL,
36 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is
40 static const BN_ULONG _nist_p_224_sqr[] = {
41 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
42 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
43 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
47 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
48 {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL,
49 0x0000000000000000ULL, 0xFFFFFFFF00000001ULL},
50 {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL,
51 0x0000000000000000ULL, 0xFFFFFFFE00000002ULL},
52 {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL,
53 0x0000000000000000ULL, 0xFFFFFFFD00000003ULL},
54 {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL,
55 0x0000000000000000ULL, 0xFFFFFFFC00000004ULL},
56 {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL,
57 0x0000000000000000ULL, 0xFFFFFFFB00000005ULL},
60 static const BN_ULONG _nist_p_256_sqr[] = {
61 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
62 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
63 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
64 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
67 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
68 {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL,
69 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
70 {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
71 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
72 {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL,
73 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
74 {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL,
75 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
76 {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL,
77 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
80 static const BN_ULONG _nist_p_384_sqr[] = {
81 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL,
82 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL,
83 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
84 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
87 static const BN_ULONG _nist_p_521[] =
88 { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
89 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
90 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
91 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
95 static const BN_ULONG _nist_p_521_sqr[] = {
96 0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
97 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
98 0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL,
99 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
100 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
101 0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL
104 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
105 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
106 {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
107 {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
110 static const BN_ULONG _nist_p_192_sqr[] = {
111 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
112 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
115 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
116 {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF,
117 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
118 {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE,
119 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
122 static const BN_ULONG _nist_p_224_sqr[] = {
123 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
124 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002,
125 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
126 0xFFFFFFFF, 0xFFFFFFFF
129 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
130 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000,
131 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF},
132 {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001,
133 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE},
134 {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002,
135 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD},
136 {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003,
137 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC},
138 {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004,
139 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB},
142 static const BN_ULONG _nist_p_256_sqr[] = {
143 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
144 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001,
145 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001,
146 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE
149 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
150 {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
151 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
152 {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
153 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
154 {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF,
155 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
156 {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF,
157 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
158 {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF,
159 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
162 static const BN_ULONG _nist_p_384_sqr[] = {
163 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE,
164 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000,
165 0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
166 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
169 static const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
170 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
171 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
172 0xFFFFFFFF, 0x000001FF
175 static const BN_ULONG _nist_p_521_sqr[] = {
176 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
177 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
178 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF,
179 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
180 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
181 0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF
184 # error "unsupported BN_BITS2"
187 static const BIGNUM _bignum_nist_p_192 = {
188 (BN_ULONG *)_nist_p_192[0],
195 static const BIGNUM _bignum_nist_p_224 = {
196 (BN_ULONG *)_nist_p_224[0],
203 static const BIGNUM _bignum_nist_p_256 = {
204 (BN_ULONG *)_nist_p_256[0],
211 static const BIGNUM _bignum_nist_p_384 = {
212 (BN_ULONG *)_nist_p_384[0],
219 static const BIGNUM _bignum_nist_p_521 = {
220 (BN_ULONG *)_nist_p_521,
227 const BIGNUM *BN_get0_nist_prime_192(void)
229 return &_bignum_nist_p_192;
232 const BIGNUM *BN_get0_nist_prime_224(void)
234 return &_bignum_nist_p_224;
237 const BIGNUM *BN_get0_nist_prime_256(void)
239 return &_bignum_nist_p_256;
242 const BIGNUM *BN_get0_nist_prime_384(void)
244 return &_bignum_nist_p_384;
247 const BIGNUM *BN_get0_nist_prime_521(void)
249 return &_bignum_nist_p_521;
252 static void nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max)
257 OPENSSL_assert(top <= max);
259 for (i = 0; i < top; i++)
265 static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
269 for (i = 0; i < top; i++)
274 # define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
275 # define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0;
277 * two following macros are implemented under assumption that they
278 * are called in a sequence with *ascending* n, i.e. as they are...
280 # 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))\
281 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
282 # define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
283 # define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
284 # if defined(L_ENDIAN)
285 # if defined(__arch64__)
286 # define NIST_INT64 long
288 # define NIST_INT64 long long
292 # define bn_cp_64(to, n, from, m) \
294 bn_cp_32(to, (n)*2, from, (m)*2); \
295 bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
297 # define bn_64_set_0(to, n) \
299 bn_32_set_0(to, (n)*2); \
300 bn_32_set_0(to, (n)*2+1); \
302 # define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
303 # define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
304 # if defined(_WIN32) && !defined(__GNUC__)
305 # define NIST_INT64 __int64
306 # elif defined(BN_LLONG)
307 # define NIST_INT64 long long
309 #endif /* BN_BITS2 != 64 */
311 #define nist_set_192(to, from, a1, a2, a3) \
313 bn_cp_64(to, 0, from, (a3) - 3) \
314 bn_cp_64(to, 1, from, (a2) - 3) \
315 bn_cp_64(to, 2, from, (a1) - 3) \
318 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
323 register BN_ULONG *r_d, *a_d = a->d;
325 BN_ULONG bn[BN_NIST_192_TOP];
326 unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) /
327 sizeof(unsigned int)];
329 BN_ULONG c_d[BN_NIST_192_TOP], *res;
331 static const BIGNUM _bignum_nist_p_192_sqr = {
332 (BN_ULONG *)_nist_p_192_sqr,
333 OSSL_NELEM(_nist_p_192_sqr),
334 OSSL_NELEM(_nist_p_192_sqr),
335 0, BN_FLG_STATIC_DATA
338 field = &_bignum_nist_p_192; /* just to make sure */
340 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
341 return BN_nnmod(r, a, field, ctx);
343 i = BN_ucmp(field, a);
348 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
351 if (!bn_wexpand(r, BN_NIST_192_TOP))
354 nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
358 nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
361 #if defined(NIST_INT64)
363 NIST_INT64 acc; /* accumulator */
364 unsigned int *rp = (unsigned int *)r_d;
365 const unsigned int *bp = (const unsigned int *)buf.ui;
368 acc += bp[3 * 2 - 6];
369 acc += bp[5 * 2 - 6];
370 rp[0] = (unsigned int)acc;
374 acc += bp[3 * 2 - 5];
375 acc += bp[5 * 2 - 5];
376 rp[1] = (unsigned int)acc;
380 acc += bp[3 * 2 - 6];
381 acc += bp[4 * 2 - 6];
382 acc += bp[5 * 2 - 6];
383 rp[2] = (unsigned int)acc;
387 acc += bp[3 * 2 - 5];
388 acc += bp[4 * 2 - 5];
389 acc += bp[5 * 2 - 5];
390 rp[3] = (unsigned int)acc;
394 acc += bp[4 * 2 - 6];
395 acc += bp[5 * 2 - 6];
396 rp[4] = (unsigned int)acc;
400 acc += bp[4 * 2 - 5];
401 acc += bp[5 * 2 - 5];
402 rp[5] = (unsigned int)acc;
404 carry = (int)(acc >> 32);
408 BN_ULONG t_d[BN_NIST_192_TOP];
410 nist_set_192(t_d, buf.bn, 0, 3, 3);
411 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
412 nist_set_192(t_d, buf.bn, 4, 4, 0);
413 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
414 nist_set_192(t_d, buf.bn, 5, 5, 5)
415 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
420 (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
426 * we need 'if (carry==0 || result>=modulus) result-=modulus;'
427 * as comparison implies subtraction, we can write
428 * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
429 * this is what happens below, but without explicit if:-) a.
432 0 - (PTR_SIZE_INT) bn_sub_words(c_d, r_d, _nist_p_192[0],
434 mask &= 0 - (PTR_SIZE_INT) carry;
437 (((PTR_SIZE_INT) res & ~mask) | ((PTR_SIZE_INT) r_d & mask));
438 nist_cp_bn(r_d, res, BN_NIST_192_TOP);
439 r->top = BN_NIST_192_TOP;
445 typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
446 const BN_ULONG *, int);
448 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
450 bn_cp_32(to, 0, from, (a7) - 7) \
451 bn_cp_32(to, 1, from, (a6) - 7) \
452 bn_cp_32(to, 2, from, (a5) - 7) \
453 bn_cp_32(to, 3, from, (a4) - 7) \
454 bn_cp_32(to, 4, from, (a3) - 7) \
455 bn_cp_32(to, 5, from, (a2) - 7) \
456 bn_cp_32(to, 6, from, (a1) - 7) \
459 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
464 BN_ULONG *r_d, *a_d = a->d;
466 BN_ULONG bn[BN_NIST_224_TOP];
467 unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) /
468 sizeof(unsigned int)];
470 BN_ULONG c_d[BN_NIST_224_TOP], *res;
476 static const BIGNUM _bignum_nist_p_224_sqr = {
477 (BN_ULONG *)_nist_p_224_sqr,
478 OSSL_NELEM(_nist_p_224_sqr),
479 OSSL_NELEM(_nist_p_224_sqr),
480 0, BN_FLG_STATIC_DATA
483 field = &_bignum_nist_p_224; /* just to make sure */
485 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
486 return BN_nnmod(r, a, field, ctx);
488 i = BN_ucmp(field, a);
493 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
496 if (!bn_wexpand(r, BN_NIST_224_TOP))
499 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
504 /* copy upper 256 bits of 448 bit number ... */
505 nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
506 top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
507 /* ... and right shift by 32 to obtain upper 224 bits */
508 nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
509 /* truncate lower part to 224 bits too */
510 r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
512 nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
516 #if defined(NIST_INT64) && BN_BITS2!=64
518 NIST_INT64 acc; /* accumulator */
519 unsigned int *rp = (unsigned int *)r_d;
520 const unsigned int *bp = (const unsigned int *)buf.ui;
525 rp[0] = (unsigned int)acc;
531 rp[1] = (unsigned int)acc;
537 rp[2] = (unsigned int)acc;
544 rp[3] = (unsigned int)acc;
551 rp[4] = (unsigned int)acc;
558 rp[5] = (unsigned int)acc;
564 rp[6] = (unsigned int)acc;
566 carry = (int)(acc >> 32);
573 BN_ULONG t_d[BN_NIST_224_TOP];
575 nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
576 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
577 nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
578 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
579 nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
580 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
581 nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
582 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
585 carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
592 (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
595 carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
597 } else if (carry < 0) {
599 * it's a bit more complicated logic in this case. if bn_add_words
600 * yields no carry, then result has to be adjusted by unconditionally
601 * *adding* the modulus. but if it does, then result has to be
602 * compared to the modulus and conditionally adjusted by
603 * *subtracting* the latter.
606 (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
608 mask = 0 - (PTR_SIZE_INT) carry;
609 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
610 ((PTR_SIZE_INT) bn_add_words & ~mask);
614 /* otherwise it's effectively same as in BN_nist_mod_192... */
616 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
617 mask &= 0 - (PTR_SIZE_INT) carry;
619 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
620 ((PTR_SIZE_INT) r_d & mask));
621 nist_cp_bn(r_d, res, BN_NIST_224_TOP);
622 r->top = BN_NIST_224_TOP;
628 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
630 bn_cp_32(to, 0, from, (a8) - 8) \
631 bn_cp_32(to, 1, from, (a7) - 8) \
632 bn_cp_32(to, 2, from, (a6) - 8) \
633 bn_cp_32(to, 3, from, (a5) - 8) \
634 bn_cp_32(to, 4, from, (a4) - 8) \
635 bn_cp_32(to, 5, from, (a3) - 8) \
636 bn_cp_32(to, 6, from, (a2) - 8) \
637 bn_cp_32(to, 7, from, (a1) - 8) \
640 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
645 register BN_ULONG *a_d = a->d, *r_d;
647 BN_ULONG bn[BN_NIST_256_TOP];
648 unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) /
649 sizeof(unsigned int)];
651 BN_ULONG c_d[BN_NIST_256_TOP], *res;
657 static const BIGNUM _bignum_nist_p_256_sqr = {
658 (BN_ULONG *)_nist_p_256_sqr,
659 OSSL_NELEM(_nist_p_256_sqr),
660 OSSL_NELEM(_nist_p_256_sqr),
661 0, BN_FLG_STATIC_DATA
664 field = &_bignum_nist_p_256; /* just to make sure */
666 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
667 return BN_nnmod(r, a, field, ctx);
669 i = BN_ucmp(field, a);
674 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
677 if (!bn_wexpand(r, BN_NIST_256_TOP))
680 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
684 nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
687 #if defined(NIST_INT64)
689 NIST_INT64 acc; /* accumulator */
690 unsigned int *rp = (unsigned int *)r_d;
691 const unsigned int *bp = (const unsigned int *)buf.ui;
700 rp[0] = (unsigned int)acc;
710 rp[1] = (unsigned int)acc;
719 rp[2] = (unsigned int)acc;
731 rp[3] = (unsigned int)acc;
742 rp[4] = (unsigned int)acc;
753 rp[5] = (unsigned int)acc;
765 rp[6] = (unsigned int)acc;
777 rp[7] = (unsigned int)acc;
779 carry = (int)(acc >> 32);
783 BN_ULONG t_d[BN_NIST_256_TOP];
788 nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
792 nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
793 carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
796 register BN_ULONG *ap, t, c;
799 for (i = BN_NIST_256_TOP; i != 0; --i) {
801 *(ap++) = ((t << 1) | c) & BN_MASK2;
802 c = (t & BN_TBIT) ? 1 : 0;
807 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
811 nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
812 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
816 nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
817 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
821 nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
822 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
826 nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
827 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
831 nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
832 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
836 nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
837 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
841 /* see BN_nist_mod_224 for explanation */
845 (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
847 else if (carry < 0) {
849 (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
851 mask = 0 - (PTR_SIZE_INT) carry;
852 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
853 ((PTR_SIZE_INT) bn_add_words & ~mask);
858 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
859 mask &= 0 - (PTR_SIZE_INT) carry;
861 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
862 ((PTR_SIZE_INT) r_d & mask));
863 nist_cp_bn(r_d, res, BN_NIST_256_TOP);
864 r->top = BN_NIST_256_TOP;
870 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
872 bn_cp_32(to, 0, from, (a12) - 12) \
873 bn_cp_32(to, 1, from, (a11) - 12) \
874 bn_cp_32(to, 2, from, (a10) - 12) \
875 bn_cp_32(to, 3, from, (a9) - 12) \
876 bn_cp_32(to, 4, from, (a8) - 12) \
877 bn_cp_32(to, 5, from, (a7) - 12) \
878 bn_cp_32(to, 6, from, (a6) - 12) \
879 bn_cp_32(to, 7, from, (a5) - 12) \
880 bn_cp_32(to, 8, from, (a4) - 12) \
881 bn_cp_32(to, 9, from, (a3) - 12) \
882 bn_cp_32(to, 10, from, (a2) - 12) \
883 bn_cp_32(to, 11, from, (a1) - 12) \
886 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
891 register BN_ULONG *r_d, *a_d = a->d;
893 BN_ULONG bn[BN_NIST_384_TOP];
894 unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) /
895 sizeof(unsigned int)];
897 BN_ULONG c_d[BN_NIST_384_TOP], *res;
903 static const BIGNUM _bignum_nist_p_384_sqr = {
904 (BN_ULONG *)_nist_p_384_sqr,
905 OSSL_NELEM(_nist_p_384_sqr),
906 OSSL_NELEM(_nist_p_384_sqr),
907 0, BN_FLG_STATIC_DATA
910 field = &_bignum_nist_p_384; /* just to make sure */
912 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
913 return BN_nnmod(r, a, field, ctx);
915 i = BN_ucmp(field, a);
920 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
923 if (!bn_wexpand(r, BN_NIST_384_TOP))
926 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
930 nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
933 #if defined(NIST_INT64)
935 NIST_INT64 acc; /* accumulator */
936 unsigned int *rp = (unsigned int *)r_d;
937 const unsigned int *bp = (const unsigned int *)buf.ui;
944 rp[0] = (unsigned int)acc;
953 rp[1] = (unsigned int)acc;
961 rp[2] = (unsigned int)acc;
972 rp[3] = (unsigned int)acc;
986 rp[4] = (unsigned int)acc;
998 rp[5] = (unsigned int)acc;
1009 rp[6] = (unsigned int)acc;
1018 rp[7] = (unsigned int)acc;
1026 rp[8] = (unsigned int)acc;
1034 rp[9] = (unsigned int)acc;
1042 rp[10] = (unsigned int)acc;
1050 rp[11] = (unsigned int)acc;
1052 carry = (int)(acc >> 32);
1056 BN_ULONG t_d[BN_NIST_384_TOP];
1061 nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
1064 register BN_ULONG *ap, t, c;
1067 for (i = 3; i != 0; --i) {
1069 *(ap++) = ((t << 1) | c) & BN_MASK2;
1070 c = (t & BN_TBIT) ? 1 : 0;
1075 (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
1076 t_d, BN_NIST_256_TOP);
1080 carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
1084 nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,
1086 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1090 nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23,
1092 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1096 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
1097 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1101 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
1102 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1106 nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
1108 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1112 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
1113 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1117 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
1118 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1122 /* see BN_nist_mod_224 for explanation */
1126 (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
1128 else if (carry < 0) {
1130 (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
1132 mask = 0 - (PTR_SIZE_INT) carry;
1133 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
1134 ((PTR_SIZE_INT) bn_add_words & ~mask);
1139 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
1140 mask &= 0 - (PTR_SIZE_INT) carry;
1142 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1143 ((PTR_SIZE_INT) r_d & mask));
1144 nist_cp_bn(r_d, res, BN_NIST_384_TOP);
1145 r->top = BN_NIST_384_TOP;
1151 #define BN_NIST_521_RSHIFT (521%BN_BITS2)
1152 #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT)
1153 #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
1155 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1158 int top = a->top, i;
1159 BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
1161 static const BIGNUM _bignum_nist_p_521_sqr = {
1162 (BN_ULONG *)_nist_p_521_sqr,
1163 OSSL_NELEM(_nist_p_521_sqr),
1164 OSSL_NELEM(_nist_p_521_sqr),
1165 0, BN_FLG_STATIC_DATA
1168 field = &_bignum_nist_p_521; /* just to make sure */
1170 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
1171 return BN_nnmod(r, a, field, ctx);
1173 i = BN_ucmp(field, a);
1178 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1181 if (!bn_wexpand(r, BN_NIST_521_TOP))
1184 nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
1188 /* upper 521 bits, copy ... */
1189 nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
1190 top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
1191 /* ... and right shift */
1192 for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
1195 * MSC ARM compiler [version 2013, presumably even earlier,
1196 * much earlier] miscompiles this code, but not one in
1197 * #else section. See RT#3541.
1199 tmp = val >> BN_NIST_521_RSHIFT;
1201 t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
1203 t_d[i] = (val >> BN_NIST_521_RSHIFT |
1204 (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2;
1208 t_d[i] = val >> BN_NIST_521_RSHIFT;
1209 /* lower 521 bits */
1210 r_d[i] &= BN_NIST_521_TOP_MASK;
1212 bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
1214 0 - (PTR_SIZE_INT) bn_sub_words(t_d, r_d, _nist_p_521,
1217 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1218 ((PTR_SIZE_INT) r_d & mask));
1219 nist_cp_bn(r_d, res, BN_NIST_521_TOP);
1220 r->top = BN_NIST_521_TOP;
1226 int (*BN_nist_mod_func(const BIGNUM *p)) (BIGNUM *r, const BIGNUM *a,
1227 const BIGNUM *field, BN_CTX *ctx) {
1228 if (BN_ucmp(&_bignum_nist_p_192, p) == 0)
1229 return BN_nist_mod_192;
1230 if (BN_ucmp(&_bignum_nist_p_224, p) == 0)
1231 return BN_nist_mod_224;
1232 if (BN_ucmp(&_bignum_nist_p_256, p) == 0)
1233 return BN_nist_mod_256;
1234 if (BN_ucmp(&_bignum_nist_p_384, p) == 0)
1235 return BN_nist_mod_384;
1236 if (BN_ucmp(&_bignum_nist_p_521, p) == 0)
1237 return BN_nist_mod_521;