f30f6c65d1692acb9cb643652ca489544c1b7876
[openssl.git] / crypto / bn / bn_nist.c
1 /* crypto/bn/bn_nist.c */
2 /* ====================================================================
3  * Copyright (c) 1998-2002 The OpenSSL Project.  All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  *
9  * 1. Redistributions of source code must retain the above copyright
10  *    notice, this list of conditions and the following disclaimer. 
11  *
12  * 2. Redistributions in binary form must reproduce the above copyright
13  *    notice, this list of conditions and the following disclaimer in
14  *    the documentation and/or other materials provided with the
15  *    distribution.
16  *
17  * 3. All advertising materials mentioning features or use of this
18  *    software must display the following acknowledgment:
19  *    "This product includes software developed by the OpenSSL Project
20  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
21  *
22  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
23  *    endorse or promote products derived from this software without
24  *    prior written permission. For written permission, please contact
25  *    openssl-core@openssl.org.
26  *
27  * 5. Products derived from this software may not be called "OpenSSL"
28  *    nor may "OpenSSL" appear in their names without prior written
29  *    permission of the OpenSSL Project.
30  *
31  * 6. Redistributions of any form whatsoever must retain the following
32  *    acknowledgment:
33  *    "This product includes software developed by the OpenSSL Project
34  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
35  *
36  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
37  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
38  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
39  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
40  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
41  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
42  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
43  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
44  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
45  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
46  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
47  * OF THE POSSIBILITY OF SUCH DAMAGE.
48  * ====================================================================
49  *
50  * This product includes cryptographic software written by Eric Young
51  * (eay@cryptsoft.com).  This product includes software written by Tim
52  * Hudson (tjh@cryptsoft.com).
53  *
54  */
55
56 #include "bn_lcl.h"
57 #include "cryptlib.h"
58
59 #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
60 #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
61 #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
62 #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
63 #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
64
65 #if BN_BITS2 == 64
66 const static BN_ULONG _nist_p_192[] =
67         {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFEULL,
68         0xFFFFFFFFFFFFFFFFULL};
69 const static BN_ULONG _nist_p_224[] =
70         {0x0000000000000001ULL,0xFFFFFFFF00000000ULL,
71         0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL};
72 const static BN_ULONG _nist_p_256[] =
73         {0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL,
74         0x0000000000000000ULL,0xFFFFFFFF00000001ULL};
75 const static BN_ULONG _nist_p_384[] =
76         {0x00000000FFFFFFFFULL,0xFFFFFFFF00000000ULL,
77         0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL,
78         0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL};
79 const static BN_ULONG _nist_p_521[] =
80         {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
81         0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
82         0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
83         0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,
84         0x00000000000001FFULL};
85 #elif BN_BITS2 == 32
86 const static BN_ULONG _nist_p_192[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,
87         0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
88 const static BN_ULONG _nist_p_224[] = {0x00000001,0x00000000,0x00000000,
89         0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
90 const static BN_ULONG _nist_p_256[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
91         0x00000000,0x00000000,0x00000000,0x00000001,0xFFFFFFFF};
92 const static BN_ULONG _nist_p_384[] = {0xFFFFFFFF,0x00000000,0x00000000,
93         0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
94         0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF};
95 const static BN_ULONG _nist_p_521[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
96         0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
97         0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,
98         0xFFFFFFFF,0x000001FF};
99 #elif BN_BITS2 == 16
100 const static BN_ULONG _nist_p_192[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFE,
101         0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
102 const static BN_ULONG _nist_p_224[] = {0x0001,0x0000,0x0000,0x0000,0x0000,
103         0x0000,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
104 const static BN_ULONG _nist_p_256[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
105         0xFFFF,0x0000,0x0000,0x0000,0x0000,0x0000,0x0000,0x0001,0x0000,0xFFFF,
106         0xFFFF};
107 const static BN_ULONG _nist_p_384[] = {0xFFFF,0xFFFF,0x0000,0x0000,0x0000,
108         0x0000,0xFFFF,0xFFFF,0xFFFE,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
109         0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF};
110 const static BN_ULONG _nist_p_521[] = {0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
111         0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
112         0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,
113         0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0x01FF};
114 #elif BN_BITS2 == 8
115 const static BN_ULONG _nist_p_192[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
116         0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
117         0xFF,0xFF};
118 const static BN_ULONG _nist_p_224[] = {0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
119         0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
120         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
121 const static BN_ULONG _nist_p_256[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
122         0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
123         0x00,0x00,0x01,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF};
124 const static BN_ULONG _nist_p_384[] = {0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,
125         0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,
126         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
127         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF};
128 const static BN_ULONG _nist_p_521[] = {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
129         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
130         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
131         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
132         0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
133         0xFF,0x01};
134 #endif
135
136 const BIGNUM *BN_get0_nist_prime_192(void)
137         {
138         static BIGNUM const_nist_192 = { (BN_ULONG *)_nist_p_192,
139                 BN_NIST_192_TOP, BN_NIST_192_TOP, 0, BN_FLG_STATIC_DATA };
140         return &const_nist_192;
141         }
142
143 const BIGNUM *BN_get0_nist_prime_224(void)
144         {
145         static BIGNUM const_nist_224 = { (BN_ULONG *)_nist_p_224,
146                 BN_NIST_224_TOP, BN_NIST_224_TOP, 0, BN_FLG_STATIC_DATA };
147         return &const_nist_224;
148         }
149
150 const BIGNUM *BN_get0_nist_prime_256(void)
151         {
152         static BIGNUM const_nist_256 = { (BN_ULONG *)_nist_p_256,
153                 BN_NIST_256_TOP, BN_NIST_256_TOP, 0, BN_FLG_STATIC_DATA };
154         return &const_nist_256;
155         }
156
157 const BIGNUM *BN_get0_nist_prime_384(void)
158         {
159         static BIGNUM const_nist_384 = { (BN_ULONG *)_nist_p_384,
160                 BN_NIST_384_TOP, BN_NIST_384_TOP, 0, BN_FLG_STATIC_DATA };
161         return &const_nist_384;
162         }
163
164 const BIGNUM *BN_get0_nist_prime_521(void)
165         {
166         static BIGNUM const_nist_521 = { (BN_ULONG *)_nist_p_521,
167                 BN_NIST_521_TOP, BN_NIST_521_TOP, 0, BN_FLG_STATIC_DATA };
168         return &const_nist_521;
169         }
170
171 /* some misc internal functions */
172 static BN_ULONG _256_data[BN_NIST_256_TOP*6];
173 static int _is_set_256_data = 0;
174 static void _init_256_data(void);
175
176 static BN_ULONG _384_data[BN_NIST_384_TOP*8];
177 static int _is_set_384_data = 0;
178 static void _init_384_data(void);
179
180 #define BN_NIST_ADD_ONE(a)      while (!(++(*(a)))) ++(a);
181 #define __buf_0                 (BN_ULONG)0
182 #define __buf_0_1               (BN_ULONG)0
183 #define __buf_0_2               (BN_ULONG)0
184 #if BN_BITS2 == 64
185 #define BN_64_BIT_BUF(n)        BN_ULONG __buf_##n = (BN_ULONG)0;
186 #define BN_CP_64_TO_BUF(n)      __buf_##n = (a)[(n)];
187 #define BN_CP_64_FROM_BUF(a,n)  *(a)++ = __buf_##n;
188 #define BN_CASE_64_BIT(n,a)     case (n): __buf_##n = (a)[(n)];
189 #if     UINT_MAX == 4294967295UL
190 #define nist32  unsigned int
191 #define BN_32_BIT_BUF(n)        nist32 __buf_##n = (nist32)0;
192 #define BN_CP_32_TO_BUF(n)      __buf_##n = ((nist32 *)(a))[(n)];
193 #define BN_CP_32_FROM_BUF(a,n)  *((nist32)(a))++ = __buf_##n;
194 #define BN_CASE_32_BIT(n,a)     case (n): __buf_##n = ((nist32)(a))[(n)];
195 #elif   ULONG_MAX == 4294967295UL
196 #define nist32  unsigned long
197 #define BN_32_BIT_BUF(n)        nist32 __buf_##n = (nist32)0;
198 #define BN_CP_32_TO_BUF(n)      __buf_##n = ((nist32 *)(a))[(n)];
199 #define BN_CP_32_FROM_BUF(a,n)  *((nist32)(a))++ = __buf_##n;
200 #define BN_CASE_32_BIT(n,a)     case (n): __buf_##n = ((nist32)(a))[(n)];
201 #else
202 #define NO_32_BIT_TYPE
203 #endif
204 #elif BN_BITS2 == 32
205 #define BN_64_BIT_BUF(n)        BN_ULONG __buf_##n##_1 = (BN_ULONG)0;\
206                                 BN_ULONG __buf_##n##_2 = (BN_ULONG)0;
207 #define BN_CP_64_TO_BUF(n)      __buf_##n##_2 = (a)[2*(n)+1];\
208                                 __buf_##n##_1 = (a)[2*(n)];
209 #define BN_CP_64_FROM_BUF(a,n)  *(a)++ = __buf_##n##_1;\
210                                 *(a)++ = __buf_##n##_2;
211 #define BN_CASE_64_BIT(n,a)     case 2*(n)+1: __buf_##n##_2 = (a)[2*(n)+1];\
212                                 case 2*(n):   __buf_##n##_1 = (a)[2*(n)];
213                                 
214 #define BN_32_BIT_BUF(n)        BN_ULONG __buf_##n = (BN_ULONG)0;
215 #define BN_CP_32_TO_BUF(n)      __buf_##n = (a)[(n)];
216 #define BN_CP_32_FROM_BUF(a,n)  *(a)++ = __buf_##n;
217 #define BN_CASE_32_BIT(n,a)     case (n): __buf_##n = (a)[(n)];
218 #elif BN_BITS2 == 16
219 #define __buf_0_3               (BN_ULONG)0
220 #define __buf_0_4               (BN_ULONG)0
221 #define BN_64_BIT_BUF(n)        BN_ULONG __buf_##n##_1 = (BN_ULONG)0;\
222                                 BN_ULONG __buf_##n##_2 = (BN_ULONG)0;\
223                                 BN_ULONG __buf_##n##_3 = (BN_ULONG)0;\
224                                 BN_ULONG __buf_##n##_4 = (BN_ULONG)0;
225 #define BN_CP_64_TO_BUF(n)      __buf_##n##_4 = (a)[4*(n)+3];\
226                                 __buf_##n##_3 = (a)[4*(n)+2];\
227                                 __buf_##n##_2 = (a)[4*(n)+1];\
228                                 __buf_##n##_1 = (a)[4*(n)];
229 #define BN_CP_64_FROM_BUF(a,n)  *(a)++ = __buf_##n##_1;\
230                                 *(a)++ = __buf_##n##_2;\
231                                 *(a)++ = __buf_##n##_3;\
232                                 *(a)++ = __buf_##n##_4;
233 #define BN_CASE_64_BIT(n,a)     case 4*(n)+3: __buf_##n##_4 = (a)[4*(n)+3];\
234                                 case 4*(n)+2: __buf_##n##_3 = (a)[4*(n)+2];\
235                                 case 4*(n)+1: __buf_##n##_2 = (a)[4*(n)+1];\
236                                 case 4*(n):   __buf_##n##_1 = (a)[4*(n)];
237 #define BN_32_BIT_BUF(n)        BN_ULONG __buf_##n##_1 = (BN_ULONG)0;\
238                                 BN_ULONG __buf_##n##_2 = (BN_ULONG)0;
239 #define BN_CP_32_TO_BUF(n)      __buf_##n##_1 = (a)[2*(n)];\
240                                 __buf_##n##_2 = (a)[2*(n)+1];
241 #define BN_CP_32_FROM_BUF(a,n)  *(a)++ = __buf_##n##_1;\
242                                 *(a)++ = __buf_##n##_2;
243 #define BN_CASE_32_BIT(n,a)     case 2*(n)+1: __buf_##n##_2 = (a)[2*(n)+1];\
244                                 case 2*(n):   __buf_##n##_1 = (a)[2*(n)];
245 #elif BN_BITS2 == 8
246 #define __buf_0_3               (BN_ULONG)0
247 #define __buf_0_4               (BN_ULONG)0
248 #define __buf_0_5               (BN_ULONG)0
249 #define __buf_0_6               (BN_ULONG)0
250 #define __buf_0_7               (BN_ULONG)0
251 #define __buf_0_8               (BN_ULONG)0
252 #define BN_64_BIT_BUF(n)        BN_ULONG __buf_##n##_1 = (BN_ULONG)0;\
253                                 BN_ULONG __buf_##n##_2 = (BN_ULONG)0;\
254                                 BN_ULONG __buf_##n##_3 = (BN_ULONG)0;\
255                                 BN_ULONG __buf_##n##_4 = (BN_ULONG)0;\
256                                 BN_ULONG __buf_##n##_5 = (BN_ULONG)0;\
257                                 BN_ULONG __buf_##n##_6 = (BN_ULONG)0;\
258                                 BN_ULONG __buf_##n##_7 = (BN_ULONG)0;\
259                                 BN_ULONG __buf_##n##_8 = (BN_ULONG)0;
260 #define BN_CP_64_TO_BUF(n)      __buf_##n##_8 = (a)[8*(n)+7];\
261                                 __buf_##n##_7 = (a)[8*(n)+6];\
262                                 __buf_##n##_6 = (a)[8*(n)+5];\
263                                 __buf_##n##_5 = (a)[8*(n)+4];\
264                                 __buf_##n##_4 = (a)[8*(n)+3];\
265                                 __buf_##n##_3 = (a)[8*(n)+2];\
266                                 __buf_##n##_2 = (a)[8*(n)+1];\
267                                 __buf_##n##_1 = (a)[8*(n)];
268 #define BN_CP_64_FROM_BUF(a,n)  *(a)++ = __buf_##n##_1;\
269                                 *(a)++ = __buf_##n##_2;\
270                                 *(a)++ = __buf_##n##_3;\
271                                 *(a)++ = __buf_##n##_4;\
272                                 *(a)++ = __buf_##n##_5;\
273                                 *(a)++ = __buf_##n##_6;\
274                                 *(a)++ = __buf_##n##_7;\
275                                 *(a)++ = __buf_##n##_8;
276 #define BN_CASE_64_BIT(n,a)     case 8*(n)+7: __buf_##n##_8 = (a)[8*(n)+7];\
277                                 case 8*(n)+6: __buf_##n##_7 = (a)[8*(n)+6];\
278                                 case 8*(n)+5: __buf_##n##_6 = (a)[8*(n)+5];\
279                                 case 8*(n)+4: __buf_##n##_5 = (a)[8*(n)+4];\
280                                 case 8*(n)+3: __buf_##n##_4 = (a)[8*(n)+3];\
281                                 case 8*(n)+2: __buf_##n##_3 = (a)[8*(n)+2];\
282                                 case 8*(n)+1: __buf_##n##_2 = (a)[8*(n)+1];\
283                                 case 8*(n):   __buf_##n##_1 = (a)[8*(n)];
284 #define BN_32_BIT_BUF(n)        BN_ULONG __buf_##n##_1 = (BN_ULONG)0;\
285                                 BN_ULONG __buf_##n##_2 = (BN_ULONG)0;\
286                                 BN_ULONG __buf_##n##_3 = (BN_ULONG)0;\
287                                 BN_ULONG __buf_##n##_4 = (BN_ULONG)0;
288 #define BN_CP_32_TO_BUF(n)      __buf_##n##_1 = (a)[4*(n)];\
289                                 __buf_##n##_2 = (a)[4*(n)+1];\
290                                 __buf_##n##_3 = (a)[4*(n)+2];\
291                                 __buf_##n##_4 = (a)[4*(n)+3];
292 #define BN_CP_32_FROM_BUF(a,n)  *(a)++ = __buf_##n##_1;\
293                                 *(a)++ = __buf_##n##_2;\
294                                 *(a)++ = __buf_##n##_3;\
295                                 *(a)++ = __buf_##n##_4;
296 #define BN_CASE_32_BIT(n,a)     case 4*(n)+3: __buf_##n##_4 = (a)[4*(n)+3];\
297                                 case 4*(n)+2: __buf_##n##_3 = (a)[4*(n)+2];\
298                                 case 4*(n)+1: __buf_##n##_2 = (a)[4*(n)+1];\
299                                 case 4*(n):   __buf_##n##_1 = (a)[4*(n)];
300 #endif
301
302
303 #define BN_192_SET(d,a1,a2,a3) \
304         {\
305         register BN_ULONG *td = (d);\
306         BN_CP_64_FROM_BUF(td,a3); BN_CP_64_FROM_BUF(td,a2);\
307         BN_CP_64_FROM_BUF(td,a1);\
308         }
309
310 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
311         BN_CTX *ctx)
312         {
313         int      top;
314         BN_ULONG carry = 0;
315         register BN_ULONG *r_d, *a_d;
316         BN_ULONG t_d[BN_NIST_192_TOP];
317         BN_64_BIT_BUF(3)  BN_64_BIT_BUF(4)
318         BN_64_BIT_BUF(5)
319
320         top = BN_ucmp(field, a);
321         if (top == 0)
322                 return BN_zero(r);
323         else if (top > 0)
324                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
325
326         if (r != a)
327                 if (!BN_ncopy(r, a, BN_NIST_192_TOP))
328                         return 0;
329
330         r_d = r->d;
331         a_d = a->d;
332         top = a->top-1;
333
334         switch (top)
335                 {
336                 BN_CASE_64_BIT(5, a_d)
337                 BN_CASE_64_BIT(4, a_d)
338                 BN_CASE_64_BIT(3, a_d)
339                         break;
340                 default: /* a->top == field->top */
341                         return BN_usub(r, a, field);
342                 }
343
344         BN_192_SET(t_d,0,3,3)
345         if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
346                 ++carry;
347
348         BN_192_SET(t_d,4,4,0)
349         if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
350                 ++carry;
351
352         BN_192_SET(t_d,5,5,5)
353         if (bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP))
354                 ++carry;
355
356         while (carry)
357                 {
358                 if (bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP))
359                         --carry; 
360                 }
361         r->top = BN_NIST_192_TOP;
362
363 #if 1
364         bn_clear_top2max(r);
365 #endif
366         bn_correct_top(r);
367
368         if (BN_ucmp(r, field) >= 0)
369                 {
370                 bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP);
371                 bn_correct_top(r);
372                 }
373
374         bn_check_top(r);
375         return 1;
376         }
377
378 #define BN_224_SET(d,a1,a2,a3,a4,a5,a6,a7) \
379         {\
380         register BN_ULONG *td = (d);\
381         BN_CP_32_FROM_BUF(td,a7); BN_CP_32_FROM_BUF(td,a6);\
382         BN_CP_32_FROM_BUF(td,a5); BN_CP_32_FROM_BUF(td,a4);\
383         BN_CP_32_FROM_BUF(td,a3); BN_CP_32_FROM_BUF(td,a2);\
384         BN_CP_32_FROM_BUF(td,a1);\
385         }
386
387 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
388         BN_CTX *ctx)
389         {
390 #ifndef NO_32_BIT_TYPE
391         int     tmp_int;
392         int     carry = 0;
393         BN_ULONG *r_d, *a_d;
394         BN_ULONG t_d[BN_NIST_224_TOP];
395         BN_32_BIT_BUF(7)  BN_32_BIT_BUF(8)
396         BN_32_BIT_BUF(9)  BN_32_BIT_BUF(10)
397         BN_32_BIT_BUF(11) BN_32_BIT_BUF(12)
398         BN_32_BIT_BUF(13)
399
400         tmp_int = BN_ucmp(field, a);
401         if (tmp_int == 0)
402                 return BN_zero(r);
403         else if (tmp_int > 0)
404                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
405
406         if (r != a)
407                 if (!BN_ncopy(r, a, BN_NIST_224_TOP))
408                         return 0;
409
410         r_d = r->d;
411         a_d = a->d;
412
413         tmp_int = a->top-1;
414
415         switch (tmp_int)
416                 {
417                 BN_CASE_32_BIT(13, a_d)
418                 BN_CASE_32_BIT(12, a_d)
419                 BN_CASE_32_BIT(11, a_d)
420                 BN_CASE_32_BIT(10, a_d)
421                 BN_CASE_32_BIT(9,  a_d)
422                 BN_CASE_32_BIT(8,  a_d)
423                 BN_CASE_32_BIT(7,  a_d)
424                         break;
425                 default: /* a->top == field->top */
426                         return BN_usub(r, a, field);
427                 }
428
429         BN_224_SET(t_d,10,9,8,7,0,0,0)
430         if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
431                 ++carry;
432         BN_224_SET(t_d,0,13,12,11,0,0,0)
433         if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
434                 ++carry;
435         BN_224_SET(t_d,13,12,11,10,9,8,7)
436         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
437                 --carry;
438         BN_224_SET(t_d,0,0,0,0,13,12,11)
439         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
440                 --carry;
441
442         if (carry > 0)
443                 while (carry)
444                         {
445                         if (bn_sub_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
446                                 --carry;
447                         }
448         else if (carry < 0)
449                 while (carry)
450                         {
451                         if (bn_add_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
452                                 ++carry;
453                         }
454
455         r->top = BN_NIST_224_TOP;
456 #if 1
457         bn_clear_top2max(r);
458 #endif
459         bn_correct_top(r);
460
461         if (BN_ucmp(r, field) >= 0)
462                 {
463                 bn_sub_words(r_d, r_d, _nist_p_224, BN_NIST_224_TOP);
464                 bn_correct_top(r);
465                 }
466         bn_check_top(r);
467         return 1;
468 #else
469         return 0;
470 #endif
471         }
472
473 static void _init_256_data(void)
474         {
475         int     i;
476         BN_ULONG *tmp1 = _256_data;
477         const BN_ULONG *tmp2 = tmp1;
478
479         memcpy(tmp1, _nist_p_256, BN_NIST_256_TOP * sizeof(BN_ULONG));
480         tmp1 += BN_NIST_256_TOP;
481
482         for (i=0; i<5; i++)
483                 {
484                 bn_add_words(tmp1, _nist_p_256, tmp2, BN_NIST_256_TOP);
485                 tmp2  = tmp1;
486                 tmp1 += BN_NIST_256_TOP;
487                 }
488         _is_set_256_data = 1;
489         }
490
491 #define BN_256_SET(d,a1,a2,a3,a4,a5,a6,a7,a8) \
492         {\
493         register BN_ULONG *td = (d);\
494         BN_CP_32_FROM_BUF(td,a8); BN_CP_32_FROM_BUF(td,a7);\
495         BN_CP_32_FROM_BUF(td,a6); BN_CP_32_FROM_BUF(td,a5);\
496         BN_CP_32_FROM_BUF(td,a4); BN_CP_32_FROM_BUF(td,a3);\
497         BN_CP_32_FROM_BUF(td,a2); BN_CP_32_FROM_BUF(td,a1);\
498         }
499
500 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
501         BN_CTX *ctx)
502         {
503 #ifndef NO_32_BIT_TYPE
504         int     tmp_int;
505         int     carry = 0;
506         register BN_ULONG *a_d, *r_d;
507         BN_ULONG t_d[BN_NIST_256_TOP];
508         BN_ULONG t_d2[BN_NIST_256_TOP];
509         BN_32_BIT_BUF(8)  BN_32_BIT_BUF(9)
510         BN_32_BIT_BUF(10) BN_32_BIT_BUF(11)
511         BN_32_BIT_BUF(12) BN_32_BIT_BUF(13)
512         BN_32_BIT_BUF(14) BN_32_BIT_BUF(15)
513
514         if (!_is_set_256_data)
515                 {
516                 CRYPTO_w_lock(CRYPTO_LOCK_BN);
517                 
518                 if (!_is_set_256_data)
519                         _init_256_data();
520                 
521                 CRYPTO_w_unlock(CRYPTO_LOCK_BN);
522                 }
523         
524         tmp_int = BN_ucmp(field, a);
525         if (tmp_int == 0)
526                 return BN_zero(r);
527         else if (tmp_int > 0)
528                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
529
530         if (r != a)
531                 if (!BN_ncopy(r, a, BN_NIST_256_TOP))
532                         return 0;
533
534         tmp_int = a->top-1;
535
536         a_d = a->d;
537         r_d = r->d;
538         switch (tmp_int)
539                 {
540                 BN_CASE_32_BIT(15, a_d)
541                 BN_CASE_32_BIT(14, a_d)
542                 BN_CASE_32_BIT(13, a_d)
543                 BN_CASE_32_BIT(12, a_d)
544                 BN_CASE_32_BIT(11, a_d)
545                 BN_CASE_32_BIT(10, a_d)
546                 BN_CASE_32_BIT(9,  a_d)
547                 BN_CASE_32_BIT(8,  a_d)
548                         break;
549                 default: /* a->top == field->top */
550                         return BN_usub(r, a, field);
551                 }
552
553         /*S1*/
554         BN_256_SET(t_d,15,14,13,12,11,0,0,0)
555         /*S2*/
556         BN_256_SET(t_d2,0,15,14,13,12,0,0,0)
557         if (bn_add_words(t_d, t_d, t_d2, BN_NIST_256_TOP))
558                 carry = 2;
559         /* left shift */
560                 {
561                 register BN_ULONG *ap,t,c;
562                 ap = t_d;
563                 c=0;
564                 for (tmp_int=BN_NIST_256_TOP; tmp_int != 0; --tmp_int)
565                         {
566                         t= *ap;
567                         *(ap++)=((t<<1)|c)&BN_MASK2;
568                         c=(t & BN_TBIT)?1:0;
569                         }
570                 if (c)
571                         ++carry;
572                 }
573
574         if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
575                 ++carry;
576         /*S3*/
577         BN_256_SET(t_d,15,14,0,0,0,10,9,8)
578         if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
579                 ++carry;
580         /*S4*/
581         BN_256_SET(t_d,8,13,15,14,13,11,10,9)
582         if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
583                 ++carry;
584         /*D1*/
585         BN_256_SET(t_d,10,8,0,0,0,13,12,11)
586         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
587                 --carry;
588         /*D2*/
589         BN_256_SET(t_d,11,9,0,0,15,14,13,12)
590         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
591                 --carry;
592         /*D3*/
593         BN_256_SET(t_d,12,0,10,9,8,15,14,13)
594         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
595                 --carry;
596         /*D4*/
597         BN_256_SET(t_d,13,0,11,10,9,0,15,14)
598         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
599                 --carry;
600         
601         if (carry)
602                 {
603                 if (carry > 0)
604                         bn_sub_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
605                                 --carry, BN_NIST_256_TOP);
606                 else
607                         {
608                         carry = -carry;
609                         bn_add_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
610                                 --carry, BN_NIST_256_TOP);
611                         }
612                 }
613
614         r->top = BN_NIST_256_TOP;
615 #if 1
616         bn_clear_top2max(r);
617 #endif
618         bn_correct_top(r);
619
620         if (BN_ucmp(r, field) >= 0)
621                 {
622                 bn_sub_words(r_d, r_d, _nist_p_256, BN_NIST_256_TOP);
623                 bn_correct_top(r);
624                 }
625         bn_check_top(r);
626         return 1;
627 #else
628         return 0;
629 #endif
630         }
631
632 static void _init_384_data(void)
633         {
634         int     i;
635         BN_ULONG *tmp1 = _384_data;
636         const BN_ULONG *tmp2 = tmp1;
637
638         memcpy(tmp1, _nist_p_384, BN_NIST_384_TOP * sizeof(BN_ULONG));
639         tmp1 += BN_NIST_384_TOP;
640
641         for (i=0; i<7; i++)
642                 {
643                 bn_add_words(tmp1, _nist_p_384, tmp2, BN_NIST_384_TOP);
644                 tmp2  = tmp1;
645                 tmp1 += BN_NIST_384_TOP;
646                 }
647         _is_set_384_data = 1;
648         }
649
650 #define BN_384_SET(d,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
651         {\
652         register BN_ULONG *td = (d);\
653         BN_CP_32_FROM_BUF(td,a12); BN_CP_32_FROM_BUF(td,a11);\
654         BN_CP_32_FROM_BUF(td,a10); BN_CP_32_FROM_BUF(td,a9);\
655         BN_CP_32_FROM_BUF(td,a8);  BN_CP_32_FROM_BUF(td,a7);\
656         BN_CP_32_FROM_BUF(td,a6);  BN_CP_32_FROM_BUF(td,a5);\
657         BN_CP_32_FROM_BUF(td,a4);  BN_CP_32_FROM_BUF(td,a3);\
658         BN_CP_32_FROM_BUF(td,a2);  BN_CP_32_FROM_BUF(td,a1);\
659         }
660
661 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
662         BN_CTX *ctx)
663         {
664 #ifndef NO_32_BIT_TYPE
665         int     tmp_int;
666         int     carry = 0;
667         register BN_ULONG *r_d, *a_d;
668         BN_ULONG t_d[BN_NIST_384_TOP];
669         BN_32_BIT_BUF(12) BN_32_BIT_BUF(13)
670         BN_32_BIT_BUF(14) BN_32_BIT_BUF(15)
671         BN_32_BIT_BUF(16) BN_32_BIT_BUF(17)
672         BN_32_BIT_BUF(18) BN_32_BIT_BUF(19)
673         BN_32_BIT_BUF(20) BN_32_BIT_BUF(21)
674         BN_32_BIT_BUF(22) BN_32_BIT_BUF(23)
675
676         if (!_is_set_384_data)
677                 {
678                 CRYPTO_w_lock(CRYPTO_LOCK_BN);
679                 
680                 if (!_is_set_384_data)
681                         _init_384_data();
682
683                 CRYPTO_w_unlock(CRYPTO_LOCK_BN);
684                 }
685
686         tmp_int = BN_ucmp(field, a);
687         if (tmp_int == 0)
688                 return BN_zero(r);
689         else if (tmp_int > 0)
690                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
691
692         if (r != a)
693                 if (!BN_ncopy(r, a, BN_NIST_384_TOP))
694                         return 0;
695
696         r_d = r->d;
697         a_d = a->d;
698         tmp_int = a->top-1;
699
700         switch (tmp_int)
701                 {
702                 BN_CASE_32_BIT(23, a_d)
703                 BN_CASE_32_BIT(22, a_d)
704                 BN_CASE_32_BIT(21, a_d)
705                 BN_CASE_32_BIT(20, a_d)
706                 BN_CASE_32_BIT(19, a_d)
707                 BN_CASE_32_BIT(18, a_d)
708                 BN_CASE_32_BIT(17, a_d)
709                 BN_CASE_32_BIT(16, a_d)
710                 BN_CASE_32_BIT(15, a_d)
711                 BN_CASE_32_BIT(14, a_d)
712                 BN_CASE_32_BIT(13, a_d)
713                 BN_CASE_32_BIT(12, a_d)
714                         break;
715                 default: /* a->top == field->top */
716                         return BN_usub(r, a, field);
717                 }
718
719         /*S1*/
720         BN_256_SET(t_d,0,0,0,0,0,23,22,21)
721                 /* left shift */
722                 {
723                 register BN_ULONG *ap,t,c;
724                 ap = t_d;
725                 c=0;
726                 for (tmp_int=BN_NIST_256_TOP; tmp_int != 0; --tmp_int)
727                         {
728                         t= *ap;
729                         *(ap++)=((t<<1)|c)&BN_MASK2;
730                         c=(t & BN_TBIT)?1:0;
731                         }
732                 }
733         if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), 
734                 t_d, BN_NIST_256_TOP))
735                 ++carry;
736         /*S2*/
737         BN_384_SET(t_d,23,22,21,20,19,18,17,16,15,14,13,12)
738         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
739                 ++carry;
740         /*S3*/
741         BN_384_SET(t_d,20,19,18,17,16,15,14,13,12,23,22,21)
742         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
743                 ++carry;
744         /*S4*/
745         BN_384_SET(t_d,19,18,17,16,15,14,13,12,20,0,23,0)
746         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
747                 ++carry;
748         /*S5*/
749         BN_256_SET(t_d,0,0,0,0,23,22,21,20)
750         if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), 
751                 t_d, BN_NIST_256_TOP))
752                 ++carry;
753         /*S6*/
754         BN_384_SET(t_d,0,0,0,0,0,0,23,22,21,0,0,20)
755         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
756                 ++carry;
757         /*D1*/
758         BN_384_SET(t_d,22,21,20,19,18,17,16,15,14,13,12,23)
759         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
760                 --carry;
761         /*D2*/
762         BN_384_SET(t_d,0,0,0,0,0,0,0,23,22,21,20,0)
763         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
764                 --carry;
765         /*D3*/
766         BN_384_SET(t_d,0,0,0,0,0,0,0,23,23,0,0,0)
767         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
768                 --carry;
769         
770         if (carry)
771                 {
772                 if (carry > 0)
773                         bn_sub_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
774                                 --carry, BN_NIST_384_TOP);
775                 else
776                         {
777                         carry = -carry;
778                         bn_add_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
779                                 --carry, BN_NIST_384_TOP);
780                         }
781                 }
782
783         r->top = BN_NIST_384_TOP;
784 #if 1
785         bn_clear_top2max(r);
786 #endif
787         bn_correct_top(r);
788
789         if (BN_ucmp(r, field) >= 0)
790                 {
791                 bn_sub_words(r_d, r_d, _nist_p_384, BN_NIST_384_TOP);
792                 bn_correct_top(r);
793                 }
794         bn_check_top(r);
795         return 1;
796 #else
797         return 0;
798 #endif
799         }
800
801 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
802         BN_CTX *ctx)
803         {
804 #if BN_BITS2 == 64
805 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1FF
806 #elif BN_BITS2 == 32
807 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1FF
808 #elif BN_BITS2 == 16
809 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1FF
810 #elif BN_BITS2 == 8
811 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1
812 #endif
813         int     top, ret = 0;
814         BN_ULONG *r_d;
815         BIGNUM  *tmp;
816
817         /* check whether a reduction is necessary */
818         top = a->top;
819         if (top < BN_NIST_521_TOP  || ( top == BN_NIST_521_TOP &&
820            (!(a->d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))))
821                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
822
823         BN_CTX_start(ctx);
824         tmp = BN_CTX_get(ctx);
825         if (!tmp)
826                 goto err;
827
828         if (!BN_ncopy(tmp, a, BN_NIST_521_TOP))
829                 return 0;
830         if (!BN_rshift(r, a, 521))
831                 return 0;
832
833         if (tmp->top == BN_NIST_521_TOP)
834                 tmp->d[BN_NIST_521_TOP-1]  &= BN_NIST_521_TOP_MASK;
835
836         bn_correct_top(tmp);
837         if (!BN_uadd(r, tmp, r))
838                 return 0;
839         top = r->top;
840         r_d = r->d;
841         if (top == BN_NIST_521_TOP  && 
842            (r_d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))
843                 {
844                 BN_NIST_ADD_ONE(r_d)
845                 r_d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK; 
846                 }
847         bn_correct_top(r);
848
849         ret = 1;
850 err:
851         BN_CTX_end(ctx);
852
853         bn_check_top(r);
854         return ret;
855         }