bn_nist.c revision 296465
1/* crypto/bn/bn_nist.c */ 2/* 3 * Written by Nils Larsch for the OpenSSL project 4 */ 5/* ==================================================================== 6 * Copyright (c) 1998-2005 The OpenSSL Project. All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 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 18 * distribution. 19 * 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/)" 24 * 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. 29 * 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. 33 * 34 * 6. Redistributions of any form whatsoever must retain the following 35 * acknowledgment: 36 * "This product includes software developed by the OpenSSL Project 37 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 38 * 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 * ==================================================================== 52 * 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). 56 * 57 */ 58 59#include "bn_lcl.h" 60#include "cryptlib.h" 61 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 67 68/* pre-computed tables are "carry-less" values of modulus*(i+1) */ 69#if BN_BITS2 == 64 70static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 71 {0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFFULL}, 72 {0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL}, 73 {0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFCULL, 0xFFFFFFFFFFFFFFFFULL} 74}; 75 76static const BN_ULONG _nist_p_192_sqr[] = { 77 0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000001ULL, 78 0xFFFFFFFFFFFFFFFEULL, 0xFFFFFFFFFFFFFFFDULL, 0xFFFFFFFFFFFFFFFFULL 79}; 80 81static 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 86 * "carry-full" */ 87}; 88 89static const BN_ULONG _nist_p_224_sqr[] = { 90 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 91 0xFFFFFFFFFFFFFFFFULL, 0x0000000200000000ULL, 92 0x0000000000000000ULL, 0xFFFFFFFFFFFFFFFEULL, 93 0xFFFFFFFFFFFFFFFFULL 94}; 95 96static 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}, 107}; 108 109static const BN_ULONG _nist_p_256_sqr[] = { 110 0x0000000000000001ULL, 0xFFFFFFFE00000000ULL, 111 0xFFFFFFFFFFFFFFFFULL, 0x00000001FFFFFFFEULL, 112 0x00000001FFFFFFFEULL, 0x00000001FFFFFFFEULL, 113 0xFFFFFFFE00000001ULL, 0xFFFFFFFE00000002ULL 114}; 115 116static 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}, 127}; 128 129static const BN_ULONG _nist_p_384_sqr[] = { 130 0xFFFFFFFE00000001ULL, 0x0000000200000000ULL, 0xFFFFFFFE00000000ULL, 131 0x0000000200000000ULL, 0x0000000000000001ULL, 0x0000000000000000ULL, 132 0x00000001FFFFFFFEULL, 0xFFFFFFFE00000000ULL, 0xFFFFFFFFFFFFFFFDULL, 133 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL 134}; 135 136static const BN_ULONG _nist_p_521[] = 137 { 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 138 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 139 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 140 0xFFFFFFFFFFFFFFFFULL, 0xFFFFFFFFFFFFFFFFULL, 141 0x00000000000001FFULL 142}; 143 144static 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 151}; 152#elif BN_BITS2 == 32 153static 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} 157}; 158 159static const BN_ULONG _nist_p_192_sqr[] = { 160 0x00000001, 0x00000000, 0x00000002, 0x00000000, 0x00000001, 0x00000000, 161 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFD, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF 162}; 163 164static 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} 169}; 170 171static 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 176}; 177 178static 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}, 189}; 190 191static 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 196}; 197 198static 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}, 209}; 210 211static 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 216}; 217 218static 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 222}; 223 224static 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 231}; 232#else 233# error "unsupported BN_BITS2" 234#endif 235 236static const BIGNUM _bignum_nist_p_192 = { 237 (BN_ULONG *)_nist_p_192[0], 238 BN_NIST_192_TOP, 239 BN_NIST_192_TOP, 240 0, 241 BN_FLG_STATIC_DATA 242}; 243 244static const BIGNUM _bignum_nist_p_224 = { 245 (BN_ULONG *)_nist_p_224[0], 246 BN_NIST_224_TOP, 247 BN_NIST_224_TOP, 248 0, 249 BN_FLG_STATIC_DATA 250}; 251 252static const BIGNUM _bignum_nist_p_256 = { 253 (BN_ULONG *)_nist_p_256[0], 254 BN_NIST_256_TOP, 255 BN_NIST_256_TOP, 256 0, 257 BN_FLG_STATIC_DATA 258}; 259 260static const BIGNUM _bignum_nist_p_384 = { 261 (BN_ULONG *)_nist_p_384[0], 262 BN_NIST_384_TOP, 263 BN_NIST_384_TOP, 264 0, 265 BN_FLG_STATIC_DATA 266}; 267 268static const BIGNUM _bignum_nist_p_521 = { 269 (BN_ULONG *)_nist_p_521, 270 BN_NIST_521_TOP, 271 BN_NIST_521_TOP, 272 0, 273 BN_FLG_STATIC_DATA 274}; 275 276const BIGNUM *BN_get0_nist_prime_192(void) 277{ 278 return &_bignum_nist_p_192; 279} 280 281const BIGNUM *BN_get0_nist_prime_224(void) 282{ 283 return &_bignum_nist_p_224; 284} 285 286const BIGNUM *BN_get0_nist_prime_256(void) 287{ 288 return &_bignum_nist_p_256; 289} 290 291const BIGNUM *BN_get0_nist_prime_384(void) 292{ 293 return &_bignum_nist_p_384; 294} 295 296const BIGNUM *BN_get0_nist_prime_521(void) 297{ 298 return &_bignum_nist_p_521; 299} 300 301static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max) 302{ 303 int i; 304 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 305 306#ifdef BN_DEBUG 307 OPENSSL_assert(top <= max); 308#endif 309 for (i = (top); i != 0; i--) 310 *_tmp1++ = *_tmp2++; 311 for (i = (max) - (top); i != 0; i--) 312 *_tmp1++ = (BN_ULONG)0; 313} 314 315static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top) 316{ 317 int i; 318 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 319 for (i = (top); i != 0; i--) 320 *_tmp1++ = *_tmp2++; 321} 322 323#if BN_BITS2 == 64 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; 326/* 327 * two following macros are implemented under assumption that they 328 * are called in a sequence with *ascending* n, i.e. as they are... 329 */ 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) 334#else 335# define bn_cp_64(to, n, from, m) \ 336 { \ 337 bn_cp_32(to, (n)*2, from, (m)*2); \ 338 bn_cp_32(to, (n)*2+1, from, (m)*2+1); \ 339 } 340# define bn_64_set_0(to, n) \ 341 { \ 342 bn_32_set_0(to, (n)*2); \ 343 bn_32_set_0(to, (n)*2+1); \ 344 } 345# if BN_BITS2 == 32 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; 348# endif 349#endif /* BN_BITS2 != 64 */ 350 351#define nist_set_192(to, from, a1, a2, a3) \ 352 { \ 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) \ 356 } 357 358int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 359 BN_CTX *ctx) 360{ 361 int top = a->top, i; 362 int carry; 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; 366 size_t mask; 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 372 }; 373 374 field = &_bignum_nist_p_192; /* just to make sure */ 375 376 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_192_sqr) >= 0) 377 return BN_nnmod(r, a, field, ctx); 378 379 i = BN_ucmp(field, a); 380 if (i == 0) { 381 BN_zero(r); 382 return 1; 383 } else if (i > 0) 384 return (r == a) ? 1 : (BN_copy(r, a) != NULL); 385 386 if (r != a) { 387 if (!bn_wexpand(r, BN_NIST_192_TOP)) 388 return 0; 389 r_d = r->d; 390 nist_cp_bn(r_d, a_d, BN_NIST_192_TOP); 391 } else 392 r_d = a_d; 393 394 nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, 395 BN_NIST_192_TOP); 396 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); 403 404 if (carry > 0) 405 carry = 406 (int)bn_sub_words(r_d, r_d, _nist_p_192[carry - 1], 407 BN_NIST_192_TOP); 408 else 409 carry = 1; 410 411 /* 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. 416 */ 417 mask = 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; 423 bn_correct_top(r); 424 425 return 1; 426} 427 428typedef BN_ULONG (*bn_addsub_f) (BN_ULONG *, const BN_ULONG *, 429 const BN_ULONG *, int); 430 431#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ 432 { \ 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) \ 440 } 441 442int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 443 BN_CTX *ctx) 444{ 445 int top = a->top, i; 446 int carry; 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; 450 size_t mask; 451 union { 452 bn_addsub_f f; 453 size_t p; 454 } u; 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 460 }; 461 462 field = &_bignum_nist_p_224; /* just to make sure */ 463 464 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_224_sqr) >= 0) 465 return BN_nnmod(r, a, field, ctx); 466 467 i = BN_ucmp(field, a); 468 if (i == 0) { 469 BN_zero(r); 470 return 1; 471 } else if (i > 0) 472 return (r == a) ? 1 : (BN_copy(r, a) != NULL); 473 474 if (r != a) { 475 if (!bn_wexpand(r, BN_NIST_224_TOP)) 476 return 0; 477 r_d = r->d; 478 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); 479 } else 480 r_d = a_d; 481 482#if BN_BITS2==64 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; 490#else 491 nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, 492 BN_NIST_224_TOP); 493#endif 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); 502 503#if BN_BITS2==64 504 carry = (int)(r_d[BN_NIST_224_TOP - 1] >> 32); 505#endif 506 u.f = bn_sub_words; 507 if (carry > 0) { 508 carry = 509 (int)bn_sub_words(r_d, r_d, _nist_p_224[carry - 1], 510 BN_NIST_224_TOP); 511#if BN_BITS2==64 512 carry = (int)(~(r_d[BN_NIST_224_TOP - 1] >> 32)) & 1; 513#endif 514 } else if (carry < 0) { 515 /* 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. 521 */ 522 carry = 523 (int)bn_add_words(r_d, r_d, _nist_p_224[-carry - 1], 524 BN_NIST_224_TOP); 525 mask = 0 - (size_t)carry; 526 u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask); 527 } else 528 carry = 1; 529 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; 536 bn_correct_top(r); 537 538 return 1; 539} 540 541#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ 542 { \ 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) \ 551 } 552 553int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 554 BN_CTX *ctx) 555{ 556 int i, top = a->top; 557 int carry = 0; 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; 561 size_t mask; 562 union { 563 bn_addsub_f f; 564 size_t p; 565 } u; 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 571 }; 572 573 field = &_bignum_nist_p_256; /* just to make sure */ 574 575 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_256_sqr) >= 0) 576 return BN_nnmod(r, a, field, ctx); 577 578 i = BN_ucmp(field, a); 579 if (i == 0) { 580 BN_zero(r); 581 return 1; 582 } else if (i > 0) 583 return (r == a) ? 1 : (BN_copy(r, a) != NULL); 584 585 if (r != a) { 586 if (!bn_wexpand(r, BN_NIST_256_TOP)) 587 return 0; 588 r_d = r->d; 589 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); 590 } else 591 r_d = a_d; 592 593 nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, 594 BN_NIST_256_TOP); 595 596 /* 597 * S1 598 */ 599 nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0); 600 /* 601 * S2 602 */ 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); 605 /* left shift */ 606 { 607 register BN_ULONG *ap, t, c; 608 ap = t_d; 609 c = 0; 610 for (i = BN_NIST_256_TOP; i != 0; --i) { 611 t = *ap; 612 *(ap++) = ((t << 1) | c) & BN_MASK2; 613 c = (t & BN_TBIT) ? 1 : 0; 614 } 615 carry <<= 1; 616 carry |= c; 617 } 618 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 619 /* 620 * S3 621 */ 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); 624 /* 625 * S4 626 */ 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); 629 /* 630 * D1 631 */ 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); 634 /* 635 * D2 636 */ 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); 639 /* 640 * D3 641 */ 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); 644 /* 645 * D4 646 */ 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); 649 650 /* see BN_nist_mod_224 for explanation */ 651 u.f = bn_sub_words; 652 if (carry > 0) 653 carry = 654 (int)bn_sub_words(r_d, r_d, _nist_p_256[carry - 1], 655 BN_NIST_256_TOP); 656 else if (carry < 0) { 657 carry = 658 (int)bn_add_words(r_d, r_d, _nist_p_256[-carry - 1], 659 BN_NIST_256_TOP); 660 mask = 0 - (size_t)carry; 661 u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask); 662 } else 663 carry = 1; 664 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; 670 bn_correct_top(r); 671 672 return 1; 673} 674 675#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ 676 { \ 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) \ 689 } 690 691int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 692 BN_CTX *ctx) 693{ 694 int i, top = a->top; 695 int carry = 0; 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; 699 size_t mask; 700 union { 701 bn_addsub_f f; 702 size_t p; 703 } u; 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 709 }; 710 711 field = &_bignum_nist_p_384; /* just to make sure */ 712 713 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_384_sqr) >= 0) 714 return BN_nnmod(r, a, field, ctx); 715 716 i = BN_ucmp(field, a); 717 if (i == 0) { 718 BN_zero(r); 719 return 1; 720 } else if (i > 0) 721 return (r == a) ? 1 : (BN_copy(r, a) != NULL); 722 723 if (r != a) { 724 if (!bn_wexpand(r, BN_NIST_384_TOP)) 725 return 0; 726 r_d = r->d; 727 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); 728 } else 729 r_d = a_d; 730 731 nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, 732 BN_NIST_384_TOP); 733 734 /* 735 * S1 736 */ 737 nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23 - 4, 22 - 4, 21 - 4); 738 /* left shift */ 739 { 740 register BN_ULONG *ap, t, c; 741 ap = t_d; 742 c = 0; 743 for (i = 3; i != 0; --i) { 744 t = *ap; 745 *(ap++) = ((t << 1) | c) & BN_MASK2; 746 c = (t & BN_TBIT) ? 1 : 0; 747 } 748 *ap = c; 749 } 750 carry = (int)bn_add_words(r_d + (128 / BN_BITS2), r_d + (128 / BN_BITS2), 751 t_d, BN_NIST_256_TOP); 752 /* 753 * S2 754 */ 755 carry += (int)bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP); 756 /* 757 * S3 758 */ 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); 761 /* 762 * S4 763 */ 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); 766 /* 767 * S5 768 */ 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); 771 /* 772 * S6 773 */ 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); 776 /* 777 * D1 778 */ 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); 781 /* 782 * D2 783 */ 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); 786 /* 787 * D3 788 */ 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); 791 792 /* see BN_nist_mod_224 for explanation */ 793 u.f = bn_sub_words; 794 if (carry > 0) 795 carry = 796 (int)bn_sub_words(r_d, r_d, _nist_p_384[carry - 1], 797 BN_NIST_384_TOP); 798 else if (carry < 0) { 799 carry = 800 (int)bn_add_words(r_d, r_d, _nist_p_384[-carry - 1], 801 BN_NIST_384_TOP); 802 mask = 0 - (size_t)carry; 803 u.p = ((size_t)bn_sub_words & mask) | ((size_t)bn_add_words & ~mask); 804 } else 805 carry = 1; 806 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; 812 bn_correct_top(r); 813 814 return 1; 815} 816 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) 820 821int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 822 BN_CTX *ctx) 823{ 824 int top = a->top, i; 825 BN_ULONG *r_d, *a_d = a->d, t_d[BN_NIST_521_TOP], val, tmp, *res; 826 size_t mask; 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 832 }; 833 834 field = &_bignum_nist_p_521; /* just to make sure */ 835 836 if (BN_is_negative(a) || BN_ucmp(a, &_bignum_nist_p_521_sqr) >= 0) 837 return BN_nnmod(r, a, field, ctx); 838 839 i = BN_ucmp(field, a); 840 if (i == 0) { 841 BN_zero(r); 842 return 1; 843 } else if (i > 0) 844 return (r == a) ? 1 : (BN_copy(r, a) != NULL); 845 846 if (r != a) { 847 if (!bn_wexpand(r, BN_NIST_521_TOP)) 848 return 0; 849 r_d = r->d; 850 nist_cp_bn(r_d, a_d, BN_NIST_521_TOP); 851 } else 852 r_d = a_d; 853 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; 860 val = t_d[i + 1]; 861 t_d[i] = (tmp | val << BN_NIST_521_LSHIFT) & BN_MASK2; 862 } 863 t_d[i] = val >> BN_NIST_521_RSHIFT; 864 /* lower 521 bits */ 865 r_d[i] &= BN_NIST_521_TOP_MASK; 866 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; 872 bn_correct_top(r); 873 874 return 1; 875} 876