Error checking and memory leak fixes in NISTZ256.
[openssl.git] / crypto / bn / bn_intern.c
1 /* ====================================================================
2  * Copyright (c) 1998-2014 The OpenSSL Project.  All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  *
11  * 2. Redistributions in binary form must reproduce the above copyright
12  *    notice, this list of conditions and the following disclaimer in
13  *    the documentation and/or other materials provided with the
14  *    distribution.
15  *
16  * 3. All advertising materials mentioning features or use of this
17  *    software must display the following acknowledgment:
18  *    "This product includes software developed by the OpenSSL Project
19  *    for use in the OpenSSL Toolkit. (http://www.openssl.org/)"
20  *
21  * 4. The names "OpenSSL Toolkit" and "OpenSSL Project" must not be used to
22  *    endorse or promote products derived from this software without
23  *    prior written permission. For written permission, please contact
24  *    openssl-core@openssl.org.
25  *
26  * 5. Products derived from this software may not be called "OpenSSL"
27  *    nor may "OpenSSL" appear in their names without prior written
28  *    permission of the OpenSSL Project.
29  *
30  * 6. Redistributions of any form whatsoever must retain the following
31  *    acknowledgment:
32  *    "This product includes software developed by the OpenSSL Project
33  *    for use in the OpenSSL Toolkit (http://www.openssl.org/)"
34  *
35  * THIS SOFTWARE IS PROVIDED BY THE OpenSSL PROJECT ``AS IS'' AND ANY
36  * EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
38  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OpenSSL PROJECT OR
39  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
41  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
42  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
43  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
44  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
45  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
46  * OF THE POSSIBILITY OF SUCH DAMAGE.
47  * ====================================================================
48  *
49  * This product includes cryptographic software written by Eric Young
50  * (eay@cryptsoft.com).  This product includes software written by Tim
51  * Hudson (tjh@cryptsoft.com).
52  *
53  */
54
55 #include "cryptlib.h"
56 #include "bn_lcl.h"
57
58 /*
59  * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
60  * This is an array  r[]  of values that are either zero or odd with an
61  * absolute value less than  2^w  satisfying
62  *     scalar = \sum_j r[j]*2^j
63  * where at most one of any  w+1  consecutive digits is non-zero
64  * with the exception that the most significant digit may be only
65  * w-1 zeros away from that next non-zero digit.
66  */
67 signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
68 {
69     int window_val;
70     int ok = 0;
71     signed char *r = NULL;
72     int sign = 1;
73     int bit, next_bit, mask;
74     size_t len = 0, j;
75
76     if (BN_is_zero(scalar)) {
77         r = OPENSSL_malloc(1);
78         if (!r) {
79             BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
80             goto err;
81         }
82         r[0] = 0;
83         *ret_len = 1;
84         return r;
85     }
86
87     if (w <= 0 || w > 7) {      /* 'signed char' can represent integers with
88                                  * absolute values less than 2^7 */
89         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
90         goto err;
91     }
92     bit = 1 << w;               /* at most 128 */
93     next_bit = bit << 1;        /* at most 256 */
94     mask = next_bit - 1;        /* at most 255 */
95
96     if (BN_is_negative(scalar)) {
97         sign = -1;
98     }
99
100     if (scalar->d == NULL || scalar->top == 0) {
101         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
102         goto err;
103     }
104
105     len = BN_num_bits(scalar);
106     r = OPENSSL_malloc(len + 1); /*
107                                   * Modified wNAF may be one digit longer than binary representation
108                                   * (*ret_len will be set to the actual length, i.e. at most
109                                   * BN_num_bits(scalar) + 1)
110                                   */
111     if (r == NULL) {
112         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
113         goto err;
114     }
115     window_val = scalar->d[0] & mask;
116     j = 0;
117     while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
118                                                       * window_val will not
119                                                       * increase */
120         int digit = 0;
121
122         /* 0 <= window_val <= 2^(w+1) */
123
124         if (window_val & 1) {
125             /* 0 < window_val < 2^(w+1) */
126
127             if (window_val & bit) {
128                 digit = window_val - next_bit; /* -2^w < digit < 0 */
129
130 #if 1                           /* modified wNAF */
131                 if (j + w + 1 >= len) {
132                     /*
133                      * Special case for generating modified wNAFs:
134                      * no new bits will be added into window_val,
135                      * so using a positive digit here will decrease
136                      * the total length of the representation
137                      */
138
139                     digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
140                 }
141 #endif
142             } else {
143                 digit = window_val; /* 0 < digit < 2^w */
144             }
145
146             if (digit <= -bit || digit >= bit || !(digit & 1)) {
147                 BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
148                 goto err;
149             }
150
151             window_val -= digit;
152
153             /*
154              * now window_val is 0 or 2^(w+1) in standard wNAF generation;
155              * for modified window NAFs, it may also be 2^w
156              */
157             if (window_val != 0 && window_val != next_bit
158                 && window_val != bit) {
159                 BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
160                 goto err;
161             }
162         }
163
164         r[j++] = sign * digit;
165
166         window_val >>= 1;
167         window_val += bit * BN_is_bit_set(scalar, j + w);
168
169         if (window_val > next_bit) {
170             BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
171             goto err;
172         }
173     }
174
175     if (j > len + 1) {
176         BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
177         goto err;
178     }
179     len = j;
180     ok = 1;
181
182  err:
183     if (!ok) {
184         OPENSSL_free(r);
185         r = NULL;
186     }
187     if (ok)
188         *ret_len = len;
189     return r;
190 }
191
192 int bn_get_top(const BIGNUM *a)
193 {
194     return a->top;
195 }
196
197 void bn_set_top(BIGNUM *a, int top)
198 {
199     a->top = top;
200 }
201
202 int bn_get_dmax(const BIGNUM *a)
203 {
204     return a->dmax;
205 }
206
207 void bn_set_all_zero(BIGNUM *a)
208 {
209     int i;
210
211     for (i = a->top; i < a->dmax; i++)
212         a->d[i] = 0;
213 }
214
215 int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
216 {
217     if (in->top > size)
218         return 0;
219
220     memset(out, 0, sizeof(BN_ULONG) * size);
221     memcpy(out, in->d, sizeof(BN_ULONG) * in->top);
222     return 1;
223 }
224
225 BN_ULONG *bn_get_words(const BIGNUM *a)
226 {
227     return a->d;
228 }
229
230 void bn_set_static_words(BIGNUM *a, BN_ULONG *words, int size)
231 {
232     a->d = words;
233     a->dmax = a->top = size;
234     a->neg = 0;
235     a->flags |= BN_FLG_STATIC_DATA;
236     bn_correct_top(a);
237 }
238
239 int bn_set_words(BIGNUM *a, BN_ULONG *words, int num_words)
240 {
241     if (bn_wexpand(a, num_words) == NULL) {
242         BNerr(BN_F_BN_SET_WORDS, ERR_R_MALLOC_FAILURE);
243         return 0;
244     }
245
246     memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
247     a->top = num_words;
248     bn_correct_top(a);
249     return 1;
250 }
251
252 size_t bn_sizeof_BIGNUM(void)
253 {
254     return sizeof(BIGNUM);
255 }
256
257 BIGNUM *bn_array_el(BIGNUM *base, int el)
258 {
259     return &base[el];
260 }