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