VirtualBox

source: vbox/trunk/src/libs/openssl-3.1.4/crypto/bn/bn_nist.c@ 102863

Last change on this file since 102863 was 102863, checked in by vboxsync, 13 months ago

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

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette