bn_nist.c revision bdfb8ad83da0647e9b9a32792598e8ce7ba3ef4d
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#if BN_BITS2 == 64 69static const BN_ULONG _nist_p_192[] = 70 {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFEULL, 71 0xFFFFFFFFFFFFFFFFULL}; 72static const BN_ULONG _nist_p_224[] = 73 {0x0000000000000001ULL,0xFFFFFFFF00000000ULL, 74 0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL}; 75static const BN_ULONG _nist_p_256[] = 76 {0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL, 77 0x0000000000000000ULL,0xFFFFFFFF00000001ULL}; 78static const BN_ULONG _nist_p_384[] = 79 {0x00000000FFFFFFFFULL,0xFFFFFFFF00000000ULL, 80 0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL, 81 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}; 82static const BN_ULONG _nist_p_521[] = 83 {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 84 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 85 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 86 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 87 0x00000000000001FFULL}; 88#elif BN_BITS2 == 32 89static const BN_ULONG _nist_p_192[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE, 90 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}; 91static const BN_ULONG _nist_p_224[] = {0x00000001,0x00000000,0x00000000, 92 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}; 93static const BN_ULONG _nist_p_256[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 94 0x00000000,0x00000000,0x00000000,0x00000001,0xFFFFFFFF}; 95static const BN_ULONG _nist_p_384[] = {0xFFFFFFFF,0x00000000,0x00000000, 96 0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 97 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}; 98static const BN_ULONG _nist_p_521[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 99 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 100 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 101 0xFFFFFFFF,0x000001FF}; 102#endif 103 104const BIGNUM *BN_get0_nist_prime_192(void) 105 { 106 static BIGNUM const_nist_192 = { (BN_ULONG *)_nist_p_192, 107 BN_NIST_192_TOP, BN_NIST_192_TOP, 0, BN_FLG_STATIC_DATA }; 108 return &const_nist_192; 109 } 110 111const BIGNUM *BN_get0_nist_prime_224(void) 112 { 113 static BIGNUM const_nist_224 = { (BN_ULONG *)_nist_p_224, 114 BN_NIST_224_TOP, BN_NIST_224_TOP, 0, BN_FLG_STATIC_DATA }; 115 return &const_nist_224; 116 } 117 118const BIGNUM *BN_get0_nist_prime_256(void) 119 { 120 static BIGNUM const_nist_256 = { (BN_ULONG *)_nist_p_256, 121 BN_NIST_256_TOP, BN_NIST_256_TOP, 0, BN_FLG_STATIC_DATA }; 122 return &const_nist_256; 123 } 124 125const BIGNUM *BN_get0_nist_prime_384(void) 126 { 127 static BIGNUM const_nist_384 = { (BN_ULONG *)_nist_p_384, 128 BN_NIST_384_TOP, BN_NIST_384_TOP, 0, BN_FLG_STATIC_DATA }; 129 return &const_nist_384; 130 } 131 132const BIGNUM *BN_get0_nist_prime_521(void) 133 { 134 static BIGNUM const_nist_521 = { (BN_ULONG *)_nist_p_521, 135 BN_NIST_521_TOP, BN_NIST_521_TOP, 0, BN_FLG_STATIC_DATA }; 136 return &const_nist_521; 137 } 138 139#define BN_NIST_ADD_ONE(a) while (!(*(a)=(*(a)+1)&BN_MASK2)) ++(a); 140 141static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max) 142 { 143 int i; 144 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 145 for (i = (top); i != 0; i--) 146 *_tmp1++ = *_tmp2++; 147 for (i = (max) - (top); i != 0; i--) 148 *_tmp1++ = (BN_ULONG) 0; 149 } 150 151static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top) 152 { 153 int i; 154 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 155 for (i = (top); i != 0; i--) 156 *_tmp1++ = *_tmp2++; 157 } 158 159#if BN_BITS2 == 64 160#define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 161#define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0; 162/* TBD */ 163#define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 164#define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0; 165#else 166#define bn_cp_64(to, n, from, m) \ 167 { \ 168 bn_cp_32(to, (n)*2, from, (m)*2); \ 169 bn_cp_32(to, (n)*2+1, from, (m)*2+1); \ 170 } 171#define bn_64_set_0(to, n) \ 172 { \ 173 bn_32_set_0(to, (n)*2); \ 174 bn_32_set_0(to, (n)*2+1); \ 175 } 176#if BN_BITS2 == 32 177#define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 178#define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0; 179#endif 180#endif /* BN_BITS2 != 64 */ 181 182 183#define nist_set_192(to, from, a1, a2, a3) \ 184 { \ 185 if (a3 != 0) bn_cp_64(to, 0, from, (a3) - 3) else bn_64_set_0(to, 0)\ 186 bn_cp_64(to, 1, from, (a2) - 3) \ 187 if (a1 != 0) bn_cp_64(to, 2, from, (a1) - 3) else bn_64_set_0(to, 2)\ 188 } 189 190int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 191 BN_CTX *ctx) 192 { 193 int top = a->top, i; 194 int carry; 195 register BN_ULONG *r_d, *a_d = a->d; 196 BN_ULONG t_d[BN_NIST_192_TOP], 197 buf[BN_NIST_192_TOP], 198 c_d[BN_NIST_192_TOP], 199 *res; 200 size_t mask; 201 202 i = BN_ucmp(field, a); 203 if (i == 0) 204 { 205 BN_zero(r); 206 return 1; 207 } 208 else if (i > 0) 209 return (r == a) ? 1 : (BN_copy(r ,a) != NULL); 210 211 if (top == BN_NIST_192_TOP) 212 return BN_usub(r, a, field); 213 214 if (r != a) 215 { 216 if (!bn_wexpand(r, BN_NIST_192_TOP)) 217 return 0; 218 r_d = r->d; 219 nist_cp_bn(r_d, a_d, BN_NIST_192_TOP); 220 } 221 else 222 r_d = a_d; 223 224 nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, BN_NIST_192_TOP); 225 226 nist_set_192(t_d, buf, 0, 3, 3); 227 carry = bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 228 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_192,BN_NIST_192_TOP); 229 mask = ~mask | (0-(size_t)carry); 230 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 231 232 nist_set_192(t_d, buf, 4, 4, 0); 233 carry = bn_add_words(r_d, res, t_d, BN_NIST_192_TOP); 234 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_192,BN_NIST_192_TOP); 235 mask = ~mask | (0-(size_t)carry); 236 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 237 238 nist_set_192(t_d, buf, 5, 5, 5) 239 carry = bn_add_words(r_d, res, t_d, BN_NIST_192_TOP); 240 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_192,BN_NIST_192_TOP); 241 mask = ~mask | (0-(size_t)carry); 242 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 243 244 nist_cp_bn(r_d, res, BN_NIST_192_TOP); 245 r->top = BN_NIST_192_TOP; 246 bn_correct_top(r); 247 248 return 1; 249 } 250 251#define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ 252 { \ 253 if (a7 != 0) bn_cp_32(to, 0, from, (a7) - 7) else bn_32_set_0(to, 0)\ 254 if (a6 != 0) bn_cp_32(to, 1, from, (a6) - 7) else bn_32_set_0(to, 1)\ 255 if (a5 != 0) bn_cp_32(to, 2, from, (a5) - 7) else bn_32_set_0(to, 2)\ 256 if (a4 != 0) bn_cp_32(to, 3, from, (a4) - 7) else bn_32_set_0(to, 3)\ 257 if (a3 != 0) bn_cp_32(to, 4, from, (a3) - 7) else bn_32_set_0(to, 4)\ 258 if (a2 != 0) bn_cp_32(to, 5, from, (a2) - 7) else bn_32_set_0(to, 5)\ 259 if (a1 != 0) bn_cp_32(to, 6, from, (a1) - 7) else bn_32_set_0(to, 6)\ 260 } 261 262int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 263 BN_CTX *ctx) 264 { 265#if BN_BITS2 == 32 266 int top = a->top, i; 267 int carry; 268 BN_ULONG *r_d, *a_d = a->d; 269 BN_ULONG t_d[BN_NIST_224_TOP], 270 buf[BN_NIST_224_TOP], 271 c_d[BN_NIST_224_TOP], 272 *res; 273 size_t mask; 274 275 i = BN_ucmp(field, a); 276 if (i == 0) 277 { 278 BN_zero(r); 279 return 1; 280 } 281 else if (i > 0) 282 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 283 284 if (top == BN_NIST_224_TOP) 285 return BN_usub(r, a, field); 286 287 if (r != a) 288 { 289 if (!bn_wexpand(r, BN_NIST_224_TOP)) 290 return 0; 291 r_d = r->d; 292 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); 293 } 294 else 295 r_d = a_d; 296 297 nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP); 298 299 nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0); 300 carry = bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 301 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_224,BN_NIST_224_TOP); 302 mask = ~mask | (0-(size_t)carry); 303 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 304 305 nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0); 306 carry = bn_add_words(r_d, res, t_d, BN_NIST_224_TOP); 307 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_224,BN_NIST_224_TOP); 308 mask = ~mask | (0-(size_t)carry); 309 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 310 311 nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7); 312#if BRANCH_FREE 313 carry = bn_sub_words(r_d, res, t_d, BN_NIST_224_TOP); 314 bn_add_words(c_d,r_d,_nist_p_224,BN_NIST_224_TOP); 315 mask = 0-(size_t)carry; 316 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 317#else 318 if (bn_sub_words(r_d, res, t_d, BN_NIST_224_TOP)) 319 bn_add_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP); 320#endif 321 nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11); 322#if BRANCH_FREE 323 carry = bn_sub_words(r_d, res, t_d, BN_NIST_224_TOP); 324 bn_add_words(c_d,r_d,_nist_p_224,BN_NIST_224_TOP); 325 mask = 0-(size_t)carry; 326 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 327 328 nist_cp_bn(r_d, res, BN_NIST_224_TOP); 329#else 330 if (bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP)) 331 bn_add_words(r_d,r_d,_nist_p_224,BN_NIST_224_TOP); 332#endif 333 r->top = BN_NIST_224_TOP; 334 bn_correct_top(r); 335 336 return 1; 337#else /* BN_BITS!=32 */ 338 return 0; 339#endif 340 } 341 342#define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ 343 { \ 344 if (a8 != 0) bn_cp_32(to, 0, from, (a8) - 8) else bn_32_set_0(to, 0)\ 345 if (a7 != 0) bn_cp_32(to, 1, from, (a7) - 8) else bn_32_set_0(to, 1)\ 346 if (a6 != 0) bn_cp_32(to, 2, from, (a6) - 8) else bn_32_set_0(to, 2)\ 347 if (a5 != 0) bn_cp_32(to, 3, from, (a5) - 8) else bn_32_set_0(to, 3)\ 348 if (a4 != 0) bn_cp_32(to, 4, from, (a4) - 8) else bn_32_set_0(to, 4)\ 349 if (a3 != 0) bn_cp_32(to, 5, from, (a3) - 8) else bn_32_set_0(to, 5)\ 350 if (a2 != 0) bn_cp_32(to, 6, from, (a2) - 8) else bn_32_set_0(to, 6)\ 351 if (a1 != 0) bn_cp_32(to, 7, from, (a1) - 8) else bn_32_set_0(to, 7)\ 352 } 353 354int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 355 BN_CTX *ctx) 356 { 357#if BN_BITS2 == 32 358 int i, top = a->top; 359 int carry = 0; 360 register BN_ULONG *a_d = a->d, *r_d; 361 BN_ULONG t_d[BN_NIST_256_TOP], 362 buf[BN_NIST_256_TOP], 363 c_d[BN_NIST_256_TOP], 364 *res; 365 size_t mask; 366 367 i = BN_ucmp(field, a); 368 if (i == 0) 369 { 370 BN_zero(r); 371 return 1; 372 } 373 else if (i > 0) 374 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 375 376 if (top == BN_NIST_256_TOP) 377 return BN_usub(r, a, field); 378 379 if (r != a) 380 { 381 if (!bn_wexpand(r, BN_NIST_256_TOP)) 382 return 0; 383 r_d = r->d; 384 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); 385 } 386 else 387 r_d = a_d; 388 389 nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, BN_NIST_256_TOP); 390 391 /*S1*/ 392 nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0); 393 /*S2*/ 394 nist_set_256(c_d,buf, 0, 15, 14, 13, 12, 0, 0, 0); 395 carry = bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP); 396 mask = 0-(size_t)bn_sub_words(c_d,t_d,_nist_p_256,BN_NIST_256_TOP); 397 mask = ~mask | (0-(size_t)carry); 398 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)t_d&~mask)); 399 400 carry = bn_add_words(t_d, res, res, BN_NIST_256_TOP); 401 mask = 0-(size_t)bn_sub_words(c_d,t_d,_nist_p_256,BN_NIST_256_TOP); 402 mask = ~mask | (0-(size_t)carry); 403 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)t_d&~mask)); 404 405 carry = bn_add_words(r_d, r_d, res, BN_NIST_256_TOP); 406 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_256,BN_NIST_256_TOP); 407 mask = ~mask | (0-(size_t)carry); 408 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 409 410 /*S3*/ 411 nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8); 412 carry = bn_add_words(r_d, res, t_d, BN_NIST_256_TOP); 413 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_256,BN_NIST_256_TOP); 414 mask = ~mask | (0-(size_t)carry); 415 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 416 417 /*S4*/ 418 nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9); 419 carry = bn_add_words(r_d, res, t_d, BN_NIST_256_TOP); 420 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_256,BN_NIST_256_TOP); 421 mask = ~mask | (0-(size_t)carry); 422 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 423 424 /*D1*/ 425 nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11); 426#if BRANCH_FREE 427 carry = bn_sub_words(r_d, res, t_d, BN_NIST_256_TOP); 428 bn_add_words(c_d,r_d,_nist_p_256,BN_NIST_256_TOP); 429 mask = 0-(size_t)carry; 430 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 431#else 432 if (bn_sub_words(r_d, res, t_d, BN_NIST_256_TOP)) 433 bn_add_words(r_d,r_d,_nist_p_256,BN_NIST_256_TOP); 434#endif 435 /*D2*/ 436 nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12); 437#if BRANCH_FREE 438 carry = bn_sub_words(r_d, res, t_d, BN_NIST_256_TOP); 439 bn_add_words(c_d,r_d,_nist_p_256,BN_NIST_256_TOP); 440 mask = 0-(size_t)carry; 441 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 442#else 443 if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP)) 444 bn_add_words(r_d,r_d,_nist_p_256,BN_NIST_256_TOP); 445#endif 446 /*D3*/ 447 nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13); 448#if BRANCH_FREE 449 carry = bn_sub_words(r_d, res, t_d, BN_NIST_256_TOP); 450 bn_add_words(c_d,r_d,_nist_p_256,BN_NIST_256_TOP); 451 mask = 0-(size_t)carry; 452 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 453#else 454 if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP)) 455 bn_add_words(r_d,r_d,_nist_p_256,BN_NIST_256_TOP); 456#endif 457 /*D4*/ 458 nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14); 459#if BRANCH_FREE 460 carry = bn_sub_words(r_d, res, t_d, BN_NIST_256_TOP); 461 bn_add_words(c_d,r_d,_nist_p_256,BN_NIST_256_TOP); 462 mask = 0-(size_t)carry; 463 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 464 465 nist_cp_bn(r_d, res, BN_NIST_384_TOP); 466#else 467 if (bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP)) 468 bn_add_words(r_d,r_d,_nist_p_256,BN_NIST_256_TOP); 469#endif 470 r->top = BN_NIST_256_TOP; 471 bn_correct_top(r); 472 473 return 1; 474#else /* BN_BITS!=32 */ 475 return 0; 476#endif 477 } 478 479#define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ 480 { \ 481 if (a12 != 0) bn_cp_32(to, 0, from, (a12) - 12) else bn_32_set_0(to, 0)\ 482 if (a11 != 0) bn_cp_32(to, 1, from, (a11) - 12) else bn_32_set_0(to, 1)\ 483 if (a10 != 0) bn_cp_32(to, 2, from, (a10) - 12) else bn_32_set_0(to, 2)\ 484 if (a9 != 0) bn_cp_32(to, 3, from, (a9) - 12) else bn_32_set_0(to, 3)\ 485 if (a8 != 0) bn_cp_32(to, 4, from, (a8) - 12) else bn_32_set_0(to, 4)\ 486 if (a7 != 0) bn_cp_32(to, 5, from, (a7) - 12) else bn_32_set_0(to, 5)\ 487 if (a6 != 0) bn_cp_32(to, 6, from, (a6) - 12) else bn_32_set_0(to, 6)\ 488 if (a5 != 0) bn_cp_32(to, 7, from, (a5) - 12) else bn_32_set_0(to, 7)\ 489 if (a4 != 0) bn_cp_32(to, 8, from, (a4) - 12) else bn_32_set_0(to, 8)\ 490 if (a3 != 0) bn_cp_32(to, 9, from, (a3) - 12) else bn_32_set_0(to, 9)\ 491 if (a2 != 0) bn_cp_32(to, 10, from, (a2) - 12) else bn_32_set_0(to, 10)\ 492 if (a1 != 0) bn_cp_32(to, 11, from, (a1) - 12) else bn_32_set_0(to, 11)\ 493 } 494 495int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 496 BN_CTX *ctx) 497 { 498#if BN_BITS2 == 32 499 int i, top = a->top; 500 int carry = 0; 501 register BN_ULONG *r_d, *a_d = a->d; 502 BN_ULONG t_d[BN_NIST_384_TOP], 503 buf[BN_NIST_384_TOP], 504 c_d[BN_NIST_384_TOP], 505 *res; 506 size_t mask; 507 508 i = BN_ucmp(field, a); 509 if (i == 0) 510 { 511 BN_zero(r); 512 return 1; 513 } 514 else if (i > 0) 515 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 516 517 if (top == BN_NIST_384_TOP) 518 return BN_usub(r, a, field); 519 520 if (r != a) 521 { 522 if (!bn_wexpand(r, BN_NIST_384_TOP)) 523 return 0; 524 r_d = r->d; 525 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); 526 } 527 else 528 r_d = a_d; 529 530 nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, BN_NIST_384_TOP); 531 532 /*S1*/ 533 nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23-4, 22-4, 21-4); 534 /* left shift */ 535 { 536 register BN_ULONG *ap,t,c; 537 ap = t_d; 538 c=0; 539 for (i = 3; i != 0; --i) 540 { 541 t= *ap; 542 *(ap++)=((t<<1)|c)&BN_MASK2; 543 c=(t & BN_TBIT)?1:0; 544 } 545 *ap=c; 546 } 547 carry = bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), 548 t_d, BN_NIST_256_TOP); 549 /* 550 * we need if (result>=modulus) subtract(result,modulus); 551 * in n-bit space this can be expressed as 552 * if (carry || result>=modulus) subtract(result,modulus); 553 * the catch is that comparison implies subtraction and 554 * therefore one can write tmp=subtract(result,modulus); 555 * and then if(carry || !borrow) result=tmp; this's what 556 * happens below, but without explicit if:-) a. 557 */ 558 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 559 mask = ~mask | (0-(size_t)carry); 560 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 561 562 /*S2 */ 563 carry = bn_add_words(r_d, res, buf, BN_NIST_384_TOP); 564 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 565 mask = ~mask | (0-(size_t)carry); 566 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 567 568 /*S3*/ 569 nist_set_384(t_d,buf,20,19,18,17,16,15,14,13,12,23,22,21); 570 carry = bn_add_words(r_d, res, t_d, BN_NIST_384_TOP); 571 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 572 mask = ~mask | (0-(size_t)carry); 573 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 574 575 /*S4*/ 576 nist_set_384(t_d,buf,19,18,17,16,15,14,13,12,20,0,23,0); 577 carry = bn_add_words(r_d, res, t_d, BN_NIST_384_TOP); 578 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 579 mask = ~mask | (0-(size_t)carry); 580 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 581 582 /*S5*/ 583 nist_set_384(t_d, buf,0,0,0,0,23,22,21,20,0,0,0,0); 584 carry = bn_add_words(r_d, res, t_d, BN_NIST_384_TOP); 585 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 586 mask = ~mask | (0-(size_t)carry); 587 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 588 589 /*S6*/ 590 nist_set_384(t_d,buf,0,0,0,0,0,0,23,22,21,0,0,20); 591 carry = bn_add_words(r_d, res, t_d, BN_NIST_384_TOP); 592 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 593 mask = ~mask | (0-(size_t)carry); 594 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 595 596 /*D1*/ 597 nist_set_384(t_d,buf,22,21,20,19,18,17,16,15,14,13,12,23); 598#if BRANCH_FREE 599 carry = bn_sub_words(r_d, res, t_d, BN_NIST_384_TOP); 600 bn_add_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 601 mask = 0-(size_t)carry; 602 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 603#else 604 if (bn_sub_words(r_d, res, t_d, BN_NIST_384_TOP)) 605 bn_add_words(r_d,r_d,_nist_p_384,BN_NIST_384_TOP); 606#endif 607 /*D2*/ 608 nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,22,21,20,0); 609#if BRANCH_FREE 610 carry = bn_sub_words(r_d, res, t_d, BN_NIST_384_TOP); 611 bn_add_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 612 mask = 0-(size_t)carry; 613 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 614#else 615 if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP)) 616 bn_add_words(r_d,r_d,_nist_p_384,BN_NIST_384_TOP); 617#endif 618 /*D3*/ 619 nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,23,0,0,0); 620#if BRANCH_FREE 621 carry = bn_sub_words(r_d, res, t_d, BN_NIST_384_TOP); 622 bn_add_words(c_d,r_d,_nist_p_384,BN_NIST_384_TOP); 623 mask = 0-(size_t)carry; 624 res = (BN_ULONG *)(((size_t)c_d&mask) | ((size_t)r_d&~mask)); 625 626 nist_cp_bn(r_d, res, BN_NIST_384_TOP); 627#else 628 if (bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP)) 629 bn_add_words(r_d,r_d,_nist_p_384,BN_NIST_384_TOP); 630#endif 631 r->top = BN_NIST_384_TOP; 632 bn_correct_top(r); 633 634 return 1; 635#else /* BN_BITS!=32 */ 636 return 0; 637#endif 638 } 639 640int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 641 BN_CTX *ctx) 642 { 643#if BN_BITS2 == 64 644#define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF 645#elif BN_BITS2 == 32 646#define BN_NIST_521_TOP_MASK (BN_ULONG)0x1FF 647#endif 648 int top, ret = 0; 649 BN_ULONG *r_d; 650 BIGNUM *tmp; 651 652 /* check whether a reduction is necessary */ 653 top = a->top; 654 if (top < BN_NIST_521_TOP || ( top == BN_NIST_521_TOP && 655 (!(a->d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK))))) 656 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 657 658 BN_CTX_start(ctx); 659 tmp = BN_CTX_get(ctx); 660 if (!tmp) 661 goto err; 662 663 if (!bn_wexpand(tmp, BN_NIST_521_TOP)) 664 goto err; 665 nist_cp_bn(tmp->d, a->d, BN_NIST_521_TOP); 666 667 tmp->top = BN_NIST_521_TOP; 668 tmp->d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK; 669 bn_correct_top(tmp); 670 671 if (!BN_rshift(r, a, 521)) 672 goto err; 673 674 if (!BN_uadd(r, tmp, r)) 675 goto err; 676 top = r->top; 677 r_d = r->d; 678 if (top == BN_NIST_521_TOP && 679 (r_d[BN_NIST_521_TOP-1] & ~(BN_NIST_521_TOP_MASK))) 680 { 681 BN_NIST_ADD_ONE(r_d) 682 r->d[BN_NIST_521_TOP-1] &= BN_NIST_521_TOP_MASK; 683 } 684 bn_correct_top(r); 685 686 ret = 1; 687err: 688 BN_CTX_end(ctx); 689 690 bn_check_top(r); 691 return ret; 692 } 693