155714Skris/* crypto/bn/bn_lib.c */ 255714Skris/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 355714Skris * All rights reserved. 455714Skris * 555714Skris * This package is an SSL implementation written 655714Skris * by Eric Young (eay@cryptsoft.com). 755714Skris * The implementation was written so as to conform with Netscapes SSL. 8280297Sjkim * 955714Skris * This library is free for commercial and non-commercial use as long as 1055714Skris * the following conditions are aheared to. The following conditions 1155714Skris * apply to all code found in this distribution, be it the RC4, RSA, 1255714Skris * lhash, DES, etc., code; not just the SSL code. The SSL documentation 1355714Skris * included with this distribution is covered by the same copyright terms 1455714Skris * except that the holder is Tim Hudson (tjh@cryptsoft.com). 15280297Sjkim * 1655714Skris * Copyright remains Eric Young's, and as such any Copyright notices in 1755714Skris * the code are not to be removed. 1855714Skris * If this package is used in a product, Eric Young should be given attribution 1955714Skris * as the author of the parts of the library used. 2055714Skris * This can be in the form of a textual message at program startup or 2155714Skris * in documentation (online or textual) provided with the package. 22280297Sjkim * 2355714Skris * Redistribution and use in source and binary forms, with or without 2455714Skris * modification, are permitted provided that the following conditions 2555714Skris * are met: 2655714Skris * 1. Redistributions of source code must retain the copyright 2755714Skris * notice, this list of conditions and the following disclaimer. 2855714Skris * 2. Redistributions in binary form must reproduce the above copyright 2955714Skris * notice, this list of conditions and the following disclaimer in the 3055714Skris * documentation and/or other materials provided with the distribution. 3155714Skris * 3. All advertising materials mentioning features or use of this software 3255714Skris * must display the following acknowledgement: 3355714Skris * "This product includes cryptographic software written by 3455714Skris * Eric Young (eay@cryptsoft.com)" 3555714Skris * The word 'cryptographic' can be left out if the rouines from the library 3655714Skris * being used are not cryptographic related :-). 37280297Sjkim * 4. If you include any Windows specific code (or a derivative thereof) from 3855714Skris * the apps directory (application code) you must include an acknowledgement: 3955714Skris * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 40280297Sjkim * 4155714Skris * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 4255714Skris * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 4355714Skris * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 4455714Skris * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 4555714Skris * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 4655714Skris * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 4755714Skris * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 4855714Skris * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 4955714Skris * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 5055714Skris * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 5155714Skris * SUCH DAMAGE. 52280297Sjkim * 5355714Skris * The licence and distribution terms for any publically available version or 5455714Skris * derivative of this code cannot be changed. i.e. this code cannot simply be 5555714Skris * copied and put under another distribution licence 5655714Skris * [including the GNU Public Licence.] 5755714Skris */ 5855714Skris 5968651Skris#ifndef BN_DEBUG 60280297Sjkim# undef NDEBUG /* avoid conflicting definitions */ 6168651Skris# define NDEBUG 6268651Skris#endif 6368651Skris 6468651Skris#include <assert.h> 6572613Skris#include <limits.h> 6655714Skris#include <stdio.h> 6755714Skris#include "cryptlib.h" 6855714Skris#include "bn_lcl.h" 6955714Skris 70280297Sjkimconst char BN_version[] = "Big Number" OPENSSL_VERSION_PTEXT; 7155714Skris 72160814Ssimon/* This stuff appears to be completely unused, so is deprecated */ 73160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 74280297Sjkim/*- 75280297Sjkim * For a 32 bit machine 7655714Skris * 2 - 4 == 128 7755714Skris * 3 - 8 == 256 7855714Skris * 4 - 16 == 512 7955714Skris * 5 - 32 == 1024 8055714Skris * 6 - 64 == 2048 8155714Skris * 7 - 128 == 4096 8255714Skris * 8 - 256 == 8192 8355714Skris */ 84280297Sjkimstatic int bn_limit_bits = 0; 85280297Sjkimstatic int bn_limit_num = 8; /* (1<<bn_limit_bits) */ 86280297Sjkimstatic int bn_limit_bits_low = 0; 87280297Sjkimstatic int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ 88280297Sjkimstatic int bn_limit_bits_high = 0; 89280297Sjkimstatic int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ 90280297Sjkimstatic int bn_limit_bits_mont = 0; 91280297Sjkimstatic int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ 9255714Skris 9355714Skrisvoid BN_set_params(int mult, int high, int low, int mont) 94280297Sjkim{ 95280297Sjkim if (mult >= 0) { 96280297Sjkim if (mult > (int)(sizeof(int) * 8) - 1) 97280297Sjkim mult = sizeof(int) * 8 - 1; 98280297Sjkim bn_limit_bits = mult; 99280297Sjkim bn_limit_num = 1 << mult; 100280297Sjkim } 101280297Sjkim if (high >= 0) { 102280297Sjkim if (high > (int)(sizeof(int) * 8) - 1) 103280297Sjkim high = sizeof(int) * 8 - 1; 104280297Sjkim bn_limit_bits_high = high; 105280297Sjkim bn_limit_num_high = 1 << high; 106280297Sjkim } 107280297Sjkim if (low >= 0) { 108280297Sjkim if (low > (int)(sizeof(int) * 8) - 1) 109280297Sjkim low = sizeof(int) * 8 - 1; 110280297Sjkim bn_limit_bits_low = low; 111280297Sjkim bn_limit_num_low = 1 << low; 112280297Sjkim } 113280297Sjkim if (mont >= 0) { 114280297Sjkim if (mont > (int)(sizeof(int) * 8) - 1) 115280297Sjkim mont = sizeof(int) * 8 - 1; 116280297Sjkim bn_limit_bits_mont = mont; 117280297Sjkim bn_limit_num_mont = 1 << mont; 118280297Sjkim } 119280297Sjkim} 12055714Skris 12155714Skrisint BN_get_params(int which) 122280297Sjkim{ 123280297Sjkim if (which == 0) 124280297Sjkim return (bn_limit_bits); 125280297Sjkim else if (which == 1) 126280297Sjkim return (bn_limit_bits_high); 127280297Sjkim else if (which == 2) 128280297Sjkim return (bn_limit_bits_low); 129280297Sjkim else if (which == 3) 130280297Sjkim return (bn_limit_bits_mont); 131280297Sjkim else 132280297Sjkim return (0); 133280297Sjkim} 134160814Ssimon#endif 13555714Skris 136109998Smarkmconst BIGNUM *BN_value_one(void) 137280297Sjkim{ 138280297Sjkim static const BN_ULONG data_one = 1L; 139280297Sjkim static const BIGNUM const_one = 140280297Sjkim { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; 14155714Skris 142280297Sjkim return (&const_one); 143280297Sjkim} 14455714Skris 14555714Skrisint BN_num_bits_word(BN_ULONG l) 146280297Sjkim{ 147280297Sjkim static const unsigned char bits[256] = { 148280297Sjkim 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 149280297Sjkim 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 150280297Sjkim 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 151280297Sjkim 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 152280297Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 153280297Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 154280297Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 155280297Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 156280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 157280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 158280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 159280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 160280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 161280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 162280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 163280297Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 164280297Sjkim }; 16555714Skris 16655714Skris#if defined(SIXTY_FOUR_BIT_LONG) 167280297Sjkim if (l & 0xffffffff00000000L) { 168280297Sjkim if (l & 0xffff000000000000L) { 169280297Sjkim if (l & 0xff00000000000000L) { 170280297Sjkim return (bits[(int)(l >> 56)] + 56); 171280297Sjkim } else 172280297Sjkim return (bits[(int)(l >> 48)] + 48); 173280297Sjkim } else { 174280297Sjkim if (l & 0x0000ff0000000000L) { 175280297Sjkim return (bits[(int)(l >> 40)] + 40); 176280297Sjkim } else 177280297Sjkim return (bits[(int)(l >> 32)] + 32); 178280297Sjkim } 179280297Sjkim } else 18055714Skris#else 181280297Sjkim# ifdef SIXTY_FOUR_BIT 182280297Sjkim if (l & 0xffffffff00000000LL) { 183280297Sjkim if (l & 0xffff000000000000LL) { 184280297Sjkim if (l & 0xff00000000000000LL) { 185280297Sjkim return (bits[(int)(l >> 56)] + 56); 186280297Sjkim } else 187280297Sjkim return (bits[(int)(l >> 48)] + 48); 188280297Sjkim } else { 189280297Sjkim if (l & 0x0000ff0000000000LL) { 190280297Sjkim return (bits[(int)(l >> 40)] + 40); 191280297Sjkim } else 192280297Sjkim return (bits[(int)(l >> 32)] + 32); 193280297Sjkim } 194280297Sjkim } else 195280297Sjkim# endif 19655714Skris#endif 197280297Sjkim { 19855714Skris#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 199280297Sjkim if (l & 0xffff0000L) { 200280297Sjkim if (l & 0xff000000L) 201280297Sjkim return (bits[(int)(l >> 24L)] + 24); 202280297Sjkim else 203280297Sjkim return (bits[(int)(l >> 16L)] + 16); 204280297Sjkim } else 20555714Skris#endif 206280297Sjkim { 207238405Sjkim#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 208280297Sjkim if (l & 0xff00L) 209280297Sjkim return (bits[(int)(l >> 8)] + 8); 210280297Sjkim else 21155714Skris#endif 212280297Sjkim return (bits[(int)(l)]); 213280297Sjkim } 214280297Sjkim } 215280297Sjkim} 21655714Skris 21755714Skrisint BN_num_bits(const BIGNUM *a) 218280297Sjkim{ 219280297Sjkim int i = a->top - 1; 220280297Sjkim bn_check_top(a); 22155714Skris 222280297Sjkim if (BN_is_zero(a)) 223280297Sjkim return 0; 224280297Sjkim return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); 225280297Sjkim} 22655714Skris 22755714Skrisvoid BN_clear_free(BIGNUM *a) 228280297Sjkim{ 229280297Sjkim int i; 23055714Skris 231280297Sjkim if (a == NULL) 232280297Sjkim return; 233280297Sjkim bn_check_top(a); 234280297Sjkim if (a->d != NULL) { 235280297Sjkim OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 236280297Sjkim if (!(BN_get_flags(a, BN_FLG_STATIC_DATA))) 237280297Sjkim OPENSSL_free(a->d); 238280297Sjkim } 239280297Sjkim i = BN_get_flags(a, BN_FLG_MALLOCED); 240280297Sjkim OPENSSL_cleanse(a, sizeof(BIGNUM)); 241280297Sjkim if (i) 242280297Sjkim OPENSSL_free(a); 243280297Sjkim} 24455714Skris 24555714Skrisvoid BN_free(BIGNUM *a) 246280297Sjkim{ 247280297Sjkim if (a == NULL) 248280297Sjkim return; 249280297Sjkim bn_check_top(a); 250280297Sjkim if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA))) 251280297Sjkim OPENSSL_free(a->d); 252280297Sjkim if (a->flags & BN_FLG_MALLOCED) 253280297Sjkim OPENSSL_free(a); 254280297Sjkim else { 255160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 256280297Sjkim a->flags |= BN_FLG_FREE; 257160814Ssimon#endif 258280297Sjkim a->d = NULL; 259280297Sjkim } 260280297Sjkim} 26155714Skris 26255714Skrisvoid BN_init(BIGNUM *a) 263280297Sjkim{ 264280297Sjkim memset(a, 0, sizeof(BIGNUM)); 265280297Sjkim bn_check_top(a); 266280297Sjkim} 26755714Skris 26855714SkrisBIGNUM *BN_new(void) 269280297Sjkim{ 270280297Sjkim BIGNUM *ret; 27155714Skris 272280297Sjkim if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) { 273280297Sjkim BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); 274280297Sjkim return (NULL); 275280297Sjkim } 276280297Sjkim ret->flags = BN_FLG_MALLOCED; 277280297Sjkim ret->top = 0; 278280297Sjkim ret->neg = 0; 279280297Sjkim ret->dmax = 0; 280280297Sjkim ret->d = NULL; 281280297Sjkim bn_check_top(ret); 282280297Sjkim return (ret); 283280297Sjkim} 28455714Skris 285109998Smarkm/* This is used both by bn_expand2() and bn_dup_expand() */ 286109998Smarkm/* The caller MUST check that words > b->dmax before calling this */ 287109998Smarkmstatic BN_ULONG *bn_expand_internal(const BIGNUM *b, int words) 288280297Sjkim{ 289280297Sjkim BN_ULONG *A, *a = NULL; 290280297Sjkim const BN_ULONG *B; 291280297Sjkim int i; 29255714Skris 293280297Sjkim bn_check_top(b); 294160814Ssimon 295280297Sjkim if (words > (INT_MAX / (4 * BN_BITS2))) { 296280297Sjkim BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); 297280297Sjkim return NULL; 298280297Sjkim } 299280297Sjkim if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { 300280297Sjkim BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 301280297Sjkim return (NULL); 302280297Sjkim } 303280297Sjkim a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); 304280297Sjkim if (A == NULL) { 305280297Sjkim BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); 306280297Sjkim return (NULL); 307280297Sjkim } 308269682Sjkim#ifdef PURIFY 309280297Sjkim /* 310280297Sjkim * Valgrind complains in BN_consttime_swap because we process the whole 311280297Sjkim * array even if it's not initialised yet. This doesn't matter in that 312280297Sjkim * function - what's important is constant time operation (we're not 313280297Sjkim * actually going to use the data) 314280297Sjkim */ 315280297Sjkim memset(a, 0, sizeof(BN_ULONG) * words); 316269682Sjkim#endif 317269682Sjkim 318109998Smarkm#if 1 319280297Sjkim B = b->d; 320280297Sjkim /* Check if the previous number needs to be copied */ 321280297Sjkim if (B != NULL) { 322280297Sjkim for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 323280297Sjkim /* 324280297Sjkim * The fact that the loop is unrolled 325280297Sjkim * 4-wise is a tribute to Intel. It's 326280297Sjkim * the one that doesn't have enough 327280297Sjkim * registers to accomodate more data. 328280297Sjkim * I'd unroll it 8-wise otherwise:-) 329280297Sjkim * 330280297Sjkim * <appro@fy.chalmers.se> 331280297Sjkim */ 332280297Sjkim BN_ULONG a0, a1, a2, a3; 333280297Sjkim a0 = B[0]; 334280297Sjkim a1 = B[1]; 335280297Sjkim a2 = B[2]; 336280297Sjkim a3 = B[3]; 337280297Sjkim A[0] = a0; 338280297Sjkim A[1] = a1; 339280297Sjkim A[2] = a2; 340280297Sjkim A[3] = a3; 341280297Sjkim } 342280297Sjkim /* 343280297Sjkim * workaround for ultrix cc: without 'case 0', the optimizer does 344280297Sjkim * the switch table by doing a=top&3; a--; goto jump_table[a]; 345280297Sjkim * which fails for top== 0 346280297Sjkim */ 347280297Sjkim switch (b->top & 3) { 348280297Sjkim case 3: 349280297Sjkim A[2] = B[2]; 350280297Sjkim case 2: 351280297Sjkim A[1] = B[1]; 352280297Sjkim case 1: 353280297Sjkim A[0] = B[0]; 354280297Sjkim case 0: 355280297Sjkim ; 356280297Sjkim } 357280297Sjkim } 358109998Smarkm#else 359280297Sjkim memset(A, 0, sizeof(BN_ULONG) * words); 360280297Sjkim memcpy(A, b->d, sizeof(b->d[0]) * b->top); 361109998Smarkm#endif 362109998Smarkm 363280297Sjkim return (a); 364280297Sjkim} 365280297Sjkim 366280297Sjkim/* 367280297Sjkim * This is an internal function that can be used instead of bn_expand2() when 368280297Sjkim * there is a need to copy BIGNUMs instead of only expanding the data part, 369280297Sjkim * while still expanding them. Especially useful when needing to expand 370280297Sjkim * BIGNUMs that are declared 'const' and should therefore not be changed. The 371280297Sjkim * reason to use this instead of a BN_dup() followed by a bn_expand2() is 372280297Sjkim * memory allocation overhead. A BN_dup() followed by a bn_expand2() will 373280297Sjkim * allocate new memory for the BIGNUM data twice, and free it once, while 374280297Sjkim * bn_dup_expand() makes sure allocation is made only once. 375109998Smarkm */ 376109998Smarkm 377160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 378109998SmarkmBIGNUM *bn_dup_expand(const BIGNUM *b, int words) 379280297Sjkim{ 380280297Sjkim BIGNUM *r = NULL; 381109998Smarkm 382280297Sjkim bn_check_top(b); 383160814Ssimon 384280297Sjkim /* 385280297Sjkim * This function does not work if words <= b->dmax && top < words because 386280297Sjkim * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used 387280297Sjkim * anywhere yet.) 388280297Sjkim */ 389160814Ssimon 390280297Sjkim if (words > b->dmax) { 391280297Sjkim BN_ULONG *a = bn_expand_internal(b, words); 392109998Smarkm 393280297Sjkim if (a) { 394280297Sjkim r = BN_new(); 395280297Sjkim if (r) { 396280297Sjkim r->top = b->top; 397280297Sjkim r->dmax = words; 398280297Sjkim r->neg = b->neg; 399280297Sjkim r->d = a; 400280297Sjkim } else { 401280297Sjkim /* r == NULL, BN_new failure */ 402280297Sjkim OPENSSL_free(a); 403280297Sjkim } 404280297Sjkim } 405280297Sjkim /* 406280297Sjkim * If a == NULL, there was an error in allocation in 407280297Sjkim * bn_expand_internal(), and NULL should be returned 408280297Sjkim */ 409280297Sjkim } else { 410280297Sjkim r = BN_dup(b); 411280297Sjkim } 41255714Skris 413280297Sjkim bn_check_top(r); 414280297Sjkim return r; 415280297Sjkim} 416160814Ssimon#endif 41755714Skris 418280297Sjkim/* 419280297Sjkim * This is an internal function that should not be used in applications. It 420280297Sjkim * ensures that 'b' has enough room for a 'words' word number and initialises 421280297Sjkim * any unused part of b->d with leading zeros. It is mostly used by the 422280297Sjkim * various BIGNUM routines. If there is an error, NULL is returned. If not, 423280297Sjkim * 'b' is returned. 424280297Sjkim */ 42555714Skris 426109998SmarkmBIGNUM *bn_expand2(BIGNUM *b, int words) 427280297Sjkim{ 428280297Sjkim bn_check_top(b); 429160814Ssimon 430280297Sjkim if (words > b->dmax) { 431280297Sjkim BN_ULONG *a = bn_expand_internal(b, words); 432280297Sjkim if (!a) 433280297Sjkim return NULL; 434280297Sjkim if (b->d) 435280297Sjkim OPENSSL_free(b->d); 436280297Sjkim b->d = a; 437280297Sjkim b->dmax = words; 438280297Sjkim } 439109998Smarkm 440160814Ssimon/* None of this should be necessary because of what b->top means! */ 441160814Ssimon#if 0 442280297Sjkim /* 443280297Sjkim * NB: bn_wexpand() calls this only if the BIGNUM really has to grow 444280297Sjkim */ 445280297Sjkim if (b->top < b->dmax) { 446280297Sjkim int i; 447280297Sjkim BN_ULONG *A = &(b->d[b->top]); 448280297Sjkim for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) { 449280297Sjkim A[0] = 0; 450280297Sjkim A[1] = 0; 451280297Sjkim A[2] = 0; 452280297Sjkim A[3] = 0; 453280297Sjkim A[4] = 0; 454280297Sjkim A[5] = 0; 455280297Sjkim A[6] = 0; 456280297Sjkim A[7] = 0; 457280297Sjkim } 458280297Sjkim for (i = (b->dmax - b->top) & 7; i > 0; i--, A++) 459280297Sjkim A[0] = 0; 460280297Sjkim assert(A == &(b->d[b->dmax])); 461280297Sjkim } 462160814Ssimon#endif 463280297Sjkim bn_check_top(b); 464280297Sjkim return b; 465280297Sjkim} 46655714Skris 46755714SkrisBIGNUM *BN_dup(const BIGNUM *a) 468280297Sjkim{ 469280297Sjkim BIGNUM *t; 47055714Skris 471280297Sjkim if (a == NULL) 472280297Sjkim return NULL; 473280297Sjkim bn_check_top(a); 47455714Skris 475280297Sjkim t = BN_new(); 476280297Sjkim if (t == NULL) 477280297Sjkim return NULL; 478280297Sjkim if (!BN_copy(t, a)) { 479280297Sjkim BN_free(t); 480280297Sjkim return NULL; 481280297Sjkim } 482280297Sjkim bn_check_top(t); 483280297Sjkim return t; 484280297Sjkim} 48555714Skris 48655714SkrisBIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 487280297Sjkim{ 488280297Sjkim int i; 489280297Sjkim BN_ULONG *A; 490280297Sjkim const BN_ULONG *B; 49155714Skris 492280297Sjkim bn_check_top(b); 49355714Skris 494280297Sjkim if (a == b) 495280297Sjkim return (a); 496280297Sjkim if (bn_wexpand(a, b->top) == NULL) 497280297Sjkim return (NULL); 49855714Skris 49955714Skris#if 1 500280297Sjkim A = a->d; 501280297Sjkim B = b->d; 502280297Sjkim for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 503280297Sjkim BN_ULONG a0, a1, a2, a3; 504280297Sjkim a0 = B[0]; 505280297Sjkim a1 = B[1]; 506280297Sjkim a2 = B[2]; 507280297Sjkim a3 = B[3]; 508280297Sjkim A[0] = a0; 509280297Sjkim A[1] = a1; 510280297Sjkim A[2] = a2; 511280297Sjkim A[3] = a3; 512280297Sjkim } 513280297Sjkim /* ultrix cc workaround, see comments in bn_expand_internal */ 514280297Sjkim switch (b->top & 3) { 515280297Sjkim case 3: 516280297Sjkim A[2] = B[2]; 517280297Sjkim case 2: 518280297Sjkim A[1] = B[1]; 519280297Sjkim case 1: 520280297Sjkim A[0] = B[0]; 521280297Sjkim case 0:; 522280297Sjkim } 52355714Skris#else 524280297Sjkim memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); 52555714Skris#endif 52655714Skris 527280297Sjkim a->top = b->top; 528280297Sjkim a->neg = b->neg; 529280297Sjkim bn_check_top(a); 530280297Sjkim return (a); 531280297Sjkim} 53255714Skris 533109998Smarkmvoid BN_swap(BIGNUM *a, BIGNUM *b) 534280297Sjkim{ 535280297Sjkim int flags_old_a, flags_old_b; 536280297Sjkim BN_ULONG *tmp_d; 537280297Sjkim int tmp_top, tmp_dmax, tmp_neg; 538160814Ssimon 539280297Sjkim bn_check_top(a); 540280297Sjkim bn_check_top(b); 541109998Smarkm 542280297Sjkim flags_old_a = a->flags; 543280297Sjkim flags_old_b = b->flags; 544109998Smarkm 545280297Sjkim tmp_d = a->d; 546280297Sjkim tmp_top = a->top; 547280297Sjkim tmp_dmax = a->dmax; 548280297Sjkim tmp_neg = a->neg; 549280297Sjkim 550280297Sjkim a->d = b->d; 551280297Sjkim a->top = b->top; 552280297Sjkim a->dmax = b->dmax; 553280297Sjkim a->neg = b->neg; 554280297Sjkim 555280297Sjkim b->d = tmp_d; 556280297Sjkim b->top = tmp_top; 557280297Sjkim b->dmax = tmp_dmax; 558280297Sjkim b->neg = tmp_neg; 559280297Sjkim 560280297Sjkim a->flags = 561280297Sjkim (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); 562280297Sjkim b->flags = 563280297Sjkim (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); 564280297Sjkim bn_check_top(a); 565280297Sjkim bn_check_top(b); 566280297Sjkim} 567280297Sjkim 56855714Skrisvoid BN_clear(BIGNUM *a) 569280297Sjkim{ 570280297Sjkim bn_check_top(a); 571280297Sjkim if (a->d != NULL) 572306198Sjkim OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 573280297Sjkim a->top = 0; 574280297Sjkim a->neg = 0; 575280297Sjkim} 57655714Skris 577109998SmarkmBN_ULONG BN_get_word(const BIGNUM *a) 578280297Sjkim{ 579280297Sjkim if (a->top > 1) 580280297Sjkim return BN_MASK2; 581280297Sjkim else if (a->top == 1) 582280297Sjkim return a->d[0]; 583280297Sjkim /* a->top == 0 */ 584280297Sjkim return 0; 585280297Sjkim} 58655714Skris 58755714Skrisint BN_set_word(BIGNUM *a, BN_ULONG w) 588280297Sjkim{ 589280297Sjkim bn_check_top(a); 590280297Sjkim if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) 591280297Sjkim return (0); 592280297Sjkim a->neg = 0; 593280297Sjkim a->d[0] = w; 594280297Sjkim a->top = (w ? 1 : 0); 595280297Sjkim bn_check_top(a); 596280297Sjkim return (1); 597280297Sjkim} 59855714Skris 59955714SkrisBIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 600280297Sjkim{ 601280297Sjkim unsigned int i, m; 602280297Sjkim unsigned int n; 603280297Sjkim BN_ULONG l; 604280297Sjkim BIGNUM *bn = NULL; 60555714Skris 606280297Sjkim if (ret == NULL) 607280297Sjkim ret = bn = BN_new(); 608280297Sjkim if (ret == NULL) 609280297Sjkim return (NULL); 610280297Sjkim bn_check_top(ret); 611280297Sjkim l = 0; 612280297Sjkim n = len; 613280297Sjkim if (n == 0) { 614280297Sjkim ret->top = 0; 615280297Sjkim return (ret); 616280297Sjkim } 617280297Sjkim i = ((n - 1) / BN_BYTES) + 1; 618280297Sjkim m = ((n - 1) % (BN_BYTES)); 619280297Sjkim if (bn_wexpand(ret, (int)i) == NULL) { 620280297Sjkim if (bn) 621280297Sjkim BN_free(bn); 622280297Sjkim return NULL; 623280297Sjkim } 624280297Sjkim ret->top = i; 625280297Sjkim ret->neg = 0; 626280297Sjkim while (n--) { 627280297Sjkim l = (l << 8L) | *(s++); 628280297Sjkim if (m-- == 0) { 629280297Sjkim ret->d[--i] = l; 630280297Sjkim l = 0; 631280297Sjkim m = BN_BYTES - 1; 632280297Sjkim } 633280297Sjkim } 634280297Sjkim /* 635280297Sjkim * need to call this due to clear byte at top if avoiding having the top 636280297Sjkim * bit set (-ve number) 637280297Sjkim */ 638280297Sjkim bn_correct_top(ret); 639280297Sjkim return (ret); 640280297Sjkim} 64155714Skris 64255714Skris/* ignore negative */ 64355714Skrisint BN_bn2bin(const BIGNUM *a, unsigned char *to) 644280297Sjkim{ 645280297Sjkim int n, i; 646280297Sjkim BN_ULONG l; 64755714Skris 648280297Sjkim bn_check_top(a); 649280297Sjkim n = i = BN_num_bytes(a); 650280297Sjkim while (i--) { 651280297Sjkim l = a->d[i / BN_BYTES]; 652280297Sjkim *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; 653280297Sjkim } 654280297Sjkim return (n); 655280297Sjkim} 65655714Skris 65755714Skrisint BN_ucmp(const BIGNUM *a, const BIGNUM *b) 658280297Sjkim{ 659280297Sjkim int i; 660280297Sjkim BN_ULONG t1, t2, *ap, *bp; 66155714Skris 662280297Sjkim bn_check_top(a); 663280297Sjkim bn_check_top(b); 66455714Skris 665280297Sjkim i = a->top - b->top; 666280297Sjkim if (i != 0) 667280297Sjkim return (i); 668280297Sjkim ap = a->d; 669280297Sjkim bp = b->d; 670280297Sjkim for (i = a->top - 1; i >= 0; i--) { 671280297Sjkim t1 = ap[i]; 672280297Sjkim t2 = bp[i]; 673280297Sjkim if (t1 != t2) 674280297Sjkim return ((t1 > t2) ? 1 : -1); 675280297Sjkim } 676280297Sjkim return (0); 677280297Sjkim} 67855714Skris 67955714Skrisint BN_cmp(const BIGNUM *a, const BIGNUM *b) 680280297Sjkim{ 681280297Sjkim int i; 682280297Sjkim int gt, lt; 683280297Sjkim BN_ULONG t1, t2; 68455714Skris 685280297Sjkim if ((a == NULL) || (b == NULL)) { 686280297Sjkim if (a != NULL) 687280297Sjkim return (-1); 688280297Sjkim else if (b != NULL) 689280297Sjkim return (1); 690280297Sjkim else 691280297Sjkim return (0); 692280297Sjkim } 69355714Skris 694280297Sjkim bn_check_top(a); 695280297Sjkim bn_check_top(b); 69655714Skris 697280297Sjkim if (a->neg != b->neg) { 698280297Sjkim if (a->neg) 699280297Sjkim return (-1); 700280297Sjkim else 701280297Sjkim return (1); 702280297Sjkim } 703280297Sjkim if (a->neg == 0) { 704280297Sjkim gt = 1; 705280297Sjkim lt = -1; 706280297Sjkim } else { 707280297Sjkim gt = -1; 708280297Sjkim lt = 1; 709280297Sjkim } 71055714Skris 711280297Sjkim if (a->top > b->top) 712280297Sjkim return (gt); 713280297Sjkim if (a->top < b->top) 714280297Sjkim return (lt); 715280297Sjkim for (i = a->top - 1; i >= 0; i--) { 716280297Sjkim t1 = a->d[i]; 717280297Sjkim t2 = b->d[i]; 718280297Sjkim if (t1 > t2) 719280297Sjkim return (gt); 720280297Sjkim if (t1 < t2) 721280297Sjkim return (lt); 722280297Sjkim } 723280297Sjkim return (0); 724280297Sjkim} 72555714Skris 72655714Skrisint BN_set_bit(BIGNUM *a, int n) 727280297Sjkim{ 728280297Sjkim int i, j, k; 72955714Skris 730280297Sjkim if (n < 0) 731280297Sjkim return 0; 732160814Ssimon 733280297Sjkim i = n / BN_BITS2; 734280297Sjkim j = n % BN_BITS2; 735280297Sjkim if (a->top <= i) { 736280297Sjkim if (bn_wexpand(a, i + 1) == NULL) 737280297Sjkim return (0); 738280297Sjkim for (k = a->top; k < i + 1; k++) 739280297Sjkim a->d[k] = 0; 740280297Sjkim a->top = i + 1; 741280297Sjkim } 74255714Skris 743280297Sjkim a->d[i] |= (((BN_ULONG)1) << j); 744280297Sjkim bn_check_top(a); 745280297Sjkim return (1); 746280297Sjkim} 74755714Skris 74855714Skrisint BN_clear_bit(BIGNUM *a, int n) 749280297Sjkim{ 750280297Sjkim int i, j; 75155714Skris 752280297Sjkim bn_check_top(a); 753280297Sjkim if (n < 0) 754280297Sjkim return 0; 755160814Ssimon 756280297Sjkim i = n / BN_BITS2; 757280297Sjkim j = n % BN_BITS2; 758280297Sjkim if (a->top <= i) 759280297Sjkim return (0); 76055714Skris 761280297Sjkim a->d[i] &= (~(((BN_ULONG)1) << j)); 762280297Sjkim bn_correct_top(a); 763280297Sjkim return (1); 764280297Sjkim} 76555714Skris 76655714Skrisint BN_is_bit_set(const BIGNUM *a, int n) 767280297Sjkim{ 768280297Sjkim int i, j; 76955714Skris 770280297Sjkim bn_check_top(a); 771280297Sjkim if (n < 0) 772280297Sjkim return 0; 773280297Sjkim i = n / BN_BITS2; 774280297Sjkim j = n % BN_BITS2; 775280297Sjkim if (a->top <= i) 776280297Sjkim return 0; 777280297Sjkim return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 778280297Sjkim} 77955714Skris 78055714Skrisint BN_mask_bits(BIGNUM *a, int n) 781280297Sjkim{ 782280297Sjkim int b, w; 78355714Skris 784280297Sjkim bn_check_top(a); 785280297Sjkim if (n < 0) 786280297Sjkim return 0; 787160814Ssimon 788280297Sjkim w = n / BN_BITS2; 789280297Sjkim b = n % BN_BITS2; 790280297Sjkim if (w >= a->top) 791280297Sjkim return 0; 792280297Sjkim if (b == 0) 793280297Sjkim a->top = w; 794280297Sjkim else { 795280297Sjkim a->top = w + 1; 796280297Sjkim a->d[w] &= ~(BN_MASK2 << b); 797280297Sjkim } 798280297Sjkim bn_correct_top(a); 799280297Sjkim return (1); 800280297Sjkim} 80155714Skris 802160814Ssimonvoid BN_set_negative(BIGNUM *a, int b) 803280297Sjkim{ 804280297Sjkim if (b && !BN_is_zero(a)) 805280297Sjkim a->neg = 1; 806280297Sjkim else 807280297Sjkim a->neg = 0; 808280297Sjkim} 809160814Ssimon 810109998Smarkmint bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 811280297Sjkim{ 812280297Sjkim int i; 813280297Sjkim BN_ULONG aa, bb; 81455714Skris 815280297Sjkim aa = a[n - 1]; 816280297Sjkim bb = b[n - 1]; 817280297Sjkim if (aa != bb) 818280297Sjkim return ((aa > bb) ? 1 : -1); 819280297Sjkim for (i = n - 2; i >= 0; i--) { 820280297Sjkim aa = a[i]; 821280297Sjkim bb = b[i]; 822280297Sjkim if (aa != bb) 823280297Sjkim return ((aa > bb) ? 1 : -1); 824280297Sjkim } 825280297Sjkim return (0); 826280297Sjkim} 82755714Skris 828280297Sjkim/* 829280297Sjkim * Here follows a specialised variants of bn_cmp_words(). It has the 830280297Sjkim * property of performing the operation on arrays of different sizes. The 831280297Sjkim * sizes of those arrays is expressed through cl, which is the common length 832280297Sjkim * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the 833280297Sjkim * two lengths, calculated as len(a)-len(b). All lengths are the number of 834280297Sjkim * BN_ULONGs... 835280297Sjkim */ 836109998Smarkm 837280297Sjkimint bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 838280297Sjkim{ 839280297Sjkim int n, i; 840280297Sjkim n = cl - 1; 841109998Smarkm 842280297Sjkim if (dl < 0) { 843280297Sjkim for (i = dl; i < 0; i++) { 844280297Sjkim if (b[n - i] != 0) 845280297Sjkim return -1; /* a < b */ 846280297Sjkim } 847280297Sjkim } 848280297Sjkim if (dl > 0) { 849280297Sjkim for (i = dl; i > 0; i--) { 850280297Sjkim if (a[n + i] != 0) 851280297Sjkim return 1; /* a > b */ 852280297Sjkim } 853280297Sjkim } 854280297Sjkim return bn_cmp_words(a, b, cl); 855280297Sjkim} 856264265Sdelphij 857280297Sjkim/* 858280297Sjkim * Constant-time conditional swap of a and b. 859264265Sdelphij * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. 860264265Sdelphij * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, 861264265Sdelphij * and that no more than nwords are used by either a or b. 862264265Sdelphij * a and b cannot be the same number 863264265Sdelphij */ 864264265Sdelphijvoid BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 865280297Sjkim{ 866280297Sjkim BN_ULONG t; 867280297Sjkim int i; 868264265Sdelphij 869280297Sjkim bn_wcheck_size(a, nwords); 870280297Sjkim bn_wcheck_size(b, nwords); 871264265Sdelphij 872280297Sjkim assert(a != b); 873280297Sjkim assert((condition & (condition - 1)) == 0); 874280297Sjkim assert(sizeof(BN_ULONG) >= sizeof(int)); 875264265Sdelphij 876280297Sjkim condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 877264265Sdelphij 878280297Sjkim t = (a->top ^ b->top) & condition; 879280297Sjkim a->top ^= t; 880280297Sjkim b->top ^= t; 881264265Sdelphij 882264265Sdelphij#define BN_CONSTTIME_SWAP(ind) \ 883280297Sjkim do { \ 884280297Sjkim t = (a->d[ind] ^ b->d[ind]) & condition; \ 885280297Sjkim a->d[ind] ^= t; \ 886280297Sjkim b->d[ind] ^= t; \ 887280297Sjkim } while (0) 888264265Sdelphij 889280297Sjkim switch (nwords) { 890280297Sjkim default: 891280297Sjkim for (i = 10; i < nwords; i++) 892280297Sjkim BN_CONSTTIME_SWAP(i); 893280297Sjkim /* Fallthrough */ 894280297Sjkim case 10: 895280297Sjkim BN_CONSTTIME_SWAP(9); /* Fallthrough */ 896280297Sjkim case 9: 897280297Sjkim BN_CONSTTIME_SWAP(8); /* Fallthrough */ 898280297Sjkim case 8: 899280297Sjkim BN_CONSTTIME_SWAP(7); /* Fallthrough */ 900280297Sjkim case 7: 901280297Sjkim BN_CONSTTIME_SWAP(6); /* Fallthrough */ 902280297Sjkim case 6: 903280297Sjkim BN_CONSTTIME_SWAP(5); /* Fallthrough */ 904280297Sjkim case 5: 905280297Sjkim BN_CONSTTIME_SWAP(4); /* Fallthrough */ 906280297Sjkim case 4: 907280297Sjkim BN_CONSTTIME_SWAP(3); /* Fallthrough */ 908280297Sjkim case 3: 909280297Sjkim BN_CONSTTIME_SWAP(2); /* Fallthrough */ 910280297Sjkim case 2: 911280297Sjkim BN_CONSTTIME_SWAP(1); /* Fallthrough */ 912280297Sjkim case 1: 913280297Sjkim BN_CONSTTIME_SWAP(0); 914280297Sjkim } 915264265Sdelphij#undef BN_CONSTTIME_SWAP 916264265Sdelphij} 917