Home | History | Annotate | Download | only in bn
      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 /* ====================================================================
     58  * Copyright (c) 1998-2001 The OpenSSL Project.  All rights reserved.
     59  *
     60  * Redistribution and use in source and binary forms, with or without
     61  * modification, are permitted provided that the following conditions
     62  * are met:
     63  *
     64  * 1. Redistributions of source code must retain the above copyright
     65  *    notice, this list of conditions and the following disclaimer.
     66  *
     67  * 2. Redistributions in binary form must reproduce the above copyright
     68  *    notice, this list of conditions and the following disclaimer in
     69  *    the documentation and/or other materials provided with the
     70  *    distribution.
     71  *
     72  * 3. All advertising materials mentioning features or use of this
     73  *    software must display the following acknowledgment:
     74  *    "This product includes software developed by the OpenSSL Project
     75  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
     76  *
     77  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
     78  *    endorse or promote products derived from this software without
     79  *    prior written permission. For written permission, please contact
     80  *    openssl-core (at) openssl.org.
     81  *
     82  * 5. Products derived from this software may not be called "OpenSSL"
     83  *    nor may "OpenSSL" appear in their names without prior written
     84  *    permission of the OpenSSL Project.
     85  *
     86  * 6. Redistributions of any form whatsoever must retain the following
     87  *    acknowledgment:
     88  *    "This product includes software developed by the OpenSSL Project
     89  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
     90  *
     91  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
     92  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
     93  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
     94  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
     95  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     96  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     97  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
     98  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
     99  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
    100  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    101  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
    102  * OF THE POSSIBILITY OF SUCH DAMAGE.
    103  * ====================================================================
    104  *
    105  * This product includes cryptographic software written by Eric Young
    106  * (eay (at) cryptsoft.com).  This product includes software written by Tim
    107  * Hudson (tjh (at) cryptsoft.com). */
    108 
    109 #include <openssl/bn.h>
    110 
    111 #include <string.h>
    112 
    113 #include <openssl/err.h>
    114 #include <openssl/mem.h>
    115 #include <openssl/rand.h>
    116 #include <openssl/sha.h>
    117 
    118 int BN_rand(BIGNUM *rnd, int bits, int top, int bottom) {
    119   uint8_t *buf = NULL;
    120   int ret = 0, bit, bytes, mask;
    121 
    122   if (rnd == NULL) {
    123     return 0;
    124   }
    125 
    126   if (bits == 0) {
    127     BN_zero(rnd);
    128     return 1;
    129   }
    130 
    131   bytes = (bits + 7) / 8;
    132   bit = (bits - 1) % 8;
    133   mask = 0xff << (bit + 1);
    134 
    135   buf = OPENSSL_malloc(bytes);
    136   if (buf == NULL) {
    137     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
    138     goto err;
    139   }
    140 
    141   /* Make a random number and set the top and bottom bits. */
    142   if (!RAND_bytes(buf, bytes)) {
    143     goto err;
    144   }
    145 
    146   if (top != -1) {
    147     if (top && bits > 1) {
    148       if (bit == 0) {
    149         buf[0] = 1;
    150         buf[1] |= 0x80;
    151       } else {
    152         buf[0] |= (3 << (bit - 1));
    153       }
    154     } else {
    155       buf[0] |= (1 << bit);
    156     }
    157   }
    158 
    159   buf[0] &= ~mask;
    160 
    161   /* set bottom bit if requested */
    162   if (bottom)  {
    163     buf[bytes - 1] |= 1;
    164   }
    165 
    166   if (!BN_bin2bn(buf, bytes, rnd)) {
    167     goto err;
    168   }
    169 
    170   ret = 1;
    171 
    172 err:
    173   if (buf != NULL) {
    174     OPENSSL_cleanse(buf, bytes);
    175     OPENSSL_free(buf);
    176   }
    177   return (ret);
    178 }
    179 
    180 int BN_pseudo_rand(BIGNUM *rnd, int bits, int top, int bottom) {
    181   return BN_rand(rnd, bits, top, bottom);
    182 }
    183 
    184 int BN_rand_range(BIGNUM *r, const BIGNUM *range) {
    185   unsigned n;
    186   unsigned count = 100;
    187 
    188   if (range->neg || BN_is_zero(range)) {
    189     OPENSSL_PUT_ERROR(BN, BN_R_INVALID_RANGE);
    190     return 0;
    191   }
    192 
    193   n = BN_num_bits(range); /* n > 0 */
    194 
    195   /* BN_is_bit_set(range, n - 1) always holds */
    196   if (n == 1) {
    197     BN_zero(r);
    198   } else if (!BN_is_bit_set(range, n - 2) && !BN_is_bit_set(range, n - 3)) {
    199     /* range = 100..._2,
    200      * so  3*range (= 11..._2)  is exactly one bit longer than  range */
    201     do {
    202       if (!BN_rand(r, n + 1, -1 /* don't set most significant bits */,
    203                    0 /* don't set least significant bits */)) {
    204         return 0;
    205       }
    206 
    207       /* If r < 3*range, use r := r MOD range (which is either r, r - range, or
    208        * r - 2*range). Otherwise, iterate again. Since 3*range = 11..._2, each
    209        * iteration succeeds with probability >= .75. */
    210       if (BN_cmp(r, range) >= 0) {
    211         if (!BN_sub(r, r, range)) {
    212           return 0;
    213         }
    214         if (BN_cmp(r, range) >= 0) {
    215           if (!BN_sub(r, r, range)) {
    216             return 0;
    217           }
    218         }
    219       }
    220 
    221       if (!--count) {
    222         OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS);
    223         return 0;
    224       }
    225     } while (BN_cmp(r, range) >= 0);
    226   } else {
    227     do {
    228       /* range = 11..._2  or  range = 101..._2 */
    229       if (!BN_rand(r, n, -1, 0)) {
    230         return 0;
    231       }
    232 
    233       if (!--count) {
    234         OPENSSL_PUT_ERROR(BN, BN_R_TOO_MANY_ITERATIONS);
    235         return 0;
    236       }
    237     } while (BN_cmp(r, range) >= 0);
    238   }
    239 
    240   return 1;
    241 }
    242 
    243 int BN_pseudo_rand_range(BIGNUM *r, const BIGNUM *range) {
    244   return BN_rand_range(r, range);
    245 }
    246 
    247 int BN_generate_dsa_nonce(BIGNUM *out, const BIGNUM *range, const BIGNUM *priv,
    248                           const uint8_t *message, size_t message_len,
    249                           BN_CTX *ctx) {
    250   SHA512_CTX sha;
    251   /* We use 512 bits of random data per iteration to
    252    * ensure that we have at least |range| bits of randomness. */
    253   uint8_t random_bytes[64];
    254   uint8_t digest[SHA512_DIGEST_LENGTH];
    255   size_t done, todo, attempt;
    256   const unsigned num_k_bytes = BN_num_bytes(range);
    257   const unsigned bits_to_mask = (8 - (BN_num_bits(range) % 8)) % 8;
    258   uint8_t private_bytes[96];
    259   uint8_t *k_bytes = NULL;
    260   int ret = 0;
    261 
    262   if (out == NULL) {
    263     return 0;
    264   }
    265 
    266   if (BN_is_zero(range)) {
    267     OPENSSL_PUT_ERROR(BN, BN_R_DIV_BY_ZERO);
    268     goto err;
    269   }
    270 
    271   k_bytes = OPENSSL_malloc(num_k_bytes);
    272   if (!k_bytes) {
    273     OPENSSL_PUT_ERROR(BN, ERR_R_MALLOC_FAILURE);
    274     goto err;
    275   }
    276 
    277   /* We copy |priv| into a local buffer to avoid furthur exposing its
    278    * length. */
    279   todo = sizeof(priv->d[0]) * priv->top;
    280   if (todo > sizeof(private_bytes)) {
    281     /* No reasonable DSA or ECDSA key should have a private key
    282      * this large and we don't handle this case in order to avoid
    283      * leaking the length of the private key. */
    284     OPENSSL_PUT_ERROR(BN, BN_R_PRIVATE_KEY_TOO_LARGE);
    285     goto err;
    286   }
    287   memcpy(private_bytes, priv->d, todo);
    288   memset(private_bytes + todo, 0, sizeof(private_bytes) - todo);
    289 
    290   for (attempt = 0;; attempt++) {
    291     for (done = 0; done < num_k_bytes;) {
    292       if (!RAND_bytes(random_bytes, sizeof(random_bytes))) {
    293         goto err;
    294       }
    295       SHA512_Init(&sha);
    296       SHA512_Update(&sha, &attempt, sizeof(attempt));
    297       SHA512_Update(&sha, &done, sizeof(done));
    298       SHA512_Update(&sha, private_bytes, sizeof(private_bytes));
    299       SHA512_Update(&sha, message, message_len);
    300       SHA512_Update(&sha, random_bytes, sizeof(random_bytes));
    301       SHA512_Final(digest, &sha);
    302 
    303       todo = num_k_bytes - done;
    304       if (todo > SHA512_DIGEST_LENGTH) {
    305         todo = SHA512_DIGEST_LENGTH;
    306       }
    307       memcpy(k_bytes + done, digest, todo);
    308       done += todo;
    309     }
    310 
    311     k_bytes[0] &= 0xff >> bits_to_mask;
    312 
    313     if (!BN_bin2bn(k_bytes, num_k_bytes, out)) {
    314       goto err;
    315     }
    316     if (BN_cmp(out, range) < 0) {
    317       break;
    318     }
    319   }
    320 
    321   ret = 1;
    322 
    323 err:
    324   OPENSSL_free(k_bytes);
    325   return ret;
    326 }
    327