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 | } |
217 | |