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. 8280304Sjkim * 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). 15280304Sjkim * 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. 22280304Sjkim * 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 :-). 37280304Sjkim * 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)" 40280304Sjkim * 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. 52280304Sjkim * 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 60280304Sjkim# 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 70280304Sjkimconst 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 74280304Sjkim/*- 75280304Sjkim * 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 */ 84280304Sjkimstatic int bn_limit_bits = 0; 85280304Sjkimstatic int bn_limit_num = 8; /* (1<<bn_limit_bits) */ 86280304Sjkimstatic int bn_limit_bits_low = 0; 87280304Sjkimstatic int bn_limit_num_low = 8; /* (1<<bn_limit_bits_low) */ 88280304Sjkimstatic int bn_limit_bits_high = 0; 89280304Sjkimstatic int bn_limit_num_high = 8; /* (1<<bn_limit_bits_high) */ 90280304Sjkimstatic int bn_limit_bits_mont = 0; 91280304Sjkimstatic int bn_limit_num_mont = 8; /* (1<<bn_limit_bits_mont) */ 9255714Skris 9355714Skrisvoid BN_set_params(int mult, int high, int low, int mont) 94280304Sjkim{ 95280304Sjkim if (mult >= 0) { 96280304Sjkim if (mult > (int)(sizeof(int) * 8) - 1) 97280304Sjkim mult = sizeof(int) * 8 - 1; 98280304Sjkim bn_limit_bits = mult; 99280304Sjkim bn_limit_num = 1 << mult; 100280304Sjkim } 101280304Sjkim if (high >= 0) { 102280304Sjkim if (high > (int)(sizeof(int) * 8) - 1) 103280304Sjkim high = sizeof(int) * 8 - 1; 104280304Sjkim bn_limit_bits_high = high; 105280304Sjkim bn_limit_num_high = 1 << high; 106280304Sjkim } 107280304Sjkim if (low >= 0) { 108280304Sjkim if (low > (int)(sizeof(int) * 8) - 1) 109280304Sjkim low = sizeof(int) * 8 - 1; 110280304Sjkim bn_limit_bits_low = low; 111280304Sjkim bn_limit_num_low = 1 << low; 112280304Sjkim } 113280304Sjkim if (mont >= 0) { 114280304Sjkim if (mont > (int)(sizeof(int) * 8) - 1) 115280304Sjkim mont = sizeof(int) * 8 - 1; 116280304Sjkim bn_limit_bits_mont = mont; 117280304Sjkim bn_limit_num_mont = 1 << mont; 118280304Sjkim } 119280304Sjkim} 12055714Skris 12155714Skrisint BN_get_params(int which) 122280304Sjkim{ 123280304Sjkim if (which == 0) 124280304Sjkim return (bn_limit_bits); 125280304Sjkim else if (which == 1) 126280304Sjkim return (bn_limit_bits_high); 127280304Sjkim else if (which == 2) 128280304Sjkim return (bn_limit_bits_low); 129280304Sjkim else if (which == 3) 130280304Sjkim return (bn_limit_bits_mont); 131280304Sjkim else 132280304Sjkim return (0); 133280304Sjkim} 134160814Ssimon#endif 13555714Skris 136109998Smarkmconst BIGNUM *BN_value_one(void) 137280304Sjkim{ 138280304Sjkim static const BN_ULONG data_one = 1L; 139280304Sjkim static const BIGNUM const_one = 140280304Sjkim { (BN_ULONG *)&data_one, 1, 1, 0, BN_FLG_STATIC_DATA }; 14155714Skris 142280304Sjkim return (&const_one); 143280304Sjkim} 14455714Skris 14555714Skrisint BN_num_bits_word(BN_ULONG l) 146280304Sjkim{ 147280304Sjkim static const unsigned char bits[256] = { 148280304Sjkim 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 149280304Sjkim 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 150280304Sjkim 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 151280304Sjkim 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 152280304Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 153280304Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 154280304Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 155280304Sjkim 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 156280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 157280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 158280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 159280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 160280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 161280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 162280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 163280304Sjkim 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 164280304Sjkim }; 16555714Skris 16655714Skris#if defined(SIXTY_FOUR_BIT_LONG) 167280304Sjkim if (l & 0xffffffff00000000L) { 168280304Sjkim if (l & 0xffff000000000000L) { 169280304Sjkim if (l & 0xff00000000000000L) { 170280304Sjkim return (bits[(int)(l >> 56)] + 56); 171280304Sjkim } else 172280304Sjkim return (bits[(int)(l >> 48)] + 48); 173280304Sjkim } else { 174280304Sjkim if (l & 0x0000ff0000000000L) { 175280304Sjkim return (bits[(int)(l >> 40)] + 40); 176280304Sjkim } else 177280304Sjkim return (bits[(int)(l >> 32)] + 32); 178280304Sjkim } 179280304Sjkim } else 18055714Skris#else 181280304Sjkim# ifdef SIXTY_FOUR_BIT 182280304Sjkim if (l & 0xffffffff00000000LL) { 183280304Sjkim if (l & 0xffff000000000000LL) { 184280304Sjkim if (l & 0xff00000000000000LL) { 185280304Sjkim return (bits[(int)(l >> 56)] + 56); 186280304Sjkim } else 187280304Sjkim return (bits[(int)(l >> 48)] + 48); 188280304Sjkim } else { 189280304Sjkim if (l & 0x0000ff0000000000LL) { 190280304Sjkim return (bits[(int)(l >> 40)] + 40); 191280304Sjkim } else 192280304Sjkim return (bits[(int)(l >> 32)] + 32); 193280304Sjkim } 194280304Sjkim } else 195280304Sjkim# endif 19655714Skris#endif 197280304Sjkim { 19855714Skris#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 199280304Sjkim if (l & 0xffff0000L) { 200280304Sjkim if (l & 0xff000000L) 201280304Sjkim return (bits[(int)(l >> 24L)] + 24); 202280304Sjkim else 203280304Sjkim return (bits[(int)(l >> 16L)] + 16); 204280304Sjkim } else 20555714Skris#endif 206280304Sjkim { 207238405Sjkim#if defined(THIRTY_TWO_BIT) || defined(SIXTY_FOUR_BIT) || defined(SIXTY_FOUR_BIT_LONG) 208280304Sjkim if (l & 0xff00L) 209280304Sjkim return (bits[(int)(l >> 8)] + 8); 210280304Sjkim else 21155714Skris#endif 212280304Sjkim return (bits[(int)(l)]); 213280304Sjkim } 214280304Sjkim } 215280304Sjkim} 21655714Skris 21755714Skrisint BN_num_bits(const BIGNUM *a) 218280304Sjkim{ 219280304Sjkim int i = a->top - 1; 220280304Sjkim bn_check_top(a); 22155714Skris 222280304Sjkim if (BN_is_zero(a)) 223280304Sjkim return 0; 224280304Sjkim return ((i * BN_BITS2) + BN_num_bits_word(a->d[i])); 225280304Sjkim} 22655714Skris 22755714Skrisvoid BN_clear_free(BIGNUM *a) 228280304Sjkim{ 229280304Sjkim int i; 23055714Skris 231280304Sjkim if (a == NULL) 232280304Sjkim return; 233280304Sjkim bn_check_top(a); 234280304Sjkim if (a->d != NULL) { 235280304Sjkim OPENSSL_cleanse(a->d, a->dmax * sizeof(a->d[0])); 236280304Sjkim if (!(BN_get_flags(a, BN_FLG_STATIC_DATA))) 237280304Sjkim OPENSSL_free(a->d); 238280304Sjkim } 239280304Sjkim i = BN_get_flags(a, BN_FLG_MALLOCED); 240280304Sjkim OPENSSL_cleanse(a, sizeof(BIGNUM)); 241280304Sjkim if (i) 242280304Sjkim OPENSSL_free(a); 243280304Sjkim} 24455714Skris 24555714Skrisvoid BN_free(BIGNUM *a) 246280304Sjkim{ 247280304Sjkim if (a == NULL) 248280304Sjkim return; 249280304Sjkim bn_check_top(a); 250280304Sjkim if ((a->d != NULL) && !(BN_get_flags(a, BN_FLG_STATIC_DATA))) 251280304Sjkim OPENSSL_free(a->d); 252280304Sjkim if (a->flags & BN_FLG_MALLOCED) 253280304Sjkim OPENSSL_free(a); 254280304Sjkim else { 255160814Ssimon#ifndef OPENSSL_NO_DEPRECATED 256280304Sjkim a->flags |= BN_FLG_FREE; 257160814Ssimon#endif 258280304Sjkim a->d = NULL; 259280304Sjkim } 260280304Sjkim} 26155714Skris 26255714Skrisvoid BN_init(BIGNUM *a) 263280304Sjkim{ 264280304Sjkim memset(a, 0, sizeof(BIGNUM)); 265280304Sjkim bn_check_top(a); 266280304Sjkim} 26755714Skris 26855714SkrisBIGNUM *BN_new(void) 269280304Sjkim{ 270280304Sjkim BIGNUM *ret; 27155714Skris 272280304Sjkim if ((ret = (BIGNUM *)OPENSSL_malloc(sizeof(BIGNUM))) == NULL) { 273280304Sjkim BNerr(BN_F_BN_NEW, ERR_R_MALLOC_FAILURE); 274280304Sjkim return (NULL); 275280304Sjkim } 276280304Sjkim ret->flags = BN_FLG_MALLOCED; 277280304Sjkim ret->top = 0; 278280304Sjkim ret->neg = 0; 279280304Sjkim ret->dmax = 0; 280280304Sjkim ret->d = NULL; 281280304Sjkim bn_check_top(ret); 282280304Sjkim return (ret); 283280304Sjkim} 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) 288280304Sjkim{ 289280304Sjkim BN_ULONG *A, *a = NULL; 290280304Sjkim const BN_ULONG *B; 291280304Sjkim int i; 29255714Skris 293280304Sjkim bn_check_top(b); 294160814Ssimon 295280304Sjkim if (words > (INT_MAX / (4 * BN_BITS2))) { 296280304Sjkim BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_BIGNUM_TOO_LONG); 297280304Sjkim return NULL; 298280304Sjkim } 299280304Sjkim if (BN_get_flags(b, BN_FLG_STATIC_DATA)) { 300280304Sjkim BNerr(BN_F_BN_EXPAND_INTERNAL, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 301280304Sjkim return (NULL); 302280304Sjkim } 303280304Sjkim a = A = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); 304280304Sjkim if (A == NULL) { 305280304Sjkim BNerr(BN_F_BN_EXPAND_INTERNAL, ERR_R_MALLOC_FAILURE); 306280304Sjkim return (NULL); 307280304Sjkim } 308269686Sjkim#ifdef PURIFY 309280304Sjkim /* 310280304Sjkim * Valgrind complains in BN_consttime_swap because we process the whole 311280304Sjkim * array even if it's not initialised yet. This doesn't matter in that 312280304Sjkim * function - what's important is constant time operation (we're not 313280304Sjkim * actually going to use the data) 314280304Sjkim */ 315280304Sjkim memset(a, 0, sizeof(BN_ULONG) * words); 316269686Sjkim#endif 317269686Sjkim 318109998Smarkm#if 1 319280304Sjkim B = b->d; 320280304Sjkim /* Check if the previous number needs to be copied */ 321280304Sjkim if (B != NULL) { 322280304Sjkim for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 323280304Sjkim /* 324280304Sjkim * The fact that the loop is unrolled 325280304Sjkim * 4-wise is a tribute to Intel. It's 326280304Sjkim * the one that doesn't have enough 327280304Sjkim * registers to accomodate more data. 328280304Sjkim * I'd unroll it 8-wise otherwise:-) 329280304Sjkim * 330280304Sjkim * <appro@fy.chalmers.se> 331280304Sjkim */ 332280304Sjkim BN_ULONG a0, a1, a2, a3; 333280304Sjkim a0 = B[0]; 334280304Sjkim a1 = B[1]; 335280304Sjkim a2 = B[2]; 336280304Sjkim a3 = B[3]; 337280304Sjkim A[0] = a0; 338280304Sjkim A[1] = a1; 339280304Sjkim A[2] = a2; 340280304Sjkim A[3] = a3; 341280304Sjkim } 342280304Sjkim /* 343280304Sjkim * workaround for ultrix cc: without 'case 0', the optimizer does 344280304Sjkim * the switch table by doing a=top&3; a--; goto jump_table[a]; 345280304Sjkim * which fails for top== 0 346280304Sjkim */ 347280304Sjkim switch (b->top & 3) { 348280304Sjkim case 3: 349280304Sjkim A[2] = B[2]; 350280304Sjkim case 2: 351280304Sjkim A[1] = B[1]; 352280304Sjkim case 1: 353280304Sjkim A[0] = B[0]; 354280304Sjkim case 0: 355280304Sjkim ; 356280304Sjkim } 357280304Sjkim } 358109998Smarkm#else 359280304Sjkim memset(A, 0, sizeof(BN_ULONG) * words); 360280304Sjkim memcpy(A, b->d, sizeof(b->d[0]) * b->top); 361109998Smarkm#endif 362109998Smarkm 363280304Sjkim return (a); 364280304Sjkim} 365280304Sjkim 366280304Sjkim/* 367280304Sjkim * This is an internal function that can be used instead of bn_expand2() when 368280304Sjkim * there is a need to copy BIGNUMs instead of only expanding the data part, 369280304Sjkim * while still expanding them. Especially useful when needing to expand 370280304Sjkim * BIGNUMs that are declared 'const' and should therefore not be changed. The 371280304Sjkim * reason to use this instead of a BN_dup() followed by a bn_expand2() is 372280304Sjkim * memory allocation overhead. A BN_dup() followed by a bn_expand2() will 373280304Sjkim * allocate new memory for the BIGNUM data twice, and free it once, while 374280304Sjkim * 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) 379280304Sjkim{ 380280304Sjkim BIGNUM *r = NULL; 381109998Smarkm 382280304Sjkim bn_check_top(b); 383160814Ssimon 384280304Sjkim /* 385280304Sjkim * This function does not work if words <= b->dmax && top < words because 386280304Sjkim * BN_dup() does not preserve 'dmax'! (But bn_dup_expand() is not used 387280304Sjkim * anywhere yet.) 388280304Sjkim */ 389160814Ssimon 390280304Sjkim if (words > b->dmax) { 391280304Sjkim BN_ULONG *a = bn_expand_internal(b, words); 392109998Smarkm 393280304Sjkim if (a) { 394280304Sjkim r = BN_new(); 395280304Sjkim if (r) { 396280304Sjkim r->top = b->top; 397280304Sjkim r->dmax = words; 398280304Sjkim r->neg = b->neg; 399280304Sjkim r->d = a; 400280304Sjkim } else { 401280304Sjkim /* r == NULL, BN_new failure */ 402280304Sjkim OPENSSL_free(a); 403280304Sjkim } 404280304Sjkim } 405280304Sjkim /* 406280304Sjkim * If a == NULL, there was an error in allocation in 407280304Sjkim * bn_expand_internal(), and NULL should be returned 408280304Sjkim */ 409280304Sjkim } else { 410280304Sjkim r = BN_dup(b); 411280304Sjkim } 41255714Skris 413280304Sjkim bn_check_top(r); 414280304Sjkim return r; 415280304Sjkim} 416160814Ssimon#endif 41755714Skris 418280304Sjkim/* 419280304Sjkim * This is an internal function that should not be used in applications. It 420280304Sjkim * ensures that 'b' has enough room for a 'words' word number and initialises 421280304Sjkim * any unused part of b->d with leading zeros. It is mostly used by the 422280304Sjkim * various BIGNUM routines. If there is an error, NULL is returned. If not, 423280304Sjkim * 'b' is returned. 424280304Sjkim */ 42555714Skris 426109998SmarkmBIGNUM *bn_expand2(BIGNUM *b, int words) 427280304Sjkim{ 428280304Sjkim bn_check_top(b); 429160814Ssimon 430280304Sjkim if (words > b->dmax) { 431280304Sjkim BN_ULONG *a = bn_expand_internal(b, words); 432280304Sjkim if (!a) 433280304Sjkim return NULL; 434280304Sjkim if (b->d) 435280304Sjkim OPENSSL_free(b->d); 436280304Sjkim b->d = a; 437280304Sjkim b->dmax = words; 438280304Sjkim } 439109998Smarkm 440160814Ssimon/* None of this should be necessary because of what b->top means! */ 441160814Ssimon#if 0 442280304Sjkim /* 443280304Sjkim * NB: bn_wexpand() calls this only if the BIGNUM really has to grow 444280304Sjkim */ 445280304Sjkim if (b->top < b->dmax) { 446280304Sjkim int i; 447280304Sjkim BN_ULONG *A = &(b->d[b->top]); 448280304Sjkim for (i = (b->dmax - b->top) >> 3; i > 0; i--, A += 8) { 449280304Sjkim A[0] = 0; 450280304Sjkim A[1] = 0; 451280304Sjkim A[2] = 0; 452280304Sjkim A[3] = 0; 453280304Sjkim A[4] = 0; 454280304Sjkim A[5] = 0; 455280304Sjkim A[6] = 0; 456280304Sjkim A[7] = 0; 457280304Sjkim } 458280304Sjkim for (i = (b->dmax - b->top) & 7; i > 0; i--, A++) 459280304Sjkim A[0] = 0; 460280304Sjkim assert(A == &(b->d[b->dmax])); 461280304Sjkim } 462160814Ssimon#endif 463280304Sjkim bn_check_top(b); 464280304Sjkim return b; 465280304Sjkim} 46655714Skris 46755714SkrisBIGNUM *BN_dup(const BIGNUM *a) 468280304Sjkim{ 469280304Sjkim BIGNUM *t; 47055714Skris 471280304Sjkim if (a == NULL) 472280304Sjkim return NULL; 473280304Sjkim bn_check_top(a); 47455714Skris 475280304Sjkim t = BN_new(); 476280304Sjkim if (t == NULL) 477280304Sjkim return NULL; 478280304Sjkim if (!BN_copy(t, a)) { 479280304Sjkim BN_free(t); 480280304Sjkim return NULL; 481280304Sjkim } 482280304Sjkim bn_check_top(t); 483280304Sjkim return t; 484280304Sjkim} 48555714Skris 48655714SkrisBIGNUM *BN_copy(BIGNUM *a, const BIGNUM *b) 487280304Sjkim{ 488280304Sjkim int i; 489280304Sjkim BN_ULONG *A; 490280304Sjkim const BN_ULONG *B; 49155714Skris 492280304Sjkim bn_check_top(b); 49355714Skris 494280304Sjkim if (a == b) 495280304Sjkim return (a); 496280304Sjkim if (bn_wexpand(a, b->top) == NULL) 497280304Sjkim return (NULL); 49855714Skris 49955714Skris#if 1 500280304Sjkim A = a->d; 501280304Sjkim B = b->d; 502280304Sjkim for (i = b->top >> 2; i > 0; i--, A += 4, B += 4) { 503280304Sjkim BN_ULONG a0, a1, a2, a3; 504280304Sjkim a0 = B[0]; 505280304Sjkim a1 = B[1]; 506280304Sjkim a2 = B[2]; 507280304Sjkim a3 = B[3]; 508280304Sjkim A[0] = a0; 509280304Sjkim A[1] = a1; 510280304Sjkim A[2] = a2; 511280304Sjkim A[3] = a3; 512280304Sjkim } 513280304Sjkim /* ultrix cc workaround, see comments in bn_expand_internal */ 514280304Sjkim switch (b->top & 3) { 515280304Sjkim case 3: 516280304Sjkim A[2] = B[2]; 517280304Sjkim case 2: 518280304Sjkim A[1] = B[1]; 519280304Sjkim case 1: 520280304Sjkim A[0] = B[0]; 521280304Sjkim case 0:; 522280304Sjkim } 52355714Skris#else 524280304Sjkim memcpy(a->d, b->d, sizeof(b->d[0]) * b->top); 52555714Skris#endif 52655714Skris 527280304Sjkim a->top = b->top; 528280304Sjkim a->neg = b->neg; 529280304Sjkim bn_check_top(a); 530280304Sjkim return (a); 531280304Sjkim} 53255714Skris 533109998Smarkmvoid BN_swap(BIGNUM *a, BIGNUM *b) 534280304Sjkim{ 535280304Sjkim int flags_old_a, flags_old_b; 536280304Sjkim BN_ULONG *tmp_d; 537280304Sjkim int tmp_top, tmp_dmax, tmp_neg; 538160814Ssimon 539280304Sjkim bn_check_top(a); 540280304Sjkim bn_check_top(b); 541109998Smarkm 542280304Sjkim flags_old_a = a->flags; 543280304Sjkim flags_old_b = b->flags; 544109998Smarkm 545280304Sjkim tmp_d = a->d; 546280304Sjkim tmp_top = a->top; 547280304Sjkim tmp_dmax = a->dmax; 548280304Sjkim tmp_neg = a->neg; 549280304Sjkim 550280304Sjkim a->d = b->d; 551280304Sjkim a->top = b->top; 552280304Sjkim a->dmax = b->dmax; 553280304Sjkim a->neg = b->neg; 554280304Sjkim 555280304Sjkim b->d = tmp_d; 556280304Sjkim b->top = tmp_top; 557280304Sjkim b->dmax = tmp_dmax; 558280304Sjkim b->neg = tmp_neg; 559280304Sjkim 560280304Sjkim a->flags = 561280304Sjkim (flags_old_a & BN_FLG_MALLOCED) | (flags_old_b & BN_FLG_STATIC_DATA); 562280304Sjkim b->flags = 563280304Sjkim (flags_old_b & BN_FLG_MALLOCED) | (flags_old_a & BN_FLG_STATIC_DATA); 564280304Sjkim bn_check_top(a); 565280304Sjkim bn_check_top(b); 566280304Sjkim} 567280304Sjkim 56855714Skrisvoid BN_clear(BIGNUM *a) 569280304Sjkim{ 570280304Sjkim bn_check_top(a); 571280304Sjkim if (a->d != NULL) 572280304Sjkim memset(a->d, 0, a->dmax * sizeof(a->d[0])); 573280304Sjkim a->top = 0; 574280304Sjkim a->neg = 0; 575280304Sjkim} 57655714Skris 577109998SmarkmBN_ULONG BN_get_word(const BIGNUM *a) 578280304Sjkim{ 579280304Sjkim if (a->top > 1) 580280304Sjkim return BN_MASK2; 581280304Sjkim else if (a->top == 1) 582280304Sjkim return a->d[0]; 583280304Sjkim /* a->top == 0 */ 584280304Sjkim return 0; 585280304Sjkim} 58655714Skris 58755714Skrisint BN_set_word(BIGNUM *a, BN_ULONG w) 588280304Sjkim{ 589280304Sjkim bn_check_top(a); 590280304Sjkim if (bn_expand(a, (int)sizeof(BN_ULONG) * 8) == NULL) 591280304Sjkim return (0); 592280304Sjkim a->neg = 0; 593280304Sjkim a->d[0] = w; 594280304Sjkim a->top = (w ? 1 : 0); 595280304Sjkim bn_check_top(a); 596280304Sjkim return (1); 597280304Sjkim} 59855714Skris 59955714SkrisBIGNUM *BN_bin2bn(const unsigned char *s, int len, BIGNUM *ret) 600280304Sjkim{ 601280304Sjkim unsigned int i, m; 602280304Sjkim unsigned int n; 603280304Sjkim BN_ULONG l; 604280304Sjkim BIGNUM *bn = NULL; 60555714Skris 606280304Sjkim if (ret == NULL) 607280304Sjkim ret = bn = BN_new(); 608280304Sjkim if (ret == NULL) 609280304Sjkim return (NULL); 610280304Sjkim bn_check_top(ret); 611280304Sjkim l = 0; 612280304Sjkim n = len; 613280304Sjkim if (n == 0) { 614280304Sjkim ret->top = 0; 615280304Sjkim return (ret); 616280304Sjkim } 617280304Sjkim i = ((n - 1) / BN_BYTES) + 1; 618280304Sjkim m = ((n - 1) % (BN_BYTES)); 619280304Sjkim if (bn_wexpand(ret, (int)i) == NULL) { 620280304Sjkim if (bn) 621280304Sjkim BN_free(bn); 622280304Sjkim return NULL; 623280304Sjkim } 624280304Sjkim ret->top = i; 625280304Sjkim ret->neg = 0; 626280304Sjkim while (n--) { 627280304Sjkim l = (l << 8L) | *(s++); 628280304Sjkim if (m-- == 0) { 629280304Sjkim ret->d[--i] = l; 630280304Sjkim l = 0; 631280304Sjkim m = BN_BYTES - 1; 632280304Sjkim } 633280304Sjkim } 634280304Sjkim /* 635280304Sjkim * need to call this due to clear byte at top if avoiding having the top 636280304Sjkim * bit set (-ve number) 637280304Sjkim */ 638280304Sjkim bn_correct_top(ret); 639280304Sjkim return (ret); 640280304Sjkim} 64155714Skris 64255714Skris/* ignore negative */ 64355714Skrisint BN_bn2bin(const BIGNUM *a, unsigned char *to) 644280304Sjkim{ 645280304Sjkim int n, i; 646280304Sjkim BN_ULONG l; 64755714Skris 648280304Sjkim bn_check_top(a); 649280304Sjkim n = i = BN_num_bytes(a); 650280304Sjkim while (i--) { 651280304Sjkim l = a->d[i / BN_BYTES]; 652280304Sjkim *(to++) = (unsigned char)(l >> (8 * (i % BN_BYTES))) & 0xff; 653280304Sjkim } 654280304Sjkim return (n); 655280304Sjkim} 65655714Skris 65755714Skrisint BN_ucmp(const BIGNUM *a, const BIGNUM *b) 658280304Sjkim{ 659280304Sjkim int i; 660280304Sjkim BN_ULONG t1, t2, *ap, *bp; 66155714Skris 662280304Sjkim bn_check_top(a); 663280304Sjkim bn_check_top(b); 66455714Skris 665280304Sjkim i = a->top - b->top; 666280304Sjkim if (i != 0) 667280304Sjkim return (i); 668280304Sjkim ap = a->d; 669280304Sjkim bp = b->d; 670280304Sjkim for (i = a->top - 1; i >= 0; i--) { 671280304Sjkim t1 = ap[i]; 672280304Sjkim t2 = bp[i]; 673280304Sjkim if (t1 != t2) 674280304Sjkim return ((t1 > t2) ? 1 : -1); 675280304Sjkim } 676280304Sjkim return (0); 677280304Sjkim} 67855714Skris 67955714Skrisint BN_cmp(const BIGNUM *a, const BIGNUM *b) 680280304Sjkim{ 681280304Sjkim int i; 682280304Sjkim int gt, lt; 683280304Sjkim BN_ULONG t1, t2; 68455714Skris 685280304Sjkim if ((a == NULL) || (b == NULL)) { 686280304Sjkim if (a != NULL) 687280304Sjkim return (-1); 688280304Sjkim else if (b != NULL) 689280304Sjkim return (1); 690280304Sjkim else 691280304Sjkim return (0); 692280304Sjkim } 69355714Skris 694280304Sjkim bn_check_top(a); 695280304Sjkim bn_check_top(b); 69655714Skris 697280304Sjkim if (a->neg != b->neg) { 698280304Sjkim if (a->neg) 699280304Sjkim return (-1); 700280304Sjkim else 701280304Sjkim return (1); 702280304Sjkim } 703280304Sjkim if (a->neg == 0) { 704280304Sjkim gt = 1; 705280304Sjkim lt = -1; 706280304Sjkim } else { 707280304Sjkim gt = -1; 708280304Sjkim lt = 1; 709280304Sjkim } 71055714Skris 711280304Sjkim if (a->top > b->top) 712280304Sjkim return (gt); 713280304Sjkim if (a->top < b->top) 714280304Sjkim return (lt); 715280304Sjkim for (i = a->top - 1; i >= 0; i--) { 716280304Sjkim t1 = a->d[i]; 717280304Sjkim t2 = b->d[i]; 718280304Sjkim if (t1 > t2) 719280304Sjkim return (gt); 720280304Sjkim if (t1 < t2) 721280304Sjkim return (lt); 722280304Sjkim } 723280304Sjkim return (0); 724280304Sjkim} 72555714Skris 72655714Skrisint BN_set_bit(BIGNUM *a, int n) 727280304Sjkim{ 728280304Sjkim int i, j, k; 72955714Skris 730280304Sjkim if (n < 0) 731280304Sjkim return 0; 732160814Ssimon 733280304Sjkim i = n / BN_BITS2; 734280304Sjkim j = n % BN_BITS2; 735280304Sjkim if (a->top <= i) { 736280304Sjkim if (bn_wexpand(a, i + 1) == NULL) 737280304Sjkim return (0); 738280304Sjkim for (k = a->top; k < i + 1; k++) 739280304Sjkim a->d[k] = 0; 740280304Sjkim a->top = i + 1; 741280304Sjkim } 74255714Skris 743280304Sjkim a->d[i] |= (((BN_ULONG)1) << j); 744280304Sjkim bn_check_top(a); 745280304Sjkim return (1); 746280304Sjkim} 74755714Skris 74855714Skrisint BN_clear_bit(BIGNUM *a, int n) 749280304Sjkim{ 750280304Sjkim int i, j; 75155714Skris 752280304Sjkim bn_check_top(a); 753280304Sjkim if (n < 0) 754280304Sjkim return 0; 755160814Ssimon 756280304Sjkim i = n / BN_BITS2; 757280304Sjkim j = n % BN_BITS2; 758280304Sjkim if (a->top <= i) 759280304Sjkim return (0); 76055714Skris 761280304Sjkim a->d[i] &= (~(((BN_ULONG)1) << j)); 762280304Sjkim bn_correct_top(a); 763280304Sjkim return (1); 764280304Sjkim} 76555714Skris 76655714Skrisint BN_is_bit_set(const BIGNUM *a, int n) 767280304Sjkim{ 768280304Sjkim int i, j; 76955714Skris 770280304Sjkim bn_check_top(a); 771280304Sjkim if (n < 0) 772280304Sjkim return 0; 773280304Sjkim i = n / BN_BITS2; 774280304Sjkim j = n % BN_BITS2; 775280304Sjkim if (a->top <= i) 776280304Sjkim return 0; 777280304Sjkim return (int)(((a->d[i]) >> j) & ((BN_ULONG)1)); 778280304Sjkim} 77955714Skris 78055714Skrisint BN_mask_bits(BIGNUM *a, int n) 781280304Sjkim{ 782280304Sjkim int b, w; 78355714Skris 784280304Sjkim bn_check_top(a); 785280304Sjkim if (n < 0) 786280304Sjkim return 0; 787160814Ssimon 788280304Sjkim w = n / BN_BITS2; 789280304Sjkim b = n % BN_BITS2; 790280304Sjkim if (w >= a->top) 791280304Sjkim return 0; 792280304Sjkim if (b == 0) 793280304Sjkim a->top = w; 794280304Sjkim else { 795280304Sjkim a->top = w + 1; 796280304Sjkim a->d[w] &= ~(BN_MASK2 << b); 797280304Sjkim } 798280304Sjkim bn_correct_top(a); 799280304Sjkim return (1); 800280304Sjkim} 80155714Skris 802160814Ssimonvoid BN_set_negative(BIGNUM *a, int b) 803280304Sjkim{ 804280304Sjkim if (b && !BN_is_zero(a)) 805280304Sjkim a->neg = 1; 806280304Sjkim else 807280304Sjkim a->neg = 0; 808280304Sjkim} 809160814Ssimon 810109998Smarkmint bn_cmp_words(const BN_ULONG *a, const BN_ULONG *b, int n) 811280304Sjkim{ 812280304Sjkim int i; 813280304Sjkim BN_ULONG aa, bb; 81455714Skris 815280304Sjkim aa = a[n - 1]; 816280304Sjkim bb = b[n - 1]; 817280304Sjkim if (aa != bb) 818280304Sjkim return ((aa > bb) ? 1 : -1); 819280304Sjkim for (i = n - 2; i >= 0; i--) { 820280304Sjkim aa = a[i]; 821280304Sjkim bb = b[i]; 822280304Sjkim if (aa != bb) 823280304Sjkim return ((aa > bb) ? 1 : -1); 824280304Sjkim } 825280304Sjkim return (0); 826280304Sjkim} 82755714Skris 828280304Sjkim/* 829280304Sjkim * Here follows a specialised variants of bn_cmp_words(). It has the 830280304Sjkim * property of performing the operation on arrays of different sizes. The 831280304Sjkim * sizes of those arrays is expressed through cl, which is the common length 832280304Sjkim * ( basicall, min(len(a),len(b)) ), and dl, which is the delta between the 833280304Sjkim * two lengths, calculated as len(a)-len(b). All lengths are the number of 834280304Sjkim * BN_ULONGs... 835280304Sjkim */ 836109998Smarkm 837280304Sjkimint bn_cmp_part_words(const BN_ULONG *a, const BN_ULONG *b, int cl, int dl) 838280304Sjkim{ 839280304Sjkim int n, i; 840280304Sjkim n = cl - 1; 841109998Smarkm 842280304Sjkim if (dl < 0) { 843280304Sjkim for (i = dl; i < 0; i++) { 844280304Sjkim if (b[n - i] != 0) 845280304Sjkim return -1; /* a < b */ 846280304Sjkim } 847280304Sjkim } 848280304Sjkim if (dl > 0) { 849280304Sjkim for (i = dl; i > 0; i--) { 850280304Sjkim if (a[n + i] != 0) 851280304Sjkim return 1; /* a > b */ 852280304Sjkim } 853280304Sjkim } 854280304Sjkim return bn_cmp_words(a, b, cl); 855280304Sjkim} 856264266Sdelphij 857280304Sjkim/* 858280304Sjkim * Constant-time conditional swap of a and b. 859264266Sdelphij * a and b are swapped if condition is not 0. The code assumes that at most one bit of condition is set. 860264266Sdelphij * nwords is the number of words to swap. The code assumes that at least nwords are allocated in both a and b, 861264266Sdelphij * and that no more than nwords are used by either a or b. 862264266Sdelphij * a and b cannot be the same number 863264266Sdelphij */ 864264266Sdelphijvoid BN_consttime_swap(BN_ULONG condition, BIGNUM *a, BIGNUM *b, int nwords) 865280304Sjkim{ 866280304Sjkim BN_ULONG t; 867280304Sjkim int i; 868264266Sdelphij 869280304Sjkim bn_wcheck_size(a, nwords); 870280304Sjkim bn_wcheck_size(b, nwords); 871264266Sdelphij 872280304Sjkim assert(a != b); 873280304Sjkim assert((condition & (condition - 1)) == 0); 874280304Sjkim assert(sizeof(BN_ULONG) >= sizeof(int)); 875264266Sdelphij 876280304Sjkim condition = ((condition - 1) >> (BN_BITS2 - 1)) - 1; 877264266Sdelphij 878280304Sjkim t = (a->top ^ b->top) & condition; 879280304Sjkim a->top ^= t; 880280304Sjkim b->top ^= t; 881264266Sdelphij 882264266Sdelphij#define BN_CONSTTIME_SWAP(ind) \ 883280304Sjkim do { \ 884280304Sjkim t = (a->d[ind] ^ b->d[ind]) & condition; \ 885280304Sjkim a->d[ind] ^= t; \ 886280304Sjkim b->d[ind] ^= t; \ 887280304Sjkim } while (0) 888264266Sdelphij 889280304Sjkim switch (nwords) { 890280304Sjkim default: 891280304Sjkim for (i = 10; i < nwords; i++) 892280304Sjkim BN_CONSTTIME_SWAP(i); 893280304Sjkim /* Fallthrough */ 894280304Sjkim case 10: 895280304Sjkim BN_CONSTTIME_SWAP(9); /* Fallthrough */ 896280304Sjkim case 9: 897280304Sjkim BN_CONSTTIME_SWAP(8); /* Fallthrough */ 898280304Sjkim case 8: 899280304Sjkim BN_CONSTTIME_SWAP(7); /* Fallthrough */ 900280304Sjkim case 7: 901280304Sjkim BN_CONSTTIME_SWAP(6); /* Fallthrough */ 902280304Sjkim case 6: 903280304Sjkim BN_CONSTTIME_SWAP(5); /* Fallthrough */ 904280304Sjkim case 5: 905280304Sjkim BN_CONSTTIME_SWAP(4); /* Fallthrough */ 906280304Sjkim case 4: 907280304Sjkim BN_CONSTTIME_SWAP(3); /* Fallthrough */ 908280304Sjkim case 3: 909280304Sjkim BN_CONSTTIME_SWAP(2); /* Fallthrough */ 910280304Sjkim case 2: 911280304Sjkim BN_CONSTTIME_SWAP(1); /* Fallthrough */ 912280304Sjkim case 1: 913280304Sjkim BN_CONSTTIME_SWAP(0); 914280304Sjkim } 915264266Sdelphij#undef BN_CONSTTIME_SWAP 916264266Sdelphij} 917