]>
Commit | Line | Data |
---|---|---|
4f22f405 | 1 | /* |
3a4a88f4 | 2 | * Copyright 1995-2018 The OpenSSL Project Authors. All Rights Reserved. |
d02b48c6 | 3 | * |
367ace68 | 4 | * Licensed under the Apache License 2.0 (the "License"). You may not use |
4f22f405 RS |
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 | |
d02b48c6 RE |
8 | */ |
9 | ||
3a4a88f4 | 10 | #include <assert.h> |
b39fc560 | 11 | #include "internal/cryptlib.h" |
706457b7 | 12 | #include "bn_local.h" |
d02b48c6 | 13 | |
020fc820 | 14 | int BN_lshift1(BIGNUM *r, const BIGNUM *a) |
0f113f3e MC |
15 | { |
16 | register BN_ULONG *ap, *rp, t, c; | |
17 | int i; | |
d02b48c6 | 18 | |
0f113f3e MC |
19 | bn_check_top(r); |
20 | bn_check_top(a); | |
18f62d4b | 21 | |
0f113f3e MC |
22 | if (r != a) { |
23 | r->neg = a->neg; | |
24 | if (bn_wexpand(r, a->top + 1) == NULL) | |
26a7d938 | 25 | return 0; |
0f113f3e MC |
26 | r->top = a->top; |
27 | } else { | |
28 | if (bn_wexpand(r, a->top + 1) == NULL) | |
26a7d938 | 29 | return 0; |
0f113f3e MC |
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); | |
208fb891 | 44 | return 1; |
0f113f3e | 45 | } |
d02b48c6 | 46 | |
020fc820 | 47 | int BN_rshift1(BIGNUM *r, const BIGNUM *a) |
0f113f3e MC |
48 | { |
49 | BN_ULONG *ap, *rp, t, c; | |
50 | int i, j; | |
d02b48c6 | 51 | |
0f113f3e MC |
52 | bn_check_top(r); |
53 | bn_check_top(a); | |
18f62d4b | 54 | |
0f113f3e MC |
55 | if (BN_is_zero(a)) { |
56 | BN_zero(r); | |
208fb891 | 57 | return 1; |
0f113f3e MC |
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) | |
26a7d938 | 64 | return 0; |
0f113f3e MC |
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; | |
0a2dcb69 RL |
78 | if (!r->top) |
79 | r->neg = 0; /* don't allow negative zero */ | |
0f113f3e | 80 | bn_check_top(r); |
208fb891 | 81 | return 1; |
0f113f3e | 82 | } |
d02b48c6 | 83 | |
84c15db5 | 84 | int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) |
0f113f3e | 85 | { |
3a4a88f4 | 86 | int ret; |
18f62d4b | 87 | |
7cc18d81 MC |
88 | if (n < 0) { |
89 | BNerr(BN_F_BN_LSHIFT, BN_R_INVALID_SHIFT); | |
90 | return 0; | |
91 | } | |
92 | ||
3a4a88f4 AP |
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 | */ | |
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 | ||
0f113f3e MC |
119 | nw = n / BN_BITS2; |
120 | if (bn_wexpand(r, a->top + nw + 1) == NULL) | |
26a7d938 | 121 | return 0; |
3a4a88f4 AP |
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; | |
0f113f3e | 137 | } |
3a4a88f4 AP |
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; | |
0f113f3e | 147 | r->top = a->top + nw + 1; |
3a4a88f4 AP |
148 | r->flags |= BN_FLG_FIXED_TOP; |
149 | ||
208fb891 | 150 | return 1; |
0f113f3e | 151 | } |
d02b48c6 | 152 | |
020fc820 | 153 | int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) |
0f113f3e MC |
154 | { |
155 | int i, j, nw, lb, rb; | |
156 | BN_ULONG *t, *f; | |
157 | BN_ULONG l, tmp; | |
d02b48c6 | 158 | |
0f113f3e MC |
159 | bn_check_top(r); |
160 | bn_check_top(a); | |
18f62d4b | 161 | |
7cc18d81 MC |
162 | if (n < 0) { |
163 | BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT); | |
164 | return 0; | |
165 | } | |
166 | ||
0f113f3e MC |
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); | |
208fb891 | 172 | return 1; |
0f113f3e MC |
173 | } |
174 | i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2; | |
175 | if (r != a) { | |
0f113f3e | 176 | if (bn_wexpand(r, i) == NULL) |
26a7d938 | 177 | return 0; |
38d1b3cc | 178 | r->neg = a->neg; |
0f113f3e MC |
179 | } else { |
180 | if (n == 0) | |
181 | return 1; /* or the copying loop will go berserk */ | |
182 | } | |
d02b48c6 | 183 | |
0f113f3e MC |
184 | f = &(a->d[nw]); |
185 | t = r->d; | |
186 | j = a->top - nw; | |
187 | r->top = i; | |
d02b48c6 | 188 | |
0f113f3e MC |
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 | } | |
38d1b3cc GT |
202 | if (!r->top) |
203 | r->neg = 0; /* don't allow negative zero */ | |
0f113f3e | 204 | bn_check_top(r); |
208fb891 | 205 | return 1; |
0f113f3e | 206 | } |
3a4a88f4 AP |
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 | */ | |
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 | } |