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