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