Coverage Report

Created: 2024-11-21 07:03

/src/openssl/crypto/bn/bn_shift.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 1995-2024 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 <assert.h>
11
#include "internal/cryptlib.h"
12
#include "bn_local.h"
13
14
int BN_lshift1(BIGNUM *r, const BIGNUM *a)
15
1.52M
{
16
1.52M
    register BN_ULONG *ap, *rp, t, c;
17
1.52M
    int i;
18
19
1.52M
    bn_check_top(r);
20
1.52M
    bn_check_top(a);
21
22
1.52M
    if (r != a) {
23
484k
        r->neg = a->neg;
24
484k
        if (bn_wexpand(r, a->top + 1) == NULL)
25
0
            return 0;
26
484k
        r->top = a->top;
27
1.03M
    } else {
28
1.03M
        if (bn_wexpand(r, a->top + 1) == NULL)
29
0
            return 0;
30
1.03M
    }
31
1.52M
    ap = a->d;
32
1.52M
    rp = r->d;
33
1.52M
    c = 0;
34
12.5M
    for (i = 0; i < a->top; i++) {
35
11.0M
        t = *(ap++);
36
11.0M
        *(rp++) = ((t << 1) | c) & BN_MASK2;
37
11.0M
        c = t >> (BN_BITS2 - 1);
38
11.0M
    }
39
1.52M
    *rp = c;
40
1.52M
    r->top += c;
41
1.52M
    bn_check_top(r);
42
1.52M
    return 1;
43
1.52M
}
44
45
int BN_rshift1(BIGNUM *r, const BIGNUM *a)
46
2.92M
{
47
2.92M
    BN_ULONG *ap, *rp, t, c;
48
2.92M
    int i;
49
50
2.92M
    bn_check_top(r);
51
2.92M
    bn_check_top(a);
52
53
2.92M
    if (BN_is_zero(a)) {
54
181k
        BN_zero(r);
55
181k
        return 1;
56
181k
    }
57
2.73M
    i = a->top;
58
2.73M
    ap = a->d;
59
2.73M
    if (a != r) {
60
30.4k
        if (bn_wexpand(r, i) == NULL)
61
0
            return 0;
62
30.4k
        r->neg = a->neg;
63
30.4k
    }
64
2.73M
    rp = r->d;
65
2.73M
    r->top = i;
66
2.73M
    t = ap[--i];
67
2.73M
    rp[i] = t >> 1;
68
2.73M
    c = t << (BN_BITS2 - 1);
69
2.73M
    r->top -= (t == 1);
70
16.4M
    while (i > 0) {
71
13.6M
        t = ap[--i];
72
13.6M
        rp[i] = ((t >> 1) & BN_MASK2) | c;
73
13.6M
        c = t << (BN_BITS2 - 1);
74
13.6M
    }
75
2.73M
    if (!r->top)
76
0
        r->neg = 0; /* don't allow negative zero */
77
2.73M
    bn_check_top(r);
78
2.73M
    return 1;
79
2.73M
}
80
81
int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
82
1.45M
{
83
1.45M
    int ret;
84
85
1.45M
    if (n < 0) {
86
0
        ERR_raise(ERR_LIB_BN, BN_R_INVALID_SHIFT);
87
0
        return 0;
88
0
    }
89
90
1.45M
    ret = bn_lshift_fixed_top(r, a, n);
91
92
1.45M
    bn_correct_top(r);
93
1.45M
    bn_check_top(r);
94
95
1.45M
    return ret;
96
1.45M
}
97
98
/*
99
 * In respect to shift factor the execution time is invariant of
100
 * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
101
 * for constant-time-ness is |n < BN_BITS2| or |n / BN_BITS2| being
102
 * non-secret.
103
 */
104
int bn_lshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
105
2.62M
{
106
2.62M
    int i, nw;
107
2.62M
    unsigned int lb, rb;
108
2.62M
    BN_ULONG *t, *f;
109
2.62M
    BN_ULONG l, m, rmask = 0;
110
111
2.62M
    assert(n >= 0);
112
113
2.62M
    bn_check_top(r);
114
2.62M
    bn_check_top(a);
115
116
2.62M
    nw = n / BN_BITS2;
117
2.62M
    if (bn_wexpand(r, a->top + nw + 1) == NULL)
118
0
        return 0;
119
120
2.62M
    if (a->top != 0) {
121
2.62M
        lb = (unsigned int)n % BN_BITS2;
122
2.62M
        rb = BN_BITS2 - lb;
123
2.62M
        rb %= BN_BITS2;            /* say no to undefined behaviour */
124
2.62M
        rmask = (BN_ULONG)0 - rb;  /* rmask = 0 - (rb != 0) */
125
2.62M
        rmask |= rmask >> 8;
126
2.62M
        f = &(a->d[0]);
127
2.62M
        t = &(r->d[nw]);
128
2.62M
        l = f[a->top - 1];
129
2.62M
        t[a->top] = (l >> rb) & rmask;
130
55.0M
        for (i = a->top - 1; i > 0; i--) {
131
52.3M
            m = l << lb;
132
52.3M
            l = f[i - 1];
133
52.3M
            t[i] = (m | ((l >> rb) & rmask)) & BN_MASK2;
134
52.3M
        }
135
2.62M
        t[0] = (l << lb) & BN_MASK2;
136
2.62M
    } else {
137
        /* shouldn't happen, but formally required */
138
2.75k
        r->d[nw] = 0;
139
2.75k
    }
140
2.62M
    if (nw != 0)
141
838k
        memset(r->d, 0, sizeof(*t) * nw);
142
143
2.62M
    r->neg = a->neg;
144
2.62M
    r->top = a->top + nw + 1;
145
2.62M
    r->flags |= BN_FLG_FIXED_TOP;
146
147
2.62M
    return 1;
148
2.62M
}
149
150
int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
151
2.97M
{
152
2.97M
    int ret = 0;
153
154
2.97M
    if (n < 0) {
155
0
        ERR_raise(ERR_LIB_BN, BN_R_INVALID_SHIFT);
156
0
        return 0;
157
0
    }
158
159
2.97M
    bn_check_top(r);
160
2.97M
    bn_check_top(a);
161
162
2.97M
    ret = bn_rshift_fixed_top(r, a, n);
163
164
2.97M
    bn_correct_top(r);
165
2.97M
    bn_check_top(r);
166
167
2.97M
    return ret;
168
2.97M
}
169
170
/*
171
 * In respect to shift factor the execution time is invariant of
172
 * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
173
 * for constant-time-ness for sufficiently[!] zero-padded inputs is
174
 * |n < BN_BITS2| or |n / BN_BITS2| being non-secret.
175
 */
176
int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
177
4.11M
{
178
4.11M
    int i, top, nw;
179
4.11M
    unsigned int lb, rb;
180
4.11M
    BN_ULONG *t, *f;
181
4.11M
    BN_ULONG l, m, mask;
182
183
4.11M
    assert(n >= 0);
184
185
4.11M
    nw = n / BN_BITS2;
186
4.11M
    if (nw >= a->top) {
187
        /* shouldn't happen, but formally required */
188
465
        BN_zero(r);
189
465
        return 1;
190
465
    }
191
192
4.11M
    rb = (unsigned int)n % BN_BITS2;
193
4.11M
    lb = BN_BITS2 - rb;
194
4.11M
    lb %= BN_BITS2;            /* say no to undefined behaviour */
195
4.11M
    mask = (BN_ULONG)0 - lb;   /* mask = 0 - (lb != 0) */
196
4.11M
    mask |= mask >> 8;
197
4.11M
    top = a->top - nw;
198
4.11M
    if (r != a && bn_wexpand(r, top) == NULL)
199
0
        return 0;
200
201
4.11M
    t = &(r->d[0]);
202
4.11M
    f = &(a->d[nw]);
203
4.11M
    l = f[0];
204
77.5M
    for (i = 0; i < top - 1; i++) {
205
73.4M
        m = f[i + 1];
206
73.4M
        t[i] = (l >> rb) | ((m << lb) & mask);
207
73.4M
        l = m;
208
73.4M
    }
209
4.11M
    t[i] = l >> rb;
210
211
4.11M
    r->neg = a->neg;
212
4.11M
    r->top = top;
213
4.11M
    r->flags |= BN_FLG_FIXED_TOP;
214
215
4.11M
    return 1;
216
4.11M
}