2 * Written by Nils Larsch for the OpenSSL project
4 /* ====================================================================
5 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in
16 * the documentation and/or other materials provided with the
19 * 3. All advertising materials mentioning features or use of this
20 * software must display the following acknowledgment:
21 * "This product includes software developed by the OpenSSL Project
22 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
24 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
25 * endorse or promote products derived from this software without
26 * prior written permission. For written permission, please contact
27 * openssl-core@openssl.org.
29 * 5. Products derived from this software may not be called "OpenSSL"
30 * nor may "OpenSSL" appear in their names without prior written
31 * permission of the OpenSSL Project.
33 * 6. Redistributions of any form whatsoever must retain the following
35 * "This product includes software developed by the OpenSSL Project
36 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
38 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
39 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
40 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
41 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
42 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
43 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
44 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
45 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
46 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
47 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
48 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
49 * OF THE POSSIBILITY OF SUCH DAMAGE.
50 * ====================================================================
52 * This product includes cryptographic software written by Eric Young
53 * (eay@cryptsoft.com). This product includes software written by Tim
54 * Hudson (tjh@cryptsoft.com).
59 #include "internal/cryptlib.h"
61 #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
62 #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
63 #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
64 #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
65 #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
67 /* pre-computed tables are "carry-less" values of modulus*(i+1) */
69 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
70 {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
71 {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
72 {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
75 static const BN_ULONG _nist_p_192_sqr[] = {
76 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
77 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
80 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
81 {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL,
82 0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL},
83 {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL,
84 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is
88 static const BN_ULONG _nist_p_224_sqr[] = {
89 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
90 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
91 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
95 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
96 {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL,
97 0x0000000000000000ULL, 0xFFFFFFFF00000001ULL},
98 {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL,
99 0x0000000000000000ULL, 0xFFFFFFFE00000002ULL},
100 {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL,
101 0x0000000000000000ULL, 0xFFFFFFFD00000003ULL},
102 {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL,
103 0x0000000000000000ULL, 0xFFFFFFFC00000004ULL},
104 {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL,
105 0x0000000000000000ULL, 0xFFFFFFFB00000005ULL},
108 static const BN_ULONG _nist_p_256_sqr[] = {
109 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
110 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
111 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
112 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
115 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
116 {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL,
117 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
118 {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
119 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
120 {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL,
121 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
122 {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL,
123 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
124 {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL,
125 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
128 static const BN_ULONG _nist_p_384_sqr[] = {
129 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL,
130 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL,
131 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
132 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
135 static const BN_ULONG _nist_p_521[] =
136 { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
137 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
138 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
139 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
140 0x00000000000001FFULL
143 static const BN_ULONG _nist_p_521_sqr[] = {
144 0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
145 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
146 0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL,
147 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
148 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
149 0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL
152 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
153 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
154 {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
155 {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
158 static const BN_ULONG _nist_p_192_sqr[] = {
159 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
160 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
163 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
164 {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF,
165 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
166 {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE,
167 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
170 static const BN_ULONG _nist_p_224_sqr[] = {
171 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
172 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002,
173 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
174 0xFFFFFFFF, 0xFFFFFFFF
177 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
178 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000,
179 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF},
180 {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001,
181 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE},
182 {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002,
183 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD},
184 {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003,
185 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC},
186 {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004,
187 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB},
190 static const BN_ULONG _nist_p_256_sqr[] = {
191 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
192 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001,
193 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001,
194 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE
197 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
198 {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
199 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
200 {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
201 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
202 {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF,
203 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
204 {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF,
205 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
206 {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF,
207 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
210 static const BN_ULONG _nist_p_384_sqr[] = {
211 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE,
212 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000,
213 0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
214 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
217 static const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
218 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
219 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
220 0xFFFFFFFF, 0x000001FF
223 static const BN_ULONG _nist_p_521_sqr[] = {
224 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
225 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
226 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF,
227 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
228 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
229 0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF
232 # error "unsupported BN_BITS2"
235 static const BIGNUM _bignum_nist_p_192 = {
236 (BN_ULONG *)_nist_p_192[0],
243 static const BIGNUM _bignum_nist_p_224 = {
244 (BN_ULONG *)_nist_p_224[0],
251 static const BIGNUM _bignum_nist_p_256 = {
252 (BN_ULONG *)_nist_p_256[0],
259 static const BIGNUM _bignum_nist_p_384 = {
260 (BN_ULONG *)_nist_p_384[0],
267 static const BIGNUM _bignum_nist_p_521 = {
268 (BN_ULONG *)_nist_p_521,
275 const BIGNUM *BN_get0_nist_prime_192(void)
277 return &_bignum_nist_p_192;
280 const BIGNUM *BN_get0_nist_prime_224(void)
282 return &_bignum_nist_p_224;
285 const BIGNUM *BN_get0_nist_prime_256(void)
287 return &_bignum_nist_p_256;
290 const BIGNUM *BN_get0_nist_prime_384(void)
292 return &_bignum_nist_p_384;
295 const BIGNUM *BN_get0_nist_prime_521(void)
297 return &_bignum_nist_p_521;
300 static void nist_cp_bn_0(BN_ULONG *dst, const BN_ULONG *src, int top, int max)
305 OPENSSL_assert(top <= max);
307 for (i = 0; i < top; i++)
313 static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
317 for (i = 0; i < top; i++)
322 # define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
323 # define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0;
325 * two following macros are implemented under assumption that they
326 * are called in a sequence with *ascending* n, i.e. as they are...
328 # 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))\
329 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
330 # define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
331 # define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
332 # if defined(L_ENDIAN)
333 # if defined(__arch64__)
334 # define NIST_INT64 long
336 # define NIST_INT64 long long
340 # define bn_cp_64(to, n, from, m) \
342 bn_cp_32(to, (n)*2, from, (m)*2); \
343 bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
345 # define bn_64_set_0(to, n) \
347 bn_32_set_0(to, (n)*2); \
348 bn_32_set_0(to, (n)*2+1); \
350 # define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
351 # define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
352 # if defined(_WIN32) && !defined(__GNUC__)
353 # define NIST_INT64 __int64
354 # elif defined(BN_LLONG)
355 # define NIST_INT64 long long
357 #endif /* BN_BITS2 != 64 */
359 #define nist_set_192(to, from, a1, a2, a3) \
361 bn_cp_64(to, 0, from, (a3) - 3) \
362 bn_cp_64(to, 1, from, (a2) - 3) \
363 bn_cp_64(to, 2, from, (a1) - 3) \
366 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
371 register BN_ULONG *r_d, *a_d = a->d;
373 BN_ULONG bn[BN_NIST_192_TOP];
374 unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) /
375 sizeof(unsigned int)];
377 BN_ULONG c_d[BN_NIST_192_TOP], *res;
379 static const BIGNUM _bignum_nist_p_192_sqr = {
380 (BN_ULONG *)_nist_p_192_sqr,
381 OSSL_NELEM(_nist_p_192_sqr),
382 OSSL_NELEM(_nist_p_192_sqr),
383 0, BN_FLG_STATIC_DATA
386 field = &_bignum_nist_p_192; /* just to make sure */
388 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
389 return BN_nnmod(r, a, field, ctx);
391 i = BN_ucmp(field, a);
396 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
399 if (!bn_wexpand(r, BN_NIST_192_TOP))
402 nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
406 nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
409 #if defined(NIST_INT64)
411 NIST_INT64 acc; /* accumulator */
412 unsigned int *rp = (unsigned int *)r_d;
413 const unsigned int *bp = (const unsigned int *)buf.ui;
416 acc += bp[3 * 2 - 6];
417 acc += bp[5 * 2 - 6];
418 rp[0] = (unsigned int)acc;
422 acc += bp[3 * 2 - 5];
423 acc += bp[5 * 2 - 5];
424 rp[1] = (unsigned int)acc;
428 acc += bp[3 * 2 - 6];
429 acc += bp[4 * 2 - 6];
430 acc += bp[5 * 2 - 6];
431 rp[2] = (unsigned int)acc;
435 acc += bp[3 * 2 - 5];
436 acc += bp[4 * 2 - 5];
437 acc += bp[5 * 2 - 5];
438 rp[3] = (unsigned int)acc;
442 acc += bp[4 * 2 - 6];
443 acc += bp[5 * 2 - 6];
444 rp[4] = (unsigned int)acc;
448 acc += bp[4 * 2 - 5];
449 acc += bp[5 * 2 - 5];
450 rp[5] = (unsigned int)acc;
452 carry = (int)(acc >> 32);
456 BN_ULONG t_d[BN_NIST_192_TOP];
458 nist_set_192(t_d, buf.bn, 0, 3, 3);
459 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
460 nist_set_192(t_d, buf.bn, 4, 4, 0);
461 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
462 nist_set_192(t_d, buf.bn, 5, 5, 5)
463 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
468 (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
474 * we need 'if (carry==0 || result>=modulus) result-=modulus;'
475 * as comparison implies subtraction, we can write
476 * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
477 * this is what happens below, but without explicit if:-) a.
480 0 - (PTR_SIZE_INT) bn_sub_words(c_d, r_d, _nist_p_192[0],
482 mask &= 0 - (PTR_SIZE_INT) carry;
485 (((PTR_SIZE_INT) res & ~mask) | ((PTR_SIZE_INT) r_d & mask));
486 nist_cp_bn(r_d, res, BN_NIST_192_TOP);
487 r->top = BN_NIST_192_TOP;
493 typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
494 const BN_ULONG *, int);
496 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
498 bn_cp_32(to, 0, from, (a7) - 7) \
499 bn_cp_32(to, 1, from, (a6) - 7) \
500 bn_cp_32(to, 2, from, (a5) - 7) \
501 bn_cp_32(to, 3, from, (a4) - 7) \
502 bn_cp_32(to, 4, from, (a3) - 7) \
503 bn_cp_32(to, 5, from, (a2) - 7) \
504 bn_cp_32(to, 6, from, (a1) - 7) \
507 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
512 BN_ULONG *r_d, *a_d = a->d;
514 BN_ULONG bn[BN_NIST_224_TOP];
515 unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) /
516 sizeof(unsigned int)];
518 BN_ULONG c_d[BN_NIST_224_TOP], *res;
524 static const BIGNUM _bignum_nist_p_224_sqr = {
525 (BN_ULONG *)_nist_p_224_sqr,
526 OSSL_NELEM(_nist_p_224_sqr),
527 OSSL_NELEM(_nist_p_224_sqr),
528 0, BN_FLG_STATIC_DATA
531 field = &_bignum_nist_p_224; /* just to make sure */
533 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
534 return BN_nnmod(r, a, field, ctx);
536 i = BN_ucmp(field, a);
541 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
544 if (!bn_wexpand(r, BN_NIST_224_TOP))
547 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
552 /* copy upper 256 bits of 448 bit number ... */
553 nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
554 top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
555 /* ... and right shift by 32 to obtain upper 224 bits */
556 nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
557 /* truncate lower part to 224 bits too */
558 r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
560 nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
564 #if defined(NIST_INT64) && BN_BITS2!=64
566 NIST_INT64 acc; /* accumulator */
567 unsigned int *rp = (unsigned int *)r_d;
568 const unsigned int *bp = (const unsigned int *)buf.ui;
573 rp[0] = (unsigned int)acc;
579 rp[1] = (unsigned int)acc;
585 rp[2] = (unsigned int)acc;
592 rp[3] = (unsigned int)acc;
599 rp[4] = (unsigned int)acc;
606 rp[5] = (unsigned int)acc;
612 rp[6] = (unsigned int)acc;
614 carry = (int)(acc >> 32);
621 BN_ULONG t_d[BN_NIST_224_TOP];
623 nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
624 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
625 nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
626 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
627 nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
628 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
629 nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
630 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
633 carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
640 (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
643 carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
645 } else if (carry < 0) {
647 * it's a bit more comlicated logic in this case. if bn_add_words
648 * yields no carry, then result has to be adjusted by unconditionally
649 * *adding* the modulus. but if it does, then result has to be
650 * compared to the modulus and conditionally adjusted by
651 * *subtracting* the latter.
654 (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
656 mask = 0 - (PTR_SIZE_INT) carry;
657 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
658 ((PTR_SIZE_INT) bn_add_words & ~mask);
662 /* otherwise it's effectively same as in BN_nist_mod_192... */
664 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
665 mask &= 0 - (PTR_SIZE_INT) carry;
667 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
668 ((PTR_SIZE_INT) r_d & mask));
669 nist_cp_bn(r_d, res, BN_NIST_224_TOP);
670 r->top = BN_NIST_224_TOP;
676 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
678 bn_cp_32(to, 0, from, (a8) - 8) \
679 bn_cp_32(to, 1, from, (a7) - 8) \
680 bn_cp_32(to, 2, from, (a6) - 8) \
681 bn_cp_32(to, 3, from, (a5) - 8) \
682 bn_cp_32(to, 4, from, (a4) - 8) \
683 bn_cp_32(to, 5, from, (a3) - 8) \
684 bn_cp_32(to, 6, from, (a2) - 8) \
685 bn_cp_32(to, 7, from, (a1) - 8) \
688 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
693 register BN_ULONG *a_d = a->d, *r_d;
695 BN_ULONG bn[BN_NIST_256_TOP];
696 unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) /
697 sizeof(unsigned int)];
699 BN_ULONG c_d[BN_NIST_256_TOP], *res;
705 static const BIGNUM _bignum_nist_p_256_sqr = {
706 (BN_ULONG *)_nist_p_256_sqr,
707 OSSL_NELEM(_nist_p_256_sqr),
708 OSSL_NELEM(_nist_p_256_sqr),
709 0, BN_FLG_STATIC_DATA
712 field = &_bignum_nist_p_256; /* just to make sure */
714 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
715 return BN_nnmod(r, a, field, ctx);
717 i = BN_ucmp(field, a);
722 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
725 if (!bn_wexpand(r, BN_NIST_256_TOP))
728 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
732 nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
735 #if defined(NIST_INT64)
737 NIST_INT64 acc; /* accumulator */
738 unsigned int *rp = (unsigned int *)r_d;
739 const unsigned int *bp = (const unsigned int *)buf.ui;
748 rp[0] = (unsigned int)acc;
758 rp[1] = (unsigned int)acc;
767 rp[2] = (unsigned int)acc;
779 rp[3] = (unsigned int)acc;
790 rp[4] = (unsigned int)acc;
801 rp[5] = (unsigned int)acc;
813 rp[6] = (unsigned int)acc;
825 rp[7] = (unsigned int)acc;
827 carry = (int)(acc >> 32);
831 BN_ULONG t_d[BN_NIST_256_TOP];
836 nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
840 nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
841 carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
844 register BN_ULONG *ap, t, c;
847 for (i = BN_NIST_256_TOP; i != 0; --i) {
849 *(ap++) = ((t << 1) | c) & BN_MASK2;
850 c = (t & BN_TBIT) ? 1 : 0;
855 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
859 nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
860 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
864 nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
865 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
869 nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
870 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
874 nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
875 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
879 nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
880 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
884 nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
885 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
889 /* see BN_nist_mod_224 for explanation */
893 (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
895 else if (carry < 0) {
897 (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
899 mask = 0 - (PTR_SIZE_INT) carry;
900 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
901 ((PTR_SIZE_INT) bn_add_words & ~mask);
906 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
907 mask &= 0 - (PTR_SIZE_INT) carry;
909 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
910 ((PTR_SIZE_INT) r_d & mask));
911 nist_cp_bn(r_d, res, BN_NIST_256_TOP);
912 r->top = BN_NIST_256_TOP;
918 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
920 bn_cp_32(to, 0, from, (a12) - 12) \
921 bn_cp_32(to, 1, from, (a11) - 12) \
922 bn_cp_32(to, 2, from, (a10) - 12) \
923 bn_cp_32(to, 3, from, (a9) - 12) \
924 bn_cp_32(to, 4, from, (a8) - 12) \
925 bn_cp_32(to, 5, from, (a7) - 12) \
926 bn_cp_32(to, 6, from, (a6) - 12) \
927 bn_cp_32(to, 7, from, (a5) - 12) \
928 bn_cp_32(to, 8, from, (a4) - 12) \
929 bn_cp_32(to, 9, from, (a3) - 12) \
930 bn_cp_32(to, 10, from, (a2) - 12) \
931 bn_cp_32(to, 11, from, (a1) - 12) \
934 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
939 register BN_ULONG *r_d, *a_d = a->d;
941 BN_ULONG bn[BN_NIST_384_TOP];
942 unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) /
943 sizeof(unsigned int)];
945 BN_ULONG c_d[BN_NIST_384_TOP], *res;
951 static const BIGNUM _bignum_nist_p_384_sqr = {
952 (BN_ULONG *)_nist_p_384_sqr,
953 OSSL_NELEM(_nist_p_384_sqr),
954 OSSL_NELEM(_nist_p_384_sqr),
955 0, BN_FLG_STATIC_DATA
958 field = &_bignum_nist_p_384; /* just to make sure */
960 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
961 return BN_nnmod(r, a, field, ctx);
963 i = BN_ucmp(field, a);
968 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
971 if (!bn_wexpand(r, BN_NIST_384_TOP))
974 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
978 nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
981 #if defined(NIST_INT64)
983 NIST_INT64 acc; /* accumulator */
984 unsigned int *rp = (unsigned int *)r_d;
985 const unsigned int *bp = (const unsigned int *)buf.ui;
992 rp[0] = (unsigned int)acc;
1001 rp[1] = (unsigned int)acc;
1009 rp[2] = (unsigned int)acc;
1020 rp[3] = (unsigned int)acc;
1034 rp[4] = (unsigned int)acc;
1046 rp[5] = (unsigned int)acc;
1057 rp[6] = (unsigned int)acc;
1066 rp[7] = (unsigned int)acc;
1074 rp[8] = (unsigned int)acc;
1082 rp[9] = (unsigned int)acc;
1090 rp[10] = (unsigned int)acc;
1098 rp[11] = (unsigned int)acc;
1100 carry = (int)(acc >> 32);
1104 BN_ULONG t_d[BN_NIST_384_TOP];
1109 nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
1112 register BN_ULONG *ap, t, c;
1115 for (i = 3; i != 0; --i) {
1117 *(ap++) = ((t << 1) | c) & BN_MASK2;
1118 c = (t & BN_TBIT) ? 1 : 0;
1123 (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
1124 t_d, BN_NIST_256_TOP);
1128 carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
1132 nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,
1134 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1138 nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23,
1140 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1144 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
1145 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1149 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
1150 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1154 nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
1156 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1160 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
1161 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1165 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
1166 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1170 /* see BN_nist_mod_224 for explanation */
1174 (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
1176 else if (carry < 0) {
1178 (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
1180 mask = 0 - (PTR_SIZE_INT) carry;
1181 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
1182 ((PTR_SIZE_INT) bn_add_words & ~mask);
1187 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
1188 mask &= 0 - (PTR_SIZE_INT) carry;
1190 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1191 ((PTR_SIZE_INT) r_d & mask));
1192 nist_cp_bn(r_d, res, BN_NIST_384_TOP);
1193 r->top = BN_NIST_384_TOP;
1199 #define BN_NIST_521_RSHIFT (521%BN_BITS2)
1200 #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT)
1201 #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
1203 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1206 int top = a->top, i;
1207 BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
1209 static const BIGNUM _bignum_nist_p_521_sqr = {
1210 (BN_ULONG *)_nist_p_521_sqr,
1211 OSSL_NELEM(_nist_p_521_sqr),
1212 OSSL_NELEM(_nist_p_521_sqr),
1213 0, BN_FLG_STATIC_DATA
1216 field = &_bignum_nist_p_521; /* just to make sure */
1218 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
1219 return BN_nnmod(r, a, field, ctx);
1221 i = BN_ucmp(field, a);
1226 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1229 if (!bn_wexpand(r, BN_NIST_521_TOP))
1232 nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
1236 /* upper 521 bits, copy ... */
1237 nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
1238 top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
1239 /* ... and right shift */
1240 for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
1243 * MSC ARM compiler [version 2013, presumably even earlier,
1244 * much earlier] miscompiles this code, but not one in
1245 * #else section. See RT#3541.
1247 tmp = val >> BN_NIST_521_RSHIFT;
1249 t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
1251 t_d[i] = (val >> BN_NIST_521_RSHIFT |
1252 (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2;
1256 t_d[i] = val >> BN_NIST_521_RSHIFT;
1257 /* lower 521 bits */
1258 r_d[i] &= BN_NIST_521_TOP_MASK;
1260 bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
1262 0 - (PTR_SIZE_INT) bn_sub_words(t_d, r_d, _nist_p_521,
1265 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1266 ((PTR_SIZE_INT) r_d & mask));
1267 nist_cp_bn(r_d, res, BN_NIST_521_TOP);
1268 r->top = BN_NIST_521_TOP;
1274 int (*BN_nist_mod_func(const BIGNUM *p)) (BIGNUM *r, const BIGNUM *a,
1275 const BIGNUM *field, BN_CTX *ctx) {
1276 if (BN_ucmp(&_bignum_nist_p_192, p) == 0)
1277 return BN_nist_mod_192;
1278 if (BN_ucmp(&_bignum_nist_p_224, p) == 0)
1279 return BN_nist_mod_224;
1280 if (BN_ucmp(&_bignum_nist_p_256, p) == 0)
1281 return BN_nist_mod_256;
1282 if (BN_ucmp(&_bignum_nist_p_384, p) == 0)
1283 return BN_nist_mod_384;
1284 if (BN_ucmp(&_bignum_nist_p_521, p) == 0)
1285 return BN_nist_mod_521;