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