1/*
2 * Copyright 2014-2020 The OpenSSL Project Authors. All Rights Reserved.
3 *
4 * Licensed under the Apache License 2.0 (the "License").  You may not use
5 * this file except in compliance with the License.  You can obtain a copy
6 * in the file LICENSE in the source distribution or at
7 * https://www.openssl.org/source/license.html
8 */
9
10#include "internal/cryptlib.h"
11#include "bn_local.h"
12
13/*
14 * Determine the modified width-(w+1) Non-Adjacent Form (wNAF) of 'scalar'.
15 * This is an array  r[]  of values that are either zero or odd with an
16 * absolute value less than  2^w  satisfying
17 *     scalar = \sum_j r[j]*2^j
18 * where at most one of any  w+1  consecutive digits is non-zero
19 * with the exception that the most significant digit may be only
20 * w-1 zeros away from that next non-zero digit.
21 */
22signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
23{
24    int window_val;
25    signed char *r = NULL;
26    int sign = 1;
27    int bit, next_bit, mask;
28    size_t len = 0, j;
29
30    if (BN_is_zero(scalar)) {
31        r = OPENSSL_malloc(1);
32        if (r == NULL) {
33            ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE);
34            goto err;
35        }
36        r[0] = 0;
37        *ret_len = 1;
38        return r;
39    }
40
41    if (w <= 0 || w > 7) {      /* 'signed char' can represent integers with
42                                 * absolute values less than 2^7 */
43        ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
44        goto err;
45    }
46    bit = 1 << w;               /* at most 128 */
47    next_bit = bit << 1;        /* at most 256 */
48    mask = next_bit - 1;        /* at most 255 */
49
50    if (BN_is_negative(scalar)) {
51        sign = -1;
52    }
53
54    if (scalar->d == NULL || scalar->top == 0) {
55        ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
56        goto err;
57    }
58
59    len = BN_num_bits(scalar);
60    r = OPENSSL_malloc(len + 1); /*
61                                  * Modified wNAF may be one digit longer than binary representation
62                                  * (*ret_len will be set to the actual length, i.e. at most
63                                  * BN_num_bits(scalar) + 1)
64                                  */
65    if (r == NULL) {
66        ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE);
67        goto err;
68    }
69    window_val = scalar->d[0] & mask;
70    j = 0;
71    while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
72                                                      * window_val will not
73                                                      * increase */
74        int digit = 0;
75
76        /* 0 <= window_val <= 2^(w+1) */
77
78        if (window_val & 1) {
79            /* 0 < window_val < 2^(w+1) */
80
81            if (window_val & bit) {
82                digit = window_val - next_bit; /* -2^w < digit < 0 */
83
84#if 1                           /* modified wNAF */
85                if (j + w + 1 >= len) {
86                    /*
87                     * Special case for generating modified wNAFs:
88                     * no new bits will be added into window_val,
89                     * so using a positive digit here will decrease
90                     * the total length of the representation
91                     */
92
93                    digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
94                }
95#endif
96            } else {
97                digit = window_val; /* 0 < digit < 2^w */
98            }
99
100            if (digit <= -bit || digit >= bit || !(digit & 1)) {
101                ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
102                goto err;
103            }
104
105            window_val -= digit;
106
107            /*
108             * now window_val is 0 or 2^(w+1) in standard wNAF generation;
109             * for modified window NAFs, it may also be 2^w
110             */
111            if (window_val != 0 && window_val != next_bit
112                && window_val != bit) {
113                ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
114                goto err;
115            }
116        }
117
118        r[j++] = sign * digit;
119
120        window_val >>= 1;
121        window_val += bit * BN_is_bit_set(scalar, j + w);
122
123        if (window_val > next_bit) {
124            ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
125            goto err;
126        }
127    }
128
129    if (j > len + 1) {
130        ERR_raise(ERR_LIB_BN, ERR_R_INTERNAL_ERROR);
131        goto err;
132    }
133    *ret_len = j;
134    return r;
135
136 err:
137    OPENSSL_free(r);
138    return NULL;
139}
140
141int bn_get_top(const BIGNUM *a)
142{
143    return a->top;
144}
145
146int bn_get_dmax(const BIGNUM *a)
147{
148    return a->dmax;
149}
150
151void bn_set_all_zero(BIGNUM *a)
152{
153    int i;
154
155    for (i = a->top; i < a->dmax; i++)
156        a->d[i] = 0;
157}
158
159int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
160{
161    if (in->top > size)
162        return 0;
163
164    memset(out, 0, sizeof(*out) * size);
165    if (in->d != NULL)
166        memcpy(out, in->d, sizeof(*out) * in->top);
167    return 1;
168}
169
170BN_ULONG *bn_get_words(const BIGNUM *a)
171{
172    return a->d;
173}
174
175void bn_set_static_words(BIGNUM *a, const BN_ULONG *words, int size)
176{
177    /*
178     * |const| qualifier omission is compensated by BN_FLG_STATIC_DATA
179     * flag, which effectively means "read-only data".
180     */
181    a->d = (BN_ULONG *)words;
182    a->dmax = a->top = size;
183    a->neg = 0;
184    a->flags |= BN_FLG_STATIC_DATA;
185    bn_correct_top(a);
186}
187
188int bn_set_words(BIGNUM *a, const BN_ULONG *words, int num_words)
189{
190    if (bn_wexpand(a, num_words) == NULL) {
191        ERR_raise(ERR_LIB_BN, ERR_R_MALLOC_FAILURE);
192        return 0;
193    }
194
195    memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
196    a->top = num_words;
197    bn_correct_top(a);
198    return 1;
199}
200