1 /* Copyright (C) 1995-1998 Eric Young (eay (at) cryptsoft.com) 2 * All rights reserved. 3 * 4 * This package is an SSL implementation written 5 * by Eric Young (eay (at) 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 (at) 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 (at) 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 (at) 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 <string.h> 61 62 #include <openssl/err.h> 63 #include <openssl/mem.h> 64 65 #include "internal.h" 66 67 68 BIGNUM *BN_new(void) { 69 BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM)); 70 71 if (bn == NULL) { 72 OPENSSL_PUT_ERROR(BN, BN_new, ERR_R_MALLOC_FAILURE); 73 return NULL; 74 } 75 76 memset(bn, 0, sizeof(BIGNUM)); 77 bn->flags = BN_FLG_MALLOCED; 78 79 return bn; 80 } 81 82 void BN_init(BIGNUM *bn) { 83 memset(bn, 0, sizeof(BIGNUM)); 84 } 85 86 void BN_free(BIGNUM *bn) { 87 if (bn == NULL) { 88 return; 89 } 90 91 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { 92 OPENSSL_free(bn->d); 93 } 94 95 if (bn->flags & BN_FLG_MALLOCED) { 96 OPENSSL_free(bn); 97 } else { 98 bn->d = NULL; 99 } 100 } 101 102 void BN_clear_free(BIGNUM *bn) { 103 char should_free; 104 105 if (bn == NULL) { 106 return; 107 } 108 109 if (bn->d != NULL) { 110 OPENSSL_cleanse(bn->d, bn->dmax * sizeof(bn->d[0])); 111 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { 112 OPENSSL_free(bn->d); 113 } 114 } 115 116 should_free = (bn->flags & BN_FLG_MALLOCED) != 0; 117 OPENSSL_cleanse(bn, sizeof(BIGNUM)); 118 if (should_free) { 119 OPENSSL_free(bn); 120 } 121 } 122 123 BIGNUM *BN_dup(const BIGNUM *src) { 124 BIGNUM *copy; 125 126 if (src == NULL) { 127 return NULL; 128 } 129 130 copy = BN_new(); 131 if (copy == NULL) { 132 return NULL; 133 } 134 135 if (!BN_copy(copy, src)) { 136 BN_free(copy); 137 return NULL; 138 } 139 140 return copy; 141 } 142 143 BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) { 144 if (src == dest) { 145 return dest; 146 } 147 148 if (bn_wexpand(dest, src->top) == NULL) { 149 return NULL; 150 } 151 152 memcpy(dest->d, src->d, sizeof(src->d[0]) * src->top); 153 154 dest->top = src->top; 155 dest->neg = src->neg; 156 return dest; 157 } 158 159 void BN_clear(BIGNUM *bn) { 160 if (bn->d != NULL) { 161 memset(bn->d, 0, bn->dmax * sizeof(bn->d[0])); 162 } 163 164 bn->top = 0; 165 bn->neg = 0; 166 } 167 168 const BIGNUM *BN_value_one(void) { 169 static const BN_ULONG data_one = 1; 170 static const BIGNUM const_one = {(BN_ULONG *)&data_one, 1, 1, 0, 171 BN_FLG_STATIC_DATA}; 172 173 return &const_one; 174 } 175 176 void BN_with_flags(BIGNUM *out, const BIGNUM *in, int flags) { 177 memcpy(out, in, sizeof(BIGNUM)); 178 out->flags &= ~BN_FLG_MALLOCED; 179 out->flags |= BN_FLG_STATIC_DATA | flags; 180 } 181 182 /* BN_num_bits_word returns the minimum number of bits needed to represent the 183 * value in |l|. */ 184 unsigned BN_num_bits_word(BN_ULONG l) { 185 static const unsigned char bits[256] = { 186 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 187 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 188 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 189 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 190 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 191 7, 7, 7, 7, 7, 7, 7, 7, 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, 8, 8, 8, 8, 8, 8, 8, 8, 195 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 196 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8}; 197 198 #if defined(OPENSSL_64_BIT) 199 if (l & 0xffffffff00000000L) { 200 if (l & 0xffff000000000000L) { 201 if (l & 0xff00000000000000L) { 202 return (bits[(int)(l >> 56)] + 56); 203 } else { 204 return (bits[(int)(l >> 48)] + 48); 205 } 206 } else { 207 if (l & 0x0000ff0000000000L) { 208 return (bits[(int)(l >> 40)] + 40); 209 } else { 210 return (bits[(int)(l >> 32)] + 32); 211 } 212 } 213 } else 214 #endif 215 { 216 if (l & 0xffff0000L) { 217 if (l & 0xff000000L) { 218 return (bits[(int)(l >> 24L)] + 24); 219 } else { 220 return (bits[(int)(l >> 16L)] + 16); 221 } 222 } else { 223 if (l & 0xff00L) { 224 return (bits[(int)(l >> 8)] + 8); 225 } else { 226 return (bits[(int)(l)]); 227 } 228 } 229 } 230 } 231 232 unsigned BN_num_bits(const BIGNUM *bn) { 233 const int max = bn->top - 1; 234 235 if (BN_is_zero(bn)) { 236 return 0; 237 } 238 239 return max*BN_BITS2 + BN_num_bits_word(bn->d[max]); 240 } 241 242 unsigned BN_num_bytes(const BIGNUM *bn) { 243 return (BN_num_bits(bn) + 7) / 8; 244 } 245 246 void BN_zero(BIGNUM *bn) { 247 bn->top = bn->neg = 0; 248 } 249 250 int BN_one(BIGNUM *bn) { 251 return BN_set_word(bn, 1); 252 } 253 254 int BN_set_word(BIGNUM *bn, BN_ULONG value) { 255 if (value == 0) { 256 BN_zero(bn); 257 return 1; 258 } 259 260 if (bn_wexpand(bn, 1) == NULL) { 261 return 0; 262 } 263 264 bn->neg = 0; 265 bn->d[0] = value; 266 bn->top = 1; 267 return 1; 268 } 269 270 int BN_is_negative(const BIGNUM *bn) { 271 return bn->neg != 0; 272 } 273 274 void BN_set_negative(BIGNUM *bn, int sign) { 275 if (sign && !BN_is_zero(bn)) { 276 bn->neg = 1; 277 } else { 278 bn->neg = 0; 279 } 280 } 281 282 BIGNUM *bn_wexpand(BIGNUM *bn, unsigned words) { 283 BN_ULONG *a; 284 285 if (words <= (unsigned) bn->dmax) { 286 return bn; 287 } 288 289 if (words > (INT_MAX / (4 * BN_BITS2))) { 290 OPENSSL_PUT_ERROR(BN, bn_wexpand, BN_R_BIGNUM_TOO_LONG); 291 return NULL; 292 } 293 294 if (bn->flags & BN_FLG_STATIC_DATA) { 295 OPENSSL_PUT_ERROR(BN, bn_wexpand, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 296 return NULL; 297 } 298 299 a = (BN_ULONG *)OPENSSL_malloc(sizeof(BN_ULONG) * words); 300 if (a == NULL) { 301 OPENSSL_PUT_ERROR(BN, bn_wexpand, ERR_R_MALLOC_FAILURE); 302 return NULL; 303 } 304 305 memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top); 306 307 OPENSSL_free(bn->d); 308 bn->d = a; 309 bn->dmax = words; 310 311 return bn; 312 } 313 314 BIGNUM *bn_expand(BIGNUM *bn, unsigned bits) { 315 return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2); 316 } 317 318 void bn_correct_top(BIGNUM *bn) { 319 BN_ULONG *ftl; 320 int tmp_top = bn->top; 321 322 if (tmp_top > 0) { 323 for (ftl = &(bn->d[tmp_top - 1]); tmp_top > 0; tmp_top--) { 324 if (*(ftl--)) { 325 break; 326 } 327 } 328 bn->top = tmp_top; 329 } 330 } 331 332 int BN_get_flags(const BIGNUM *bn, int flags) { 333 return bn->flags & flags; 334 } 335 336 void BN_set_flags(BIGNUM *bn, int flags) { 337 bn->flags |= flags; 338 } 339