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 #include "../delocate.h" 67 68 69 BIGNUM *BN_new(void) { 70 BIGNUM *bn = OPENSSL_malloc(sizeof(BIGNUM)); 71 72 if (bn == NULL) { 73 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 74 return NULL; 75 } 76 77 OPENSSL_memset(bn, 0, sizeof(BIGNUM)); 78 bn->flags = BN_FLG_MALLOCED; 79 80 return bn; 81 } 82 83 void BN_init(BIGNUM *bn) { 84 OPENSSL_memset(bn, 0, sizeof(BIGNUM)); 85 } 86 87 void BN_free(BIGNUM *bn) { 88 if (bn == NULL) { 89 return; 90 } 91 92 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { 93 OPENSSL_free(bn->d); 94 } 95 96 if (bn->flags & BN_FLG_MALLOCED) { 97 OPENSSL_free(bn); 98 } else { 99 bn->d = NULL; 100 } 101 } 102 103 void BN_clear_free(BIGNUM *bn) { 104 char should_free; 105 106 if (bn == NULL) { 107 return; 108 } 109 110 if (bn->d != NULL) { 111 OPENSSL_cleanse(bn->d, bn->dmax * sizeof(bn->d[0])); 112 if ((bn->flags & BN_FLG_STATIC_DATA) == 0) { 113 OPENSSL_free(bn->d); 114 } 115 } 116 117 should_free = (bn->flags & BN_FLG_MALLOCED) != 0; 118 OPENSSL_cleanse(bn, sizeof(BIGNUM)); 119 if (should_free) { 120 OPENSSL_free(bn); 121 } 122 } 123 124 BIGNUM *BN_dup(const BIGNUM *src) { 125 BIGNUM *copy; 126 127 if (src == NULL) { 128 return NULL; 129 } 130 131 copy = BN_new(); 132 if (copy == NULL) { 133 return NULL; 134 } 135 136 if (!BN_copy(copy, src)) { 137 BN_free(copy); 138 return NULL; 139 } 140 141 return copy; 142 } 143 144 BIGNUM *BN_copy(BIGNUM *dest, const BIGNUM *src) { 145 if (src == dest) { 146 return dest; 147 } 148 149 if (!bn_wexpand(dest, src->top)) { 150 return NULL; 151 } 152 153 OPENSSL_memcpy(dest->d, src->d, sizeof(src->d[0]) * src->top); 154 155 dest->top = src->top; 156 dest->neg = src->neg; 157 return dest; 158 } 159 160 void BN_clear(BIGNUM *bn) { 161 if (bn->d != NULL) { 162 OPENSSL_memset(bn->d, 0, bn->dmax * sizeof(bn->d[0])); 163 } 164 165 bn->top = 0; 166 bn->neg = 0; 167 } 168 169 DEFINE_METHOD_FUNCTION(BIGNUM, BN_value_one) { 170 static const BN_ULONG kOneLimbs[1] = { 1 }; 171 out->d = (BN_ULONG*) kOneLimbs; 172 out->top = 1; 173 out->dmax = 1; 174 out->neg = 0; 175 out->flags = BN_FLG_STATIC_DATA; 176 } 177 178 /* BN_num_bits_word returns the minimum number of bits needed to represent the 179 * value in |l|. */ 180 unsigned BN_num_bits_word(BN_ULONG l) { 181 static const unsigned char bits[256] = { 182 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 183 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 184 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 185 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 186 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 187 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 188 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 189 8, 8, 8, 8, 8, 8, 8, 8, 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}; 193 194 #if defined(OPENSSL_64_BIT) 195 if (l & 0xffffffff00000000L) { 196 if (l & 0xffff000000000000L) { 197 if (l & 0xff00000000000000L) { 198 return (bits[(int)(l >> 56)] + 56); 199 } else { 200 return (bits[(int)(l >> 48)] + 48); 201 } 202 } else { 203 if (l & 0x0000ff0000000000L) { 204 return (bits[(int)(l >> 40)] + 40); 205 } else { 206 return (bits[(int)(l >> 32)] + 32); 207 } 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 228 unsigned 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 238 unsigned BN_num_bytes(const BIGNUM *bn) { 239 return (BN_num_bits(bn) + 7) / 8; 240 } 241 242 void BN_zero(BIGNUM *bn) { 243 bn->top = bn->neg = 0; 244 } 245 246 int BN_one(BIGNUM *bn) { 247 return BN_set_word(bn, 1); 248 } 249 250 int 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)) { 257 return 0; 258 } 259 260 bn->neg = 0; 261 bn->d[0] = value; 262 bn->top = 1; 263 return 1; 264 } 265 266 int BN_set_u64(BIGNUM *bn, uint64_t value) { 267 #if BN_BITS2 == 64 268 return BN_set_word(bn, value); 269 #elif BN_BITS2 == 32 270 if (value <= BN_MASK2) { 271 return BN_set_word(bn, (BN_ULONG)value); 272 } 273 274 if (!bn_wexpand(bn, 2)) { 275 return 0; 276 } 277 278 bn->neg = 0; 279 bn->d[0] = (BN_ULONG)value; 280 bn->d[1] = (BN_ULONG)(value >> 32); 281 bn->top = 2; 282 return 1; 283 #else 284 #error "BN_BITS2 must be 32 or 64." 285 #endif 286 } 287 288 int bn_set_words(BIGNUM *bn, const BN_ULONG *words, size_t num) { 289 if (!bn_wexpand(bn, num)) { 290 return 0; 291 } 292 OPENSSL_memmove(bn->d, words, num * sizeof(BN_ULONG)); 293 /* |bn_wexpand| verified that |num| isn't too large. */ 294 bn->top = (int)num; 295 bn_correct_top(bn); 296 bn->neg = 0; 297 return 1; 298 } 299 300 int BN_is_negative(const BIGNUM *bn) { 301 return bn->neg != 0; 302 } 303 304 void BN_set_negative(BIGNUM *bn, int sign) { 305 if (sign && !BN_is_zero(bn)) { 306 bn->neg = 1; 307 } else { 308 bn->neg = 0; 309 } 310 } 311 312 int bn_wexpand(BIGNUM *bn, size_t words) { 313 BN_ULONG *a; 314 315 if (words <= (size_t)bn->dmax) { 316 return 1; 317 } 318 319 if (words > (INT_MAX / (4 * BN_BITS2))) { 320 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); 321 return 0; 322 } 323 324 if (bn->flags & BN_FLG_STATIC_DATA) { 325 OPENSSL_PUT_ERROR(BN, BN_R_EXPAND_ON_STATIC_BIGNUM_DATA); 326 return 0; 327 } 328 329 a = OPENSSL_malloc(sizeof(BN_ULONG) * words); 330 if (a == NULL) { 331 OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE); 332 return 0; 333 } 334 335 OPENSSL_memcpy(a, bn->d, sizeof(BN_ULONG) * bn->top); 336 337 OPENSSL_free(bn->d); 338 bn->d = a; 339 bn->dmax = (int)words; 340 341 return 1; 342 } 343 344 int bn_expand(BIGNUM *bn, size_t bits) { 345 if (bits + BN_BITS2 - 1 < bits) { 346 OPENSSL_PUT_ERROR(BN, BN_R_BIGNUM_TOO_LONG); 347 return 0; 348 } 349 return bn_wexpand(bn, (bits+BN_BITS2-1)/BN_BITS2); 350 } 351 352 void bn_correct_top(BIGNUM *bn) { 353 BN_ULONG *ftl; 354 int tmp_top = bn->top; 355 356 if (tmp_top > 0) { 357 for (ftl = &(bn->d[tmp_top - 1]); tmp_top > 0; tmp_top--) { 358 if (*(ftl--)) { 359 break; 360 } 361 } 362 bn->top = tmp_top; 363 } 364 365 if (bn->top == 0) { 366 bn->neg = 0; 367 } 368 } 369