1 /*
2 * Copyright 1995-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 <assert.h>
11 #include "internal/cryptlib.h"
12 #include "bn_lcl.h"
13
BN_lshift1(BIGNUM * r,const BIGNUM * a)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_TBIT) ? 1 : 0;
38 }
39 if (c) {
40 *rp = 1;
41 r->top++;
42 }
43 bn_check_top(r);
44 return 1;
45 }
46
BN_rshift1(BIGNUM * r,const BIGNUM * a)47 int BN_rshift1(BIGNUM *r, const BIGNUM *a)
48 {
49 BN_ULONG *ap, *rp, t, c;
50 int i, j;
51
52 bn_check_top(r);
53 bn_check_top(a);
54
55 if (BN_is_zero(a)) {
56 BN_zero(r);
57 return 1;
58 }
59 i = a->top;
60 ap = a->d;
61 j = i - (ap[i - 1] == 1);
62 if (a != r) {
63 if (bn_wexpand(r, j) == NULL)
64 return 0;
65 r->neg = a->neg;
66 }
67 rp = r->d;
68 t = ap[--i];
69 c = (t & 1) ? BN_TBIT : 0;
70 if (t >>= 1)
71 rp[i] = t;
72 while (i > 0) {
73 t = ap[--i];
74 rp[i] = ((t >> 1) & BN_MASK2) | c;
75 c = (t & 1) ? BN_TBIT : 0;
76 }
77 r->top = j;
78 if (!r->top)
79 r->neg = 0; /* don't allow negative zero */
80 bn_check_top(r);
81 return 1;
82 }
83
BN_lshift(BIGNUM * r,const BIGNUM * a,int n)84 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n)
85 {
86 int ret;
87
88 if (n < 0) {
89 BNerr(BN_F_BN_LSHIFT, BN_R_INVALID_SHIFT);
90 return 0;
91 }
92
93 ret = bn_lshift_fixed_top(r, a, n);
94
95 bn_correct_top(r);
96 bn_check_top(r);
97
98 return ret;
99 }
100
101 /*
102 * In respect to shift factor the execution time is invariant of
103 * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
104 * for constant-time-ness is |n < BN_BITS2| or |n / BN_BITS2| being
105 * non-secret.
106 */
bn_lshift_fixed_top(BIGNUM * r,const BIGNUM * a,int n)107 int bn_lshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
108 {
109 int i, nw;
110 unsigned int lb, rb;
111 BN_ULONG *t, *f;
112 BN_ULONG l, m, rmask = 0;
113
114 assert(n >= 0);
115
116 bn_check_top(r);
117 bn_check_top(a);
118
119 nw = n / BN_BITS2;
120 if (bn_wexpand(r, a->top + nw + 1) == NULL)
121 return 0;
122
123 if (a->top != 0) {
124 lb = (unsigned int)n % BN_BITS2;
125 rb = BN_BITS2 - lb;
126 rb %= BN_BITS2; /* say no to undefined behaviour */
127 rmask = (BN_ULONG)0 - rb; /* rmask = 0 - (rb != 0) */
128 rmask |= rmask >> 8;
129 f = &(a->d[0]);
130 t = &(r->d[nw]);
131 l = f[a->top - 1];
132 t[a->top] = (l >> rb) & rmask;
133 for (i = a->top - 1; i > 0; i--) {
134 m = l << lb;
135 l = f[i - 1];
136 t[i] = (m | ((l >> rb) & rmask)) & BN_MASK2;
137 }
138 t[0] = (l << lb) & BN_MASK2;
139 } else {
140 /* shouldn't happen, but formally required */
141 r->d[nw] = 0;
142 }
143 if (nw != 0)
144 memset(r->d, 0, sizeof(*t) * nw);
145
146 r->neg = a->neg;
147 r->top = a->top + nw + 1;
148 r->flags |= BN_FLG_FIXED_TOP;
149
150 return 1;
151 }
152
BN_rshift(BIGNUM * r,const BIGNUM * a,int n)153 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n)
154 {
155 int i, j, nw, lb, rb;
156 BN_ULONG *t, *f;
157 BN_ULONG l, tmp;
158
159 bn_check_top(r);
160 bn_check_top(a);
161
162 if (n < 0) {
163 BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);
164 return 0;
165 }
166
167 nw = n / BN_BITS2;
168 rb = n % BN_BITS2;
169 lb = BN_BITS2 - rb;
170 if (nw >= a->top || a->top == 0) {
171 BN_zero(r);
172 return 1;
173 }
174 i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2;
175 if (r != a) {
176 if (bn_wexpand(r, i) == NULL)
177 return 0;
178 r->neg = a->neg;
179 } else {
180 if (n == 0)
181 return 1; /* or the copying loop will go berserk */
182 }
183
184 f = &(a->d[nw]);
185 t = r->d;
186 j = a->top - nw;
187 r->top = i;
188
189 if (rb == 0) {
190 for (i = j; i != 0; i--)
191 *(t++) = *(f++);
192 } else {
193 l = *(f++);
194 for (i = j - 1; i != 0; i--) {
195 tmp = (l >> rb) & BN_MASK2;
196 l = *(f++);
197 *(t++) = (tmp | (l << lb)) & BN_MASK2;
198 }
199 if ((l = (l >> rb) & BN_MASK2))
200 *(t) = l;
201 }
202 if (!r->top)
203 r->neg = 0; /* don't allow negative zero */
204 bn_check_top(r);
205 return 1;
206 }
207
208 /*
209 * In respect to shift factor the execution time is invariant of
210 * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
211 * for constant-time-ness for sufficiently[!] zero-padded inputs is
212 * |n < BN_BITS2| or |n / BN_BITS2| being non-secret.
213 */
bn_rshift_fixed_top(BIGNUM * r,const BIGNUM * a,int n)214 int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
215 {
216 int i, top, nw;
217 unsigned int lb, rb;
218 BN_ULONG *t, *f;
219 BN_ULONG l, m, mask;
220
221 bn_check_top(r);
222 bn_check_top(a);
223
224 assert(n >= 0);
225
226 nw = n / BN_BITS2;
227 if (nw >= a->top) {
228 /* shouldn't happen, but formally required */
229 BN_zero(r);
230 return 1;
231 }
232
233 rb = (unsigned int)n % BN_BITS2;
234 lb = BN_BITS2 - rb;
235 lb %= BN_BITS2; /* say no to undefined behaviour */
236 mask = (BN_ULONG)0 - lb; /* mask = 0 - (lb != 0) */
237 mask |= mask >> 8;
238 top = a->top - nw;
239 if (r != a && bn_wexpand(r, top) == NULL)
240 return 0;
241
242 t = &(r->d[0]);
243 f = &(a->d[nw]);
244 l = f[0];
245 for (i = 0; i < top - 1; i++) {
246 m = f[i + 1];
247 t[i] = (l >> rb) | ((m << lb) & mask);
248 l = m;
249 }
250 t[i] = l >> rb;
251
252 r->neg = a->neg;
253 r->top = top;
254 r->flags |= BN_FLG_FIXED_TOP;
255
256 return 1;
257 }
258