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