1/* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay@cryptsoft.com). 6 * The implementation was written so as to conform with Netscapes SSL. 7 * 8 * This library is free for commercial and non-commercial use as long as 9 * the following conditions are aheared to. The following conditions 10 * apply to all code found in this distribution, be it the RC4, RSA, 11 * lhash, DES, etc., code; not just the SSL code. The SSL documentation 12 * included with this distribution is covered by the same copyright terms 13 * except that the holder is Tim Hudson (tjh@cryptsoft.com). 14 * 15 * Copyright remains Eric Young's, and as such any Copyright notices in 16 * the code are not to be removed. 17 * If this package is used in a product, Eric Young should be given attribution 18 * as the author of the parts of the library used. 19 * This can be in the form of a textual message at program startup or 20 * in documentation (online or textual) provided with the package. 21 * 22 * Redistribution and use in source and binary forms, with or without 23 * modification, are permitted provided that the following conditions 24 * are met: 25 * 1. Redistributions of source code must retain the copyright 26 * notice, this list of conditions and the following disclaimer. 27 * 2. Redistributions in binary form must reproduce the above copyright 28 * notice, this list of conditions and the following disclaimer in the 29 * documentation and/or other materials provided with the distribution. 30 * 3. All advertising materials mentioning features or use of this software 31 * must display the following acknowledgement: 32 * "This product includes cryptographic software written by 33 * Eric Young (eay@cryptsoft.com)" 34 * The word 'cryptographic' can be left out if the rouines from the library 35 * being used are not cryptographic related :-). 36 * 4. If you include any Windows specific code (or a derivative thereof) from 37 * the apps directory (application code) you must include an acknowledgement: 38 * "This product includes software written by Tim Hudson (tjh@cryptsoft.com)" 39 * 40 * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND 41 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 42 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 43 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 44 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 45 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 46 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 47 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 48 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 49 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 50 * SUCH DAMAGE. 51 * 52 * The licence and distribution terms for any publically available version or 53 * derivative of this code cannot be changed. i.e. this code cannot simply be 54 * copied and put under another distribution licence 55 * [including the GNU Public Licence.] */ 56 57#include <openssl/bn.h> 58 59#include <limits.h> 60#include <openssl/err.h> 61#include <openssl/mem.h> 62 63#include "internal.h" 64 65 66BIGNUM *BN_new(void) { 67 BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM)); 68 69 if (bn == NULL) { 70 OPENSSL_PUT_ERROR(BN, BN_new, ERR_R_MALLOC_FAILURE); 71 return NULL; 72 } 73 74 memset(bn, 0, sizeof(BIGNUM)); 75 bn->flags = BN_FLG_MALLOCED; 76 77 return bn; 78} 79 80void BN_init(BIGNUM *bn) { 81 memset(bn, 0, sizeof(BIGNUM)); 82} 83 84void BN_free(BIGNUM *bn) { 85 if (bn == NULL) { 86 return; 87 } 88 89 if (bn->d != NULL && (bn->flags & BN_FLG_STATIC_DATA) == 0) { 90 OPENSSL_free(bn->d); 91 } 92 93 if (bn->flags & BN_FLG_MALLOCED) { 94 OPENSSL_free(bn); 95 } else { 96 bn->d = NULL; 97 } 98} 99 100void BN_clear_free(BIGNUM *bn) { 101 char should_free; 102 103 if (bn == NULL) { 104 return; 105 } 106 107 if (bn->d != NULL) { 108 OPENSSL_cleanse(bn->d, bn->dmax * sizeof(bn->d[0])); 109 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { 110 OPENSSL_free(bn->d); 111 } 112 } 113 114 should_free = (bn->flags & BN_FLG_MALLOCED) != 0; 115 OPENSSL_cleanse(bn, sizeof(BIGNUM)); 116 if (should_free) { 117 OPENSSL_free(bn); 118 } 119} 120 121BIGNUM *BN_dup(const BIGNUM *src) { 122 BIGNUM *copy; 123 124 if (src == NULL) { 125 return NULL; 126 } 127 128 copy = BN_new(); 129 if (copy == NULL) { 130 return NULL; 131 } 132 133 if (!BN_copy(copy, src)) { 134 BN_free(copy); 135 return NULL; 136 } 137 138 return copy; 139} 140 141BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) { 142 if (src == dest) { 143 return dest; 144 } 145 146 if (bn_wexpand(dest, src->top) == NULL) { 147 return NULL; 148 } 149 150 memcpy(dest->d, src->d, sizeof(src->d[0]) * src->top); 151 152 dest->top = src->top; 153 dest->neg = src->neg; 154 return dest; 155} 156 157void BN_clear(BIGNUM *bn) { 158 if (bn->d != NULL) { 159 memset(bn->d, 0, bn->dmax * sizeof(bn->d[0])); 160 } 161 162 bn->top = 0; 163 bn->neg = 0; 164} 165 166const BIGNUM *BN_value_one(void) { 167 static const BN_ULONG data_one = 1; 168 static const BIGNUM const_one = {(BN_ULONG *)&data_one, 1, 1, 0, 169 BN_FLG_STATIC_DATA}; 170 171 return &const_one; 172} 173 174void BN_with_flags(BIGNUM *out, const BIGNUM *in, int flags) { 175 memcpy(out, in, sizeof(BIGNUM)); 176 out->flags &= ~BN_FLG_MALLOCED; 177 out->flags |= BN_FLG_STATIC_DATA | flags; 178} 179 180/* BN_num_bits_word returns the minimum number of bits needed to represent the 181 * value in |l|. */ 182unsigned BN_num_bits_word(BN_ULONG l) { 183 static const unsigned char bits[256] = { 184 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 185 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 186 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 187 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 188 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 189 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 190 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 191 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 192 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 193 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 194 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8}; 195 196#if defined(OPENSSL_64_BIT) 197 if (l & 0xffffffff00000000L) { 198 if (l & 0xffff000000000000L) { 199 if (l & 0xff00000000000000L) { 200 return (bits[(int)(l >> 56)] + 56); 201 } else 202 return (bits[(int)(l >> 48)] + 48); 203 } else { 204 if (l & 0x0000ff0000000000L) { 205 return (bits[(int)(l >> 40)] + 40); 206 } else 207 return (bits[(int)(l >> 32)] + 32); 208 } 209 } else 210#endif 211 { 212 if (l & 0xffff0000L) { 213 if (l & 0xff000000L) { 214 return (bits[(int)(l >> 24L)] + 24); 215 } else { 216 return (bits[(int)(l >> 16L)] + 16); 217 } 218 } else { 219 if (l & 0xff00L) { 220 return (bits[(int)(l >> 8)] + 8); 221 } else { 222 return (bits[(int)(l)]); 223 } 224 } 225 } 226} 227 228unsigned BN_num_bits(const BIGNUM *bn) { 229 const int max = bn->top - 1; 230 231 if (BN_is_zero(bn)) { 232 return 0; 233 } 234 235 return max*BN_BITS2 + BN_num_bits_word(bn->d[max]); 236} 237 238unsigned BN_num_bytes(const BIGNUM *bn) { 239 return (BN_num_bits(bn) + 7) / 8; 240} 241 242void BN_zero(BIGNUM *bn) { 243 bn->top = bn->neg = 0; 244} 245 246int BN_one(BIGNUM *bn) { 247 return BN_set_word(bn, 1); 248} 249 250int BN_set_word(BIGNUM *bn, BN_ULONG value) { 251 if (value == 0) { 252 BN_zero(bn); 253 return 1; 254 } 255 256 if (bn_wexpand(bn, 1) == NULL) { 257 return 0; 258 } 259 260 bn->neg = 0; 261 bn->d[0] = value; 262 bn->top = 1; 263 return 1; 264} 265 266int BN_is_negative(const BIGNUM *bn) { 267 return bn->neg != 0; 268} 269 270void BN_set_negative(BIGNUM *bn, int sign) { 271 if (sign && !BN_is_zero(bn)) { 272 bn->neg = 1; 273 } else { 274 bn->neg = 0; 275 } 276} 277 278BIGNUM *bn_wexpand(BIGNUM *bn, unsigned words) { 279 BN_ULONG *a; 280 281 if (words <= (unsigned) bn->dmax) { 282 return bn; 283 } 284 285 if (words > (INT_MAX / (4 * BN_BITS2))) { 286 OPENSSL_PUT_ERROR(BN, bn_wexpand, BN_R_BIGNUM_TOO_LONG); 287 return NULL; 288 } 289 290 if (bn->flags & BN_FLG_STATIC_DATA) { 291 OPENSSL_PUT_ERROR(BN, bn_wexpand, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 292 return NULL; 293 } 294 295 a = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); 296 if (a == NULL) { 297 OPENSSL_PUT_ERROR(BN, bn_wexpand, ERR_R_MALLOC_FAILURE); 298 return NULL; 299 } 300 301 memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top); 302 303 if (bn->d) { 304 OPENSSL_free(bn->d); 305 } 306 bn->d = a; 307 bn->dmax = words; 308 309 return bn; 310} 311 312BIGNUM *bn_expand(BIGNUM *bn, unsigned bits) { 313 return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2); 314} 315 316void bn_correct_top(BIGNUM *bn) { 317 BN_ULONG *ftl; 318 int tmp_top = bn->top; 319 320 if (tmp_top > 0) { 321 for (ftl = &(bn->d[tmp_top - 1]); tmp_top > 0; tmp_top--) { 322 if (*(ftl--)) { 323 break; 324 } 325 } 326 bn->top = tmp_top; 327 } 328} 329 330int BN_get_flags(const BIGNUM *bn, int flags) { 331 return bn->flags & flags; 332} 333 334void BN_set_flags(BIGNUM *bn, int flags) { 335 bn->flags |= flags; 336} 337