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 *dst, const BN_ULONG *src, int top, int max)
306 OPENSSL_assert(top <= max);
308 for (i = 0; i < top; i++)
314 static void nist_cp_bn(BN_ULONG *dst, const BN_ULONG *src, int top)
318 for (i = 0; i < top; i++)
323 # define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
324 # define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0;
326 * two following macros are implemented under assumption that they
327 * are called in a sequence with *ascending* n, i.e. as they are...
329 # 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))\
330 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l)))
331 # define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0));
332 # define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n)
333 # if defined(L_ENDIAN)
334 # if defined(__arch64__)
335 # define NIST_INT64 long
337 # define NIST_INT64 long long
341 # define bn_cp_64(to, n, from, m) \
343 bn_cp_32(to, (n)*2, from, (m)*2); \
344 bn_cp_32(to, (n)*2+1, from, (m)*2+1); \
346 # define bn_64_set_0(to, n) \
348 bn_32_set_0(to, (n)*2); \
349 bn_32_set_0(to, (n)*2+1); \
351 # define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0;
352 # define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0;
353 # if defined(_WIN32) && !defined(__GNUC__)
354 # define NIST_INT64 __int64
355 # elif defined(BN_LLONG)
356 # define NIST_INT64 long long
358 #endif /* BN_BITS2 != 64 */
360 #define nist_set_192(to, from, a1, a2, a3) \
362 bn_cp_64(to, 0, from, (a3) - 3) \
363 bn_cp_64(to, 1, from, (a2) - 3) \
364 bn_cp_64(to, 2, from, (a1) - 3) \
367 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
372 register BN_ULONG *r_d, *a_d = a->d;
374 BN_ULONG bn[BN_NIST_192_TOP];
375 unsigned int ui[BN_NIST_192_TOP * sizeof(BN_ULONG) /
376 sizeof(unsigned int)];
378 BN_ULONG c_d[BN_NIST_192_TOP], *res;
380 static const BIGNUM _bignum_nist_p_192_sqr = {
381 (BN_ULONG *)_nist_p_192_sqr,
382 sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
383 sizeof(_nist_p_192_sqr) / sizeof(_nist_p_192_sqr[0]),
384 0, BN_FLG_STATIC_DATA
387 field = &_bignum_nist_p_192; /* just to make sure */
389 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0)
390 return BN_nnmod(r, a, field, ctx);
392 i = BN_ucmp(field, a);
397 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
400 if (!bn_wexpand(r, BN_NIST_192_TOP))
403 nist_cp_bn(r_d, a_d, BN_NIST_192_TOP);
407 nist_cp_bn_0(buf.bn, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP,
410 #if defined(NIST_INT64)
412 NIST_INT64 acc; /* accumulator */
413 unsigned int *rp = (unsigned int *)r_d;
414 const unsigned int *bp = (const unsigned int *)buf.ui;
417 acc += bp[3 * 2 - 6];
418 acc += bp[5 * 2 - 6];
419 rp[0] = (unsigned int)acc;
423 acc += bp[3 * 2 - 5];
424 acc += bp[5 * 2 - 5];
425 rp[1] = (unsigned int)acc;
429 acc += bp[3 * 2 - 6];
430 acc += bp[4 * 2 - 6];
431 acc += bp[5 * 2 - 6];
432 rp[2] = (unsigned int)acc;
436 acc += bp[3 * 2 - 5];
437 acc += bp[4 * 2 - 5];
438 acc += bp[5 * 2 - 5];
439 rp[3] = (unsigned int)acc;
443 acc += bp[4 * 2 - 6];
444 acc += bp[5 * 2 - 6];
445 rp[4] = (unsigned int)acc;
449 acc += bp[4 * 2 - 5];
450 acc += bp[5 * 2 - 5];
451 rp[5] = (unsigned int)acc;
453 carry = (int)(acc >> 32);
457 BN_ULONG t_d[BN_NIST_192_TOP];
459 nist_set_192(t_d, buf.bn, 0, 3, 3);
460 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
461 nist_set_192(t_d, buf.bn, 4, 4, 0);
462 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
463 nist_set_192(t_d, buf.bn, 5, 5, 5)
464 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP);
469 (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1],
475 * we need 'if (carry==0 || result>=modulus) result-=modulus;'
476 * as comparison implies subtraction, we can write
477 * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;'
478 * this is what happens below, but without explicit if:-) a.
481 0 - (PTR_SIZE_INT) bn_sub_words(c_d, r_d, _nist_p_192[0],
483 mask &= 0 - (PTR_SIZE_INT) carry;
486 (((PTR_SIZE_INT) res & ~mask) | ((PTR_SIZE_INT) r_d & mask));
487 nist_cp_bn(r_d, res, BN_NIST_192_TOP);
488 r->top = BN_NIST_192_TOP;
494 typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *,
495 const BN_ULONG *, int);
497 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \
499 bn_cp_32(to, 0, from, (a7) - 7) \
500 bn_cp_32(to, 1, from, (a6) - 7) \
501 bn_cp_32(to, 2, from, (a5) - 7) \
502 bn_cp_32(to, 3, from, (a4) - 7) \
503 bn_cp_32(to, 4, from, (a3) - 7) \
504 bn_cp_32(to, 5, from, (a2) - 7) \
505 bn_cp_32(to, 6, from, (a1) - 7) \
508 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
513 BN_ULONG *r_d, *a_d = a->d;
515 BN_ULONG bn[BN_NIST_224_TOP];
516 unsigned int ui[BN_NIST_224_TOP * sizeof(BN_ULONG) /
517 sizeof(unsigned int)];
519 BN_ULONG c_d[BN_NIST_224_TOP], *res;
525 static const BIGNUM _bignum_nist_p_224_sqr = {
526 (BN_ULONG *)_nist_p_224_sqr,
527 sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
528 sizeof(_nist_p_224_sqr) / sizeof(_nist_p_224_sqr[0]),
529 0, BN_FLG_STATIC_DATA
532 field = &_bignum_nist_p_224; /* just to make sure */
534 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0)
535 return BN_nnmod(r, a, field, ctx);
537 i = BN_ucmp(field, a);
542 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
545 if (!bn_wexpand(r, BN_NIST_224_TOP))
548 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP);
553 /* copy upper 256 bits of 448 bit number ... */
554 nist_cp_bn_0(c_d, a_d + (BN_NIST_224_TOP - 1),
555 top - (BN_NIST_224_TOP - 1), BN_NIST_224_TOP);
556 /* ... and right shift by 32 to obtain upper 224 bits */
557 nist_set_224(buf.bn, c_d, 14, 13, 12, 11, 10, 9, 8);
558 /* truncate lower part to 224 bits too */
559 r_d[BN_NIST_224_TOP - 1] &= BN_MASK2l;
561 nist_cp_bn_0(buf.bn, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP,
565 #if defined(NIST_INT64) && BN_BITS2!=64
567 NIST_INT64 acc; /* accumulator */
568 unsigned int *rp = (unsigned int *)r_d;
569 const unsigned int *bp = (const unsigned int *)buf.ui;
574 rp[0] = (unsigned int)acc;
580 rp[1] = (unsigned int)acc;
586 rp[2] = (unsigned int)acc;
593 rp[3] = (unsigned int)acc;
600 rp[4] = (unsigned int)acc;
607 rp[5] = (unsigned int)acc;
613 rp[6] = (unsigned int)acc;
615 carry = (int)(acc >> 32);
622 BN_ULONG t_d[BN_NIST_224_TOP];
624 nist_set_224(t_d, buf.bn, 10, 9, 8, 7, 0, 0, 0);
625 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
626 nist_set_224(t_d, buf.bn, 0, 13, 12, 11, 0, 0, 0);
627 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP);
628 nist_set_224(t_d, buf.bn, 13, 12, 11, 10, 9, 8, 7);
629 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
630 nist_set_224(t_d, buf.bn, 0, 0, 0, 0, 13, 12, 11);
631 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP);
634 carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32);
641 (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1],
644 carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1;
646 } else if (carry < 0) {
648 * it's a bit more comlicated logic in this case. if bn_add_words
649 * yields no carry, then result has to be adjusted by unconditionally
650 * *adding* the modulus. but if it does, then result has to be
651 * compared to the modulus and conditionally adjusted by
652 * *subtracting* the latter.
655 (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1],
657 mask = 0 - (PTR_SIZE_INT) carry;
658 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
659 ((PTR_SIZE_INT) bn_add_words & ~mask);
663 /* otherwise it's effectively same as in BN_nist_mod_192... */
665 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_224[0], BN_NIST_224_TOP);
666 mask &= 0 - (PTR_SIZE_INT) carry;
668 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
669 ((PTR_SIZE_INT) r_d & mask));
670 nist_cp_bn(r_d, res, BN_NIST_224_TOP);
671 r->top = BN_NIST_224_TOP;
677 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \
679 bn_cp_32(to, 0, from, (a8) - 8) \
680 bn_cp_32(to, 1, from, (a7) - 8) \
681 bn_cp_32(to, 2, from, (a6) - 8) \
682 bn_cp_32(to, 3, from, (a5) - 8) \
683 bn_cp_32(to, 4, from, (a4) - 8) \
684 bn_cp_32(to, 5, from, (a3) - 8) \
685 bn_cp_32(to, 6, from, (a2) - 8) \
686 bn_cp_32(to, 7, from, (a1) - 8) \
689 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
694 register BN_ULONG *a_d = a->d, *r_d;
696 BN_ULONG bn[BN_NIST_256_TOP];
697 unsigned int ui[BN_NIST_256_TOP * sizeof(BN_ULONG) /
698 sizeof(unsigned int)];
700 BN_ULONG c_d[BN_NIST_256_TOP], *res;
706 static const BIGNUM _bignum_nist_p_256_sqr = {
707 (BN_ULONG *)_nist_p_256_sqr,
708 sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
709 sizeof(_nist_p_256_sqr) / sizeof(_nist_p_256_sqr[0]),
710 0, BN_FLG_STATIC_DATA
713 field = &_bignum_nist_p_256; /* just to make sure */
715 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0)
716 return BN_nnmod(r, a, field, ctx);
718 i = BN_ucmp(field, a);
723 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
726 if (!bn_wexpand(r, BN_NIST_256_TOP))
729 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP);
733 nist_cp_bn_0(buf.bn, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP,
736 #if defined(NIST_INT64)
738 NIST_INT64 acc; /* accumulator */
739 unsigned int *rp = (unsigned int *)r_d;
740 const unsigned int *bp = (const unsigned int *)buf.ui;
749 rp[0] = (unsigned int)acc;
759 rp[1] = (unsigned int)acc;
768 rp[2] = (unsigned int)acc;
780 rp[3] = (unsigned int)acc;
791 rp[4] = (unsigned int)acc;
802 rp[5] = (unsigned int)acc;
814 rp[6] = (unsigned int)acc;
826 rp[7] = (unsigned int)acc;
828 carry = (int)(acc >> 32);
832 BN_ULONG t_d[BN_NIST_256_TOP];
837 nist_set_256(t_d, buf.bn, 15, 14, 13, 12, 11, 0, 0, 0);
841 nist_set_256(c_d, buf.bn, 0, 15, 14, 13, 12, 0, 0, 0);
842 carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP);
845 register BN_ULONG *ap, t, c;
848 for (i = BN_NIST_256_TOP; i != 0; --i) {
850 *(ap++) = ((t << 1) | c) & BN_MASK2;
851 c = (t & BN_TBIT) ? 1 : 0;
856 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
860 nist_set_256(t_d, buf.bn, 15, 14, 0, 0, 0, 10, 9, 8);
861 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
865 nist_set_256(t_d, buf.bn, 8, 13, 15, 14, 13, 11, 10, 9);
866 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP);
870 nist_set_256(t_d, buf.bn, 10, 8, 0, 0, 0, 13, 12, 11);
871 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
875 nist_set_256(t_d, buf.bn, 11, 9, 0, 0, 15, 14, 13, 12);
876 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
880 nist_set_256(t_d, buf.bn, 12, 0, 10, 9, 8, 15, 14, 13);
881 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
885 nist_set_256(t_d, buf.bn, 13, 0, 11, 10, 9, 0, 15, 14);
886 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP);
890 /* see BN_nist_mod_224 for explanation */
894 (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1],
896 else if (carry < 0) {
898 (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1],
900 mask = 0 - (PTR_SIZE_INT) carry;
901 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
902 ((PTR_SIZE_INT) bn_add_words & ~mask);
907 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_256[0], BN_NIST_256_TOP);
908 mask &= 0 - (PTR_SIZE_INT) carry;
910 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
911 ((PTR_SIZE_INT) r_d & mask));
912 nist_cp_bn(r_d, res, BN_NIST_256_TOP);
913 r->top = BN_NIST_256_TOP;
919 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \
921 bn_cp_32(to, 0, from, (a12) - 12) \
922 bn_cp_32(to, 1, from, (a11) - 12) \
923 bn_cp_32(to, 2, from, (a10) - 12) \
924 bn_cp_32(to, 3, from, (a9) - 12) \
925 bn_cp_32(to, 4, from, (a8) - 12) \
926 bn_cp_32(to, 5, from, (a7) - 12) \
927 bn_cp_32(to, 6, from, (a6) - 12) \
928 bn_cp_32(to, 7, from, (a5) - 12) \
929 bn_cp_32(to, 8, from, (a4) - 12) \
930 bn_cp_32(to, 9, from, (a3) - 12) \
931 bn_cp_32(to, 10, from, (a2) - 12) \
932 bn_cp_32(to, 11, from, (a1) - 12) \
935 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
940 register BN_ULONG *r_d, *a_d = a->d;
942 BN_ULONG bn[BN_NIST_384_TOP];
943 unsigned int ui[BN_NIST_384_TOP * sizeof(BN_ULONG) /
944 sizeof(unsigned int)];
946 BN_ULONG c_d[BN_NIST_384_TOP], *res;
952 static const BIGNUM _bignum_nist_p_384_sqr = {
953 (BN_ULONG *)_nist_p_384_sqr,
954 sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
955 sizeof(_nist_p_384_sqr) / sizeof(_nist_p_384_sqr[0]),
956 0, BN_FLG_STATIC_DATA
959 field = &_bignum_nist_p_384; /* just to make sure */
961 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0)
962 return BN_nnmod(r, a, field, ctx);
964 i = BN_ucmp(field, a);
969 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
972 if (!bn_wexpand(r, BN_NIST_384_TOP))
975 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP);
979 nist_cp_bn_0(buf.bn, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP,
982 #if defined(NIST_INT64)
984 NIST_INT64 acc; /* accumulator */
985 unsigned int *rp = (unsigned int *)r_d;
986 const unsigned int *bp = (const unsigned int *)buf.ui;
993 rp[0] = (unsigned int)acc;
1002 rp[1] = (unsigned int)acc;
1010 rp[2] = (unsigned int)acc;
1021 rp[3] = (unsigned int)acc;
1035 rp[4] = (unsigned int)acc;
1047 rp[5] = (unsigned int)acc;
1058 rp[6] = (unsigned int)acc;
1067 rp[7] = (unsigned int)acc;
1075 rp[8] = (unsigned int)acc;
1083 rp[9] = (unsigned int)acc;
1091 rp[10] = (unsigned int)acc;
1099 rp[11] = (unsigned int)acc;
1101 carry = (int)(acc >> 32);
1105 BN_ULONG t_d[BN_NIST_384_TOP];
1110 nist_set_256(t_d, buf.bn, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4);
1113 register BN_ULONG *ap, t, c;
1116 for (i = 3; i != 0; --i) {
1118 *(ap++) = ((t << 1) | c) & BN_MASK2;
1119 c = (t & BN_TBIT) ? 1 : 0;
1124 (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2),
1125 t_d, BN_NIST_256_TOP);
1129 carry += (int)bn_add_words(r_d, r_d, buf.bn, BN_NIST_384_TOP);
1133 nist_set_384(t_d, buf.bn, 20, 19, 18, 17, 16, 15, 14, 13, 12, 23, 22,
1135 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1139 nist_set_384(t_d, buf.bn, 19, 18, 17, 16, 15, 14, 13, 12, 20, 0, 23,
1141 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1145 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 23, 22, 21, 20, 0, 0, 0, 0);
1146 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1150 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 23, 22, 21, 0, 0, 20);
1151 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1155 nist_set_384(t_d, buf.bn, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12,
1157 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1161 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 22, 21, 20, 0);
1162 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1166 nist_set_384(t_d, buf.bn, 0, 0, 0, 0, 0, 0, 0, 23, 23, 0, 0, 0);
1167 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP);
1171 /* see BN_nist_mod_224 for explanation */
1175 (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1],
1177 else if (carry < 0) {
1179 (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1],
1181 mask = 0 - (PTR_SIZE_INT) carry;
1182 u.p = ((PTR_SIZE_INT) bn_sub_words & mask) |
1183 ((PTR_SIZE_INT) bn_add_words & ~mask);
1188 0 - (PTR_SIZE_INT) (*u.f) (c_d, r_d, _nist_p_384[0], BN_NIST_384_TOP);
1189 mask &= 0 - (PTR_SIZE_INT) carry;
1191 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1192 ((PTR_SIZE_INT) r_d & mask));
1193 nist_cp_bn(r_d, res, BN_NIST_384_TOP);
1194 r->top = BN_NIST_384_TOP;
1200 #define BN_NIST_521_RSHIFT (521%BN_BITS2)
1201 #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT)
1202 #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT)
1204 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field,
1207 int top = a->top, i;
1208 BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res;
1210 static const BIGNUM _bignum_nist_p_521_sqr = {
1211 (BN_ULONG *)_nist_p_521_sqr,
1212 sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
1213 sizeof(_nist_p_521_sqr) / sizeof(_nist_p_521_sqr[0]),
1214 0, BN_FLG_STATIC_DATA
1217 field = &_bignum_nist_p_521; /* just to make sure */
1219 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0)
1220 return BN_nnmod(r, a, field, ctx);
1222 i = BN_ucmp(field, a);
1227 return (r == a) ? 1 : (BN_copy(r, a) != NULL);
1230 if (!bn_wexpand(r, BN_NIST_521_TOP))
1233 nist_cp_bn(r_d, a_d, BN_NIST_521_TOP);
1237 /* upper 521 bits, copy ... */
1238 nist_cp_bn_0(t_d, a_d + (BN_NIST_521_TOP - 1),
1239 top - (BN_NIST_521_TOP - 1), BN_NIST_521_TOP);
1240 /* ... and right shift */
1241 for (val = t_d[0], i = 0; i < BN_NIST_521_TOP - 1; i++) {
1242 t_d[i] = (val >> BN_NIST_521_RSHIFT |
1243 (tmp = t_d[i + 1]) << BN_NIST_521_LSHIFT) & BN_MASK2;
1246 t_d[i] = val >> BN_NIST_521_RSHIFT;
1247 /* lower 521 bits */
1248 r_d[i] &= BN_NIST_521_TOP_MASK;
1250 bn_add_words(r_d, r_d, t_d, BN_NIST_521_TOP);
1252 0 - (PTR_SIZE_INT) bn_sub_words(t_d, r_d, _nist_p_521,
1255 res = (BN_ULONG *)(((PTR_SIZE_INT) res & ~mask) |
1256 ((PTR_SIZE_INT) r_d & mask));
1257 nist_cp_bn(r_d, res, BN_NIST_521_TOP);
1258 r->top = BN_NIST_521_TOP;