1 /* crypto/bn/bn_nist.c */
3 * Written by Nils Larsch for the OpenSSL project
5 /* ====================================================================
6 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
15 * 2. Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
20 * 3. All advertising materials mentioning features or use of this
21 * software must display the following acknowledgment:
22 * "This product includes software developed by the OpenSSL Project
23 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
25 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
26 * endorse or promote products derived from this software without
27 * prior written permission. For written permission, please contact
28 * openssl-core@openssl.org.
30 * 5. Products derived from this software may not be called "OpenSSL"
31 * nor may "OpenSSL" appear in their names without prior written
32 * permission of the OpenSSL Project.
34 * 6. Redistributions of any form whatsoever must retain the following
36 * "This product includes software developed by the OpenSSL Project
37 * for use in the OpenSSL Toolkit (http://www.openssl.org/)"
39 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
40 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
41 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
42 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR
43 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
44 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
45 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
46 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
48 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
49 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
50 * OF THE POSSIBILITY OF SUCH DAMAGE.
51 * ====================================================================
53 * This product includes cryptographic software written by Eric Young
54 * (eay@cryptsoft.com). This product includes software written by Tim
55 * Hudson (tjh@cryptsoft.com).
62 #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2
63 #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2
64 #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2
65 #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2
66 #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2
68 /* pre-computed tables are "carry-less" values of modulus*(i+1) */
70 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
71 {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL},
72 {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL},
73 {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL}
76 static const BN_ULONG _nist_p_192_sqr[] = {
77 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL,
78 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL
81 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
82 {0x0000000000000001ULL, 0xFFFFFFFF00000000ULL,
83 0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL},
84 {0x0000000000000002ULL, 0xFFFFFFFE00000000ULL,
85 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFFULL} /* this one is
89 static const BN_ULONG _nist_p_224_sqr[] = {
90 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
91 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL,
92 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL,
96 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
97 {0xFFFFFFFFFFFFFFFFULL, 0x00000000FFFFFFFFULL,
98 0x0000000000000000ULL, 0xFFFFFFFF00000001ULL},
99 {0xFFFFFFFFFFFFFFFEULL, 0x00000001FFFFFFFFULL,
100 0x0000000000000000ULL, 0xFFFFFFFE00000002ULL},
101 {0xFFFFFFFFFFFFFFFDULL, 0x00000002FFFFFFFFULL,
102 0x0000000000000000ULL, 0xFFFFFFFD00000003ULL},
103 {0xFFFFFFFFFFFFFFFCULL, 0x00000003FFFFFFFFULL,
104 0x0000000000000000ULL, 0xFFFFFFFC00000004ULL},
105 {0xFFFFFFFFFFFFFFFBULL, 0x00000004FFFFFFFFULL,
106 0x0000000000000000ULL, 0xFFFFFFFB00000005ULL},
109 static const BN_ULONG _nist_p_256_sqr[] = {
110 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL,
111 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL,
112 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL,
113 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL
116 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
117 {0x00000000FFFFFFFFULL, 0xFFFFFFFF00000000ULL, 0xFFFFFFFFFFFFFFFEULL,
118 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
119 {0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
120 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
121 {0x00000002FFFFFFFDULL, 0xFFFFFFFD00000000ULL, 0xFFFFFFFFFFFFFFFCULL,
122 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
123 {0x00000003FFFFFFFCULL, 0xFFFFFFFC00000000ULL, 0xFFFFFFFFFFFFFFFBULL,
124 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
125 {0x00000004FFFFFFFBULL, 0xFFFFFFFB00000000ULL, 0xFFFFFFFFFFFFFFFAULL,
126 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL},
129 static const BN_ULONG _nist_p_384_sqr[] = {
130 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL,
131 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL,
132 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL,
133 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL
136 static const BN_ULONG _nist_p_521[] =
137 { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
138 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
139 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
140 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
141 0x00000000000001FFULL
144 static const BN_ULONG _nist_p_521_sqr[] = {
145 0x0000000000000001ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
146 0x0000000000000000ULL, 0x0000000000000000ULL, 0x0000000000000000ULL,
147 0x0000000000000000ULL, 0x0000000000000000ULL, 0xFFFFFFFFFFFFFC00ULL,
148 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
149 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL,
150 0xFFFFFFFFFFFFFFFFULL, 0x000000000003FFFFULL
153 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = {
154 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
155 {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
156 {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
159 static const BN_ULONG _nist_p_192_sqr[] = {
160 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000,
161 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
164 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = {
165 {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF,
166 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
167 {0x00000002, 0x00000000, 0x00000000, 0xFFFFFFFE,
168 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
171 static const BN_ULONG _nist_p_224_sqr[] = {
172 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
173 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000002,
174 0x00000000, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFF,
175 0xFFFFFFFF, 0xFFFFFFFF
178 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = {
179 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000,
180 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF},
181 {0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000001,
182 0x00000000, 0x00000000, 0x00000002, 0xFFFFFFFE},
183 {0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000002,
184 0x00000000, 0x00000000, 0x00000003, 0xFFFFFFFD},
185 {0xFFFFFFFC, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000003,
186 0x00000000, 0x00000000, 0x00000004, 0xFFFFFFFC},
187 {0xFFFFFFFB, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000004,
188 0x00000000, 0x00000000, 0x00000005, 0xFFFFFFFB},
191 static const BN_ULONG _nist_p_256_sqr[] = {
192 0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFE,
193 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0x00000001,
194 0xFFFFFFFE, 0x00000001, 0xFFFFFFFE, 0x00000001,
195 0x00000001, 0xFFFFFFFE, 0x00000002, 0xFFFFFFFE
198 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = {
199 {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF,
200 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
201 {0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
202 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
203 {0xFFFFFFFD, 0x00000002, 0x00000000, 0xFFFFFFFD, 0xFFFFFFFC, 0xFFFFFFFF,
204 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
205 {0xFFFFFFFC, 0x00000003, 0x00000000, 0xFFFFFFFC, 0xFFFFFFFB, 0xFFFFFFFF,
206 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
207 {0xFFFFFFFB, 0x00000004, 0x00000000, 0xFFFFFFFB, 0xFFFFFFFA, 0xFFFFFFFF,
208 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF},
211 static const BN_ULONG _nist_p_384_sqr[] = {
212 0x00000001, 0xFFFFFFFE, 0x00000000, 0x00000002, 0x00000000, 0xFFFFFFFE,
213 0x00000000, 0x00000002, 0x00000001, 0x00000000, 0x00000000, 0x00000000,
214 0xFFFFFFFE, 0x00000001, 0x00000000, 0xFFFFFFFE, 0xFFFFFFFD, 0xFFFFFFFF,
215 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF
218 static const BN_ULONG _nist_p_521[] = { 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
219 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
220 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
221 0xFFFFFFFF, 0x000001FF
224 static const BN_ULONG _nist_p_521_sqr[] = {
225 0x00000001, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
226 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000,
227 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0xFFFFFC00, 0xFFFFFFFF,
228 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
229 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF,
230 0xFFFFFFFF, 0xFFFFFFFF, 0x0003FFFF
233 # error "unsupported BN_BITS2"
236 static const BIGNUM _bignum_nist_p_192 = {
237 (BN_ULONG *)_nist_p_192[0],
244 static const BIGNUM _bignum_nist_p_224 = {
245 (BN_ULONG *)_nist_p_224[0],
252 static const BIGNUM _bignum_nist_p_256 = {
253 (BN_ULONG *)_nist_p_256[0],
260 static const BIGNUM _bignum_nist_p_384 = {
261 (BN_ULONG *)_nist_p_384[0],
268 static const BIGNUM _bignum_nist_p_521 = {
269 (BN_ULONG *)_nist_p_521,
276 const BIGNUM *BN_get0_nist_prime_192(void)
278 return &_bignum_nist_p_192;
281 const BIGNUM *BN_get0_nist_prime_224(void)
283 return &_bignum_nist_p_224;
286 const BIGNUM *BN_get0_nist_prime_256(void)
288 return &_bignum_nist_p_256;
291 const BIGNUM *BN_get0_nist_prime_384(void)
293 return &_bignum_nist_p_384;
296 const BIGNUM *BN_get0_nist_prime_521(void)
298 return &_bignum_nist_p_521;
301 static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max)
304 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
307 OPENSSL_assert(top <= max);
309 for (i = (top); i != 0; i--)
311 for (i = (max) - (top); i != 0; i--)
312 *_tmp1++ = (BN_ULONG)0;
315 static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top)
318 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a);
319 for (i = (top); i != 0; i--)
324 # define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
325 # define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0;
327 * two following macros are implemented under assumption that they
328 * are called in a sequence with *ascending* n, i.e. as they are...
330 # 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))\
331 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
332 # define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
333 # define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
335 # define bn_cp_64(to, n, from, m) \
337 bn_cp_32(to, (n)*2, from, (m)*2); \
338 bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
340 # define bn_64_set_0(to, n) \
342 bn_32_set_0(to, (n)*2); \
343 bn_32_set_0(to, (n)*2+1); \
346 # define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
347 # define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
349 #endif /* BN_BITS2 != 64 */
351 #define nist_set_192(to, from, a1, a2, a3) \
353 bn_cp_64(to, 0, from, (a3) - 3) \
354 bn_cp_64(to, 1, from, (a2) - 3) \
355 bn_cp_64(to, 2, from, (a1) - 3) \
358 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
363 register BN_ULONG *r_d, *a_d = a->d;
364 BN_ULONG t_d[BN_NIST_192_TOP],
365 buf[BN_NIST_192_TOP], c_d[BN_NIST_192_TOP], *res;
367 static const BIGNUM _bignum_nist_p_192_sqr = {
368 (BN_ULONG *)_nist_p_192_sqr,
369 sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
370 sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
371 0, BN_FLG_STATIC_DATA
374 field = &_bignum_nist_p_192; /* just to make sure */
376 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
377 return BN_nnmod(r, a, field, ctx);
379 i = BN_ucmp(field, a);
384 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
387 if (!bn_wexpand(r, BN_NIST_192_TOP))
390 nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
394 nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
397 nist_set_192(t_d, buf, 0, 3, 3);
398 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
399 nist_set_192(t_d, buf, 4, 4, 0);
400 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
401 nist_set_192(t_d, buf, 5, 5, 5)
402 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
406 (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
412 * we need 'if (carry==0 || result>=modulus) result-=modulus;'
413 * as comparison implies subtraction, we can write
414 * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
415 * this is what happens below, but without explicit if:-) a.
418 0 - (size_t)bn_sub_words(c_d, r_d, _nist_p_192[0], BN_NIST_192_TOP);
419 mask &= 0 - (size_t)carry;
420 res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
421 nist_cp_bn(r_d, res, BN_NIST_192_TOP);
422 r->top = BN_NIST_192_TOP;
428 typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
429 const BN_ULONG *, int);
431 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
433 bn_cp_32(to, 0, from, (a7) - 7) \
434 bn_cp_32(to, 1, from, (a6) - 7) \
435 bn_cp_32(to, 2, from, (a5) - 7) \
436 bn_cp_32(to, 3, from, (a4) - 7) \
437 bn_cp_32(to, 4, from, (a3) - 7) \
438 bn_cp_32(to, 5, from, (a2) - 7) \
439 bn_cp_32(to, 6, from, (a1) - 7) \
442 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
447 BN_ULONG *r_d, *a_d = a->d;
448 BN_ULONG t_d[BN_NIST_224_TOP],
449 buf[BN_NIST_224_TOP], c_d[BN_NIST_224_TOP], *res;
455 static const BIGNUM _bignum_nist_p_224_sqr = {
456 (BN_ULONG *)_nist_p_224_sqr,
457 sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
458 sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
459 0, BN_FLG_STATIC_DATA
462 field = &_bignum_nist_p_224; /* just to make sure */
464 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
465 return BN_nnmod(r, a, field, ctx);
467 i = BN_ucmp(field, a);
472 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
475 if (!bn_wexpand(r, BN_NIST_224_TOP))
478 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
483 /* copy upper 256 bits of 448 bit number ... */
484 nist_cp_bn_0(t_d, a_d + (BN_NIST_224_TOP - 1),
485 top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
486 /* ... and right shift by 32 to obtain upper 224 bits */
487 nist_set_224(buf, t_d, 14, 13, 12, 11, 10, 9, 8);
488 /* truncate lower part to 224 bits too */
489 r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
491 nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
494 nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0);
495 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
496 nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0);
497 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
498 nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7);
499 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
500 nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11);
501 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
504 carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
509 (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
512 carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
514 } else if (carry < 0) {
516 * it's a bit more comlicated logic in this case. if bn_add_words
517 * yields no carry, then result has to be adjusted by unconditionally
518 * *adding* the modulus. but if it does, then result has to be
519 * compared to the modulus and conditionally adjusted by
520 * *subtracting* the latter.
523 (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
525 mask = 0 - (size_t)carry;
526 u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask);
530 /* otherwise it's effectively same as in BN_nist_mod_192... */
531 mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
532 mask &= 0 - (size_t)carry;
533 res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
534 nist_cp_bn(r_d, res, BN_NIST_224_TOP);
535 r->top = BN_NIST_224_TOP;
541 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
543 bn_cp_32(to, 0, from, (a8) - 8) \
544 bn_cp_32(to, 1, from, (a7) - 8) \
545 bn_cp_32(to, 2, from, (a6) - 8) \
546 bn_cp_32(to, 3, from, (a5) - 8) \
547 bn_cp_32(to, 4, from, (a4) - 8) \
548 bn_cp_32(to, 5, from, (a3) - 8) \
549 bn_cp_32(to, 6, from, (a2) - 8) \
550 bn_cp_32(to, 7, from, (a1) - 8) \
553 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
558 register BN_ULONG *a_d = a->d, *r_d;
559 BN_ULONG t_d[BN_NIST_256_TOP],
560 buf[BN_NIST_256_TOP], c_d[BN_NIST_256_TOP], *res;
566 static const BIGNUM _bignum_nist_p_256_sqr = {
567 (BN_ULONG *)_nist_p_256_sqr,
568 sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
569 sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
570 0, BN_FLG_STATIC_DATA
573 field = &_bignum_nist_p_256; /* just to make sure */
575 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
576 return BN_nnmod(r, a, field, ctx);
578 i = BN_ucmp(field, a);
583 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
586 if (!bn_wexpand(r, BN_NIST_256_TOP))
589 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
593 nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
599 nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0);
603 nist_set_256(c_d, buf, 0, 15, 14, 13, 12, 0, 0, 0);
604 carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
607 register BN_ULONG *ap, t, c;
610 for (i = BN_NIST_256_TOP; i != 0; --i) {
612 *(ap++) = ((t << 1) | c) & BN_MASK2;
613 c = (t & BN_TBIT) ? 1 : 0;
618 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
622 nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8);
623 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
627 nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9);
628 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
632 nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11);
633 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
637 nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12);
638 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
642 nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13);
643 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
647 nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14);
648 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
650 /* see BN_nist_mod_224 for explanation */
654 (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
656 else if (carry < 0) {
658 (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
660 mask = 0 - (size_t)carry;
661 u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask);
665 mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
666 mask &= 0 - (size_t)carry;
667 res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
668 nist_cp_bn(r_d, res, BN_NIST_256_TOP);
669 r->top = BN_NIST_256_TOP;
675 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
677 bn_cp_32(to, 0, from, (a12) - 12) \
678 bn_cp_32(to, 1, from, (a11) - 12) \
679 bn_cp_32(to, 2, from, (a10) - 12) \
680 bn_cp_32(to, 3, from, (a9) - 12) \
681 bn_cp_32(to, 4, from, (a8) - 12) \
682 bn_cp_32(to, 5, from, (a7) - 12) \
683 bn_cp_32(to, 6, from, (a6) - 12) \
684 bn_cp_32(to, 7, from, (a5) - 12) \
685 bn_cp_32(to, 8, from, (a4) - 12) \
686 bn_cp_32(to, 9, from, (a3) - 12) \
687 bn_cp_32(to, 10, from, (a2) - 12) \
688 bn_cp_32(to, 11, from, (a1) - 12) \
691 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
696 register BN_ULONG *r_d, *a_d = a->d;
697 BN_ULONG t_d[BN_NIST_384_TOP],
698 buf[BN_NIST_384_TOP], c_d[BN_NIST_384_TOP], *res;
704 static const BIGNUM _bignum_nist_p_384_sqr = {
705 (BN_ULONG *)_nist_p_384_sqr,
706 sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
707 sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
708 0, BN_FLG_STATIC_DATA
711 field = &_bignum_nist_p_384; /* just to make sure */
713 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
714 return BN_nnmod(r, a, field, ctx);
716 i = BN_ucmp(field, a);
721 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
724 if (!bn_wexpand(r, BN_NIST_384_TOP))
727 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
731 nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
737 nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
740 register BN_ULONG *ap, t, c;
743 for (i = 3; i != 0; --i) {
745 *(ap++) = ((t << 1) | c) & BN_MASK2;
746 c = (t & BN_TBIT) ? 1 : 0;
750 carry = (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
751 t_d, BN_NIST_256_TOP);
755 carry += (int)bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP);
759 nist_set_384(t_d, buf, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22, 21);
760 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
764 nist_set_384(t_d, buf, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23, 0);
765 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
769 nist_set_384(t_d, buf, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
770 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
774 nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
775 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
779 nist_set_384(t_d, buf, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23);
780 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
784 nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
785 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
789 nist_set_384(t_d, buf, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
790 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
792 /* see BN_nist_mod_224 for explanation */
796 (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
798 else if (carry < 0) {
800 (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
802 mask = 0 - (size_t)carry;
803 u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask);
807 mask = 0 - (size_t)(*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
808 mask &= 0 - (size_t)carry;
809 res = (BN_ULONG *)(((size_t)c_d & ~mask) | ((size_t)r_d & mask));
810 nist_cp_bn(r_d, res, BN_NIST_384_TOP);
811 r->top = BN_NIST_384_TOP;
817 #define BN_NIST_521_RSHIFT (521%BN_BITS2)
818 #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT)
819 #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
821 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
825 BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
827 static const BIGNUM _bignum_nist_p_521_sqr = {
828 (BN_ULONG *)_nist_p_521_sqr,
829 sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
830 sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
831 0, BN_FLG_STATIC_DATA
834 field = &_bignum_nist_p_521; /* just to make sure */
836 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
837 return BN_nnmod(r, a, field, ctx);
839 i = BN_ucmp(field, a);
844 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
847 if (!bn_wexpand(r, BN_NIST_521_TOP))
850 nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
854 /* upper 521 bits, copy ... */
855 nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
856 top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
857 /* ... and right shift */
858 for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
859 tmp = val >> BN_NIST_521_RSHIFT;
861 t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2;
863 t_d[i] = val >> BN_NIST_521_RSHIFT;
865 r_d[i] &= BN_NIST_521_TOP_MASK;
867 bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
868 mask = 0 - (size_t)bn_sub_words(t_d, r_d, _nist_p_521, BN_NIST_521_TOP);
869 res = (BN_ULONG *)(((size_t)t_d & ~mask) | ((size_t)r_d & mask));
870 nist_cp_bn(r_d, res, BN_NIST_521_TOP);
871 r->top = BN_NIST_521_TOP;