a29503be25e9ae47c3a167a2c6e77acd7193a4e7
[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         bn_correct_top(r);
363         if (BN_ucmp(r, field) >= 0)
364                 {
365                 bn_sub_words(r_d, r_d, _nist_p_192, BN_NIST_192_TOP);
366                 bn_correct_top(r);
367                 }
368
369         bn_check_top(r);
370         return 1;
371         }
372
373 #define BN_224_SET(d,a1,a2,a3,a4,a5,a6,a7) \
374         {\
375         register BN_ULONG *td = (d);\
376         BN_CP_32_FROM_BUF(td,a7); BN_CP_32_FROM_BUF(td,a6);\
377         BN_CP_32_FROM_BUF(td,a5); BN_CP_32_FROM_BUF(td,a4);\
378         BN_CP_32_FROM_BUF(td,a3); BN_CP_32_FROM_BUF(td,a2);\
379         BN_CP_32_FROM_BUF(td,a1);\
380         }
381
382 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
383         BN_CTX *ctx)
384         {
385 #ifndef NO_32_BIT_TYPE
386         int     tmp_int;
387         int     carry = 0;
388         BN_ULONG *r_d, *a_d;
389         BN_ULONG t_d[BN_NIST_224_TOP];
390         BN_32_BIT_BUF(7)  BN_32_BIT_BUF(8)
391         BN_32_BIT_BUF(9)  BN_32_BIT_BUF(10)
392         BN_32_BIT_BUF(11) BN_32_BIT_BUF(12)
393         BN_32_BIT_BUF(13)
394
395         tmp_int = BN_ucmp(field, a);
396         if (tmp_int == 0)
397                 return BN_zero(r);
398         else if (tmp_int > 0)
399                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
400
401         if (r != a)
402                 if (!BN_ncopy(r, a, BN_NIST_224_TOP))
403                         return 0;
404
405         r_d = r->d;
406         a_d = a->d;
407
408         tmp_int = a->top-1;
409
410         switch (tmp_int)
411                 {
412                 BN_CASE_32_BIT(13, a_d)
413                 BN_CASE_32_BIT(12, a_d)
414                 BN_CASE_32_BIT(11, a_d)
415                 BN_CASE_32_BIT(10, a_d)
416                 BN_CASE_32_BIT(9,  a_d)
417                 BN_CASE_32_BIT(8,  a_d)
418                 BN_CASE_32_BIT(7,  a_d)
419                         break;
420                 default: /* a->top == field->top */
421                         return BN_usub(r, a, field);
422                 }
423
424         BN_224_SET(t_d,10,9,8,7,0,0,0)
425         if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
426                 ++carry;
427         BN_224_SET(t_d,0,13,12,11,0,0,0)
428         if (bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP))
429                 ++carry;
430         BN_224_SET(t_d,13,12,11,10,9,8,7)
431         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
432                 --carry;
433         BN_224_SET(t_d,0,0,0,0,13,12,11)
434         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP))
435                 --carry;
436
437         if (carry > 0)
438                 while (carry)
439                         {
440                         if (bn_sub_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
441                                 --carry;
442                         }
443         else if (carry < 0)
444                 while (carry)
445                         {
446                         if (bn_add_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP))
447                                 ++carry;
448                         }
449
450         r->top = BN_NIST_224_TOP;
451         bn_correct_top(r);
452         if (BN_ucmp(r, field) >= 0)
453                 {
454                 bn_sub_words(r_d, r_d, _nist_p_224, BN_NIST_224_TOP);
455                 bn_correct_top(r);
456                 }
457         bn_check_top(r);
458         return 1;
459 #else
460         return 0;
461 #endif
462         }
463
464 static void _init_256_data(void)
465         {
466         int     i;
467         BN_ULONG *tmp1 = _256_data;
468         const BN_ULONG *tmp2 = tmp1;
469
470         memcpy(tmp1, _nist_p_256, BN_NIST_256_TOP * sizeof(BN_ULONG));
471         tmp1 += BN_NIST_256_TOP;
472
473         for (i=0; i<5; i++)
474                 {
475                 bn_add_words(tmp1, _nist_p_256, tmp2, BN_NIST_256_TOP);
476                 tmp2  = tmp1;
477                 tmp1 += BN_NIST_256_TOP;
478                 }
479         _is_set_256_data = 1;
480         }
481
482 #define BN_256_SET(d,a1,a2,a3,a4,a5,a6,a7,a8) \
483         {\
484         register BN_ULONG *td = (d);\
485         BN_CP_32_FROM_BUF(td,a8); BN_CP_32_FROM_BUF(td,a7);\
486         BN_CP_32_FROM_BUF(td,a6); BN_CP_32_FROM_BUF(td,a5);\
487         BN_CP_32_FROM_BUF(td,a4); BN_CP_32_FROM_BUF(td,a3);\
488         BN_CP_32_FROM_BUF(td,a2); BN_CP_32_FROM_BUF(td,a1);\
489         }
490
491 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
492         BN_CTX *ctx)
493         {
494 #ifndef NO_32_BIT_TYPE
495         int     tmp_int;
496         int     carry = 0;
497         register BN_ULONG *a_d, *r_d;
498         BN_ULONG t_d[BN_NIST_256_TOP];
499         BN_ULONG t_d2[BN_NIST_256_TOP];
500         BN_32_BIT_BUF(8)  BN_32_BIT_BUF(9)
501         BN_32_BIT_BUF(10) BN_32_BIT_BUF(11)
502         BN_32_BIT_BUF(12) BN_32_BIT_BUF(13)
503         BN_32_BIT_BUF(14) BN_32_BIT_BUF(15)
504
505         if (!_is_set_256_data)
506                 {
507                 CRYPTO_w_lock(CRYPTO_LOCK_BN);
508                 
509                 if (!_is_set_256_data)
510                         _init_256_data();
511                 
512                 CRYPTO_w_unlock(CRYPTO_LOCK_BN);
513                 }
514         
515         tmp_int = BN_ucmp(field, a);
516         if (tmp_int == 0)
517                 return BN_zero(r);
518         else if (tmp_int > 0)
519                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
520
521         if (r != a)
522                 if (!BN_ncopy(r, a, BN_NIST_256_TOP))
523                         return 0;
524
525         tmp_int = a->top-1;
526
527         a_d = a->d;
528         r_d = r->d;
529         switch (tmp_int)
530                 {
531                 BN_CASE_32_BIT(15, a_d)
532                 BN_CASE_32_BIT(14, a_d)
533                 BN_CASE_32_BIT(13, a_d)
534                 BN_CASE_32_BIT(12, a_d)
535                 BN_CASE_32_BIT(11, a_d)
536                 BN_CASE_32_BIT(10, a_d)
537                 BN_CASE_32_BIT(9,  a_d)
538                 BN_CASE_32_BIT(8,  a_d)
539                         break;
540                 default: /* a->top == field->top */
541                         return BN_usub(r, a, field);
542                 }
543
544         /*S1*/
545         BN_256_SET(t_d,15,14,13,12,11,0,0,0)
546         /*S2*/
547         BN_256_SET(t_d2,0,15,14,13,12,0,0,0)
548         if (bn_add_words(t_d, t_d, t_d2, BN_NIST_256_TOP))
549                 carry = 2;
550         /* left shift */
551                 {
552                 register BN_ULONG *ap,t,c;
553                 ap = t_d;
554                 c=0;
555                 for (tmp_int=BN_NIST_256_TOP; tmp_int != 0; --tmp_int)
556                         {
557                         t= *ap;
558                         *(ap++)=((t<<1)|c)&BN_MASK2;
559                         c=(t & BN_TBIT)?1:0;
560                         }
561                 if (c)
562                         ++carry;
563                 }
564
565         if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
566                 ++carry;
567         /*S3*/
568         BN_256_SET(t_d,15,14,0,0,0,10,9,8)
569         if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
570                 ++carry;
571         /*S4*/
572         BN_256_SET(t_d,8,13,15,14,13,11,10,9)
573         if (bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP))
574                 ++carry;
575         /*D1*/
576         BN_256_SET(t_d,10,8,0,0,0,13,12,11)
577         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
578                 --carry;
579         /*D2*/
580         BN_256_SET(t_d,11,9,0,0,15,14,13,12)
581         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
582                 --carry;
583         /*D3*/
584         BN_256_SET(t_d,12,0,10,9,8,15,14,13)
585         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
586                 --carry;
587         /*D4*/
588         BN_256_SET(t_d,13,0,11,10,9,0,15,14)
589         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP))
590                 --carry;
591         
592         if (carry)
593                 {
594                 if (carry > 0)
595                         bn_sub_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
596                                 --carry, BN_NIST_256_TOP);
597                 else
598                         {
599                         carry = -carry;
600                         bn_add_words(r_d, r_d, _256_data + BN_NIST_256_TOP *
601                                 --carry, BN_NIST_256_TOP);
602                         }
603                 }
604
605         r->top = BN_NIST_256_TOP;
606         bn_correct_top(r);
607         if (BN_ucmp(r, field) >= 0)
608                 {
609                 bn_sub_words(r_d, r_d, _nist_p_256, BN_NIST_256_TOP);
610                 bn_correct_top(r);
611                 }
612         bn_check_top(r);
613         return 1;
614 #else
615         return 0;
616 #endif
617         }
618
619 static void _init_384_data(void)
620         {
621         int     i;
622         BN_ULONG *tmp1 = _384_data;
623         const BN_ULONG *tmp2 = tmp1;
624
625         memcpy(tmp1, _nist_p_384, BN_NIST_384_TOP * sizeof(BN_ULONG));
626         tmp1 += BN_NIST_384_TOP;
627
628         for (i=0; i<7; i++)
629                 {
630                 bn_add_words(tmp1, _nist_p_384, tmp2, BN_NIST_384_TOP);
631                 tmp2  = tmp1;
632                 tmp1 += BN_NIST_384_TOP;
633                 }
634         _is_set_384_data = 1;
635         }
636
637 #define BN_384_SET(d,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
638         {\
639         register BN_ULONG *td = (d);\
640         BN_CP_32_FROM_BUF(td,a12); BN_CP_32_FROM_BUF(td,a11);\
641         BN_CP_32_FROM_BUF(td,a10); BN_CP_32_FROM_BUF(td,a9);\
642         BN_CP_32_FROM_BUF(td,a8);  BN_CP_32_FROM_BUF(td,a7);\
643         BN_CP_32_FROM_BUF(td,a6);  BN_CP_32_FROM_BUF(td,a5);\
644         BN_CP_32_FROM_BUF(td,a4);  BN_CP_32_FROM_BUF(td,a3);\
645         BN_CP_32_FROM_BUF(td,a2);  BN_CP_32_FROM_BUF(td,a1);\
646         }
647
648 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
649         BN_CTX *ctx)
650         {
651 #ifndef NO_32_BIT_TYPE
652         int     tmp_int;
653         int     carry = 0;
654         register BN_ULONG *r_d, *a_d;
655         BN_ULONG t_d[BN_NIST_384_TOP];
656         BN_32_BIT_BUF(12) BN_32_BIT_BUF(13)
657         BN_32_BIT_BUF(14) BN_32_BIT_BUF(15)
658         BN_32_BIT_BUF(16) BN_32_BIT_BUF(17)
659         BN_32_BIT_BUF(18) BN_32_BIT_BUF(19)
660         BN_32_BIT_BUF(20) BN_32_BIT_BUF(21)
661         BN_32_BIT_BUF(22) BN_32_BIT_BUF(23)
662
663         if (!_is_set_384_data)
664                 {
665                 CRYPTO_w_lock(CRYPTO_LOCK_BN);
666                 
667                 if (!_is_set_384_data)
668                         _init_384_data();
669
670                 CRYPTO_w_unlock(CRYPTO_LOCK_BN);
671                 }
672
673         tmp_int = BN_ucmp(field, a);
674         if (tmp_int == 0)
675                 return BN_zero(r);
676         else if (tmp_int > 0)
677                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
678
679         if (r != a)
680                 if (!BN_ncopy(r, a, BN_NIST_384_TOP))
681                         return 0;
682
683         r_d = r->d;
684         a_d = a->d;
685         tmp_int = a->top-1;
686
687         switch (tmp_int)
688                 {
689                 BN_CASE_32_BIT(23, a_d)
690                 BN_CASE_32_BIT(22, a_d)
691                 BN_CASE_32_BIT(21, a_d)
692                 BN_CASE_32_BIT(20, a_d)
693                 BN_CASE_32_BIT(19, a_d)
694                 BN_CASE_32_BIT(18, a_d)
695                 BN_CASE_32_BIT(17, a_d)
696                 BN_CASE_32_BIT(16, a_d)
697                 BN_CASE_32_BIT(15, a_d)
698                 BN_CASE_32_BIT(14, a_d)
699                 BN_CASE_32_BIT(13, a_d)
700                 BN_CASE_32_BIT(12, a_d)
701                         break;
702                 default: /* a->top == field->top */
703                         return BN_usub(r, a, field);
704                 }
705
706         /*S1*/
707         BN_256_SET(t_d,0,0,0,0,0,23,22,21)
708                 /* left shift */
709                 {
710                 register BN_ULONG *ap,t,c;
711                 ap = t_d;
712                 c=0;
713                 for (tmp_int=BN_NIST_256_TOP; tmp_int != 0; --tmp_int)
714                         {
715                         t= *ap;
716                         *(ap++)=((t<<1)|c)&BN_MASK2;
717                         c=(t & BN_TBIT)?1:0;
718                         }
719                 }
720         if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), 
721                 t_d, BN_NIST_256_TOP))
722                 ++carry;
723         /*S2*/
724         BN_384_SET(t_d,23,22,21,20,19,18,17,16,15,14,13,12)
725         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
726                 ++carry;
727         /*S3*/
728         BN_384_SET(t_d,20,19,18,17,16,15,14,13,12,23,22,21)
729         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
730                 ++carry;
731         /*S4*/
732         BN_384_SET(t_d,19,18,17,16,15,14,13,12,20,0,23,0)
733         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
734                 ++carry;
735         /*S5*/
736         BN_256_SET(t_d,0,0,0,0,23,22,21,20)
737         if (bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), 
738                 t_d, BN_NIST_256_TOP))
739                 ++carry;
740         /*S6*/
741         BN_384_SET(t_d,0,0,0,0,0,0,23,22,21,0,0,20)
742         if (bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP))
743                 ++carry;
744         /*D1*/
745         BN_384_SET(t_d,22,21,20,19,18,17,16,15,14,13,12,23)
746         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
747                 --carry;
748         /*D2*/
749         BN_384_SET(t_d,0,0,0,0,0,0,0,23,22,21,20,0)
750         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
751                 --carry;
752         /*D3*/
753         BN_384_SET(t_d,0,0,0,0,0,0,0,23,23,0,0,0)
754         if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP))
755                 --carry;
756         
757         if (carry)
758                 {
759                 if (carry > 0)
760                         bn_sub_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
761                                 --carry, BN_NIST_384_TOP);
762                 else
763                         {
764                         carry = -carry;
765                         bn_add_words(r_d, r_d, _384_data + BN_NIST_384_TOP *
766                                 --carry, BN_NIST_384_TOP);
767                         }
768                 }
769
770         r->top = BN_NIST_384_TOP;
771         bn_correct_top(r);
772         if (BN_ucmp(r, field) >= 0)
773                 {
774                 bn_sub_words(r_d, r_d, _nist_p_384, BN_NIST_384_TOP);
775                 bn_correct_top(r);
776                 }
777         bn_check_top(r);
778         return 1;
779 #else
780         return 0;
781 #endif
782         }
783
784 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
785         BN_CTX *ctx)
786         {
787 #if BN_BITS2 == 64
788 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1FF
789 #elif BN_BITS2 == 32
790 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1FF
791 #elif BN_BITS2 == 16
792 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1FF
793 #elif BN_BITS2 == 8
794 #define BN_NIST_521_TOP_MASK    (BN_ULONG)0x1
795 #endif
796         int     top, ret = 0;
797         BN_ULONG *r_d;
798         BIGNUM  *tmp;
799
800         /* check whether a reduction is necessary */
801         top = a->top;
802         if (top < BN_NIST_521_TOP  || ( top == BN_NIST_521_TOP &&
803            (!(a->d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))))
804                 return (r == a)? 1 : (BN_copy(r ,a) != NULL);
805
806         BN_CTX_start(ctx);
807         tmp = BN_CTX_get(ctx);
808         if (!tmp)
809                 goto err;
810
811         if (!BN_ncopy(tmp, a, BN_NIST_521_TOP))
812                 return 0;
813         if (!BN_rshift(r, a, 521))
814                 return 0;
815
816         if (tmp->top == BN_NIST_521_TOP)
817                 tmp->d[BN_NIST_521_TOP-1]  &= BN_NIST_521_TOP_MASK;
818
819         bn_correct_top(tmp);
820         if (!BN_uadd(r, tmp, r))
821                 return 0;
822         top = r->top;
823         r_d = r->d;
824         if (top == BN_NIST_521_TOP  && 
825            (r_d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK)))
826                 {
827                 BN_NIST_ADD_ONE(r_d)
828                 r_d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK; 
829                 }
830         bn_correct_top(r);
831
832         ret = 1;
833 err:
834         BN_CTX_end(ctx);
835
836         bn_check_top(r);
837         return ret;
838         }