5481609d0fa80ed2495e73c442b4476f99ebcc0f
[openssl.git] / crypto / bn / bn_shift.c
1 /*
2  * Copyright 1995-2018 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 {
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
45 int 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
81 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
82 {
83     int ret;
84
85     if (n < 0) {
86         BNerr(BN_F_BN_LSHIFT, 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  */
104 int 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
150 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
151 {
152     int ret = 0;
153
154     if (n < 0) {
155         BNerr(BN_F_BN_RSHIFT, 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  */
173 int 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 }