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 (at) 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 (at) cryptsoft.com). This product includes software written by Tim 55 * Hudson (tjh (at) cryptsoft.com). 56 * 57 */ 58 59 #include "bn_lcl.h" 60 #include "cryptlib.h" 61 62 63 #define BN_NIST_192_TOP (192+BN_BITS2-1)/BN_BITS2 64 #define BN_NIST_224_TOP (224+BN_BITS2-1)/BN_BITS2 65 #define BN_NIST_256_TOP (256+BN_BITS2-1)/BN_BITS2 66 #define BN_NIST_384_TOP (384+BN_BITS2-1)/BN_BITS2 67 #define BN_NIST_521_TOP (521+BN_BITS2-1)/BN_BITS2 68 69 /* pre-computed tables are "carry-less" values of modulus*(i+1) */ 70 #if BN_BITS2 == 64 71 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 72 {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFFULL}, 73 {0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFDULL,0xFFFFFFFFFFFFFFFFULL}, 74 {0xFFFFFFFFFFFFFFFDULL,0xFFFFFFFFFFFFFFFCULL,0xFFFFFFFFFFFFFFFFULL} 75 }; 76 static const BN_ULONG _nist_p_192_sqr[] = { 77 0x0000000000000001ULL,0x0000000000000002ULL,0x0000000000000001ULL, 78 0xFFFFFFFFFFFFFFFEULL,0xFFFFFFFFFFFFFFFDULL,0xFFFFFFFFFFFFFFFFULL 79 }; 80 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 81 {0x0000000000000001ULL,0xFFFFFFFF00000000ULL, 82 0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL}, 83 {0x0000000000000002ULL,0xFFFFFFFE00000000ULL, 84 0xFFFFFFFFFFFFFFFFULL,0x00000001FFFFFFFFULL} /* this one is "carry-full" */ 85 }; 86 static const BN_ULONG _nist_p_224_sqr[] = { 87 0x0000000000000001ULL,0xFFFFFFFE00000000ULL, 88 0xFFFFFFFFFFFFFFFFULL,0x0000000200000000ULL, 89 0x0000000000000000ULL,0xFFFFFFFFFFFFFFFEULL, 90 0xFFFFFFFFFFFFFFFFULL 91 }; 92 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 93 {0xFFFFFFFFFFFFFFFFULL,0x00000000FFFFFFFFULL, 94 0x0000000000000000ULL,0xFFFFFFFF00000001ULL}, 95 {0xFFFFFFFFFFFFFFFEULL,0x00000001FFFFFFFFULL, 96 0x0000000000000000ULL,0xFFFFFFFE00000002ULL}, 97 {0xFFFFFFFFFFFFFFFDULL,0x00000002FFFFFFFFULL, 98 0x0000000000000000ULL,0xFFFFFFFD00000003ULL}, 99 {0xFFFFFFFFFFFFFFFCULL,0x00000003FFFFFFFFULL, 100 0x0000000000000000ULL,0xFFFFFFFC00000004ULL}, 101 {0xFFFFFFFFFFFFFFFBULL,0x00000004FFFFFFFFULL, 102 0x0000000000000000ULL,0xFFFFFFFB00000005ULL}, 103 }; 104 static const BN_ULONG _nist_p_256_sqr[] = { 105 0x0000000000000001ULL,0xFFFFFFFE00000000ULL, 106 0xFFFFFFFFFFFFFFFFULL,0x00000001FFFFFFFEULL, 107 0x00000001FFFFFFFEULL,0x00000001FFFFFFFEULL, 108 0xFFFFFFFE00000001ULL,0xFFFFFFFE00000002ULL 109 }; 110 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 111 {0x00000000FFFFFFFFULL,0xFFFFFFFF00000000ULL,0xFFFFFFFFFFFFFFFEULL, 112 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, 113 {0x00000001FFFFFFFEULL,0xFFFFFFFE00000000ULL,0xFFFFFFFFFFFFFFFDULL, 114 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, 115 {0x00000002FFFFFFFDULL,0xFFFFFFFD00000000ULL,0xFFFFFFFFFFFFFFFCULL, 116 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, 117 {0x00000003FFFFFFFCULL,0xFFFFFFFC00000000ULL,0xFFFFFFFFFFFFFFFBULL, 118 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, 119 {0x00000004FFFFFFFBULL,0xFFFFFFFB00000000ULL,0xFFFFFFFFFFFFFFFAULL, 120 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL}, 121 }; 122 static const BN_ULONG _nist_p_384_sqr[] = { 123 0xFFFFFFFE00000001ULL,0x0000000200000000ULL,0xFFFFFFFE00000000ULL, 124 0x0000000200000000ULL,0x0000000000000001ULL,0x0000000000000000ULL, 125 0x00000001FFFFFFFEULL,0xFFFFFFFE00000000ULL,0xFFFFFFFFFFFFFFFDULL, 126 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL 127 }; 128 static const BN_ULONG _nist_p_521[] = 129 {0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 130 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 131 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 132 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 133 0x00000000000001FFULL}; 134 static const BN_ULONG _nist_p_521_sqr[] = { 135 0x0000000000000001ULL,0x0000000000000000ULL,0x0000000000000000ULL, 136 0x0000000000000000ULL,0x0000000000000000ULL,0x0000000000000000ULL, 137 0x0000000000000000ULL,0x0000000000000000ULL,0xFFFFFFFFFFFFFC00ULL, 138 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 139 0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL,0xFFFFFFFFFFFFFFFFULL, 140 0xFFFFFFFFFFFFFFFFULL,0x000000000003FFFFULL 141 }; 142 #elif BN_BITS2 == 32 143 static const BN_ULONG _nist_p_192[][BN_NIST_192_TOP] = { 144 {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 145 {0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 146 {0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFC,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF} 147 }; 148 static const BN_ULONG _nist_p_192_sqr[] = { 149 0x00000001,0x00000000,0x00000002,0x00000000,0x00000001,0x00000000, 150 0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF 151 }; 152 static const BN_ULONG _nist_p_224[][BN_NIST_224_TOP] = { 153 {0x00000001,0x00000000,0x00000000,0xFFFFFFFF, 154 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 155 {0x00000002,0x00000000,0x00000000,0xFFFFFFFE, 156 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF} 157 }; 158 static const BN_ULONG _nist_p_224_sqr[] = { 159 0x00000001,0x00000000,0x00000000,0xFFFFFFFE, 160 0xFFFFFFFF,0xFFFFFFFF,0x00000000,0x00000002, 161 0x00000000,0x00000000,0xFFFFFFFE,0xFFFFFFFF, 162 0xFFFFFFFF,0xFFFFFFFF 163 }; 164 static const BN_ULONG _nist_p_256[][BN_NIST_256_TOP] = { 165 {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0x00000000, 166 0x00000000,0x00000000,0x00000001,0xFFFFFFFF}, 167 {0xFFFFFFFE,0xFFFFFFFF,0xFFFFFFFF,0x00000001, 168 0x00000000,0x00000000,0x00000002,0xFFFFFFFE}, 169 {0xFFFFFFFD,0xFFFFFFFF,0xFFFFFFFF,0x00000002, 170 0x00000000,0x00000000,0x00000003,0xFFFFFFFD}, 171 {0xFFFFFFFC,0xFFFFFFFF,0xFFFFFFFF,0x00000003, 172 0x00000000,0x00000000,0x00000004,0xFFFFFFFC}, 173 {0xFFFFFFFB,0xFFFFFFFF,0xFFFFFFFF,0x00000004, 174 0x00000000,0x00000000,0x00000005,0xFFFFFFFB}, 175 }; 176 static const BN_ULONG _nist_p_256_sqr[] = { 177 0x00000001,0x00000000,0x00000000,0xFFFFFFFE, 178 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFE,0x00000001, 179 0xFFFFFFFE,0x00000001,0xFFFFFFFE,0x00000001, 180 0x00000001,0xFFFFFFFE,0x00000002,0xFFFFFFFE 181 }; 182 static const BN_ULONG _nist_p_384[][BN_NIST_384_TOP] = { 183 {0xFFFFFFFF,0x00000000,0x00000000,0xFFFFFFFF,0xFFFFFFFE,0xFFFFFFFF, 184 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 185 {0xFFFFFFFE,0x00000001,0x00000000,0xFFFFFFFE,0xFFFFFFFD,0xFFFFFFFF, 186 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 187 {0xFFFFFFFD,0x00000002,0x00000000,0xFFFFFFFD,0xFFFFFFFC,0xFFFFFFFF, 188 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 189 {0xFFFFFFFC,0x00000003,0x00000000,0xFFFFFFFC,0xFFFFFFFB,0xFFFFFFFF, 190 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 191 {0xFFFFFFFB,0x00000004,0x00000000,0xFFFFFFFB,0xFFFFFFFA,0xFFFFFFFF, 192 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF}, 193 }; 194 static const BN_ULONG _nist_p_384_sqr[] = { 195 0x00000001,0xFFFFFFFE,0x00000000,0x00000002,0x00000000,0xFFFFFFFE, 196 0x00000000,0x00000002,0x00000001,0x00000000,0x00000000,0x00000000, 197 0xFFFFFFFE,0x00000001,0x00000000,0xFFFFFFFE,0xFFFFFFFD,0xFFFFFFFF, 198 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF 199 }; 200 static const BN_ULONG _nist_p_521[] = {0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 201 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 202 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 203 0xFFFFFFFF,0x000001FF}; 204 static const BN_ULONG _nist_p_521_sqr[] = { 205 0x00000001,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000, 206 0x00000000,0x00000000,0x00000000,0x00000000,0x00000000,0x00000000, 207 0x00000000,0x00000000,0x00000000,0x00000000,0xFFFFFC00,0xFFFFFFFF, 208 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 209 0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF,0xFFFFFFFF, 210 0xFFFFFFFF,0xFFFFFFFF,0x0003FFFF 211 }; 212 #else 213 #error "unsupported BN_BITS2" 214 #endif 215 216 217 static const BIGNUM _bignum_nist_p_192 = 218 { 219 (BN_ULONG *)_nist_p_192[0], 220 BN_NIST_192_TOP, 221 BN_NIST_192_TOP, 222 0, 223 BN_FLG_STATIC_DATA 224 }; 225 226 static const BIGNUM _bignum_nist_p_224 = 227 { 228 (BN_ULONG *)_nist_p_224[0], 229 BN_NIST_224_TOP, 230 BN_NIST_224_TOP, 231 0, 232 BN_FLG_STATIC_DATA 233 }; 234 235 static const BIGNUM _bignum_nist_p_256 = 236 { 237 (BN_ULONG *)_nist_p_256[0], 238 BN_NIST_256_TOP, 239 BN_NIST_256_TOP, 240 0, 241 BN_FLG_STATIC_DATA 242 }; 243 244 static const BIGNUM _bignum_nist_p_384 = 245 { 246 (BN_ULONG *)_nist_p_384[0], 247 BN_NIST_384_TOP, 248 BN_NIST_384_TOP, 249 0, 250 BN_FLG_STATIC_DATA 251 }; 252 253 static const BIGNUM _bignum_nist_p_521 = 254 { 255 (BN_ULONG *)_nist_p_521, 256 BN_NIST_521_TOP, 257 BN_NIST_521_TOP, 258 0, 259 BN_FLG_STATIC_DATA 260 }; 261 262 263 const BIGNUM *BN_get0_nist_prime_192(void) 264 { 265 return &_bignum_nist_p_192; 266 } 267 268 const BIGNUM *BN_get0_nist_prime_224(void) 269 { 270 return &_bignum_nist_p_224; 271 } 272 273 const BIGNUM *BN_get0_nist_prime_256(void) 274 { 275 return &_bignum_nist_p_256; 276 } 277 278 const BIGNUM *BN_get0_nist_prime_384(void) 279 { 280 return &_bignum_nist_p_384; 281 } 282 283 const BIGNUM *BN_get0_nist_prime_521(void) 284 { 285 return &_bignum_nist_p_521; 286 } 287 288 289 static void nist_cp_bn_0(BN_ULONG *buf, BN_ULONG *a, int top, int max) 290 { 291 int i; 292 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 293 294 #ifdef BN_DEBUG 295 OPENSSL_assert(top <= max); 296 #endif 297 for (i = (top); i != 0; i--) 298 *_tmp1++ = *_tmp2++; 299 for (i = (max) - (top); i != 0; i--) 300 *_tmp1++ = (BN_ULONG) 0; 301 } 302 303 static void nist_cp_bn(BN_ULONG *buf, BN_ULONG *a, int top) 304 { 305 int i; 306 BN_ULONG *_tmp1 = (buf), *_tmp2 = (a); 307 for (i = (top); i != 0; i--) 308 *_tmp1++ = *_tmp2++; 309 } 310 311 #if BN_BITS2 == 64 312 #define bn_cp_64(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 313 #define bn_64_set_0(to, n) (to)[n] = (BN_ULONG)0; 314 /* 315 * two following macros are implemented under assumption that they 316 * are called in a sequence with *ascending* n, i.e. as they are... 317 */ 318 #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))\ 319 :(to[(n)/2] =((m)&1)?(from[(m)/2]>>32):(from[(m)/2]&BN_MASK2l))) 320 #define bn_32_set_0(to, n) (((n)&1)?(to[(n)/2]&=BN_MASK2l):(to[(n)/2]=0)); 321 #define bn_cp_32(to,n,from,m) ((m)>=0)?bn_cp_32_naked(to,n,from,m):bn_32_set_0(to,n) 322 #else 323 #define bn_cp_64(to, n, from, m) \ 324 { \ 325 bn_cp_32(to, (n)*2, from, (m)*2); \ 326 bn_cp_32(to, (n)*2+1, from, (m)*2+1); \ 327 } 328 #define bn_64_set_0(to, n) \ 329 { \ 330 bn_32_set_0(to, (n)*2); \ 331 bn_32_set_0(to, (n)*2+1); \ 332 } 333 #if BN_BITS2 == 32 334 #define bn_cp_32(to, n, from, m) (to)[n] = (m>=0)?((from)[m]):0; 335 #define bn_32_set_0(to, n) (to)[n] = (BN_ULONG)0; 336 #endif 337 #endif /* BN_BITS2 != 64 */ 338 339 340 #define nist_set_192(to, from, a1, a2, a3) \ 341 { \ 342 bn_cp_64(to, 0, from, (a3) - 3) \ 343 bn_cp_64(to, 1, from, (a2) - 3) \ 344 bn_cp_64(to, 2, from, (a1) - 3) \ 345 } 346 347 int BN_nist_mod_192(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 348 BN_CTX *ctx) 349 { 350 int top = a->top, i; 351 int carry; 352 register BN_ULONG *r_d, *a_d = a->d; 353 BN_ULONG t_d[BN_NIST_192_TOP], 354 buf[BN_NIST_192_TOP], 355 c_d[BN_NIST_192_TOP], 356 *res; 357 size_t mask; 358 static const BIGNUM _bignum_nist_p_192_sqr = { 359 (BN_ULONG *)_nist_p_192_sqr, 360 sizeof(_nist_p_192_sqr)/sizeof(_nist_p_192_sqr[0]), 361 sizeof(_nist_p_192_sqr)/sizeof(_nist_p_192_sqr[0]), 362 0,BN_FLG_STATIC_DATA }; 363 364 field = &_bignum_nist_p_192; /* just to make sure */ 365 366 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_192_sqr)>=0) 367 return BN_nnmod(r, a, field, ctx); 368 369 i = BN_ucmp(field, a); 370 if (i == 0) 371 { 372 BN_zero(r); 373 return 1; 374 } 375 else if (i > 0) 376 return (r == a) ? 1 : (BN_copy(r ,a) != NULL); 377 378 if (r != a) 379 { 380 if (!bn_wexpand(r, BN_NIST_192_TOP)) 381 return 0; 382 r_d = r->d; 383 nist_cp_bn(r_d, a_d, BN_NIST_192_TOP); 384 } 385 else 386 r_d = a_d; 387 388 nist_cp_bn_0(buf, a_d + BN_NIST_192_TOP, top - BN_NIST_192_TOP, BN_NIST_192_TOP); 389 390 nist_set_192(t_d, buf, 0, 3, 3); 391 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 392 nist_set_192(t_d, buf, 4, 4, 0); 393 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 394 nist_set_192(t_d, buf, 5, 5, 5) 395 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_192_TOP); 396 397 if (carry > 0) 398 carry = (int)bn_sub_words(r_d,r_d,_nist_p_192[carry-1],BN_NIST_192_TOP); 399 else 400 carry = 1; 401 402 /* 403 * we need 'if (carry==0 || result>=modulus) result-=modulus;' 404 * as comparison implies subtraction, we can write 405 * 'tmp=result-modulus; if (!carry || !borrow) result=tmp;' 406 * this is what happens below, but without explicit if:-) a. 407 */ 408 mask = 0-(size_t)bn_sub_words(c_d,r_d,_nist_p_192[0],BN_NIST_192_TOP); 409 mask &= 0-(size_t)carry; 410 res = (BN_ULONG *)(((size_t)c_d&~mask) | ((size_t)r_d&mask)); 411 nist_cp_bn(r_d, res, BN_NIST_192_TOP); 412 r->top = BN_NIST_192_TOP; 413 bn_correct_top(r); 414 415 return 1; 416 } 417 418 typedef BN_ULONG (*bn_addsub_f)(BN_ULONG *,const BN_ULONG *,const BN_ULONG *,int); 419 420 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ 421 { \ 422 bn_cp_32(to, 0, from, (a7) - 7) \ 423 bn_cp_32(to, 1, from, (a6) - 7) \ 424 bn_cp_32(to, 2, from, (a5) - 7) \ 425 bn_cp_32(to, 3, from, (a4) - 7) \ 426 bn_cp_32(to, 4, from, (a3) - 7) \ 427 bn_cp_32(to, 5, from, (a2) - 7) \ 428 bn_cp_32(to, 6, from, (a1) - 7) \ 429 } 430 431 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 432 BN_CTX *ctx) 433 { 434 int top = a->top, i; 435 int carry; 436 BN_ULONG *r_d, *a_d = a->d; 437 BN_ULONG t_d[BN_NIST_224_TOP], 438 buf[BN_NIST_224_TOP], 439 c_d[BN_NIST_224_TOP], 440 *res; 441 size_t mask; 442 union { bn_addsub_f f; size_t p; } u; 443 static const BIGNUM _bignum_nist_p_224_sqr = { 444 (BN_ULONG *)_nist_p_224_sqr, 445 sizeof(_nist_p_224_sqr)/sizeof(_nist_p_224_sqr[0]), 446 sizeof(_nist_p_224_sqr)/sizeof(_nist_p_224_sqr[0]), 447 0,BN_FLG_STATIC_DATA }; 448 449 450 field = &_bignum_nist_p_224; /* just to make sure */ 451 452 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_224_sqr)>=0) 453 return BN_nnmod(r, a, field, ctx); 454 455 i = BN_ucmp(field, a); 456 if (i == 0) 457 { 458 BN_zero(r); 459 return 1; 460 } 461 else if (i > 0) 462 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 463 464 if (r != a) 465 { 466 if (!bn_wexpand(r, BN_NIST_224_TOP)) 467 return 0; 468 r_d = r->d; 469 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); 470 } 471 else 472 r_d = a_d; 473 474 #if BN_BITS2==64 475 /* copy upper 256 bits of 448 bit number ... */ 476 nist_cp_bn_0(t_d, a_d + (BN_NIST_224_TOP-1), top - (BN_NIST_224_TOP-1), BN_NIST_224_TOP); 477 /* ... and right shift by 32 to obtain upper 224 bits */ 478 nist_set_224(buf, t_d, 14, 13, 12, 11, 10, 9, 8); 479 /* truncate lower part to 224 bits too */ 480 r_d[BN_NIST_224_TOP-1] &= BN_MASK2l; 481 #else 482 nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP); 483 #endif 484 nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0); 485 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 486 nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0); 487 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 488 nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7); 489 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 490 nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11); 491 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 492 493 #if BN_BITS2==64 494 carry = (int)(r_d[BN_NIST_224_TOP-1]>>32); 495 #endif 496 u.f = bn_sub_words; 497 if (carry > 0) 498 { 499 carry = (int)bn_sub_words(r_d,r_d,_nist_p_224[carry-1],BN_NIST_224_TOP); 500 #if BN_BITS2==64 501 carry=(int)(~(r_d[BN_NIST_224_TOP-1]>>32))&1; 502 #endif 503 } 504 else if (carry < 0) 505 { 506 /* it's a bit more comlicated logic in this case. 507 * if bn_add_words yields no carry, then result 508 * has to be adjusted by unconditionally *adding* 509 * the modulus. but if it does, then result has 510 * to be compared to the modulus and conditionally 511 * adjusted by *subtracting* the latter. */ 512 carry = (int)bn_add_words(r_d,r_d,_nist_p_224[-carry-1],BN_NIST_224_TOP); 513 mask = 0-(size_t)carry; 514 u.p = ((size_t)bn_sub_words&mask) | ((size_t)bn_add_words&~mask); 515 } 516 else 517 carry = 1; 518 519 /* otherwise it's effectively same as in BN_nist_mod_192... */ 520 mask = 0-(size_t)(*u.f)(c_d,r_d,_nist_p_224[0],BN_NIST_224_TOP); 521 mask &= 0-(size_t)carry; 522 res = (BN_ULONG *)(((size_t)c_d&~mask) | ((size_t)r_d&mask)); 523 nist_cp_bn(r_d, res, BN_NIST_224_TOP); 524 r->top = BN_NIST_224_TOP; 525 bn_correct_top(r); 526 527 return 1; 528 } 529 530 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ 531 { \ 532 bn_cp_32(to, 0, from, (a8) - 8) \ 533 bn_cp_32(to, 1, from, (a7) - 8) \ 534 bn_cp_32(to, 2, from, (a6) - 8) \ 535 bn_cp_32(to, 3, from, (a5) - 8) \ 536 bn_cp_32(to, 4, from, (a4) - 8) \ 537 bn_cp_32(to, 5, from, (a3) - 8) \ 538 bn_cp_32(to, 6, from, (a2) - 8) \ 539 bn_cp_32(to, 7, from, (a1) - 8) \ 540 } 541 542 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 543 BN_CTX *ctx) 544 { 545 int i, top = a->top; 546 int carry = 0; 547 register BN_ULONG *a_d = a->d, *r_d; 548 BN_ULONG t_d[BN_NIST_256_TOP], 549 buf[BN_NIST_256_TOP], 550 c_d[BN_NIST_256_TOP], 551 *res; 552 size_t mask; 553 union { bn_addsub_f f; size_t p; } u; 554 static const BIGNUM _bignum_nist_p_256_sqr = { 555 (BN_ULONG *)_nist_p_256_sqr, 556 sizeof(_nist_p_256_sqr)/sizeof(_nist_p_256_sqr[0]), 557 sizeof(_nist_p_256_sqr)/sizeof(_nist_p_256_sqr[0]), 558 0,BN_FLG_STATIC_DATA }; 559 560 field = &_bignum_nist_p_256; /* just to make sure */ 561 562 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_256_sqr)>=0) 563 return BN_nnmod(r, a, field, ctx); 564 565 i = BN_ucmp(field, a); 566 if (i == 0) 567 { 568 BN_zero(r); 569 return 1; 570 } 571 else if (i > 0) 572 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 573 574 if (r != a) 575 { 576 if (!bn_wexpand(r, BN_NIST_256_TOP)) 577 return 0; 578 r_d = r->d; 579 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); 580 } 581 else 582 r_d = a_d; 583 584 nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, BN_NIST_256_TOP); 585 586 /*S1*/ 587 nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0); 588 /*S2*/ 589 nist_set_256(c_d, buf, 0, 15, 14, 13, 12, 0, 0, 0); 590 carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP); 591 /* left shift */ 592 { 593 register BN_ULONG *ap,t,c; 594 ap = t_d; 595 c=0; 596 for (i = BN_NIST_256_TOP; i != 0; --i) 597 { 598 t= *ap; 599 *(ap++)=((t<<1)|c)&BN_MASK2; 600 c=(t & BN_TBIT)?1:0; 601 } 602 carry <<= 1; 603 carry |= c; 604 } 605 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 606 /*S3*/ 607 nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8); 608 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 609 /*S4*/ 610 nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9); 611 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 612 /*D1*/ 613 nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11); 614 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 615 /*D2*/ 616 nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12); 617 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 618 /*D3*/ 619 nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13); 620 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 621 /*D4*/ 622 nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14); 623 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 624 625 /* see BN_nist_mod_224 for explanation */ 626 u.f = bn_sub_words; 627 if (carry > 0) 628 carry = (int)bn_sub_words(r_d,r_d,_nist_p_256[carry-1],BN_NIST_256_TOP); 629 else if (carry < 0) 630 { 631 carry = (int)bn_add_words(r_d,r_d,_nist_p_256[-carry-1],BN_NIST_256_TOP); 632 mask = 0-(size_t)carry; 633 u.p = ((size_t)bn_sub_words&mask) | ((size_t)bn_add_words&~mask); 634 } 635 else 636 carry = 1; 637 638 mask = 0-(size_t)(*u.f)(c_d,r_d,_nist_p_256[0],BN_NIST_256_TOP); 639 mask &= 0-(size_t)carry; 640 res = (BN_ULONG *)(((size_t)c_d&~mask) | ((size_t)r_d&mask)); 641 nist_cp_bn(r_d, res, BN_NIST_256_TOP); 642 r->top = BN_NIST_256_TOP; 643 bn_correct_top(r); 644 645 return 1; 646 } 647 648 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ 649 { \ 650 bn_cp_32(to, 0, from, (a12) - 12) \ 651 bn_cp_32(to, 1, from, (a11) - 12) \ 652 bn_cp_32(to, 2, from, (a10) - 12) \ 653 bn_cp_32(to, 3, from, (a9) - 12) \ 654 bn_cp_32(to, 4, from, (a8) - 12) \ 655 bn_cp_32(to, 5, from, (a7) - 12) \ 656 bn_cp_32(to, 6, from, (a6) - 12) \ 657 bn_cp_32(to, 7, from, (a5) - 12) \ 658 bn_cp_32(to, 8, from, (a4) - 12) \ 659 bn_cp_32(to, 9, from, (a3) - 12) \ 660 bn_cp_32(to, 10, from, (a2) - 12) \ 661 bn_cp_32(to, 11, from, (a1) - 12) \ 662 } 663 664 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 665 BN_CTX *ctx) 666 { 667 int i, top = a->top; 668 int carry = 0; 669 register BN_ULONG *r_d, *a_d = a->d; 670 BN_ULONG t_d[BN_NIST_384_TOP], 671 buf[BN_NIST_384_TOP], 672 c_d[BN_NIST_384_TOP], 673 *res; 674 size_t mask; 675 union { bn_addsub_f f; size_t p; } u; 676 static const BIGNUM _bignum_nist_p_384_sqr = { 677 (BN_ULONG *)_nist_p_384_sqr, 678 sizeof(_nist_p_384_sqr)/sizeof(_nist_p_384_sqr[0]), 679 sizeof(_nist_p_384_sqr)/sizeof(_nist_p_384_sqr[0]), 680 0,BN_FLG_STATIC_DATA }; 681 682 683 field = &_bignum_nist_p_384; /* just to make sure */ 684 685 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_384_sqr)>=0) 686 return BN_nnmod(r, a, field, ctx); 687 688 i = BN_ucmp(field, a); 689 if (i == 0) 690 { 691 BN_zero(r); 692 return 1; 693 } 694 else if (i > 0) 695 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 696 697 if (r != a) 698 { 699 if (!bn_wexpand(r, BN_NIST_384_TOP)) 700 return 0; 701 r_d = r->d; 702 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); 703 } 704 else 705 r_d = a_d; 706 707 nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, BN_NIST_384_TOP); 708 709 /*S1*/ 710 nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23-4, 22-4, 21-4); 711 /* left shift */ 712 { 713 register BN_ULONG *ap,t,c; 714 ap = t_d; 715 c=0; 716 for (i = 3; i != 0; --i) 717 { 718 t= *ap; 719 *(ap++)=((t<<1)|c)&BN_MASK2; 720 c=(t & BN_TBIT)?1:0; 721 } 722 *ap=c; 723 } 724 carry = (int)bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), 725 t_d, BN_NIST_256_TOP); 726 /*S2 */ 727 carry += (int)bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP); 728 /*S3*/ 729 nist_set_384(t_d,buf,20,19,18,17,16,15,14,13,12,23,22,21); 730 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 731 /*S4*/ 732 nist_set_384(t_d,buf,19,18,17,16,15,14,13,12,20,0,23,0); 733 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 734 /*S5*/ 735 nist_set_384(t_d, buf,0,0,0,0,23,22,21,20,0,0,0,0); 736 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 737 /*S6*/ 738 nist_set_384(t_d,buf,0,0,0,0,0,0,23,22,21,0,0,20); 739 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 740 /*D1*/ 741 nist_set_384(t_d,buf,22,21,20,19,18,17,16,15,14,13,12,23); 742 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 743 /*D2*/ 744 nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,22,21,20,0); 745 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 746 /*D3*/ 747 nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,23,0,0,0); 748 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 749 750 /* see BN_nist_mod_224 for explanation */ 751 u.f = bn_sub_words; 752 if (carry > 0) 753 carry = (int)bn_sub_words(r_d,r_d,_nist_p_384[carry-1],BN_NIST_384_TOP); 754 else if (carry < 0) 755 { 756 carry = (int)bn_add_words(r_d,r_d,_nist_p_384[-carry-1],BN_NIST_384_TOP); 757 mask = 0-(size_t)carry; 758 u.p = ((size_t)bn_sub_words&mask) | ((size_t)bn_add_words&~mask); 759 } 760 else 761 carry = 1; 762 763 mask = 0-(size_t)(*u.f)(c_d,r_d,_nist_p_384[0],BN_NIST_384_TOP); 764 mask &= 0-(size_t)carry; 765 res = (BN_ULONG *)(((size_t)c_d&~mask) | ((size_t)r_d&mask)); 766 nist_cp_bn(r_d, res, BN_NIST_384_TOP); 767 r->top = BN_NIST_384_TOP; 768 bn_correct_top(r); 769 770 return 1; 771 } 772 773 #define BN_NIST_521_RSHIFT (521%BN_BITS2) 774 #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT) 775 #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT) 776 777 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 778 BN_CTX *ctx) 779 { 780 int top = a->top, i; 781 BN_ULONG *r_d, *a_d = a->d, 782 t_d[BN_NIST_521_TOP], 783 val,tmp,*res; 784 size_t mask; 785 static const BIGNUM _bignum_nist_p_521_sqr = { 786 (BN_ULONG *)_nist_p_521_sqr, 787 sizeof(_nist_p_521_sqr)/sizeof(_nist_p_521_sqr[0]), 788 sizeof(_nist_p_521_sqr)/sizeof(_nist_p_521_sqr[0]), 789 0,BN_FLG_STATIC_DATA }; 790 791 field = &_bignum_nist_p_521; /* just to make sure */ 792 793 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_521_sqr)>=0) 794 return BN_nnmod(r, a, field, ctx); 795 796 i = BN_ucmp(field, a); 797 if (i == 0) 798 { 799 BN_zero(r); 800 return 1; 801 } 802 else if (i > 0) 803 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 804 805 if (r != a) 806 { 807 if (!bn_wexpand(r,BN_NIST_521_TOP)) 808 return 0; 809 r_d = r->d; 810 nist_cp_bn(r_d,a_d, BN_NIST_521_TOP); 811 } 812 else 813 r_d = a_d; 814 815 /* upper 521 bits, copy ... */ 816 nist_cp_bn_0(t_d,a_d + (BN_NIST_521_TOP-1), top - (BN_NIST_521_TOP-1),BN_NIST_521_TOP); 817 /* ... and right shift */ 818 for (val=t_d[0],i=0; i<BN_NIST_521_TOP-1; i++) 819 { 820 tmp = val>>BN_NIST_521_RSHIFT; 821 val = t_d[i+1]; 822 t_d[i] = (tmp | val<<BN_NIST_521_LSHIFT) & BN_MASK2; 823 } 824 t_d[i] = val>>BN_NIST_521_RSHIFT; 825 /* lower 521 bits */ 826 r_d[i] &= BN_NIST_521_TOP_MASK; 827 828 bn_add_words(r_d,r_d,t_d,BN_NIST_521_TOP); 829 mask = 0-(size_t)bn_sub_words(t_d,r_d,_nist_p_521,BN_NIST_521_TOP); 830 res = (BN_ULONG *)(((size_t)t_d&~mask) | ((size_t)r_d&mask)); 831 nist_cp_bn(r_d,res,BN_NIST_521_TOP); 832 r->top = BN_NIST_521_TOP; 833 bn_correct_top(r); 834 835 return 1; 836 } 837
