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 PTR_SIZE_INT 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-(PTR_SIZE_INT)bn_sub_words(c_d,r_d,_nist_p_192[0],BN_NIST_192_TOP); 409 mask &= 0-(PTR_SIZE_INT)carry; 410 res = (BN_ULONG *) 411 (((PTR_SIZE_INT)c_d&~mask) | ((PTR_SIZE_INT)r_d&mask)); 412 nist_cp_bn(r_d, res, BN_NIST_192_TOP); 413 r->top = BN_NIST_192_TOP; 414 bn_correct_top(r); 415 416 return 1; 417 } 418 419 typedef BN_ULONG (*bn_addsub_f)(BN_ULONG *,const BN_ULONG *,const BN_ULONG *,int); 420 421 #define nist_set_224(to, from, a1, a2, a3, a4, a5, a6, a7) \ 422 { \ 423 bn_cp_32(to, 0, from, (a7) - 7) \ 424 bn_cp_32(to, 1, from, (a6) - 7) \ 425 bn_cp_32(to, 2, from, (a5) - 7) \ 426 bn_cp_32(to, 3, from, (a4) - 7) \ 427 bn_cp_32(to, 4, from, (a3) - 7) \ 428 bn_cp_32(to, 5, from, (a2) - 7) \ 429 bn_cp_32(to, 6, from, (a1) - 7) \ 430 } 431 432 int BN_nist_mod_224(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 433 BN_CTX *ctx) 434 { 435 int top = a->top, i; 436 int carry; 437 BN_ULONG *r_d, *a_d = a->d; 438 BN_ULONG t_d[BN_NIST_224_TOP], 439 buf[BN_NIST_224_TOP], 440 c_d[BN_NIST_224_TOP], 441 *res; 442 PTR_SIZE_INT mask; 443 union { bn_addsub_f f; PTR_SIZE_INT p; } u; 444 static const BIGNUM _bignum_nist_p_224_sqr = { 445 (BN_ULONG *)_nist_p_224_sqr, 446 sizeof(_nist_p_224_sqr)/sizeof(_nist_p_224_sqr[0]), 447 sizeof(_nist_p_224_sqr)/sizeof(_nist_p_224_sqr[0]), 448 0,BN_FLG_STATIC_DATA }; 449 450 451 field = &_bignum_nist_p_224; /* just to make sure */ 452 453 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_224_sqr)>=0) 454 return BN_nnmod(r, a, field, ctx); 455 456 i = BN_ucmp(field, a); 457 if (i == 0) 458 { 459 BN_zero(r); 460 return 1; 461 } 462 else if (i > 0) 463 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 464 465 if (r != a) 466 { 467 if (!bn_wexpand(r, BN_NIST_224_TOP)) 468 return 0; 469 r_d = r->d; 470 nist_cp_bn(r_d, a_d, BN_NIST_224_TOP); 471 } 472 else 473 r_d = a_d; 474 475 #if BN_BITS2==64 476 /* copy upper 256 bits of 448 bit number ... */ 477 nist_cp_bn_0(t_d, a_d + (BN_NIST_224_TOP-1), top - (BN_NIST_224_TOP-1), BN_NIST_224_TOP); 478 /* ... and right shift by 32 to obtain upper 224 bits */ 479 nist_set_224(buf, t_d, 14, 13, 12, 11, 10, 9, 8); 480 /* truncate lower part to 224 bits too */ 481 r_d[BN_NIST_224_TOP-1] &= BN_MASK2l; 482 #else 483 nist_cp_bn_0(buf, a_d + BN_NIST_224_TOP, top - BN_NIST_224_TOP, BN_NIST_224_TOP); 484 #endif 485 nist_set_224(t_d, buf, 10, 9, 8, 7, 0, 0, 0); 486 carry = (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 487 nist_set_224(t_d, buf, 0, 13, 12, 11, 0, 0, 0); 488 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_224_TOP); 489 nist_set_224(t_d, buf, 13, 12, 11, 10, 9, 8, 7); 490 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 491 nist_set_224(t_d, buf, 0, 0, 0, 0, 13, 12, 11); 492 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_224_TOP); 493 494 #if BN_BITS2==64 495 carry = (int)(r_d[BN_NIST_224_TOP-1]>>32); 496 #endif 497 u.f = bn_sub_words; 498 if (carry > 0) 499 { 500 carry = (int)bn_sub_words(r_d,r_d,_nist_p_224[carry-1],BN_NIST_224_TOP); 501 #if BN_BITS2==64 502 carry=(int)(~(r_d[BN_NIST_224_TOP-1]>>32))&1; 503 #endif 504 } 505 else if (carry < 0) 506 { 507 /* it's a bit more comlicated logic in this case. 508 * if bn_add_words yields no carry, then result 509 * has to be adjusted by unconditionally *adding* 510 * the modulus. but if it does, then result has 511 * to be compared to the modulus and conditionally 512 * adjusted by *subtracting* the latter. */ 513 carry = (int)bn_add_words(r_d,r_d,_nist_p_224[-carry-1],BN_NIST_224_TOP); 514 mask = 0-(PTR_SIZE_INT)carry; 515 u.p = ((PTR_SIZE_INT)bn_sub_words&mask) | 516 ((PTR_SIZE_INT)bn_add_words&~mask); 517 } 518 else 519 carry = 1; 520 521 /* otherwise it's effectively same as in BN_nist_mod_192... */ 522 mask = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_224[0],BN_NIST_224_TOP); 523 mask &= 0-(PTR_SIZE_INT)carry; 524 res = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) | 525 ((PTR_SIZE_INT)r_d&mask)); 526 nist_cp_bn(r_d, res, BN_NIST_224_TOP); 527 r->top = BN_NIST_224_TOP; 528 bn_correct_top(r); 529 530 return 1; 531 } 532 533 #define nist_set_256(to, from, a1, a2, a3, a4, a5, a6, a7, a8) \ 534 { \ 535 bn_cp_32(to, 0, from, (a8) - 8) \ 536 bn_cp_32(to, 1, from, (a7) - 8) \ 537 bn_cp_32(to, 2, from, (a6) - 8) \ 538 bn_cp_32(to, 3, from, (a5) - 8) \ 539 bn_cp_32(to, 4, from, (a4) - 8) \ 540 bn_cp_32(to, 5, from, (a3) - 8) \ 541 bn_cp_32(to, 6, from, (a2) - 8) \ 542 bn_cp_32(to, 7, from, (a1) - 8) \ 543 } 544 545 int BN_nist_mod_256(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 546 BN_CTX *ctx) 547 { 548 int i, top = a->top; 549 int carry = 0; 550 register BN_ULONG *a_d = a->d, *r_d; 551 BN_ULONG t_d[BN_NIST_256_TOP], 552 buf[BN_NIST_256_TOP], 553 c_d[BN_NIST_256_TOP], 554 *res; 555 PTR_SIZE_INT mask; 556 union { bn_addsub_f f; PTR_SIZE_INT p; } u; 557 static const BIGNUM _bignum_nist_p_256_sqr = { 558 (BN_ULONG *)_nist_p_256_sqr, 559 sizeof(_nist_p_256_sqr)/sizeof(_nist_p_256_sqr[0]), 560 sizeof(_nist_p_256_sqr)/sizeof(_nist_p_256_sqr[0]), 561 0,BN_FLG_STATIC_DATA }; 562 563 field = &_bignum_nist_p_256; /* just to make sure */ 564 565 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_256_sqr)>=0) 566 return BN_nnmod(r, a, field, ctx); 567 568 i = BN_ucmp(field, a); 569 if (i == 0) 570 { 571 BN_zero(r); 572 return 1; 573 } 574 else if (i > 0) 575 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 576 577 if (r != a) 578 { 579 if (!bn_wexpand(r, BN_NIST_256_TOP)) 580 return 0; 581 r_d = r->d; 582 nist_cp_bn(r_d, a_d, BN_NIST_256_TOP); 583 } 584 else 585 r_d = a_d; 586 587 nist_cp_bn_0(buf, a_d + BN_NIST_256_TOP, top - BN_NIST_256_TOP, BN_NIST_256_TOP); 588 589 /*S1*/ 590 nist_set_256(t_d, buf, 15, 14, 13, 12, 11, 0, 0, 0); 591 /*S2*/ 592 nist_set_256(c_d, buf, 0, 15, 14, 13, 12, 0, 0, 0); 593 carry = (int)bn_add_words(t_d, t_d, c_d, BN_NIST_256_TOP); 594 /* left shift */ 595 { 596 register BN_ULONG *ap,t,c; 597 ap = t_d; 598 c=0; 599 for (i = BN_NIST_256_TOP; i != 0; --i) 600 { 601 t= *ap; 602 *(ap++)=((t<<1)|c)&BN_MASK2; 603 c=(t & BN_TBIT)?1:0; 604 } 605 carry <<= 1; 606 carry |= c; 607 } 608 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 609 /*S3*/ 610 nist_set_256(t_d, buf, 15, 14, 0, 0, 0, 10, 9, 8); 611 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 612 /*S4*/ 613 nist_set_256(t_d, buf, 8, 13, 15, 14, 13, 11, 10, 9); 614 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_256_TOP); 615 /*D1*/ 616 nist_set_256(t_d, buf, 10, 8, 0, 0, 0, 13, 12, 11); 617 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 618 /*D2*/ 619 nist_set_256(t_d, buf, 11, 9, 0, 0, 15, 14, 13, 12); 620 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 621 /*D3*/ 622 nist_set_256(t_d, buf, 12, 0, 10, 9, 8, 15, 14, 13); 623 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 624 /*D4*/ 625 nist_set_256(t_d, buf, 13, 0, 11, 10, 9, 0, 15, 14); 626 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_256_TOP); 627 628 /* see BN_nist_mod_224 for explanation */ 629 u.f = bn_sub_words; 630 if (carry > 0) 631 carry = (int)bn_sub_words(r_d,r_d,_nist_p_256[carry-1],BN_NIST_256_TOP); 632 else if (carry < 0) 633 { 634 carry = (int)bn_add_words(r_d,r_d,_nist_p_256[-carry-1],BN_NIST_256_TOP); 635 mask = 0-(PTR_SIZE_INT)carry; 636 u.p = ((PTR_SIZE_INT)bn_sub_words&mask) | 637 ((PTR_SIZE_INT)bn_add_words&~mask); 638 } 639 else 640 carry = 1; 641 642 mask = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_256[0],BN_NIST_256_TOP); 643 mask &= 0-(PTR_SIZE_INT)carry; 644 res = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) | 645 ((PTR_SIZE_INT)r_d&mask)); 646 nist_cp_bn(r_d, res, BN_NIST_256_TOP); 647 r->top = BN_NIST_256_TOP; 648 bn_correct_top(r); 649 650 return 1; 651 } 652 653 #define nist_set_384(to,from,a1,a2,a3,a4,a5,a6,a7,a8,a9,a10,a11,a12) \ 654 { \ 655 bn_cp_32(to, 0, from, (a12) - 12) \ 656 bn_cp_32(to, 1, from, (a11) - 12) \ 657 bn_cp_32(to, 2, from, (a10) - 12) \ 658 bn_cp_32(to, 3, from, (a9) - 12) \ 659 bn_cp_32(to, 4, from, (a8) - 12) \ 660 bn_cp_32(to, 5, from, (a7) - 12) \ 661 bn_cp_32(to, 6, from, (a6) - 12) \ 662 bn_cp_32(to, 7, from, (a5) - 12) \ 663 bn_cp_32(to, 8, from, (a4) - 12) \ 664 bn_cp_32(to, 9, from, (a3) - 12) \ 665 bn_cp_32(to, 10, from, (a2) - 12) \ 666 bn_cp_32(to, 11, from, (a1) - 12) \ 667 } 668 669 int BN_nist_mod_384(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 670 BN_CTX *ctx) 671 { 672 int i, top = a->top; 673 int carry = 0; 674 register BN_ULONG *r_d, *a_d = a->d; 675 BN_ULONG t_d[BN_NIST_384_TOP], 676 buf[BN_NIST_384_TOP], 677 c_d[BN_NIST_384_TOP], 678 *res; 679 PTR_SIZE_INT mask; 680 union { bn_addsub_f f; PTR_SIZE_INT p; } u; 681 static const BIGNUM _bignum_nist_p_384_sqr = { 682 (BN_ULONG *)_nist_p_384_sqr, 683 sizeof(_nist_p_384_sqr)/sizeof(_nist_p_384_sqr[0]), 684 sizeof(_nist_p_384_sqr)/sizeof(_nist_p_384_sqr[0]), 685 0,BN_FLG_STATIC_DATA }; 686 687 688 field = &_bignum_nist_p_384; /* just to make sure */ 689 690 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_384_sqr)>=0) 691 return BN_nnmod(r, a, field, ctx); 692 693 i = BN_ucmp(field, a); 694 if (i == 0) 695 { 696 BN_zero(r); 697 return 1; 698 } 699 else if (i > 0) 700 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 701 702 if (r != a) 703 { 704 if (!bn_wexpand(r, BN_NIST_384_TOP)) 705 return 0; 706 r_d = r->d; 707 nist_cp_bn(r_d, a_d, BN_NIST_384_TOP); 708 } 709 else 710 r_d = a_d; 711 712 nist_cp_bn_0(buf, a_d + BN_NIST_384_TOP, top - BN_NIST_384_TOP, BN_NIST_384_TOP); 713 714 /*S1*/ 715 nist_set_256(t_d, buf, 0, 0, 0, 0, 0, 23-4, 22-4, 21-4); 716 /* left shift */ 717 { 718 register BN_ULONG *ap,t,c; 719 ap = t_d; 720 c=0; 721 for (i = 3; i != 0; --i) 722 { 723 t= *ap; 724 *(ap++)=((t<<1)|c)&BN_MASK2; 725 c=(t & BN_TBIT)?1:0; 726 } 727 *ap=c; 728 } 729 carry = (int)bn_add_words(r_d+(128/BN_BITS2), r_d+(128/BN_BITS2), 730 t_d, BN_NIST_256_TOP); 731 /*S2 */ 732 carry += (int)bn_add_words(r_d, r_d, buf, BN_NIST_384_TOP); 733 /*S3*/ 734 nist_set_384(t_d,buf,20,19,18,17,16,15,14,13,12,23,22,21); 735 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 736 /*S4*/ 737 nist_set_384(t_d,buf,19,18,17,16,15,14,13,12,20,0,23,0); 738 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 739 /*S5*/ 740 nist_set_384(t_d, buf,0,0,0,0,23,22,21,20,0,0,0,0); 741 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 742 /*S6*/ 743 nist_set_384(t_d,buf,0,0,0,0,0,0,23,22,21,0,0,20); 744 carry += (int)bn_add_words(r_d, r_d, t_d, BN_NIST_384_TOP); 745 /*D1*/ 746 nist_set_384(t_d,buf,22,21,20,19,18,17,16,15,14,13,12,23); 747 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 748 /*D2*/ 749 nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,22,21,20,0); 750 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 751 /*D3*/ 752 nist_set_384(t_d,buf,0,0,0,0,0,0,0,23,23,0,0,0); 753 carry -= (int)bn_sub_words(r_d, r_d, t_d, BN_NIST_384_TOP); 754 755 /* see BN_nist_mod_224 for explanation */ 756 u.f = bn_sub_words; 757 if (carry > 0) 758 carry = (int)bn_sub_words(r_d,r_d,_nist_p_384[carry-1],BN_NIST_384_TOP); 759 else if (carry < 0) 760 { 761 carry = (int)bn_add_words(r_d,r_d,_nist_p_384[-carry-1],BN_NIST_384_TOP); 762 mask = 0-(PTR_SIZE_INT)carry; 763 u.p = ((PTR_SIZE_INT)bn_sub_words&mask) | 764 ((PTR_SIZE_INT)bn_add_words&~mask); 765 } 766 else 767 carry = 1; 768 769 mask = 0-(PTR_SIZE_INT)(*u.f)(c_d,r_d,_nist_p_384[0],BN_NIST_384_TOP); 770 mask &= 0-(PTR_SIZE_INT)carry; 771 res = (BN_ULONG *)(((PTR_SIZE_INT)c_d&~mask) | 772 ((PTR_SIZE_INT)r_d&mask)); 773 nist_cp_bn(r_d, res, BN_NIST_384_TOP); 774 r->top = BN_NIST_384_TOP; 775 bn_correct_top(r); 776 777 return 1; 778 } 779 780 #define BN_NIST_521_RSHIFT (521%BN_BITS2) 781 #define BN_NIST_521_LSHIFT (BN_BITS2-BN_NIST_521_RSHIFT) 782 #define BN_NIST_521_TOP_MASK ((BN_ULONG)BN_MASK2>>BN_NIST_521_LSHIFT) 783 784 int BN_nist_mod_521(BIGNUM *r, const BIGNUM *a, const BIGNUM *field, 785 BN_CTX *ctx) 786 { 787 int top = a->top, i; 788 BN_ULONG *r_d, *a_d = a->d, 789 t_d[BN_NIST_521_TOP], 790 val,tmp,*res; 791 PTR_SIZE_INT mask; 792 static const BIGNUM _bignum_nist_p_521_sqr = { 793 (BN_ULONG *)_nist_p_521_sqr, 794 sizeof(_nist_p_521_sqr)/sizeof(_nist_p_521_sqr[0]), 795 sizeof(_nist_p_521_sqr)/sizeof(_nist_p_521_sqr[0]), 796 0,BN_FLG_STATIC_DATA }; 797 798 field = &_bignum_nist_p_521; /* just to make sure */ 799 800 if (BN_is_negative(a) || BN_ucmp(a,&_bignum_nist_p_521_sqr)>=0) 801 return BN_nnmod(r, a, field, ctx); 802 803 i = BN_ucmp(field, a); 804 if (i == 0) 805 { 806 BN_zero(r); 807 return 1; 808 } 809 else if (i > 0) 810 return (r == a)? 1 : (BN_copy(r ,a) != NULL); 811 812 if (r != a) 813 { 814 if (!bn_wexpand(r,BN_NIST_521_TOP)) 815 return 0; 816 r_d = r->d; 817 nist_cp_bn(r_d,a_d, BN_NIST_521_TOP); 818 } 819 else 820 r_d = a_d; 821 822 /* upper 521 bits, copy ... */ 823 nist_cp_bn_0(t_d,a_d + (BN_NIST_521_TOP-1), top - (BN_NIST_521_TOP-1),BN_NIST_521_TOP); 824 /* ... and right shift */ 825 for (val=t_d[0],i=0; i<BN_NIST_521_TOP-1; i++) 826 { 827 tmp = val>>BN_NIST_521_RSHIFT; 828 val = t_d[i+1]; 829 t_d[i] = (tmp | val<<BN_NIST_521_LSHIFT) & BN_MASK2; 830 } 831 t_d[i] = val>>BN_NIST_521_RSHIFT; 832 /* lower 521 bits */ 833 r_d[i] &= BN_NIST_521_TOP_MASK; 834 835 bn_add_words(r_d,r_d,t_d,BN_NIST_521_TOP); 836 mask = 0-(PTR_SIZE_INT)bn_sub_words(t_d,r_d,_nist_p_521,BN_NIST_521_TOP); 837 res = (BN_ULONG *)(((PTR_SIZE_INT)t_d&~mask) | 838 ((PTR_SIZE_INT)r_d&mask)); 839 nist_cp_bn(r_d,res,BN_NIST_521_TOP); 840 r->top = BN_NIST_521_TOP; 841 bn_correct_top(r); 842 843 return 1; 844 } 845
