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
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_BITS2 - 1);
38 }
39 *rp = c;
40 r->top += c;
41 bn_check_top(r);
42 return 1;
43 }
44
BN_rshift1(BIGNUM * r,const BIGNUM * a)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
BN_lshift(BIGNUM * r,const BIGNUM * a,int n)81 int 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 */
bn_lshift_fixed_top(BIGNUM * r,const BIGNUM * a,int n)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
BN_rshift(BIGNUM * r,const BIGNUM * a,int n)150 int 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 bn_check_top(r);
160 bn_check_top(a);
161
162 ret = bn_rshift_fixed_top(r, a, n);
163
164 bn_correct_top(r);
165 bn_check_top(r);
166
167 return ret;
168 }
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 */
bn_rshift_fixed_top(BIGNUM * r,const BIGNUM * a,int n)176 int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
177 {
178 int i, top, nw;
179 unsigned int lb, rb;
180 BN_ULONG *t, *f;
181 BN_ULONG l, m, mask;
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
