]>
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 | 154 | { |
8eba6de5 | 155 | int ret = 0; |
18f62d4b | 156 | |
7cc18d81 MC |
157 | if (n < 0) { |
158 | BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT); | |
159 | return 0; | |
160 | } | |
161 | ||
8eba6de5 | 162 | ret = bn_rshift_fixed_top(r, a, n); |
d02b48c6 | 163 | |
8eba6de5 | 164 | bn_correct_top(r); |
0f113f3e | 165 | bn_check_top(r); |
8eba6de5 CPG |
166 | |
167 | return ret; | |
0f113f3e | 168 | } |
3a4a88f4 AP |
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 | */ | |
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 | bn_check_top(r); | |
184 | bn_check_top(a); | |
185 | ||
186 | assert(n >= 0); | |
187 | ||
188 | nw = n / BN_BITS2; | |
189 | if (nw >= a->top) { | |
190 | /* shouldn't happen, but formally required */ | |
191 | BN_zero(r); | |
192 | return 1; | |
193 | } | |
194 | ||
195 | rb = (unsigned int)n % BN_BITS2; | |
196 | lb = BN_BITS2 - rb; | |
197 | lb %= BN_BITS2; /* say no to undefined behaviour */ | |
198 | mask = (BN_ULONG)0 - lb; /* mask = 0 - (lb != 0) */ | |
199 | mask |= mask >> 8; | |
200 | top = a->top - nw; | |
201 | if (r != a && bn_wexpand(r, top) == NULL) | |
202 | return 0; | |
203 | ||
204 | t = &(r->d[0]); | |
205 | f = &(a->d[nw]); | |
206 | l = f[0]; | |
207 | for (i = 0; i < top - 1; i++) { | |
208 | m = f[i + 1]; | |
209 | t[i] = (l >> rb) | ((m << lb) & mask); | |
210 | l = m; | |
211 | } | |
212 | t[i] = l >> rb; | |
213 | ||
214 | r->neg = a->neg; | |
215 | r->top = top; | |
216 | r->flags |= BN_FLG_FIXED_TOP; | |
217 | ||
218 | return 1; | |
219 | } |