Coverage Report

Created: 2023-06-08 06:41

/src/openssl111/crypto/bn/bn_intern.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2014-2018 The OpenSSL Project Authors. All Rights Reserved.
3
 *
4
 * Licensed under the OpenSSL license (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
 */
22
signed char *bn_compute_wNAF(const BIGNUM *scalar, int w, size_t *ret_len)
23
0
{
24
0
    int window_val;
25
0
    signed char *r = NULL;
26
0
    int sign = 1;
27
0
    int bit, next_bit, mask;
28
0
    size_t len = 0, j;
29
30
0
    if (BN_is_zero(scalar)) {
31
0
        r = OPENSSL_malloc(1);
32
0
        if (r == NULL) {
33
0
            BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
34
0
            goto err;
35
0
        }
36
0
        r[0] = 0;
37
0
        *ret_len = 1;
38
0
        return r;
39
0
    }
40
41
0
    if (w <= 0 || w > 7) {      /* 'signed char' can represent integers with
42
                                 * absolute values less than 2^7 */
43
0
        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
44
0
        goto err;
45
0
    }
46
0
    bit = 1 << w;               /* at most 128 */
47
0
    next_bit = bit << 1;        /* at most 256 */
48
0
    mask = next_bit - 1;        /* at most 255 */
49
50
0
    if (BN_is_negative(scalar)) {
51
0
        sign = -1;
52
0
    }
53
54
0
    if (scalar->d == NULL || scalar->top == 0) {
55
0
        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
56
0
        goto err;
57
0
    }
58
59
0
    len = BN_num_bits(scalar);
60
0
    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
0
    if (r == NULL) {
66
0
        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_MALLOC_FAILURE);
67
0
        goto err;
68
0
    }
69
0
    window_val = scalar->d[0] & mask;
70
0
    j = 0;
71
0
    while ((window_val != 0) || (j + w + 1 < len)) { /* if j+w+1 >= len,
72
                                                      * window_val will not
73
                                                      * increase */
74
0
        int digit = 0;
75
76
        /* 0 <= window_val <= 2^(w+1) */
77
78
0
        if (window_val & 1) {
79
            /* 0 < window_val < 2^(w+1) */
80
81
0
            if (window_val & bit) {
82
0
                digit = window_val - next_bit; /* -2^w < digit < 0 */
83
84
0
#if 1                           /* modified wNAF */
85
0
                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
0
                    digit = window_val & (mask >> 1); /* 0 < digit < 2^w */
94
0
                }
95
0
#endif
96
0
            } else {
97
0
                digit = window_val; /* 0 < digit < 2^w */
98
0
            }
99
100
0
            if (digit <= -bit || digit >= bit || !(digit & 1)) {
101
0
                BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
102
0
                goto err;
103
0
            }
104
105
0
            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
0
            if (window_val != 0 && window_val != next_bit
112
0
                && window_val != bit) {
113
0
                BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
114
0
                goto err;
115
0
            }
116
0
        }
117
118
0
        r[j++] = sign * digit;
119
120
0
        window_val >>= 1;
121
0
        window_val += bit * BN_is_bit_set(scalar, j + w);
122
123
0
        if (window_val > next_bit) {
124
0
            BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
125
0
            goto err;
126
0
        }
127
0
    }
128
129
0
    if (j > len + 1) {
130
0
        BNerr(BN_F_BN_COMPUTE_WNAF, ERR_R_INTERNAL_ERROR);
131
0
        goto err;
132
0
    }
133
0
    *ret_len = j;
134
0
    return r;
135
136
0
 err:
137
0
    OPENSSL_free(r);
138
0
    return NULL;
139
0
}
140
141
int bn_get_top(const BIGNUM *a)
142
12.9k
{
143
12.9k
    return a->top;
144
12.9k
}
145
146
int bn_get_dmax(const BIGNUM *a)
147
0
{
148
0
    return a->dmax;
149
0
}
150
151
void bn_set_all_zero(BIGNUM *a)
152
0
{
153
0
    int i;
154
155
0
    for (i = a->top; i < a->dmax; i++)
156
0
        a->d[i] = 0;
157
0
}
158
159
int bn_copy_words(BN_ULONG *out, const BIGNUM *in, int size)
160
5.67k
{
161
5.67k
    if (in->top > size)
162
0
        return 0;
163
164
5.67k
    memset(out, 0, sizeof(*out) * size);
165
5.67k
    if (in->d != NULL)
166
5.66k
        memcpy(out, in->d, sizeof(*out) * in->top);
167
5.67k
    return 1;
168
5.67k
}
169
170
BN_ULONG *bn_get_words(const BIGNUM *a)
171
10.9k
{
172
10.9k
    return a->d;
173
10.9k
}
174
175
void bn_set_static_words(BIGNUM *a, const BN_ULONG *words, int size)
176
0
{
177
    /*
178
     * |const| qualifier omission is compensated by BN_FLG_STATIC_DATA
179
     * flag, which effectively means "read-only data".
180
     */
181
0
    a->d = (BN_ULONG *)words;
182
0
    a->dmax = a->top = size;
183
0
    a->neg = 0;
184
0
    a->flags |= BN_FLG_STATIC_DATA;
185
0
    bn_correct_top(a);
186
0
}
187
188
int bn_set_words(BIGNUM *a, const BN_ULONG *words, int num_words)
189
7.01k
{
190
7.01k
    if (bn_wexpand(a, num_words) == NULL) {
191
0
        BNerr(BN_F_BN_SET_WORDS, ERR_R_MALLOC_FAILURE);
192
0
        return 0;
193
0
    }
194
195
7.01k
    memcpy(a->d, words, sizeof(BN_ULONG) * num_words);
196
7.01k
    a->top = num_words;
197
7.01k
    bn_correct_top(a);
198
7.01k
    return 1;
199
7.01k
}