Prepare for bn opaquify. Implement internal helper functions.

Reviewed-by: Tim Hudson <tjh@openssl.org>

1 files changed, 248 insertions, 0 deletions

diff --git a/crypto/bn/bn_intern.c b/crypto/bn/bn_intern.c
new file mode 100644
index 0000000000..a0cfcff303
--- /dev/null
+++ b/crypto/bn/bn_intern.c
@@ -0,0 +1,248 @@
+/* ====================================================================
+ * Copyright (c) 1998-2014 The OpenSSL Project.  All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ *
+ * 3. All advertising materials mentioning features or use of this
+ *    software must display the following acknowledgment:
+ *    "This product includes software developed by the OpenSSL Project
+ *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
+ *
+ * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
+ *    endorse or promote products derived from this software without
+ *    prior written permission. For written permission, please contact
+ *    openssl-core@openssl.org.
+ *
+ * 5. Products derived from this software may not be called "OpenSSL"
+ *    nor may "OpenSSL" appear in their names without prior written
+ *    permission of the OpenSSL Project.
+ *
+ * 6. Redistributions of any form whatsoever must retain the following
+ *    acknowledgment:
+ *    "This product includes software developed by the OpenSSL Project
+ *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
+ * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
+ * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
+ * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE.
+ * ====================================================================
+ *
+ * This product includes cryptographic software written by Eric Young
+ * (eay@cryptsoft.com).  This product includes software written by Tim
+ * Hudson (tjh@cryptsoft.com).
+ *
+ */
+
+#include "cryptlib.h"
+#include "bn_lcl.h"
+
+/*
+ * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
+ * This is an array  r[]  of values that are either zero or odd with an
+ * absolute value less than  2^w  satisfying
+ *     scalar = \sum_j r[j]*2^j
+ * where at most one of any  w+1  consecutive digits is non-zero
+ * with the exception that the most significant digit may be only
+ * w-1 zeros away from that next non-zero digit.
+ */
+signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
+{
+    int window_val;
+    int ok = 0;
+    signed char *r = NULL;
+    int sign = 1;
+    int bit, next_bit, mask;
+    size_t len = 0, j;
+
+    if (BN_is_zero(scalar)) {
+        r = OPENSSL_malloc(1);
+        if (!r) {
+            BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
+            goto err;
+        }
+        r[0] = 0;
+        *ret_len = 1;
+        return r;
+    }
+
+    if (w <= 0 || w > 7) { /* 'signed char' can represent integers with absolute values less than 2^7 */
+        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
+        goto err;
+    }
+    bit = 1 << w; /* at most 128 */
+    next_bit = bit << 1; /* at most 256 */
+    mask = next_bit - 1; /* at most 255 */
+
+    if (BN_is_negative(scalar)) {
+        sign = -1;
+    }
+
+    if (scalar->d == NULL || scalar->top == 0) {
+        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
+        goto err;
+    }
+
+    len = BN_num_bits(scalar);
+    r = OPENSSL_malloc(len + 1); /*
+                                  * Modified wNAF may be one digit longer than binary representation
+                                  * (*ret_len will be set to the actual length, i.e. at most
+                                  * BN_num_bits(scalar) + 1)
+                                  */
+    if (r == NULL) {
+        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
+        goto err;
+    }
+    window_val = scalar->d[0] & mask;
+    j = 0;
+    while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len, window_val will not increase */
+        int digit = 0;
+
+        /* 0 <= window_val <= 2^(w+1) */
+
+        if (window_val & 1) {
+            /* 0 < window_val < 2^(w+1) */
+
+            if (window_val & bit) {
+                digit = window_val - next_bit; /* -2^w < digit < 0 */
+
+#if 1 /* modified wNAF */
+                if (j + w + 1 >= len) {
+                    /*
+                     * Special case for generating modified wNAFs:
+                     * no new bits will be added into window_val,
+                     * so using a positive digit here will decrease
+                     * the total length of the representation
+                     */
+
+                    digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
+                }
+#endif
+            } else {
+                digit = window_val; /* 0 < digit < 2^w */
+            }
+
+            if (digit <= -bit || digit >= bit || !(digit & 1)) {
+                BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
+                goto err;
+            }
+
+            window_val -= digit;
+
+            /* now window_val is 0 or 2^(w+1) in standard wNAF generation;
+             * for modified window NAFs, it may also be 2^w
+             */
+            if (window_val != 0 && window_val != next_bit && window_val != bit) {
+                BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
+                goto err;
+            }
+        }
+
+        r[j++] = sign * digit;
+
+        window_val >>= 1;
+        window_val += bit * BN_is_bit_set(scalar, j + w);
+
+        if (window_val > next_bit) {
+            BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
+            goto err;
+        }
+    }
+
+    if (j > len + 1) {
+        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
+        goto err;
+    }
+    len = j;
+    ok = 1;
+
+ err:
+    if (!ok) {
+        OPENSSL_free(r);
+        r = NULL;
+    }
+    if (ok)
+        *ret_len = len;
+    return r;
+}
+
+int bn_get_top(const BIGNUM *a)
+{
+    return a->top;
+}
+
+void bn_set_top(BIGNUM *a, int top)
+{
+    a->top = top;
+}
+
+int bn_get_dmax(const BIGNUM *a)
+{
+    return a->dmax;
+}
+
+void bn_set_all_zero(BIGNUM *a)
+{
+    int i;
+
+    for (i = a->top; i < a->dmax; i++) a->d[i] = 0;
+}
+
+int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
+{
+    if (in->top > size)
+        return 0;
+
+    memset(out, 0, sizeof(BN_ULONG) * size);
+    memcpy(out, in->d, sizeof(BN_ULONG) * in->top);
+    return 1;
+}
+
+BN_ULONG *bn_get_words(const BIGNUM *a)
+{
+    return a->d;
+}
+
+void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size)
+{
+    a->d = words;
+    a->dmax = a->top = size;
+    a->neg = 0;
+    a->flags |= BN_FLG_STATIC_DATA;
+}
+
+void bn_set_data(BIGNUM *a, const void *data, size_t size)
+{
+    memcpy(a->d, data, size);
+}
+
+size_t bn_sizeof_BIGNUM(void)
+{
+    return sizeof(BIGNUM);
+}
+
+BIGNUM *bn_array_el(BIGNUM *base, int el)
+{
+    return &base[el];
+}
+
+
+