xref: /openssl/crypto/bn/bn_nist.c (revision 7ed6de99)
1 /*
2  * Copyright 2002-2024 The OpenSSL Project Authors. All Rights Reserved.
3  *
4  * Licensed under the Apache License 2.0 (the "License").  You may not use
5  * this file except in compliance with the License.  You can obtain a copy
6  * in the file LICENSE in the source distribution or at
7  * https://www.openssl.org/source/license.html
8  */
9 
10 #include "bn_local.h"
11 #include "internal/cryptlib.h"
12 
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
18 
19 /* pre-computed tables are "carry-less" values of modulus*(i+1) */
20 #if BN_BITS2 == 64
21 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
22     {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
23     {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
24     {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
25 };
26 
27 static const BN_ULONG _nist_p_192_sqr[] = {
28     0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
29     0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
30 };
31 
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
37                                                     * "carry-full" */
38 };
39 
40 static const BN_ULONG _nist_p_224_sqr[] = {
41     0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
42     0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
43     0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
44     0xFFFFFFFFFFFFFFFFULL
45 };
46 
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},
58 };
59 
60 static const BN_ULONG _nist_p_256_sqr[] = {
61     0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
62     0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
63     0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
64     0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
65 };
66 
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},
78 };
79 
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
85 };
86 
87 static const BN_ULONG _nist_p_521[] = {
88     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
89     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
90     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
91     0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
92     0x00000000000001FFULL
93 };
94 
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
102 };
103 #elif BN_BITS2 == 32
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}
108 };
109 
110 static const BN_ULONG _nist_p_192_sqr[] = {
111     0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
112     0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
113 };
114 
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}
120 };
121 
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
127 };
128 
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},
140 };
141 
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
147 };
148 
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},
160 };
161 
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
167 };
168 
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
173 };
174 
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
182 };
183 #else
184 # error "unsupported BN_BITS2"
185 #endif
186 
187 static const BIGNUM ossl_bignum_nist_p_192 = {
188     (BN_ULONG *)_nist_p_192[0],
189     BN_NIST_192_TOP,
190     BN_NIST_192_TOP,
191     0,
192     BN_FLG_STATIC_DATA
193 };
194 
195 static const BIGNUM ossl_bignum_nist_p_224 = {
196     (BN_ULONG *)_nist_p_224[0],
197     BN_NIST_224_TOP,
198     BN_NIST_224_TOP,
199     0,
200     BN_FLG_STATIC_DATA
201 };
202 
203 static const BIGNUM ossl_bignum_nist_p_256 = {
204     (BN_ULONG *)_nist_p_256[0],
205     BN_NIST_256_TOP,
206     BN_NIST_256_TOP,
207     0,
208     BN_FLG_STATIC_DATA
209 };
210 
211 static const BIGNUM ossl_bignum_nist_p_384 = {
212     (BN_ULONG *)_nist_p_384[0],
213     BN_NIST_384_TOP,
214     BN_NIST_384_TOP,
215     0,
216     BN_FLG_STATIC_DATA
217 };
218 
219 static const BIGNUM ossl_bignum_nist_p_521 = {
220     (BN_ULONG *)_nist_p_521,
221     BN_NIST_521_TOP,
222     BN_NIST_521_TOP,
223     0,
224     BN_FLG_STATIC_DATA
225 };
226 
BN_get0_nist_prime_192(void)227 const BIGNUM *BN_get0_nist_prime_192(void)
228 {
229     return &ossl_bignum_nist_p_192;
230 }
231 
BN_get0_nist_prime_224(void)232 const BIGNUM *BN_get0_nist_prime_224(void)
233 {
234     return &ossl_bignum_nist_p_224;
235 }
236 
BN_get0_nist_prime_256(void)237 const BIGNUM *BN_get0_nist_prime_256(void)
238 {
239     return &ossl_bignum_nist_p_256;
240 }
241 
BN_get0_nist_prime_384(void)242 const BIGNUM *BN_get0_nist_prime_384(void)
243 {
244     return &ossl_bignum_nist_p_384;
245 }
246 
BN_get0_nist_prime_521(void)247 const BIGNUM *BN_get0_nist_prime_521(void)
248 {
249     return &ossl_bignum_nist_p_521;
250 }
251 
252 /*
253  * To avoid more recent compilers (specifically clang-14) from treating this
254  * code as a violation of the strict aliasing conditions and omitting it, this
255  * cannot be declared as a function.  Moreover, the dst parameter cannot be
256  * cached in a local since this no longer references the union and again falls
257  * foul of the strict aliasing criteria.  Refer to #18225 for the initial
258  * diagnostics and llvm/llvm-project#55255 for the later discussions with the
259  * LLVM developers.  The problem boils down to if an array in the union is
260  * converted to a pointer or if it is used directly.
261  *
262  * This function was inlined regardless, so there is no space cost to be
263  * paid for making it a macro.
264  */
265 #define nist_cp_bn_0(dst, src_in, top, max) \
266 {                                           \
267     int ii;                                 \
268     const BN_ULONG *src = src_in;           \
269                                             \
270     for (ii = 0; ii < top; ii++)            \
271         (dst)[ii] = src[ii];                \
272     for (; ii < max; ii++)                  \
273         (dst)[ii] = 0;                      \
274 }
275 
nist_cp_bn(BN_ULONG * dst,const BN_ULONG * src,int top)276 static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
277 {
278     int i;
279 
280     for (i = 0; i < top; i++)
281         dst[i] = src[i];
282 }
283 
284 #if BN_BITS2 == 64
285 # define bn_cp_64(to, n, from, m)        (to)[n] = (m>=0)?((from)[m]):0;
286 # define bn_64_set_0(to, n)              (to)[n] = (BN_ULONG)0;
287 /*
288  * two following macros are implemented under assumption that they
289  * are called in a sequence with *ascending* n, i.e. as they are...
290  */
291 # 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))\
292                                                 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
293 # define bn_32_set_0(to, n)              (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
294 # define bn_cp_32(to,n,from,m)           ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
295 # if defined(L_ENDIAN)
296 #  if defined(__arch64__)
297 #   define NIST_INT64 long
298 #  else
299 #   define NIST_INT64 long long
300 #  endif
301 # endif
302 #else
303 # define bn_cp_64(to, n, from, m) \
304         { \
305         bn_cp_32(to, (n)*2, from, (m)*2); \
306         bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
307         }
308 # define bn_64_set_0(to, n) \
309         { \
310         bn_32_set_0(to, (n)*2); \
311         bn_32_set_0(to, (n)*2+1); \
312         }
313 # define bn_cp_32(to, n, from, m)        (to)[n] = (m>=0)?((from)[m]):0;
314 # define bn_32_set_0(to, n)              (to)[n] = (BN_ULONG)0;
315 # if defined(_WIN32) && !defined(__GNUC__)
316 #  define NIST_INT64 __int64
317 # elif defined(BN_LLONG)
318 #  define NIST_INT64 long long
319 # endif
320 #endif                          /* BN_BITS2 != 64 */
321 
322 #ifdef NIST_INT64
323 /* Helpers to load/store a 32-bit word (uint32_t) from/into a memory
324  * location and avoid potential aliasing issue.  */
load_u32(const void * ptr)325 static ossl_inline uint32_t load_u32(const void *ptr)
326 {
327     uint32_t tmp;
328 
329     memcpy(&tmp, ptr, sizeof(tmp));
330     return tmp;
331 }
332 
store_lo32(void * ptr,NIST_INT64 val)333 static ossl_inline void store_lo32(void *ptr, NIST_INT64 val)
334 {
335     /* A cast is needed for big-endian system: on a 32-bit BE system
336      * NIST_INT64 may be defined as well if the compiler supports 64-bit
337      * long long.  */
338     uint32_t tmp = (uint32_t)val;
339 
340     memcpy(ptr, &tmp, sizeof(tmp));
341 }
342 #endif /* NIST_INT64 */
343 
344 #define nist_set_192(to, from, a1, a2, a3) \
345         { \
346         bn_cp_64(to, 0, from, (a3) - 3) \
347         bn_cp_64(to, 1, from, (a2) - 3) \
348         bn_cp_64(to, 2, from, (a1) - 3) \
349         }
350 
BN_nist_mod_192(BIGNUM * r,const BIGNUM * a,const BIGNUM * field,BN_CTX * ctx)351 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
352                     BN_CTX *ctx)
353 {
354     int top = a->top, i;
355     int carry;
356     register BN_ULONG *r_d, *a_d = a->d;
357     union {
358         BN_ULONG bn[BN_NIST_192_TOP];
359         unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) /
360                         sizeof(unsigned int)];
361     } buf;
362     BN_ULONG c_d[BN_NIST_192_TOP], *res;
363     static const BIGNUM ossl_bignum_nist_p_192_sqr = {
364         (BN_ULONG *)_nist_p_192_sqr,
365         OSSL_NELEM(_nist_p_192_sqr),
366         OSSL_NELEM(_nist_p_192_sqr),
367         0, BN_FLG_STATIC_DATA
368     };
369 
370     field = &ossl_bignum_nist_p_192; /* just to make sure */
371 
372     if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_192_sqr) >= 0)
373         return BN_nnmod(r, a, field, ctx);
374 
375     i = BN_ucmp(field, a);
376     if (i == 0) {
377         BN_zero(r);
378         return 1;
379     } else if (i > 0)
380         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
381 
382     if (r != a) {
383         if (!bn_wexpand(r, BN_NIST_192_TOP))
384             return 0;
385         r_d = r->d;
386         nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
387     } else
388         r_d = a_d;
389 
390     nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
391                  BN_NIST_192_TOP);
392 
393 #if defined(NIST_INT64)
394     {
395         NIST_INT64 acc;         /* accumulator */
396         unsigned int *rp = (unsigned int *)r_d;
397         const unsigned int *bp = (const unsigned int *)buf.ui;
398 
399         acc = load_u32(&rp[0]);
400         acc += bp[3 * 2 - 6];
401         acc += bp[5 * 2 - 6];
402         store_lo32(&rp[0], acc);
403         acc >>= 32;
404 
405         acc += load_u32(&rp[1]);
406         acc += bp[3 * 2 - 5];
407         acc += bp[5 * 2 - 5];
408         store_lo32(&rp[1], acc);
409         acc >>= 32;
410 
411         acc += load_u32(&rp[2]);
412         acc += bp[3 * 2 - 6];
413         acc += bp[4 * 2 - 6];
414         acc += bp[5 * 2 - 6];
415         store_lo32(&rp[2], acc);
416         acc >>= 32;
417 
418         acc += load_u32(&rp[3]);
419         acc += bp[3 * 2 - 5];
420         acc += bp[4 * 2 - 5];
421         acc += bp[5 * 2 - 5];
422         store_lo32(&rp[3], acc);
423         acc >>= 32;
424 
425         acc += load_u32(&rp[4]);
426         acc += bp[4 * 2 - 6];
427         acc += bp[5 * 2 - 6];
428         store_lo32(&rp[4], acc);
429         acc >>= 32;
430 
431         acc += load_u32(&rp[5]);
432         acc += bp[4 * 2 - 5];
433         acc += bp[5 * 2 - 5];
434         store_lo32(&rp[5], acc);
435 
436         carry = (int)(acc >> 32);
437     }
438 #else
439     {
440         BN_ULONG t_d[BN_NIST_192_TOP];
441 
442         nist_set_192(t_d, buf.bn, 0, 3, 3);
443         carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
444         nist_set_192(t_d, buf.bn, 4, 4, 0);
445         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
446         nist_set_192(t_d, buf.bn, 5, 5, 5)
447             carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
448     }
449 #endif
450     if (carry > 0)
451         carry =
452             (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
453                               BN_NIST_192_TOP);
454     else
455         carry = 1;
456 
457     /*
458      * we need 'if (carry==0 || result>=modulus) result-=modulus;'
459      * as comparison implies subtraction, we can write
460      * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
461      * this is what happens below, but without explicit if:-) a.
462      */
463     res = (bn_sub_words(c_d, r_d, _nist_p_192[0], BN_NIST_192_TOP) && carry)
464         ? r_d
465         : c_d;
466     nist_cp_bn(r_d, res, BN_NIST_192_TOP);
467     r->top = BN_NIST_192_TOP;
468     bn_correct_top(r);
469 
470     return 1;
471 }
472 
473 typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
474                                  const BN_ULONG *, int);
475 
476 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
477         { \
478         bn_cp_32(to, 0, from, (a7) - 7) \
479         bn_cp_32(to, 1, from, (a6) - 7) \
480         bn_cp_32(to, 2, from, (a5) - 7) \
481         bn_cp_32(to, 3, from, (a4) - 7) \
482         bn_cp_32(to, 4, from, (a3) - 7) \
483         bn_cp_32(to, 5, from, (a2) - 7) \
484         bn_cp_32(to, 6, from, (a1) - 7) \
485         }
486 
BN_nist_mod_224(BIGNUM * r,const BIGNUM * a,const BIGNUM * field,BN_CTX * ctx)487 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
488                     BN_CTX *ctx)
489 {
490     int top = a->top, i;
491     int carry;
492     BN_ULONG *r_d, *a_d = a->d;
493     union {
494         BN_ULONG bn[BN_NIST_224_TOP];
495         unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) /
496                         sizeof(unsigned int)];
497     } buf;
498     BN_ULONG c_d[BN_NIST_224_TOP], *res;
499     bn_addsub_f adjust;
500     static const BIGNUM ossl_bignum_nist_p_224_sqr = {
501         (BN_ULONG *)_nist_p_224_sqr,
502         OSSL_NELEM(_nist_p_224_sqr),
503         OSSL_NELEM(_nist_p_224_sqr),
504         0, BN_FLG_STATIC_DATA
505     };
506 
507     field = &ossl_bignum_nist_p_224; /* just to make sure */
508 
509     if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_224_sqr) >= 0)
510         return BN_nnmod(r, a, field, ctx);
511 
512     i = BN_ucmp(field, a);
513     if (i == 0) {
514         BN_zero(r);
515         return 1;
516     } else if (i > 0)
517         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
518 
519     if (r != a) {
520         if (!bn_wexpand(r, BN_NIST_224_TOP))
521             return 0;
522         r_d = r->d;
523         nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
524     } else
525         r_d = a_d;
526 
527 #if BN_BITS2==64
528     /* copy upper 256 bits of 448 bit number ... */
529     nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
530                  top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
531     /* ... and right shift by 32 to obtain upper 224 bits */
532     nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
533     /* truncate lower part to 224 bits too */
534     r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
535 #else
536     nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
537                  BN_NIST_224_TOP);
538 #endif
539 
540 #if defined(NIST_INT64) && BN_BITS2!=64
541     {
542         NIST_INT64 acc;         /* accumulator */
543         unsigned int *rp = (unsigned int *)r_d;
544         const unsigned int *bp = (const unsigned int *)buf.ui;
545 
546         acc = rp[0];
547         acc -= bp[7 - 7];
548         acc -= bp[11 - 7];
549         rp[0] = (unsigned int)acc;
550         acc >>= 32;
551 
552         acc += rp[1];
553         acc -= bp[8 - 7];
554         acc -= bp[12 - 7];
555         rp[1] = (unsigned int)acc;
556         acc >>= 32;
557 
558         acc += rp[2];
559         acc -= bp[9 - 7];
560         acc -= bp[13 - 7];
561         rp[2] = (unsigned int)acc;
562         acc >>= 32;
563 
564         acc += rp[3];
565         acc += bp[7 - 7];
566         acc += bp[11 - 7];
567         acc -= bp[10 - 7];
568         rp[3] = (unsigned int)acc;
569         acc >>= 32;
570 
571         acc += rp[4];
572         acc += bp[8 - 7];
573         acc += bp[12 - 7];
574         acc -= bp[11 - 7];
575         rp[4] = (unsigned int)acc;
576         acc >>= 32;
577 
578         acc += rp[5];
579         acc += bp[9 - 7];
580         acc += bp[13 - 7];
581         acc -= bp[12 - 7];
582         rp[5] = (unsigned int)acc;
583         acc >>= 32;
584 
585         acc += rp[6];
586         acc += bp[10 - 7];
587         acc -= bp[13 - 7];
588         rp[6] = (unsigned int)acc;
589 
590         carry = (int)(acc >> 32);
591 # if BN_BITS2==64
592         rp[7] = carry;
593 # endif
594     }
595 #else
596     {
597         BN_ULONG t_d[BN_NIST_224_TOP];
598 
599         nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
600         carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
601         nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
602         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
603         nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
604         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
605         nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
606         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
607 
608 # if BN_BITS2==64
609         carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
610 # endif
611     }
612 #endif
613     adjust = bn_sub_words;
614     if (carry > 0) {
615         carry =
616             (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
617                               BN_NIST_224_TOP);
618 #if BN_BITS2==64
619         carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
620 #endif
621     } else if (carry < 0) {
622         /*
623          * it's a bit more complicated logic in this case. if bn_add_words
624          * yields no carry, then result has to be adjusted by unconditionally
625          * *adding* the modulus. but if it does, then result has to be
626          * compared to the modulus and conditionally adjusted by
627          * *subtracting* the latter.
628          */
629         carry =
630             (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
631                               BN_NIST_224_TOP);
632         adjust = carry ? bn_sub_words : bn_add_words;
633     } else
634         carry = 1;
635 
636     /* otherwise it's effectively same as in BN_nist_mod_192... */
637     res = ((*adjust) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP) && carry)
638         ? r_d
639         : c_d;
640     nist_cp_bn(r_d, res, BN_NIST_224_TOP);
641     r->top = BN_NIST_224_TOP;
642     bn_correct_top(r);
643 
644     return 1;
645 }
646 
647 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
648         { \
649         bn_cp_32(to, 0, from, (a8) - 8) \
650         bn_cp_32(to, 1, from, (a7) - 8) \
651         bn_cp_32(to, 2, from, (a6) - 8) \
652         bn_cp_32(to, 3, from, (a5) - 8) \
653         bn_cp_32(to, 4, from, (a4) - 8) \
654         bn_cp_32(to, 5, from, (a3) - 8) \
655         bn_cp_32(to, 6, from, (a2) - 8) \
656         bn_cp_32(to, 7, from, (a1) - 8) \
657         }
658 
BN_nist_mod_256(BIGNUM * r,const BIGNUM * a,const BIGNUM * field,BN_CTX * ctx)659 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
660                     BN_CTX *ctx)
661 {
662     int i, top = a->top;
663     int carry = 0;
664     register BN_ULONG *a_d = a->d, *r_d;
665     union {
666         BN_ULONG bn[BN_NIST_256_TOP];
667         unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) /
668                         sizeof(unsigned int)];
669     } buf;
670     BN_ULONG c_d[BN_NIST_256_TOP], *res;
671     bn_addsub_f adjust;
672     static const BIGNUM ossl_bignum_nist_p_256_sqr = {
673         (BN_ULONG *)_nist_p_256_sqr,
674         OSSL_NELEM(_nist_p_256_sqr),
675         OSSL_NELEM(_nist_p_256_sqr),
676         0, BN_FLG_STATIC_DATA
677     };
678 
679     field = &ossl_bignum_nist_p_256; /* just to make sure */
680 
681     if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_256_sqr) >= 0)
682         return BN_nnmod(r, a, field, ctx);
683 
684     i = BN_ucmp(field, a);
685     if (i == 0) {
686         BN_zero(r);
687         return 1;
688     } else if (i > 0)
689         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
690 
691     if (r != a) {
692         if (!bn_wexpand(r, BN_NIST_256_TOP))
693             return 0;
694         r_d = r->d;
695         nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
696     } else
697         r_d = a_d;
698 
699     nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
700                  BN_NIST_256_TOP);
701 
702 #if defined(NIST_INT64)
703     {
704         NIST_INT64 acc;         /* accumulator */
705         unsigned int *rp = (unsigned int *)r_d;
706         const unsigned int *bp = (const unsigned int *)buf.ui;
707 
708         acc = load_u32(&rp[0]);
709         acc += bp[8 - 8];
710         acc += bp[9 - 8];
711         acc -= bp[11 - 8];
712         acc -= bp[12 - 8];
713         acc -= bp[13 - 8];
714         acc -= bp[14 - 8];
715         store_lo32(&rp[0], acc);
716         acc >>= 32;
717 
718         acc += load_u32(&rp[1]);
719         acc += bp[9 - 8];
720         acc += bp[10 - 8];
721         acc -= bp[12 - 8];
722         acc -= bp[13 - 8];
723         acc -= bp[14 - 8];
724         acc -= bp[15 - 8];
725         store_lo32(&rp[1], acc);
726         acc >>= 32;
727 
728         acc += load_u32(&rp[2]);
729         acc += bp[10 - 8];
730         acc += bp[11 - 8];
731         acc -= bp[13 - 8];
732         acc -= bp[14 - 8];
733         acc -= bp[15 - 8];
734         store_lo32(&rp[2], acc);
735         acc >>= 32;
736 
737         acc += load_u32(&rp[3]);
738         acc += bp[11 - 8];
739         acc += bp[11 - 8];
740         acc += bp[12 - 8];
741         acc += bp[12 - 8];
742         acc += bp[13 - 8];
743         acc -= bp[15 - 8];
744         acc -= bp[8 - 8];
745         acc -= bp[9 - 8];
746         store_lo32(&rp[3], acc);
747         acc >>= 32;
748 
749         acc += load_u32(&rp[4]);
750         acc += bp[12 - 8];
751         acc += bp[12 - 8];
752         acc += bp[13 - 8];
753         acc += bp[13 - 8];
754         acc += bp[14 - 8];
755         acc -= bp[9 - 8];
756         acc -= bp[10 - 8];
757         store_lo32(&rp[4], acc);
758         acc >>= 32;
759 
760         acc += load_u32(&rp[5]);
761         acc += bp[13 - 8];
762         acc += bp[13 - 8];
763         acc += bp[14 - 8];
764         acc += bp[14 - 8];
765         acc += bp[15 - 8];
766         acc -= bp[10 - 8];
767         acc -= bp[11 - 8];
768         store_lo32(&rp[5], acc);
769         acc >>= 32;
770 
771         acc += load_u32(&rp[6]);
772         acc += bp[14 - 8];
773         acc += bp[14 - 8];
774         acc += bp[15 - 8];
775         acc += bp[15 - 8];
776         acc += bp[14 - 8];
777         acc += bp[13 - 8];
778         acc -= bp[8 - 8];
779         acc -= bp[9 - 8];
780         store_lo32(&rp[6], acc);
781         acc >>= 32;
782 
783         acc += load_u32(&rp[7]);
784         acc += bp[15 - 8];
785         acc += bp[15 - 8];
786         acc += bp[15 - 8];
787         acc += bp[8 - 8];
788         acc -= bp[10 - 8];
789         acc -= bp[11 - 8];
790         acc -= bp[12 - 8];
791         acc -= bp[13 - 8];
792         store_lo32(&rp[7], acc);
793 
794         carry = (int)(acc >> 32);
795     }
796 #else
797     {
798         BN_ULONG t_d[BN_NIST_256_TOP];
799 
800         /*
801          * S1
802          */
803         nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
804         /*
805          * S2
806          */
807         nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
808         carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
809         /* left shift */
810         {
811             register BN_ULONG *ap, t, c;
812             ap = t_d;
813             c = 0;
814             for (i = BN_NIST_256_TOP; i != 0; --i) {
815                 t = *ap;
816                 *(ap++) = ((t << 1) | c) & BN_MASK2;
817                 c = (t & BN_TBIT) ? 1 : 0;
818             }
819             carry <<= 1;
820             carry |= c;
821         }
822         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
823         /*
824          * S3
825          */
826         nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
827         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
828         /*
829          * S4
830          */
831         nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
832         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
833         /*
834          * D1
835          */
836         nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
837         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
838         /*
839          * D2
840          */
841         nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
842         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
843         /*
844          * D3
845          */
846         nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
847         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
848         /*
849          * D4
850          */
851         nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
852         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
853 
854     }
855 #endif
856     /* see BN_nist_mod_224 for explanation */
857     adjust = bn_sub_words;
858     if (carry > 0)
859         carry =
860             (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
861                               BN_NIST_256_TOP);
862     else if (carry < 0) {
863         carry =
864             (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
865                               BN_NIST_256_TOP);
866         adjust = carry ? bn_sub_words : bn_add_words;
867     } else
868         carry = 1;
869 
870     res = ((*adjust) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP) && carry)
871         ? r_d
872         : c_d;
873     nist_cp_bn(r_d, res, BN_NIST_256_TOP);
874     r->top = BN_NIST_256_TOP;
875     bn_correct_top(r);
876 
877     return 1;
878 }
879 
880 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
881         { \
882         bn_cp_32(to, 0, from,  (a12) - 12) \
883         bn_cp_32(to, 1, from,  (a11) - 12) \
884         bn_cp_32(to, 2, from,  (a10) - 12) \
885         bn_cp_32(to, 3, from,  (a9) - 12)  \
886         bn_cp_32(to, 4, from,  (a8) - 12)  \
887         bn_cp_32(to, 5, from,  (a7) - 12)  \
888         bn_cp_32(to, 6, from,  (a6) - 12)  \
889         bn_cp_32(to, 7, from,  (a5) - 12)  \
890         bn_cp_32(to, 8, from,  (a4) - 12)  \
891         bn_cp_32(to, 9, from,  (a3) - 12)  \
892         bn_cp_32(to, 10, from, (a2) - 12)  \
893         bn_cp_32(to, 11, from, (a1) - 12)  \
894         }
895 
BN_nist_mod_384(BIGNUM * r,const BIGNUM * a,const BIGNUM * field,BN_CTX * ctx)896 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
897                     BN_CTX *ctx)
898 {
899     int i, top = a->top;
900     int carry = 0;
901     register BN_ULONG *r_d, *a_d = a->d;
902     union {
903         BN_ULONG bn[BN_NIST_384_TOP];
904         unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) /
905                         sizeof(unsigned int)];
906     } buf;
907     BN_ULONG c_d[BN_NIST_384_TOP], *res;
908     bn_addsub_f adjust;
909     static const BIGNUM ossl_bignum_nist_p_384_sqr = {
910         (BN_ULONG *)_nist_p_384_sqr,
911         OSSL_NELEM(_nist_p_384_sqr),
912         OSSL_NELEM(_nist_p_384_sqr),
913         0, BN_FLG_STATIC_DATA
914     };
915 
916     field = &ossl_bignum_nist_p_384; /* just to make sure */
917 
918     if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_384_sqr) >= 0)
919         return BN_nnmod(r, a, field, ctx);
920 
921     i = BN_ucmp(field, a);
922     if (i == 0) {
923         BN_zero(r);
924         return 1;
925     } else if (i > 0)
926         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
927 
928     if (r != a) {
929         if (!bn_wexpand(r, BN_NIST_384_TOP))
930             return 0;
931         r_d = r->d;
932         nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
933     } else
934         r_d = a_d;
935 
936     nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
937                  BN_NIST_384_TOP);
938 
939 #if defined(NIST_INT64)
940     {
941         NIST_INT64 acc;         /* accumulator */
942         unsigned int *rp = (unsigned int *)r_d;
943         const unsigned int *bp = (const unsigned int *)buf.ui;
944 
945         acc = load_u32(&rp[0]);
946         acc += bp[12 - 12];
947         acc += bp[21 - 12];
948         acc += bp[20 - 12];
949         acc -= bp[23 - 12];
950         store_lo32(&rp[0], acc);
951         acc >>= 32;
952 
953         acc += load_u32(&rp[1]);
954         acc += bp[13 - 12];
955         acc += bp[22 - 12];
956         acc += bp[23 - 12];
957         acc -= bp[12 - 12];
958         acc -= bp[20 - 12];
959         store_lo32(&rp[1], acc);
960         acc >>= 32;
961 
962         acc += load_u32(&rp[2]);
963         acc += bp[14 - 12];
964         acc += bp[23 - 12];
965         acc -= bp[13 - 12];
966         acc -= bp[21 - 12];
967         store_lo32(&rp[2], acc);
968         acc >>= 32;
969 
970         acc += load_u32(&rp[3]);
971         acc += bp[15 - 12];
972         acc += bp[12 - 12];
973         acc += bp[20 - 12];
974         acc += bp[21 - 12];
975         acc -= bp[14 - 12];
976         acc -= bp[22 - 12];
977         acc -= bp[23 - 12];
978         store_lo32(&rp[3], acc);
979         acc >>= 32;
980 
981         acc += load_u32(&rp[4]);
982         acc += bp[21 - 12];
983         acc += bp[21 - 12];
984         acc += bp[16 - 12];
985         acc += bp[13 - 12];
986         acc += bp[12 - 12];
987         acc += bp[20 - 12];
988         acc += bp[22 - 12];
989         acc -= bp[15 - 12];
990         acc -= bp[23 - 12];
991         acc -= bp[23 - 12];
992         store_lo32(&rp[4], acc);
993         acc >>= 32;
994 
995         acc += load_u32(&rp[5]);
996         acc += bp[22 - 12];
997         acc += bp[22 - 12];
998         acc += bp[17 - 12];
999         acc += bp[14 - 12];
1000         acc += bp[13 - 12];
1001         acc += bp[21 - 12];
1002         acc += bp[23 - 12];
1003         acc -= bp[16 - 12];
1004         store_lo32(&rp[5], acc);
1005         acc >>= 32;
1006 
1007         acc += load_u32(&rp[6]);
1008         acc += bp[23 - 12];
1009         acc += bp[23 - 12];
1010         acc += bp[18 - 12];
1011         acc += bp[15 - 12];
1012         acc += bp[14 - 12];
1013         acc += bp[22 - 12];
1014         acc -= bp[17 - 12];
1015         store_lo32(&rp[6], acc);
1016         acc >>= 32;
1017 
1018         acc += load_u32(&rp[7]);
1019         acc += bp[19 - 12];
1020         acc += bp[16 - 12];
1021         acc += bp[15 - 12];
1022         acc += bp[23 - 12];
1023         acc -= bp[18 - 12];
1024         store_lo32(&rp[7], acc);
1025         acc >>= 32;
1026 
1027         acc += load_u32(&rp[8]);
1028         acc += bp[20 - 12];
1029         acc += bp[17 - 12];
1030         acc += bp[16 - 12];
1031         acc -= bp[19 - 12];
1032         store_lo32(&rp[8], acc);
1033         acc >>= 32;
1034 
1035         acc += load_u32(&rp[9]);
1036         acc += bp[21 - 12];
1037         acc += bp[18 - 12];
1038         acc += bp[17 - 12];
1039         acc -= bp[20 - 12];
1040         store_lo32(&rp[9], acc);
1041         acc >>= 32;
1042 
1043         acc += load_u32(&rp[10]);
1044         acc += bp[22 - 12];
1045         acc += bp[19 - 12];
1046         acc += bp[18 - 12];
1047         acc -= bp[21 - 12];
1048         store_lo32(&rp[10], acc);
1049         acc >>= 32;
1050 
1051         acc += load_u32(&rp[11]);
1052         acc += bp[23 - 12];
1053         acc += bp[20 - 12];
1054         acc += bp[19 - 12];
1055         acc -= bp[22 - 12];
1056         store_lo32(&rp[11], acc);
1057 
1058         carry = (int)(acc >> 32);
1059     }
1060 #else
1061     {
1062         BN_ULONG t_d[BN_NIST_384_TOP];
1063 
1064         /*
1065          * S1
1066          */
1067         nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
1068         /* left shift */
1069         {
1070             register BN_ULONG *ap, t, c;
1071             ap = t_d;
1072             c = 0;
1073             for (i = 3; i != 0; --i) {
1074                 t = *ap;
1075                 *(ap++) = ((t << 1) | c) & BN_MASK2;
1076                 c = (t & BN_TBIT) ? 1 : 0;
1077             }
1078             *ap = c;
1079         }
1080         carry =
1081             (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
1082                               t_d, BN_NIST_256_TOP);
1083         /*
1084          * S2
1085          */
1086         carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
1087         /*
1088          * S3
1089          */
1090         nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,
1091                      21);
1092         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1093         /*
1094          * S4
1095          */
1096         nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23,
1097                      0);
1098         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1099         /*
1100          * S5
1101          */
1102         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
1103         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1104         /*
1105          * S6
1106          */
1107         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
1108         carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1109         /*
1110          * D1
1111          */
1112         nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
1113                      23);
1114         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1115         /*
1116          * D2
1117          */
1118         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
1119         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1120         /*
1121          * D3
1122          */
1123         nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
1124         carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1125 
1126     }
1127 #endif
1128     /* see BN_nist_mod_224 for explanation */
1129     adjust = bn_sub_words;
1130     if (carry > 0)
1131         carry =
1132             (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
1133                               BN_NIST_384_TOP);
1134     else if (carry < 0) {
1135         carry =
1136             (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
1137                               BN_NIST_384_TOP);
1138         adjust = carry ? bn_sub_words : bn_add_words;
1139     } else
1140         carry = 1;
1141 
1142     res = ((*adjust) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP) && carry)
1143         ? r_d
1144         : c_d;
1145     nist_cp_bn(r_d, res, BN_NIST_384_TOP);
1146     r->top = BN_NIST_384_TOP;
1147     bn_correct_top(r);
1148 
1149     return 1;
1150 }
1151 
1152 #define BN_NIST_521_RSHIFT      (521%BN_BITS2)
1153 #define BN_NIST_521_LSHIFT      (BN_BITS2-BN_NIST_521_RSHIFT)
1154 #define BN_NIST_521_TOP_MASK    ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
1155 
BN_nist_mod_521(BIGNUM * r,const BIGNUM * a,const BIGNUM * field,BN_CTX * ctx)1156 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1157                     BN_CTX *ctx)
1158 {
1159     int top = a->top, i;
1160     BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
1161     static const BIGNUM ossl_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
1166     };
1167 
1168     field = &ossl_bignum_nist_p_521; /* just to make sure */
1169 
1170     if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_521_sqr) >= 0)
1171         return BN_nnmod(r, a, field, ctx);
1172 
1173     i = BN_ucmp(field, a);
1174     if (i == 0) {
1175         BN_zero(r);
1176         return 1;
1177     } else if (i > 0)
1178         return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1179 
1180     if (r != a) {
1181         if (!bn_wexpand(r, BN_NIST_521_TOP))
1182             return 0;
1183         r_d = r->d;
1184         nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
1185     } else
1186         r_d = a_d;
1187 
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++) {
1193 #if 0
1194         /*
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.
1198          */
1199         tmp = val >> BN_NIST_521_RSHIFT;
1200         val = t_d[i + 1];
1201         t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
1202 #else
1203         t_d[i] = (val >> BN_NIST_521_RSHIFT |
1204                   (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2;
1205         val = tmp;
1206 #endif
1207     }
1208     t_d[i] = val >> BN_NIST_521_RSHIFT;
1209     /* lower 521 bits */
1210     r_d[i] &= BN_NIST_521_TOP_MASK;
1211 
1212     bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
1213     res = bn_sub_words(t_d, r_d, _nist_p_521,
1214                        BN_NIST_521_TOP)
1215         ? r_d
1216         : t_d;
1217     nist_cp_bn(r_d, res, BN_NIST_521_TOP);
1218     r->top = BN_NIST_521_TOP;
1219     bn_correct_top(r);
1220 
1221     return 1;
1222 }
1223 
BN_nist_mod_func(const BIGNUM * p)1224 int (*BN_nist_mod_func(const BIGNUM *p)) (BIGNUM *r, const BIGNUM *a,
1225                                           const BIGNUM *field, BN_CTX *ctx) {
1226     if (BN_ucmp(&ossl_bignum_nist_p_192, p) == 0)
1227         return BN_nist_mod_192;
1228     if (BN_ucmp(&ossl_bignum_nist_p_224, p) == 0)
1229         return BN_nist_mod_224;
1230     if (BN_ucmp(&ossl_bignum_nist_p_256, p) == 0)
1231         return BN_nist_mod_256;
1232     if (BN_ucmp(&ossl_bignum_nist_p_384, p) == 0)
1233         return BN_nist_mod_384;
1234     if (BN_ucmp(&ossl_bignum_nist_p_521, p) == 0)
1235         return BN_nist_mod_521;
1236     return 0;
1237 }
1238