Coverage Report

Created: 2024-11-21 07:03

/src/openssl/crypto/bn/bn_nist.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2002-2024 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
432k
#define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
14
1.96M
#define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
15
2.04M
#define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
16
2.35M
#define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
17
7.80M
#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
21
static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
22
    {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
23
    {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
24
    {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
25
};
26
27
static const BN_ULONG _nist_p_192_sqr[] = {
28
    0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
29
    0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
30
};
31
32
static 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
40
static const BN_ULONG _nist_p_224_sqr[] = {
41
    0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
42
    0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
43
    0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
44
    0xFFFFFFFFFFFFFFFFULL
45
};
46
47
static 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
60
static const BN_ULONG _nist_p_256_sqr[] = {
61
    0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
62
    0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
63
    0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
64
    0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
65
};
66
67
static 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
80
static 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
87
static const BN_ULONG _nist_p_521[] = {
88
    0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
89
    0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
90
    0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
91
    0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
92
    0x00000000000001FFULL
93
};
94
95
static 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
104
static 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
110
static const BN_ULONG _nist_p_192_sqr[] = {
111
    0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
112
    0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
113
};
114
115
static 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
122
static 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
129
static 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
142
static 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
149
static 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
162
static 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
169
static 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
175
static 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
187
static 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
195
static 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
203
static 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
211
static 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
219
static 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
227
const BIGNUM *BN_get0_nist_prime_192(void)
228
521
{
229
521
    return &ossl_bignum_nist_p_192;
230
521
}
231
232
const BIGNUM *BN_get0_nist_prime_224(void)
233
462
{
234
462
    return &ossl_bignum_nist_p_224;
235
462
}
236
237
const BIGNUM *BN_get0_nist_prime_256(void)
238
375
{
239
375
    return &ossl_bignum_nist_p_256;
240
375
}
241
242
const BIGNUM *BN_get0_nist_prime_384(void)
243
214
{
244
214
    return &ossl_bignum_nist_p_384;
245
214
}
246
247
const BIGNUM *BN_get0_nist_prime_521(void)
248
90
{
249
90
    return &ossl_bignum_nist_p_521;
250
90
}
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 omitting 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
2.10M
#define nist_cp_bn_0(dst, src_in, top, max) \
266
2.10M
{                                           \
267
2.10M
    int ii;                                 \
268
2.10M
    const BN_ULONG *src = src_in;           \
269
2.10M
                                            \
270
14.6M
    for (ii = 0; ii < top; ii++)            \
271
12.5M
        (dst)[ii] = src[ii];                \
272
2.10M
    for (; ii < max; ii++)                  \
273
2.10M
        (dst)[ii] = 0;                      \
274
2.10M
}
275
276
static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
277
2.10M
{
278
2.10M
    int i;
279
280
14.6M
    for (i = 0; i < top; i++)
281
12.5M
        dst[i] = src[i];
282
2.10M
}
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
4.90M
# 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
4.90M
                                                :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
293
2.24M
# define bn_32_set_0(to, n)              (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
294
7.15M
# 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
1.30M
#   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
#ifdef NIST_INT64
323
/* Helpers to load/store a 32-bit word (uint32_t) from/into a memory
324
 * location and avoid potential aliasing issue.  */
325
static ossl_inline uint32_t load_u32(const void *ptr)
326
12.7M
{
327
12.7M
    uint32_t tmp;
328
329
12.7M
    memcpy(&tmp, ptr, sizeof(tmp));
330
12.7M
    return tmp;
331
12.7M
}
332
333
static ossl_inline void store_lo32(void *ptr, NIST_INT64 val)
334
12.7M
{
335
    /* A cast is needed for big-endian system: on a 32-bit BE system
336
     * NIST_INT64 may be defined as well if the compiler supports 64-bit
337
     * long long.  */
338
12.7M
    uint32_t tmp = (uint32_t)val;
339
340
12.7M
    memcpy(ptr, &tmp, sizeof(tmp));
341
12.7M
}
342
#endif /* NIST_INT64 */
343
344
#define nist_set_192(to, from, a1, a2, a3) \
345
        { \
346
        bn_cp_64(to, 0, from, (a3) - 3) \
347
        bn_cp_64(to, 1, from, (a2) - 3) \
348
        bn_cp_64(to, 2, from, (a1) - 3) \
349
        }
350
351
int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
352
                    BN_CTX *ctx)
353
116k
{
354
116k
    int top = a->top, i;
355
116k
    int carry;
356
116k
    register BN_ULONG *r_d, *a_d = a->d;
357
116k
    union {
358
116k
        BN_ULONG bn[BN_NIST_192_TOP];
359
116k
        unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) /
360
116k
                        sizeof(unsigned int)];
361
116k
    } buf;
362
116k
    BN_ULONG c_d[BN_NIST_192_TOP], *res;
363
116k
    static const BIGNUM ossl_bignum_nist_p_192_sqr = {
364
116k
        (BN_ULONG *)_nist_p_192_sqr,
365
116k
        OSSL_NELEM(_nist_p_192_sqr),
366
116k
        OSSL_NELEM(_nist_p_192_sqr),
367
116k
        0, BN_FLG_STATIC_DATA
368
116k
    };
369
370
116k
    field = &ossl_bignum_nist_p_192; /* just to make sure */
371
372
116k
    if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_192_sqr) >= 0)
373
2
        return BN_nnmod(r, a, field, ctx);
374
375
116k
    i = BN_ucmp(field, a);
376
116k
    if (i == 0) {
377
0
        BN_zero(r);
378
0
        return 1;
379
116k
    } else if (i > 0)
380
82
        return (r == a) ? 1 : (BN_copy(r, a) != NULL);
381
382
116k
    if (r != a) {
383
4
        if (!bn_wexpand(r, BN_NIST_192_TOP))
384
0
            return 0;
385
4
        r_d = r->d;
386
4
        nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
387
4
    } else
388
116k
        r_d = a_d;
389
390
116k
    nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
391
116k
                 BN_NIST_192_TOP);
392
393
116k
#if defined(NIST_INT64)
394
116k
    {
395
116k
        NIST_INT64 acc;         /* accumulator */
396
116k
        unsigned int *rp = (unsigned int *)r_d;
397
116k
        const unsigned int *bp = (const unsigned int *)buf.ui;
398
399
116k
        acc = load_u32(&rp[0]);
400
116k
        acc += bp[3 * 2 - 6];
401
116k
        acc += bp[5 * 2 - 6];
402
116k
        store_lo32(&rp[0], acc);
403
116k
        acc >>= 32;
404
405
116k
        acc += load_u32(&rp[1]);
406
116k
        acc += bp[3 * 2 - 5];
407
116k
        acc += bp[5 * 2 - 5];
408
116k
        store_lo32(&rp[1], acc);
409
116k
        acc >>= 32;
410
411
116k
        acc += load_u32(&rp[2]);
412
116k
        acc += bp[3 * 2 - 6];
413
116k
        acc += bp[4 * 2 - 6];
414
116k
        acc += bp[5 * 2 - 6];
415
116k
        store_lo32(&rp[2], acc);
416
116k
        acc >>= 32;
417
418
116k
        acc += load_u32(&rp[3]);
419
116k
        acc += bp[3 * 2 - 5];
420
116k
        acc += bp[4 * 2 - 5];
421
116k
        acc += bp[5 * 2 - 5];
422
116k
        store_lo32(&rp[3], acc);
423
116k
        acc >>= 32;
424
425
116k
        acc += load_u32(&rp[4]);
426
116k
        acc += bp[4 * 2 - 6];
427
116k
        acc += bp[5 * 2 - 6];
428
116k
        store_lo32(&rp[4], acc);
429
116k
        acc >>= 32;
430
431
116k
        acc += load_u32(&rp[5]);
432
116k
        acc += bp[4 * 2 - 5];
433
116k
        acc += bp[5 * 2 - 5];
434
116k
        store_lo32(&rp[5], acc);
435
436
116k
        carry = (int)(acc >> 32);
437
116k
    }
438
#else
439
    {
440
        BN_ULONG t_d[BN_NIST_192_TOP];
441
442
        nist_set_192(t_d, buf.bn, 0, 3, 3);
443
        carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
444
        nist_set_192(t_d, buf.bn, 4, 4, 0);
445
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
446
        nist_set_192(t_d, buf.bn, 5, 5, 5)
447
            carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
448
    }
449
#endif
450
116k
    if (carry > 0)
451
83.2k
        carry =
452
83.2k
            (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
453
83.2k
                              BN_NIST_192_TOP);
454
33.2k
    else
455
33.2k
        carry = 1;
456
457
    /*
458
     * we need 'if (carry==0 || result>=modulus) result-=modulus;'
459
     * as comparison implies subtraction, we can write
460
     * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
461
     * this is what happens below, but without explicit if:-) a.
462
     */
463
116k
    res = (bn_sub_words(c_d, r_d, _nist_p_192[0], BN_NIST_192_TOP) && carry)
464
116k
        ? r_d
465
116k
        : c_d;
466
116k
    nist_cp_bn(r_d, res, BN_NIST_192_TOP);
467
116k
    r->top = BN_NIST_192_TOP;
468
116k
    bn_correct_top(r);
469
470
116k
    return 1;
471
116k
}
472
473
typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
474
                                 const BN_ULONG *, int);
475
476
#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
477
1.02M
        { \
478
1.02M
        bn_cp_32(to, 0, from, (a7) - 7) \
479
1.02M
        bn_cp_32(to, 1, from, (a6) - 7) \
480
1.02M
        bn_cp_32(to, 2, from, (a5) - 7) \
481
1.02M
        bn_cp_32(to, 3, from, (a4) - 7) \
482
1.02M
        bn_cp_32(to, 4, from, (a3) - 7) \
483
1.02M
        bn_cp_32(to, 5, from, (a2) - 7) \
484
1.02M
        bn_cp_32(to, 6, from, (a1) - 7) \
485
1.02M
        }
486
487
int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
488
                    BN_CTX *ctx)
489
204k
{
490
204k
    int top = a->top, i;
491
204k
    int carry;
492
204k
    BN_ULONG *r_d, *a_d = a->d;
493
204k
    union {
494
204k
        BN_ULONG bn[BN_NIST_224_TOP];
495
204k
        unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) /
496
204k
                        sizeof(unsigned int)];
497
204k
    } buf;
498
204k
    BN_ULONG c_d[BN_NIST_224_TOP], *res;
499
204k
    bn_addsub_f adjust;
500
204k
    static const BIGNUM ossl_bignum_nist_p_224_sqr = {
501
204k
        (BN_ULONG *)_nist_p_224_sqr,
502
204k
        OSSL_NELEM(_nist_p_224_sqr),
503
204k
        OSSL_NELEM(_nist_p_224_sqr),
504
204k
        0, BN_FLG_STATIC_DATA
505
204k
    };
506
507
204k
    field = &ossl_bignum_nist_p_224; /* just to make sure */
508
509
204k
    if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_224_sqr) >= 0)
510
3
        return BN_nnmod(r, a, field, ctx);
511
512
204k
    i = BN_ucmp(field, a);
513
204k
    if (i == 0) {
514
0
        BN_zero(r);
515
0
        return 1;
516
204k
    } else if (i > 0)
517
115
        return (r == a) ? 1 : (BN_copy(r, a) != NULL);
518
519
204k
    if (r != a) {
520
5
        if (!bn_wexpand(r, BN_NIST_224_TOP))
521
0
            return 0;
522
5
        r_d = r->d;
523
5
        nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
524
5
    } else
525
204k
        r_d = a_d;
526
527
204k
#if BN_BITS2==64
528
    /* copy upper 256 bits of 448 bit number ... */
529
204k
    nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
530
204k
                 top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
531
    /* ... and right shift by 32 to obtain upper 224 bits */
532
204k
    nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
533
    /* truncate lower part to 224 bits too */
534
204k
    r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
535
#else
536
    nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
537
                 BN_NIST_224_TOP);
538
#endif
539
540
#if defined(NIST_INT64) && BN_BITS2!=64
541
    {
542
        NIST_INT64 acc;         /* accumulator */
543
        unsigned int *rp = (unsigned int *)r_d;
544
        const unsigned int *bp = (const unsigned int *)buf.ui;
545
546
        acc = rp[0];
547
        acc -= bp[7 - 7];
548
        acc -= bp[11 - 7];
549
        rp[0] = (unsigned int)acc;
550
        acc >>= 32;
551
552
        acc += rp[1];
553
        acc -= bp[8 - 7];
554
        acc -= bp[12 - 7];
555
        rp[1] = (unsigned int)acc;
556
        acc >>= 32;
557
558
        acc += rp[2];
559
        acc -= bp[9 - 7];
560
        acc -= bp[13 - 7];
561
        rp[2] = (unsigned int)acc;
562
        acc >>= 32;
563
564
        acc += rp[3];
565
        acc += bp[7 - 7];
566
        acc += bp[11 - 7];
567
        acc -= bp[10 - 7];
568
        rp[3] = (unsigned int)acc;
569
        acc >>= 32;
570
571
        acc += rp[4];
572
        acc += bp[8 - 7];
573
        acc += bp[12 - 7];
574
        acc -= bp[11 - 7];
575
        rp[4] = (unsigned int)acc;
576
        acc >>= 32;
577
578
        acc += rp[5];
579
        acc += bp[9 - 7];
580
        acc += bp[13 - 7];
581
        acc -= bp[12 - 7];
582
        rp[5] = (unsigned int)acc;
583
        acc >>= 32;
584
585
        acc += rp[6];
586
        acc += bp[10 - 7];
587
        acc -= bp[13 - 7];
588
        rp[6] = (unsigned int)acc;
589
590
        carry = (int)(acc >> 32);
591
# if BN_BITS2==64
592
        rp[7] = carry;
593
# endif
594
    }
595
#else
596
204k
    {
597
204k
        BN_ULONG t_d[BN_NIST_224_TOP];
598
599
204k
        nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
600
204k
        carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
601
204k
        nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
602
204k
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
603
204k
        nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
604
204k
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
605
204k
        nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
606
204k
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
607
608
204k
# if BN_BITS2==64
609
204k
        carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
610
204k
# endif
611
204k
    }
612
204k
#endif
613
204k
    adjust = bn_sub_words;
614
204k
    if (carry > 0) {
615
53.1k
        carry =
616
53.1k
            (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
617
53.1k
                              BN_NIST_224_TOP);
618
53.1k
#if BN_BITS2==64
619
53.1k
        carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
620
53.1k
#endif
621
151k
    } else if (carry < 0) {
622
        /*
623
         * it's a bit more complicated logic in this case. if bn_add_words
624
         * yields no carry, then result has to be adjusted by unconditionally
625
         * *adding* the modulus. but if it does, then result has to be
626
         * compared to the modulus and conditionally adjusted by
627
         * *subtracting* the latter.
628
         */
629
17.6k
        carry =
630
17.6k
            (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
631
17.6k
                              BN_NIST_224_TOP);
632
17.6k
        adjust = carry ? bn_sub_words : bn_add_words;
633
17.6k
    } else
634
133k
        carry = 1;
635
636
    /* otherwise it's effectively same as in BN_nist_mod_192... */
637
204k
    res = ((*adjust) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP) && carry)
638
204k
        ? r_d
639
204k
        : c_d;
640
204k
    nist_cp_bn(r_d, res, BN_NIST_224_TOP);
641
204k
    r->top = BN_NIST_224_TOP;
642
204k
    bn_correct_top(r);
643
644
204k
    return 1;
645
204k
}
646
647
#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
648
        { \
649
        bn_cp_32(to, 0, from, (a8) - 8) \
650
        bn_cp_32(to, 1, from, (a7) - 8) \
651
        bn_cp_32(to, 2, from, (a6) - 8) \
652
        bn_cp_32(to, 3, from, (a5) - 8) \
653
        bn_cp_32(to, 4, from, (a4) - 8) \
654
        bn_cp_32(to, 5, from, (a3) - 8) \
655
        bn_cp_32(to, 6, from, (a2) - 8) \
656
        bn_cp_32(to, 7, from, (a1) - 8) \
657
        }
658
659
int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
660
                    BN_CTX *ctx)
661
549k
{
662
549k
    int i, top = a->top;
663
549k
    int carry = 0;
664
549k
    register BN_ULONG *a_d = a->d, *r_d;
665
549k
    union {
666
549k
        BN_ULONG bn[BN_NIST_256_TOP];
667
549k
        unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) /
668
549k
                        sizeof(unsigned int)];
669
549k
    } buf;
670
549k
    BN_ULONG c_d[BN_NIST_256_TOP], *res;
671
549k
    bn_addsub_f adjust;
672
549k
    static const BIGNUM ossl_bignum_nist_p_256_sqr = {
673
549k
        (BN_ULONG *)_nist_p_256_sqr,
674
549k
        OSSL_NELEM(_nist_p_256_sqr),
675
549k
        OSSL_NELEM(_nist_p_256_sqr),
676
549k
        0, BN_FLG_STATIC_DATA
677
549k
    };
678
679
549k
    field = &ossl_bignum_nist_p_256; /* just to make sure */
680
681
549k
    if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_256_sqr) >= 0)
682
4
        return BN_nnmod(r, a, field, ctx);
683
684
549k
    i = BN_ucmp(field, a);
685
549k
    if (i == 0) {
686
0
        BN_zero(r);
687
0
        return 1;
688
549k
    } else if (i > 0)
689
386
        return (r == a) ? 1 : (BN_copy(r, a) != NULL);
690
691
548k
    if (r != a) {
692
4
        if (!bn_wexpand(r, BN_NIST_256_TOP))
693
0
            return 0;
694
4
        r_d = r->d;
695
4
        nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
696
4
    } else
697
548k
        r_d = a_d;
698
699
548k
    nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
700
548k
                 BN_NIST_256_TOP);
701
702
548k
#if defined(NIST_INT64)
703
548k
    {
704
548k
        NIST_INT64 acc;         /* accumulator */
705
548k
        unsigned int *rp = (unsigned int *)r_d;
706
548k
        const unsigned int *bp = (const unsigned int *)buf.ui;
707
708
548k
        acc = load_u32(&rp[0]);
709
548k
        acc += bp[8 - 8];
710
548k
        acc += bp[9 - 8];
711
548k
        acc -= bp[11 - 8];
712
548k
        acc -= bp[12 - 8];
713
548k
        acc -= bp[13 - 8];
714
548k
        acc -= bp[14 - 8];
715
548k
        store_lo32(&rp[0], acc);
716
548k
        acc >>= 32;
717
718
548k
        acc += load_u32(&rp[1]);
719
548k
        acc += bp[9 - 8];
720
548k
        acc += bp[10 - 8];
721
548k
        acc -= bp[12 - 8];
722
548k
        acc -= bp[13 - 8];
723
548k
        acc -= bp[14 - 8];
724
548k
        acc -= bp[15 - 8];
725
548k
        store_lo32(&rp[1], acc);
726
548k
        acc >>= 32;
727
728
548k
        acc += load_u32(&rp[2]);
729
548k
        acc += bp[10 - 8];
730
548k
        acc += bp[11 - 8];
731
548k
        acc -= bp[13 - 8];
732
548k
        acc -= bp[14 - 8];
733
548k
        acc -= bp[15 - 8];
734
548k
        store_lo32(&rp[2], acc);
735
548k
        acc >>= 32;
736
737
548k
        acc += load_u32(&rp[3]);
738
548k
        acc += bp[11 - 8];
739
548k
        acc += bp[11 - 8];
740
548k
        acc += bp[12 - 8];
741
548k
        acc += bp[12 - 8];
742
548k
        acc += bp[13 - 8];
743
548k
        acc -= bp[15 - 8];
744
548k
        acc -= bp[8 - 8];
745
548k
        acc -= bp[9 - 8];
746
548k
        store_lo32(&rp[3], acc);
747
548k
        acc >>= 32;
748
749
548k
        acc += load_u32(&rp[4]);
750
548k
        acc += bp[12 - 8];
751
548k
        acc += bp[12 - 8];
752
548k
        acc += bp[13 - 8];
753
548k
        acc += bp[13 - 8];
754
548k
        acc += bp[14 - 8];
755
548k
        acc -= bp[9 - 8];
756
548k
        acc -= bp[10 - 8];
757
548k
        store_lo32(&rp[4], acc);
758
548k
        acc >>= 32;
759
760
548k
        acc += load_u32(&rp[5]);
761
548k
        acc += bp[13 - 8];
762
548k
        acc += bp[13 - 8];
763
548k
        acc += bp[14 - 8];
764
548k
        acc += bp[14 - 8];
765
548k
        acc += bp[15 - 8];
766
548k
        acc -= bp[10 - 8];
767
548k
        acc -= bp[11 - 8];
768
548k
        store_lo32(&rp[5], acc);
769
548k
        acc >>= 32;
770
771
548k
        acc += load_u32(&rp[6]);
772
548k
        acc += bp[14 - 8];
773
548k
        acc += bp[14 - 8];
774
548k
        acc += bp[15 - 8];
775
548k
        acc += bp[15 - 8];
776
548k
        acc += bp[14 - 8];
777
548k
        acc += bp[13 - 8];
778
548k
        acc -= bp[8 - 8];
779
548k
        acc -= bp[9 - 8];
780
548k
        store_lo32(&rp[6], acc);
781
548k
        acc >>= 32;
782
783
548k
        acc += load_u32(&rp[7]);
784
548k
        acc += bp[15 - 8];
785
548k
        acc += bp[15 - 8];
786
548k
        acc += bp[15 - 8];
787
548k
        acc += bp[8 - 8];
788
548k
        acc -= bp[10 - 8];
789
548k
        acc -= bp[11 - 8];
790
548k
        acc -= bp[12 - 8];
791
548k
        acc -= bp[13 - 8];
792
548k
        store_lo32(&rp[7], acc);
793
794
548k
        carry = (int)(acc >> 32);
795
548k
    }
796
#else
797
    {
798
        BN_ULONG t_d[BN_NIST_256_TOP];
799
800
        /*
801
         * S1
802
         */
803
        nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
804
        /*
805
         * S2
806
         */
807
        nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
808
        carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
809
        /* left shift */
810
        {
811
            register BN_ULONG *ap, t, c;
812
            ap = t_d;
813
            c = 0;
814
            for (i = BN_NIST_256_TOP; i != 0; --i) {
815
                t = *ap;
816
                *(ap++) = ((t << 1) | c) & BN_MASK2;
817
                c = (t & BN_TBIT) ? 1 : 0;
818
            }
819
            carry <<= 1;
820
            carry |= c;
821
        }
822
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
823
        /*
824
         * S3
825
         */
826
        nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
827
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
828
        /*
829
         * S4
830
         */
831
        nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
832
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
833
        /*
834
         * D1
835
         */
836
        nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
837
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
838
        /*
839
         * D2
840
         */
841
        nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
842
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
843
        /*
844
         * D3
845
         */
846
        nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
847
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
848
        /*
849
         * D4
850
         */
851
        nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
852
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
853
854
    }
855
#endif
856
    /* see BN_nist_mod_224 for explanation */
857
548k
    adjust = bn_sub_words;
858
548k
    if (carry > 0)
859
82.6k
        carry =
860
82.6k
            (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
861
82.6k
                              BN_NIST_256_TOP);
862
466k
    else if (carry < 0) {
863
317k
        carry =
864
317k
            (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
865
317k
                              BN_NIST_256_TOP);
866
317k
        adjust = carry ? bn_sub_words : bn_add_words;
867
317k
    } else
868
148k
        carry = 1;
869
870
548k
    res = ((*adjust) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP) && carry)
871
548k
        ? r_d
872
548k
        : c_d;
873
548k
    nist_cp_bn(r_d, res, BN_NIST_256_TOP);
874
548k
    r->top = BN_NIST_256_TOP;
875
548k
    bn_correct_top(r);
876
877
548k
    return 1;
878
548k
}
879
880
#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
881
        { \
882
        bn_cp_32(to, 0, from,  (a12) - 12) \
883
        bn_cp_32(to, 1, from,  (a11) - 12) \
884
        bn_cp_32(to, 2, from,  (a10) - 12) \
885
        bn_cp_32(to, 3, from,  (a9) - 12)  \
886
        bn_cp_32(to, 4, from,  (a8) - 12)  \
887
        bn_cp_32(to, 5, from,  (a7) - 12)  \
888
        bn_cp_32(to, 6, from,  (a6) - 12)  \
889
        bn_cp_32(to, 7, from,  (a5) - 12)  \
890
        bn_cp_32(to, 8, from,  (a4) - 12)  \
891
        bn_cp_32(to, 9, from,  (a3) - 12)  \
892
        bn_cp_32(to, 10, from, (a2) - 12)  \
893
        bn_cp_32(to, 11, from, (a1) - 12)  \
894
        }
895
896
int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
897
                    BN_CTX *ctx)
898
636k
{
899
636k
    int i, top = a->top;
900
636k
    int carry = 0;
901
636k
    register BN_ULONG *r_d, *a_d = a->d;
902
636k
    union {
903
636k
        BN_ULONG bn[BN_NIST_384_TOP];
904
636k
        unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) /
905
636k
                        sizeof(unsigned int)];
906
636k
    } buf;
907
636k
    BN_ULONG c_d[BN_NIST_384_TOP], *res;
908
636k
    bn_addsub_f adjust;
909
636k
    static const BIGNUM ossl_bignum_nist_p_384_sqr = {
910
636k
        (BN_ULONG *)_nist_p_384_sqr,
911
636k
        OSSL_NELEM(_nist_p_384_sqr),
912
636k
        OSSL_NELEM(_nist_p_384_sqr),
913
636k
        0, BN_FLG_STATIC_DATA
914
636k
    };
915
916
636k
    field = &ossl_bignum_nist_p_384; /* just to make sure */
917
918
636k
    if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_384_sqr) >= 0)
919
4
        return BN_nnmod(r, a, field, ctx);
920
921
636k
    i = BN_ucmp(field, a);
922
636k
    if (i == 0) {
923
0
        BN_zero(r);
924
0
        return 1;
925
636k
    } else if (i > 0)
926
249
        return (r == a) ? 1 : (BN_copy(r, a) != NULL);
927
928
636k
    if (r != a) {
929
2
        if (!bn_wexpand(r, BN_NIST_384_TOP))
930
0
            return 0;
931
2
        r_d = r->d;
932
2
        nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
933
2
    } else
934
636k
        r_d = a_d;
935
936
636k
    nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
937
636k
                 BN_NIST_384_TOP);
938
939
636k
#if defined(NIST_INT64)
940
636k
    {
941
636k
        NIST_INT64 acc;         /* accumulator */
942
636k
        unsigned int *rp = (unsigned int *)r_d;
943
636k
        const unsigned int *bp = (const unsigned int *)buf.ui;
944
945
636k
        acc = load_u32(&rp[0]);
946
636k
        acc += bp[12 - 12];
947
636k
        acc += bp[21 - 12];
948
636k
        acc += bp[20 - 12];
949
636k
        acc -= bp[23 - 12];
950
636k
        store_lo32(&rp[0], acc);
951
636k
        acc >>= 32;
952
953
636k
        acc += load_u32(&rp[1]);
954
636k
        acc += bp[13 - 12];
955
636k
        acc += bp[22 - 12];
956
636k
        acc += bp[23 - 12];
957
636k
        acc -= bp[12 - 12];
958
636k
        acc -= bp[20 - 12];
959
636k
        store_lo32(&rp[1], acc);
960
636k
        acc >>= 32;
961
962
636k
        acc += load_u32(&rp[2]);
963
636k
        acc += bp[14 - 12];
964
636k
        acc += bp[23 - 12];
965
636k
        acc -= bp[13 - 12];
966
636k
        acc -= bp[21 - 12];
967
636k
        store_lo32(&rp[2], acc);
968
636k
        acc >>= 32;
969
970
636k
        acc += load_u32(&rp[3]);
971
636k
        acc += bp[15 - 12];
972
636k
        acc += bp[12 - 12];
973
636k
        acc += bp[20 - 12];
974
636k
        acc += bp[21 - 12];
975
636k
        acc -= bp[14 - 12];
976
636k
        acc -= bp[22 - 12];
977
636k
        acc -= bp[23 - 12];
978
636k
        store_lo32(&rp[3], acc);
979
636k
        acc >>= 32;
980
981
636k
        acc += load_u32(&rp[4]);
982
636k
        acc += bp[21 - 12];
983
636k
        acc += bp[21 - 12];
984
636k
        acc += bp[16 - 12];
985
636k
        acc += bp[13 - 12];
986
636k
        acc += bp[12 - 12];
987
636k
        acc += bp[20 - 12];
988
636k
        acc += bp[22 - 12];
989
636k
        acc -= bp[15 - 12];
990
636k
        acc -= bp[23 - 12];
991
636k
        acc -= bp[23 - 12];
992
636k
        store_lo32(&rp[4], acc);
993
636k
        acc >>= 32;
994
995
636k
        acc += load_u32(&rp[5]);
996
636k
        acc += bp[22 - 12];
997
636k
        acc += bp[22 - 12];
998
636k
        acc += bp[17 - 12];
999
636k
        acc += bp[14 - 12];
1000
636k
        acc += bp[13 - 12];
1001
636k
        acc += bp[21 - 12];
1002
636k
        acc += bp[23 - 12];
1003
636k
        acc -= bp[16 - 12];
1004
636k
        store_lo32(&rp[5], acc);
1005
636k
        acc >>= 32;
1006
1007
636k
        acc += load_u32(&rp[6]);
1008
636k
        acc += bp[23 - 12];
1009
636k
        acc += bp[23 - 12];
1010
636k
        acc += bp[18 - 12];
1011
636k
        acc += bp[15 - 12];
1012
636k
        acc += bp[14 - 12];
1013
636k
        acc += bp[22 - 12];
1014
636k
        acc -= bp[17 - 12];
1015
636k
        store_lo32(&rp[6], acc);
1016
636k
        acc >>= 32;
1017
1018
636k
        acc += load_u32(&rp[7]);
1019
636k
        acc += bp[19 - 12];
1020
636k
        acc += bp[16 - 12];
1021
636k
        acc += bp[15 - 12];
1022
636k
        acc += bp[23 - 12];
1023
636k
        acc -= bp[18 - 12];
1024
636k
        store_lo32(&rp[7], acc);
1025
636k
        acc >>= 32;
1026
1027
636k
        acc += load_u32(&rp[8]);
1028
636k
        acc += bp[20 - 12];
1029
636k
        acc += bp[17 - 12];
1030
636k
        acc += bp[16 - 12];
1031
636k
        acc -= bp[19 - 12];
1032
636k
        store_lo32(&rp[8], acc);
1033
636k
        acc >>= 32;
1034
1035
636k
        acc += load_u32(&rp[9]);
1036
636k
        acc += bp[21 - 12];
1037
636k
        acc += bp[18 - 12];
1038
636k
        acc += bp[17 - 12];
1039
636k
        acc -= bp[20 - 12];
1040
636k
        store_lo32(&rp[9], acc);
1041
636k
        acc >>= 32;
1042
1043
636k
        acc += load_u32(&rp[10]);
1044
636k
        acc += bp[22 - 12];
1045
636k
        acc += bp[19 - 12];
1046
636k
        acc += bp[18 - 12];
1047
636k
        acc -= bp[21 - 12];
1048
636k
        store_lo32(&rp[10], acc);
1049
636k
        acc >>= 32;
1050
1051
636k
        acc += load_u32(&rp[11]);
1052
636k
        acc += bp[23 - 12];
1053
636k
        acc += bp[20 - 12];
1054
636k
        acc += bp[19 - 12];
1055
636k
        acc -= bp[22 - 12];
1056
636k
        store_lo32(&rp[11], acc);
1057
1058
636k
        carry = (int)(acc >> 32);
1059
636k
    }
1060
#else
1061
    {
1062
        BN_ULONG t_d[BN_NIST_384_TOP];
1063
1064
        /*
1065
         * S1
1066
         */
1067
        nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
1068
        /* left shift */
1069
        {
1070
            register BN_ULONG *ap, t, c;
1071
            ap = t_d;
1072
            c = 0;
1073
            for (i = 3; i != 0; --i) {
1074
                t = *ap;
1075
                *(ap++) = ((t << 1) | c) & BN_MASK2;
1076
                c = (t & BN_TBIT) ? 1 : 0;
1077
            }
1078
            *ap = c;
1079
        }
1080
        carry =
1081
            (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
1082
                              t_d, BN_NIST_256_TOP);
1083
        /*
1084
         * S2
1085
         */
1086
        carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
1087
        /*
1088
         * S3
1089
         */
1090
        nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,
1091
                     21);
1092
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1093
        /*
1094
         * S4
1095
         */
1096
        nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23,
1097
                     0);
1098
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1099
        /*
1100
         * S5
1101
         */
1102
        nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
1103
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1104
        /*
1105
         * S6
1106
         */
1107
        nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
1108
        carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1109
        /*
1110
         * D1
1111
         */
1112
        nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
1113
                     23);
1114
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1115
        /*
1116
         * D2
1117
         */
1118
        nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
1119
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1120
        /*
1121
         * D3
1122
         */
1123
        nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
1124
        carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1125
1126
    }
1127
#endif
1128
    /* see BN_nist_mod_224 for explanation */
1129
636k
    adjust = bn_sub_words;
1130
636k
    if (carry > 0)
1131
435k
        carry =
1132
435k
            (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
1133
435k
                              BN_NIST_384_TOP);
1134
200k
    else if (carry < 0) {
1135
10.3k
        carry =
1136
10.3k
            (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
1137
10.3k
                              BN_NIST_384_TOP);
1138
10.3k
        adjust = carry ? bn_sub_words : bn_add_words;
1139
10.3k
    } else
1140
190k
        carry = 1;
1141
1142
636k
    res = ((*adjust) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP) && carry)
1143
636k
        ? r_d
1144
636k
        : c_d;
1145
636k
    nist_cp_bn(r_d, res, BN_NIST_384_TOP);
1146
636k
    r->top = BN_NIST_384_TOP;
1147
636k
    bn_correct_top(r);
1148
1149
636k
    return 1;
1150
636k
}
1151
1152
10.8M
#define BN_NIST_521_RSHIFT      (521%BN_BITS2)
1153
5.40M
#define BN_NIST_521_LSHIFT      (BN_BITS2-BN_NIST_521_RSHIFT)
1154
600k
#define BN_NIST_521_TOP_MASK    ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
1155
1156
int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1157
                    BN_CTX *ctx)
1158
600k
{
1159
600k
    int top = a->top, i;
1160
600k
    BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
1161
600k
    static const BIGNUM ossl_bignum_nist_p_521_sqr = {
1162
600k
        (BN_ULONG *)_nist_p_521_sqr,
1163
600k
        OSSL_NELEM(_nist_p_521_sqr),
1164
600k
        OSSL_NELEM(_nist_p_521_sqr),
1165
600k
        0, BN_FLG_STATIC_DATA
1166
600k
    };
1167
1168
600k
    field = &ossl_bignum_nist_p_521; /* just to make sure */
1169
1170
600k
    if (BN_is_negative(a) || BN_ucmp(a, &ossl_bignum_nist_p_521_sqr) >= 0)
1171
3
        return BN_nnmod(r, a, field, ctx);
1172
1173
600k
    i = BN_ucmp(field, a);
1174
600k
    if (i == 0) {
1175
0
        BN_zero(r);
1176
0
        return 1;
1177
600k
    } else if (i > 0)
1178
144
        return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1179
1180
600k
    if (r != a) {
1181
2
        if (!bn_wexpand(r, BN_NIST_521_TOP))
1182
0
            return 0;
1183
2
        r_d = r->d;
1184
2
        nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
1185
2
    } else
1186
600k
        r_d = a_d;
1187
1188
    /* upper 521 bits, copy ... */
1189
600k
    nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
1190
600k
                 top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
1191
    /* ... and right shift */
1192
5.40M
    for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
1193
#if 0
1194
        /*
1195
         * MSC ARM compiler [version 2013, presumably even earlier,
1196
         * much earlier] miscompiles this code, but not one in
1197
         * #else section. See RT#3541.
1198
         */
1199
        tmp = val >> BN_NIST_521_RSHIFT;
1200
        val = t_d[i + 1];
1201
        t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
1202
#else
1203
4.80M
        t_d[i] = (val >> BN_NIST_521_RSHIFT |
1204
4.80M
                  (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2;
1205
4.80M
        val = tmp;
1206
4.80M
#endif
1207
4.80M
    }
1208
600k
    t_d[i] = val >> BN_NIST_521_RSHIFT;
1209
    /* lower 521 bits */
1210
600k
    r_d[i] &= BN_NIST_521_TOP_MASK;
1211
1212
600k
    bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
1213
600k
    res = bn_sub_words(t_d, r_d, _nist_p_521,
1214
600k
                       BN_NIST_521_TOP)
1215
600k
        ? r_d
1216
600k
        : t_d;
1217
600k
    nist_cp_bn(r_d, res, BN_NIST_521_TOP);
1218
600k
    r->top = BN_NIST_521_TOP;
1219
600k
    bn_correct_top(r);
1220
1221
600k
    return 1;
1222
600k
}
1223
1224
int (*BN_nist_mod_func(const BIGNUM *p)) (BIGNUM *r, const BIGNUM *a,
1225
941
                                          const BIGNUM *field, BN_CTX *ctx) {
1226
941
    if (BN_ucmp(&ossl_bignum_nist_p_192, p) == 0)
1227
59
        return BN_nist_mod_192;
1228
882
    if (BN_ucmp(&ossl_bignum_nist_p_224, p) == 0)
1229
87
        return BN_nist_mod_224;
1230
795
    if (BN_ucmp(&ossl_bignum_nist_p_256, p) == 0)
1231
161
        return BN_nist_mod_256;
1232
634
    if (BN_ucmp(&ossl_bignum_nist_p_384, p) == 0)
1233
124
        return BN_nist_mod_384;
1234
510
    if (BN_ucmp(&ossl_bignum_nist_p_521, p) == 0)
1235
90
        return BN_nist_mod_521;
1236
420
    return 0;
1237
510
}