1 /* $OpenBSD: bn_lcl.h,v 1.35 2022/07/15 06:10:00 tb Exp $ */ 2 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 3 * All rights reserved. 4 * 5 * This package is an SSL implementation written 6 * by Eric Young (eay@cryptsoft.com). 7 * The implementation was written so as to conform with Netscapes SSL. 8 * 9 * This library is free for commercial and non-commercial use as long as 10 * the following conditions are aheared to. The following conditions 11 * apply to all code found in this distribution, be it the RC4, RSA, 12 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 13 * included with this distribution is covered by the same copyright terms 14 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15 * 16 * Copyright remains Eric Young's, and as such any Copyright notices in 17 * the code are not to be removed. 18 * If this package is used in a product, Eric Young should be given attribution 19 * as the author of the parts of the library used. 20 * This can be in the form of a textual message at program startup or 21 * in documentation (online or textual) provided with the package. 22 * 23 * Redistribution and use in source and binary forms, with or without 24 * modification, are permitted provided that the following conditions 25 * are met: 26 * 1. Redistributions of source code must retain the copyright 27 * notice, this list of conditions and the following disclaimer. 28 * 2. Redistributions in binary form must reproduce the above copyright 29 * notice, this list of conditions and the following disclaimer in the 30 * documentation and/or other materials provided with the distribution. 31 * 3. All advertising materials mentioning features or use of this software 32 * must display the following acknowledgement: 33 * "This product includes cryptographic software written by 34 * Eric Young (eay@cryptsoft.com)" 35 * The word 'cryptographic' can be left out if the rouines from the library 36 * being used are not cryptographic related :-). 37 * 4. If you include any Windows specific code (or a derivative thereof) from 38 * the apps directory (application code) you must include an acknowledgement: 39 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40 * 41 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 42 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 43 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 44 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 45 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 46 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 47 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 48 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 49 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 50 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 51 * SUCH DAMAGE. 52 * 53 * The licence and distribution terms for any publically available version or 54 * derivative of this code cannot be changed. i.e. this code cannot simply be 55 * copied and put under another distribution licence 56 * [including the GNU Public Licence.] 57 */ 58 /* ==================================================================== 59 * Copyright (c) 1998-2000 The OpenSSL Project. All rights reserved. 60 * 61 * Redistribution and use in source and binary forms, with or without 62 * modification, are permitted provided that the following conditions 63 * are met: 64 * 65 * 1. Redistributions of source code must retain the above copyright 66 * notice, this list of conditions and the following disclaimer. 67 * 68 * 2. Redistributions in binary form must reproduce the above copyright 69 * notice, this list of conditions and the following disclaimer in 70 * the documentation and/or other materials provided with the 71 * distribution. 72 * 73 * 3. All advertising materials mentioning features or use of this 74 * software must display the following acknowledgment: 75 * "This product includes software developed by the OpenSSL Project 76 * for use in the OpenSSL Toolkit. (http://www.openssl.org/)" 77 * 78 * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to 79 * endorse or promote products derived from this software without 80 * prior written permission. For written permission, please contact 81 * openssl-core@openssl.org. 82 * 83 * 5. Products derived from this software may not be called "OpenSSL" 84 * nor may "OpenSSL" appear in their names without prior written 85 * permission of the OpenSSL Project. 86 * 87 * 6. Redistributions of any form whatsoever must retain the following 88 * acknowledgment: 89 * "This product includes software developed by the OpenSSL Project 90 * for use in the OpenSSL Toolkit (http://www.openssl.org/)" 91 * 92 * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY 93 * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 94 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 95 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE OpenSSL PROJECT OR 96 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 97 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 98 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 99 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 100 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 101 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 102 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED 103 * OF THE POSSIBILITY OF SUCH DAMAGE. 104 * ==================================================================== 105 * 106 * This product includes cryptographic software written by Eric Young 107 * (eay@cryptsoft.com). This product includes software written by Tim 108 * Hudson (tjh@cryptsoft.com). 109 * 110 */ 111 112 #ifndef HEADER_BN_LCL_H 113 #define HEADER_BN_LCL_H 114 115 #include <openssl/opensslconf.h> 116 117 #include <openssl/bn.h> 118 119 __BEGIN_HIDDEN_DECLS 120 121 struct bignum_st { 122 BN_ULONG *d; /* Pointer to an array of 'BN_BITS2' bit chunks. */ 123 int top; /* Index of last used d +1. */ 124 /* The next are internal book keeping for bn_expand. */ 125 int dmax; /* Size of the d array. */ 126 int neg; /* one if the number is negative */ 127 int flags; 128 }; 129 130 /* Used for montgomery multiplication */ 131 struct bn_mont_ctx_st { 132 int ri; /* number of bits in R */ 133 BIGNUM RR; /* used to convert to montgomery form */ 134 BIGNUM N; /* The modulus */ 135 BIGNUM Ni; /* R*(1/R mod N) - N*Ni = 1 136 * (Ni is only stored for bignum algorithm) */ 137 BN_ULONG n0[2];/* least significant word(s) of Ni; 138 (type changed with 0.9.9, was "BN_ULONG n0;" before) */ 139 int flags; 140 }; 141 142 /* Used for reciprocal division/mod functions 143 * It cannot be shared between threads 144 */ 145 struct bn_recp_ctx_st { 146 BIGNUM N; /* the divisor */ 147 BIGNUM Nr; /* the reciprocal */ 148 int num_bits; 149 int shift; 150 int flags; 151 }; 152 153 /* Used for slow "generation" functions. */ 154 struct bn_gencb_st { 155 unsigned int ver; /* To handle binary (in)compatibility */ 156 void *arg; /* callback-specific data */ 157 union { 158 /* if(ver==1) - handles old style callbacks */ 159 void (*cb_1)(int, int, void *); 160 /* if(ver==2) - new callback style */ 161 int (*cb_2)(int, int, BN_GENCB *); 162 } cb; 163 }; 164 165 /* 166 * BN_window_bits_for_exponent_size -- macro for sliding window mod_exp functions 167 * 168 * 169 * For window size 'w' (w >= 2) and a random 'b' bits exponent, 170 * the number of multiplications is a constant plus on average 171 * 172 * 2^(w-1) + (b-w)/(w+1); 173 * 174 * here 2^(w-1) is for precomputing the table (we actually need 175 * entries only for windows that have the lowest bit set), and 176 * (b-w)/(w+1) is an approximation for the expected number of 177 * w-bit windows, not counting the first one. 178 * 179 * Thus we should use 180 * 181 * w >= 6 if b > 671 182 * w = 5 if 671 > b > 239 183 * w = 4 if 239 > b > 79 184 * w = 3 if 79 > b > 23 185 * w <= 2 if 23 > b 186 * 187 * (with draws in between). Very small exponents are often selected 188 * with low Hamming weight, so we use w = 1 for b <= 23. 189 */ 190 #define BN_window_bits_for_exponent_size(b) \ 191 ((b) > 671 ? 6 : \ 192 (b) > 239 ? 5 : \ 193 (b) > 79 ? 4 : \ 194 (b) > 23 ? 3 : 1) 195 196 197 /* BN_mod_exp_mont_consttime is based on the assumption that the 198 * L1 data cache line width of the target processor is at least 199 * the following value. 200 */ 201 #define MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH ( 64 ) 202 #define MOD_EXP_CTIME_MIN_CACHE_LINE_MASK (MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH - 1) 203 204 /* Window sizes optimized for fixed window size modular exponentiation 205 * algorithm (BN_mod_exp_mont_consttime). 206 * 207 * To achieve the security goals of BN_mode_exp_mont_consttime, the 208 * maximum size of the window must not exceed 209 * log_2(MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH). 210 * 211 * Window size thresholds are defined for cache line sizes of 32 and 64, 212 * cache line sizes where log_2(32)=5 and log_2(64)=6 respectively. A 213 * window size of 7 should only be used on processors that have a 128 214 * byte or greater cache line size. 215 */ 216 #if MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 64 217 218 # define BN_window_bits_for_ctime_exponent_size(b) \ 219 ((b) > 937 ? 6 : \ 220 (b) > 306 ? 5 : \ 221 (b) > 89 ? 4 : \ 222 (b) > 22 ? 3 : 1) 223 # define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (6) 224 225 #elif MOD_EXP_CTIME_MIN_CACHE_LINE_WIDTH == 32 226 227 # define BN_window_bits_for_ctime_exponent_size(b) \ 228 ((b) > 306 ? 5 : \ 229 (b) > 89 ? 4 : \ 230 (b) > 22 ? 3 : 1) 231 # define BN_MAX_WINDOW_BITS_FOR_CTIME_EXPONENT_SIZE (5) 232 233 #endif 234 235 236 /* Pentium pro 16,16,16,32,64 */ 237 /* Alpha 16,16,16,16.64 */ 238 #define BN_MULL_SIZE_NORMAL (16) /* 32 */ 239 #define BN_MUL_RECURSIVE_SIZE_NORMAL (16) /* 32 less than */ 240 #define BN_SQR_RECURSIVE_SIZE_NORMAL (16) /* 32 */ 241 #define BN_MUL_LOW_RECURSIVE_SIZE_NORMAL (32) /* 32 */ 242 #define BN_MONT_CTX_SET_SIZE_WORD (64) /* 32 */ 243 244 #if !defined(OPENSSL_NO_ASM) && !defined(OPENSSL_NO_INLINE_ASM) 245 /* 246 * BN_UMULT_HIGH section. 247 * 248 * No, I'm not trying to overwhelm you when stating that the 249 * product of N-bit numbers is 2*N bits wide:-) No, I don't expect 250 * you to be impressed when I say that if the compiler doesn't 251 * support 2*N integer type, then you have to replace every N*N 252 * multiplication with 4 (N/2)*(N/2) accompanied by some shifts 253 * and additions which unavoidably results in severe performance 254 * penalties. Of course provided that the hardware is capable of 255 * producing 2*N result... That's when you normally start 256 * considering assembler implementation. However! It should be 257 * pointed out that some CPUs (most notably Alpha, PowerPC and 258 * upcoming IA-64 family:-) provide *separate* instruction 259 * calculating the upper half of the product placing the result 260 * into a general purpose register. Now *if* the compiler supports 261 * inline assembler, then it's not impossible to implement the 262 * "bignum" routines (and have the compiler optimize 'em) 263 * exhibiting "native" performance in C. That's what BN_UMULT_HIGH 264 * macro is about:-) 265 * 266 * <appro@fy.chalmers.se> 267 */ 268 # if defined(__alpha) 269 # if defined(__GNUC__) && __GNUC__>=2 270 # define BN_UMULT_HIGH(a,b) ({ \ 271 BN_ULONG ret; \ 272 asm ("umulh %1,%2,%0" \ 273 : "=r"(ret) \ 274 : "r"(a), "r"(b)); \ 275 ret; }) 276 # endif /* compiler */ 277 # elif defined(_ARCH_PPC) && defined(_LP64) 278 # if defined(__GNUC__) && __GNUC__>=2 279 # define BN_UMULT_HIGH(a,b) ({ \ 280 BN_ULONG ret; \ 281 asm ("mulhdu %0,%1,%2" \ 282 : "=r"(ret) \ 283 : "r"(a), "r"(b)); \ 284 ret; }) 285 # endif /* compiler */ 286 # elif (defined(__x86_64) || defined(__x86_64__)) && defined(_LP64) 287 # if defined(__GNUC__) && __GNUC__>=2 288 # define BN_UMULT_HIGH(a,b) ({ \ 289 BN_ULONG ret,discard; \ 290 asm ("mulq %3" \ 291 : "=a"(discard),"=d"(ret) \ 292 : "a"(a), "g"(b) \ 293 : "cc"); \ 294 ret; }) 295 # define BN_UMULT_LOHI(low,high,a,b) \ 296 asm ("mulq %3" \ 297 : "=a"(low),"=d"(high) \ 298 : "a"(a),"g"(b) \ 299 : "cc"); 300 # endif 301 # elif defined(__mips) && defined(_LP64) 302 # if defined(__GNUC__) && __GNUC__>=2 303 # if __GNUC__ > 4 || (__GNUC__ == 4 && __GNUC_MINOR__ >= 4) /* "h" constraint is no more since 4.4 */ 304 # define BN_UMULT_HIGH(a,b) (((__uint128_t)(a)*(b))>>64) 305 # define BN_UMULT_LOHI(low,high,a,b) ({ \ 306 __uint128_t ret=(__uint128_t)(a)*(b); \ 307 (high)=ret>>64; (low)=ret; }) 308 # else 309 # define BN_UMULT_HIGH(a,b) ({ \ 310 BN_ULONG ret; \ 311 asm ("dmultu %1,%2" \ 312 : "=h"(ret) \ 313 : "r"(a), "r"(b) : "l"); \ 314 ret; }) 315 # define BN_UMULT_LOHI(low,high,a,b)\ 316 asm ("dmultu %2,%3" \ 317 : "=l"(low),"=h"(high) \ 318 : "r"(a), "r"(b)); 319 # endif 320 # endif 321 # endif /* cpu */ 322 #endif /* OPENSSL_NO_ASM */ 323 324 /************************************************************* 325 * Using the long long type 326 */ 327 #define Lw(t) (((BN_ULONG)(t))&BN_MASK2) 328 #define Hw(t) (((BN_ULONG)((t)>>BN_BITS2))&BN_MASK2) 329 330 #ifdef BN_DEBUG_RAND 331 #define bn_clear_top2max(a) \ 332 { \ 333 int ind = (a)->dmax - (a)->top; \ 334 BN_ULONG *ftl = &(a)->d[(a)->top-1]; \ 335 for (; ind != 0; ind--) \ 336 *(++ftl) = 0x0; \ 337 } 338 #else 339 #define bn_clear_top2max(a) 340 #endif 341 342 #ifdef BN_LLONG 343 #define mul_add(r,a,w,c) { \ 344 BN_ULLONG t; \ 345 t=(BN_ULLONG)w * (a) + (r) + (c); \ 346 (r)= Lw(t); \ 347 (c)= Hw(t); \ 348 } 349 350 #define mul(r,a,w,c) { \ 351 BN_ULLONG t; \ 352 t=(BN_ULLONG)w * (a) + (c); \ 353 (r)= Lw(t); \ 354 (c)= Hw(t); \ 355 } 356 357 #define sqr(r0,r1,a) { \ 358 BN_ULLONG t; \ 359 t=(BN_ULLONG)(a)*(a); \ 360 (r0)=Lw(t); \ 361 (r1)=Hw(t); \ 362 } 363 364 #elif defined(BN_UMULT_LOHI) 365 #define mul_add(r,a,w,c) { \ 366 BN_ULONG high,low,ret,tmp=(a); \ 367 ret = (r); \ 368 BN_UMULT_LOHI(low,high,w,tmp); \ 369 ret += (c); \ 370 (c) = (ret<(c))?1:0; \ 371 (c) += high; \ 372 ret += low; \ 373 (c) += (ret<low)?1:0; \ 374 (r) = ret; \ 375 } 376 377 #define mul(r,a,w,c) { \ 378 BN_ULONG high,low,ret,ta=(a); \ 379 BN_UMULT_LOHI(low,high,w,ta); \ 380 ret = low + (c); \ 381 (c) = high; \ 382 (c) += (ret<low)?1:0; \ 383 (r) = ret; \ 384 } 385 386 #define sqr(r0,r1,a) { \ 387 BN_ULONG tmp=(a); \ 388 BN_UMULT_LOHI(r0,r1,tmp,tmp); \ 389 } 390 391 #elif defined(BN_UMULT_HIGH) 392 #define mul_add(r,a,w,c) { \ 393 BN_ULONG high,low,ret,tmp=(a); \ 394 ret = (r); \ 395 high= BN_UMULT_HIGH(w,tmp); \ 396 ret += (c); \ 397 low = (w) * tmp; \ 398 (c) = (ret<(c))?1:0; \ 399 (c) += high; \ 400 ret += low; \ 401 (c) += (ret<low)?1:0; \ 402 (r) = ret; \ 403 } 404 405 #define mul(r,a,w,c) { \ 406 BN_ULONG high,low,ret,ta=(a); \ 407 low = (w) * ta; \ 408 high= BN_UMULT_HIGH(w,ta); \ 409 ret = low + (c); \ 410 (c) = high; \ 411 (c) += (ret<low)?1:0; \ 412 (r) = ret; \ 413 } 414 415 #define sqr(r0,r1,a) { \ 416 BN_ULONG tmp=(a); \ 417 (r0) = tmp * tmp; \ 418 (r1) = BN_UMULT_HIGH(tmp,tmp); \ 419 } 420 421 #else 422 /************************************************************* 423 * No long long type 424 */ 425 426 #define LBITS(a) ((a)&BN_MASK2l) 427 #define HBITS(a) (((a)>>BN_BITS4)&BN_MASK2l) 428 #define L2HBITS(a) (((a)<<BN_BITS4)&BN_MASK2) 429 430 #define mul64(l,h,bl,bh) \ 431 { \ 432 BN_ULONG m,m1,lt,ht; \ 433 \ 434 lt=l; \ 435 ht=h; \ 436 m =(bh)*(lt); \ 437 lt=(bl)*(lt); \ 438 m1=(bl)*(ht); \ 439 ht =(bh)*(ht); \ 440 m=(m+m1)&BN_MASK2; if (m < m1) ht+=L2HBITS((BN_ULONG)1); \ 441 ht+=HBITS(m); \ 442 m1=L2HBITS(m); \ 443 lt=(lt+m1)&BN_MASK2; if (lt < m1) ht++; \ 444 (l)=lt; \ 445 (h)=ht; \ 446 } 447 448 #define sqr64(lo,ho,in) \ 449 { \ 450 BN_ULONG l,h,m; \ 451 \ 452 h=(in); \ 453 l=LBITS(h); \ 454 h=HBITS(h); \ 455 m =(l)*(h); \ 456 l*=l; \ 457 h*=h; \ 458 h+=(m&BN_MASK2h1)>>(BN_BITS4-1); \ 459 m =(m&BN_MASK2l)<<(BN_BITS4+1); \ 460 l=(l+m)&BN_MASK2; if (l < m) h++; \ 461 (lo)=l; \ 462 (ho)=h; \ 463 } 464 465 #define mul_add(r,a,bl,bh,c) { \ 466 BN_ULONG l,h; \ 467 \ 468 h= (a); \ 469 l=LBITS(h); \ 470 h=HBITS(h); \ 471 mul64(l,h,(bl),(bh)); \ 472 \ 473 /* non-multiply part */ \ 474 l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ 475 (c)=(r); \ 476 l=(l+(c))&BN_MASK2; if (l < (c)) h++; \ 477 (c)=h&BN_MASK2; \ 478 (r)=l; \ 479 } 480 481 #define mul(r,a,bl,bh,c) { \ 482 BN_ULONG l,h; \ 483 \ 484 h= (a); \ 485 l=LBITS(h); \ 486 h=HBITS(h); \ 487 mul64(l,h,(bl),(bh)); \ 488 \ 489 /* non-multiply part */ \ 490 l+=(c); if ((l&BN_MASK2) < (c)) h++; \ 491 (c)=h&BN_MASK2; \ 492 (r)=l&BN_MASK2; \ 493 } 494 #endif /* !BN_LLONG */ 495 496 /* The least significant word of a BIGNUM. */ 497 #define BN_lsw(n) (((n)->top == 0) ? (BN_ULONG) 0 : (n)->d[0]) 498 499 void bn_mul_normal(BN_ULONG *r, BN_ULONG *a, int na, BN_ULONG *b, int nb); 500 void bn_mul_comba8(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); 501 void bn_mul_comba4(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b); 502 void bn_sqr_normal(BN_ULONG *r, const BN_ULONG *a, int n, BN_ULONG *tmp); 503 void bn_sqr_comba8(BN_ULONG *r, const BN_ULONG *a); 504 void bn_sqr_comba4(BN_ULONG *r, const BN_ULONG *a); 505 int bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n); 506 int bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, 507 int cl, int dl); 508 void bn_mul_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 509 int dna, int dnb, BN_ULONG *t); 510 void bn_mul_part_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, 511 int n, int tna, int tnb, BN_ULONG *t); 512 void bn_sqr_recursive(BN_ULONG *r, const BN_ULONG *a, int n2, BN_ULONG *t); 513 void bn_mul_low_normal(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n); 514 void bn_mul_low_recursive(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, int n2, 515 BN_ULONG *t); 516 void bn_mul_high(BN_ULONG *r, BN_ULONG *a, BN_ULONG *b, BN_ULONG *l, int n2, 517 BN_ULONG *t); 518 BN_ULONG bn_add_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, 519 int cl, int dl); 520 BN_ULONG bn_sub_part_words(BN_ULONG *r, const BN_ULONG *a, const BN_ULONG *b, 521 int cl, int dl); 522 int bn_mul_mont(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, const BN_ULONG *np, const BN_ULONG *n0, int num); 523 524 #define bn_wexpand(a,words) (((words) <= (a)->dmax)?(a):bn_expand2((a),(words))) 525 BIGNUM *bn_expand2(BIGNUM *a, int words); 526 BIGNUM *bn_expand(BIGNUM *a, int bits); 527 528 BIGNUM *bn_dup_expand(const BIGNUM *a, int words); /* unused */ 529 530 /* Bignum consistency macros 531 * There is one "API" macro, bn_fix_top(), for stripping leading zeroes from 532 * bignum data after direct manipulations on the data. There is also an 533 * "internal" macro, bn_check_top(), for verifying that there are no leading 534 * zeroes. Unfortunately, some auditing is required due to the fact that 535 * bn_fix_top() has become an overabused duct-tape because bignum data is 536 * occasionally passed around in an inconsistent state. So the following 537 * changes have been made to sort this out; 538 * - bn_fix_top()s implementation has been moved to bn_correct_top() 539 * - if BN_DEBUG isn't defined, bn_fix_top() maps to bn_correct_top(), and 540 * bn_check_top() is as before. 541 * - if BN_DEBUG *is* defined; 542 * - bn_check_top() tries to pollute unused words even if the bignum 'top' is 543 * consistent. (ed: only if BN_DEBUG_RAND is defined) 544 * - bn_fix_top() maps to bn_check_top() rather than "fixing" anything. 545 * The idea is to have debug builds flag up inconsistent bignums when they 546 * occur. If that occurs in a bn_fix_top(), we examine the code in question; if 547 * the use of bn_fix_top() was appropriate (ie. it follows directly after code 548 * that manipulates the bignum) it is converted to bn_correct_top(), and if it 549 * was not appropriate, we convert it permanently to bn_check_top() and track 550 * down the cause of the bug. Eventually, no internal code should be using the 551 * bn_fix_top() macro. External applications and libraries should try this with 552 * their own code too, both in terms of building against the openssl headers 553 * with BN_DEBUG defined *and* linking with a version of OpenSSL built with it 554 * defined. This not only improves external code, it provides more test 555 * coverage for openssl's own code. 556 */ 557 558 #ifdef BN_DEBUG 559 560 /* We only need assert() when debugging */ 561 #include <assert.h> 562 563 #ifdef BN_DEBUG_RAND 564 #define bn_pollute(a) \ 565 do { \ 566 const BIGNUM *_bnum1 = (a); \ 567 if(_bnum1->top < _bnum1->dmax) { \ 568 unsigned char _tmp_char; \ 569 /* We cast away const without the compiler knowing, any \ 570 * *genuinely* constant variables that aren't mutable \ 571 * wouldn't be constructed with top!=dmax. */ \ 572 BN_ULONG *_not_const; \ 573 memcpy(&_not_const, &_bnum1->d, sizeof(BN_ULONG*)); \ 574 arc4random_buf(&_tmp_char, 1); \ 575 memset((unsigned char *)(_not_const + _bnum1->top), _tmp_char, \ 576 (_bnum1->dmax - _bnum1->top) * sizeof(BN_ULONG)); \ 577 } \ 578 } while(0) 579 #else 580 #define bn_pollute(a) 581 #endif 582 583 #define bn_check_top(a) \ 584 do { \ 585 const BIGNUM *_bnum2 = (a); \ 586 if (_bnum2 != NULL) { \ 587 assert((_bnum2->top == 0) || \ 588 (_bnum2->d[_bnum2->top - 1] != 0)); \ 589 bn_pollute(_bnum2); \ 590 } \ 591 } while(0) 592 593 #define bn_fix_top(a) bn_check_top(a) 594 595 #define bn_check_size(bn, bits) bn_wcheck_size(bn, ((bits+BN_BITS2-1))/BN_BITS2) 596 #define bn_wcheck_size(bn, words) \ 597 do { \ 598 const BIGNUM *_bnum2 = (bn); \ 599 assert(words <= (_bnum2)->dmax && words >= (_bnum2)->top); \ 600 } while(0) 601 602 #else /* !BN_DEBUG */ 603 604 #define bn_pollute(a) 605 #define bn_check_top(a) 606 #define bn_fix_top(a) bn_correct_top(a) 607 #define bn_check_size(bn, bits) 608 #define bn_wcheck_size(bn, words) 609 610 #endif 611 612 #define bn_correct_top(a) \ 613 { \ 614 BN_ULONG *ftl; \ 615 int tmp_top = (a)->top; \ 616 if (tmp_top > 0) \ 617 { \ 618 for (ftl= &((a)->d[tmp_top-1]); tmp_top > 0; tmp_top--) \ 619 if (*(ftl--)) break; \ 620 (a)->top = tmp_top; \ 621 } \ 622 bn_pollute(a); \ 623 } 624 625 BN_ULONG bn_mul_add_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w); 626 BN_ULONG bn_mul_words(BN_ULONG *rp, const BN_ULONG *ap, int num, BN_ULONG w); 627 void bn_sqr_words(BN_ULONG *rp, const BN_ULONG *ap, int num); 628 BN_ULONG bn_div_words(BN_ULONG h, BN_ULONG l, BN_ULONG d); 629 BN_ULONG bn_add_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, int num); 630 BN_ULONG bn_sub_words(BN_ULONG *rp, const BN_ULONG *ap, const BN_ULONG *bp, int num); 631 632 int BN_bntest_rand(BIGNUM *rnd, int bits, int top, int bottom); 633 int bn_rand_interval(BIGNUM *rnd, const BIGNUM *lower_inc, const BIGNUM *upper_exc); 634 635 /* Explicitly const time / non-const time versions for internal use */ 636 int BN_mod_exp_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 637 const BIGNUM *m, BN_CTX *ctx); 638 int BN_mod_exp_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 639 const BIGNUM *m, BN_CTX *ctx); 640 int BN_mod_exp_mont_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 641 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); 642 int BN_mod_exp_mont_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *p, 643 const BIGNUM *m, BN_CTX *ctx, BN_MONT_CTX *m_ctx); 644 int BN_div_nonct(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, 645 BN_CTX *ctx); 646 int BN_div_ct(BIGNUM *dv, BIGNUM *rem, const BIGNUM *m, const BIGNUM *d, 647 BN_CTX *ctx); 648 #define BN_mod_ct(rem,m,d,ctx) BN_div_ct(NULL,(rem),(m),(d),(ctx)) 649 #define BN_mod_nonct(rem,m,d,ctx) BN_div_nonct(NULL,(rem),(m),(d),(ctx)) 650 BIGNUM *BN_mod_inverse_ct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n, 651 BN_CTX *ctx); 652 BIGNUM *BN_mod_inverse_nonct(BIGNUM *ret, const BIGNUM *a, const BIGNUM *n, 653 BN_CTX *ctx); 654 int BN_gcd_ct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); 655 int BN_gcd_nonct(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, BN_CTX *ctx); 656 657 int BN_swap_ct(BN_ULONG swap, BIGNUM *a, BIGNUM *b, size_t nwords); 658 659 int bn_isqrt(BIGNUM *out_sqrt, int *out_perfect, const BIGNUM *n, BN_CTX *ctx); 660 int bn_is_perfect_square(int *out_perfect, const BIGNUM *n, BN_CTX *ctx); 661 662 int bn_is_prime_bpsw(int *is_prime, const BIGNUM *n, BN_CTX *in_ctx); 663 664 __END_HIDDEN_DECLS 665 #endif 666