• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /* Copyright (C) 1995-1998 Eric Young (eay@cryptsoft.com)
2  * All rights reserved.
3  *
4  * This package is an SSL implementation written
5  * by Eric Young (eay@cryptsoft.com).
6  * The implementation was written so as to conform with Netscapes SSL.
7  *
8  * This library is free for commercial and non-commercial use as long as
9  * the following conditions are aheared to.  The following conditions
10  * apply to all code found in this distribution, be it the RC4, RSA,
11  * lhash, DES, etc., code; not just the SSL code.  The SSL documentation
12  * included with this distribution is covered by the same copyright terms
13  * except that the holder is Tim Hudson (tjh@cryptsoft.com).
14  *
15  * Copyright remains Eric Young's, and as such any Copyright notices in
16  * the code are not to be removed.
17  * If this package is used in a product, Eric Young should be given attribution
18  * as the author of the parts of the library used.
19  * This can be in the form of a textual message at program startup or
20  * in documentation (online or textual) provided with the package.
21  *
22  * Redistribution and use in source and binary forms, with or without
23  * modification, are permitted provided that the following conditions
24  * are met:
25  * 1. Redistributions of source code must retain the copyright
26  *    notice, this list of conditions and the following disclaimer.
27  * 2. Redistributions in binary form must reproduce the above copyright
28  *    notice, this list of conditions and the following disclaimer in the
29  *    documentation and/or other materials provided with the distribution.
30  * 3. All advertising materials mentioning features or use of this software
31  *    must display the following acknowledgement:
32  *    "This product includes cryptographic software written by
33  *     Eric Young (eay@cryptsoft.com)"
34  *    The word 'cryptographic' can be left out if the rouines from the library
35  *    being used are not cryptographic related :-).
36  * 4. If you include any Windows specific code (or a derivative thereof) from
37  *    the apps directory (application code) you must include an acknowledgement:
38  *    "This product includes software written by Tim Hudson (tjh@cryptsoft.com)"
39  *
40  * THIS SOFTWARE IS PROVIDED BY ERIC YOUNG ``AS IS'' AND
41  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
43  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
44  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
46  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
47  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
48  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
49  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
50  * SUCH DAMAGE.
51  *
52  * The licence and distribution terms for any publically available version or
53  * derivative of this code cannot be changed.  i.e. this code cannot simply be
54  * copied and put under another distribution licence
55  * [including the GNU Public Licence.] */
56 
57 #include <openssl/bn.h>
58 
59 #include <string.h>
60 
61 #include <openssl/err.h>
62 #include <openssl/type_check.h>
63 
64 #include "internal.h"
65 
66 
BN_lshift(BIGNUM * r,const BIGNUM * a,int n)67 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) {
68   int i, nw, lb, rb;
69   BN_ULONG *t, *f;
70   BN_ULONG l;
71 
72   if (n < 0) {
73     OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
74     return 0;
75   }
76 
77   r->neg = a->neg;
78   nw = n / BN_BITS2;
79   if (!bn_wexpand(r, a->width + nw + 1)) {
80     return 0;
81   }
82   lb = n % BN_BITS2;
83   rb = BN_BITS2 - lb;
84   f = a->d;
85   t = r->d;
86   t[a->width + nw] = 0;
87   if (lb == 0) {
88     for (i = a->width - 1; i >= 0; i--) {
89       t[nw + i] = f[i];
90     }
91   } else {
92     for (i = a->width - 1; i >= 0; i--) {
93       l = f[i];
94       t[nw + i + 1] |= l >> rb;
95       t[nw + i] = l << lb;
96     }
97   }
98   OPENSSL_memset(t, 0, nw * sizeof(t[0]));
99   r->width = a->width + nw + 1;
100   bn_set_minimal_width(r);
101 
102   return 1;
103 }
104 
BN_lshift1(BIGNUM * r,const BIGNUM * a)105 int BN_lshift1(BIGNUM *r, const BIGNUM *a) {
106   BN_ULONG *ap, *rp, t, c;
107   int i;
108 
109   if (r != a) {
110     r->neg = a->neg;
111     if (!bn_wexpand(r, a->width + 1)) {
112       return 0;
113     }
114     r->width = a->width;
115   } else {
116     if (!bn_wexpand(r, a->width + 1)) {
117       return 0;
118     }
119   }
120   ap = a->d;
121   rp = r->d;
122   c = 0;
123   for (i = 0; i < a->width; i++) {
124     t = *(ap++);
125     *(rp++) = (t << 1) | c;
126     c = t >> (BN_BITS2 - 1);
127   }
128   if (c) {
129     *rp = 1;
130     r->width++;
131   }
132 
133   return 1;
134 }
135 
bn_rshift_words(BN_ULONG * r,const BN_ULONG * a,unsigned shift,size_t num)136 void bn_rshift_words(BN_ULONG *r, const BN_ULONG *a, unsigned shift,
137                      size_t num) {
138   unsigned shift_bits = shift % BN_BITS2;
139   size_t shift_words = shift / BN_BITS2;
140   if (shift_words >= num) {
141     OPENSSL_memset(r, 0, num * sizeof(BN_ULONG));
142     return;
143   }
144   if (shift_bits == 0) {
145     OPENSSL_memmove(r, a + shift_words, (num - shift_words) * sizeof(BN_ULONG));
146   } else {
147     for (size_t i = shift_words; i < num - 1; i++) {
148       r[i - shift_words] =
149           (a[i] >> shift_bits) | (a[i + 1] << (BN_BITS2 - shift_bits));
150     }
151     r[num - 1 - shift_words] = a[num - 1] >> shift_bits;
152   }
153   OPENSSL_memset(r + num - shift_words, 0, shift_words * sizeof(BN_ULONG));
154 }
155 
BN_rshift(BIGNUM * r,const BIGNUM * a,int n)156 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) {
157   if (n < 0) {
158     OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER);
159     return 0;
160   }
161 
162   if (!bn_wexpand(r, a->width)) {
163     return 0;
164   }
165   bn_rshift_words(r->d, a->d, n, a->width);
166   r->neg = a->neg;
167   r->width = a->width;
168   bn_set_minimal_width(r);
169   return 1;
170 }
171 
bn_rshift_secret_shift(BIGNUM * r,const BIGNUM * a,unsigned n,BN_CTX * ctx)172 int bn_rshift_secret_shift(BIGNUM *r, const BIGNUM *a, unsigned n,
173                            BN_CTX *ctx) {
174   int ret = 0;
175   BN_CTX_start(ctx);
176   BIGNUM *tmp = BN_CTX_get(ctx);
177   if (tmp == NULL ||
178       !BN_copy(r, a) ||
179       !bn_wexpand(tmp, r->width)) {
180     goto err;
181   }
182 
183   // Shift conditionally by powers of two.
184   unsigned max_bits = BN_BITS2 * r->width;
185   for (unsigned i = 0; (max_bits >> i) != 0; i++) {
186     BN_ULONG mask = (n >> i) & 1;
187     mask = 0 - mask;
188     bn_rshift_words(tmp->d, r->d, 1u << i, r->width);
189     bn_select_words(r->d, mask, tmp->d /* apply shift */,
190                     r->d /* ignore shift */, r->width);
191   }
192 
193   ret = 1;
194 
195 err:
196   BN_CTX_end(ctx);
197   return ret;
198 }
199 
bn_rshift1_words(BN_ULONG * r,const BN_ULONG * a,size_t num)200 void bn_rshift1_words(BN_ULONG *r, const BN_ULONG *a, size_t num) {
201   if (num == 0) {
202     return;
203   }
204   for (size_t i = 0; i < num - 1; i++) {
205     r[i] = (a[i] >> 1) | (a[i + 1] << (BN_BITS2 - 1));
206   }
207   r[num - 1] = a[num - 1] >> 1;
208 }
209 
BN_rshift1(BIGNUM * r,const BIGNUM * a)210 int BN_rshift1(BIGNUM *r, const BIGNUM *a) {
211   if (!bn_wexpand(r, a->width)) {
212     return 0;
213   }
214   bn_rshift1_words(r->d, a->d, a->width);
215   r->width = a->width;
216   r->neg = a->neg;
217   bn_set_minimal_width(r);
218   return 1;
219 }
220 
BN_set_bit(BIGNUM * a,int n)221 int BN_set_bit(BIGNUM *a, int n) {
222   if (n < 0) {
223     return 0;
224   }
225 
226   int i = n / BN_BITS2;
227   int j = n % BN_BITS2;
228   if (a->width <= i) {
229     if (!bn_wexpand(a, i + 1)) {
230       return 0;
231     }
232     for (int k = a->width; k < i + 1; k++) {
233       a->d[k] = 0;
234     }
235     a->width = i + 1;
236   }
237 
238   a->d[i] |= (((BN_ULONG)1) << j);
239 
240   return 1;
241 }
242 
BN_clear_bit(BIGNUM * a,int n)243 int BN_clear_bit(BIGNUM *a, int n) {
244   int i, j;
245 
246   if (n < 0) {
247     return 0;
248   }
249 
250   i = n / BN_BITS2;
251   j = n % BN_BITS2;
252   if (a->width <= i) {
253     return 0;
254   }
255 
256   a->d[i] &= (~(((BN_ULONG)1) << j));
257   bn_set_minimal_width(a);
258   return 1;
259 }
260 
bn_is_bit_set_words(const BN_ULONG * a,size_t num,unsigned bit)261 int bn_is_bit_set_words(const BN_ULONG *a, size_t num, unsigned bit) {
262   unsigned i = bit / BN_BITS2;
263   unsigned j = bit % BN_BITS2;
264   if (i >= num) {
265     return 0;
266   }
267   return (a[i] >> j) & 1;
268 }
269 
BN_is_bit_set(const BIGNUM * a,int n)270 int BN_is_bit_set(const BIGNUM *a, int n) {
271   if (n < 0) {
272     return 0;
273   }
274   return bn_is_bit_set_words(a->d, a->width, n);
275 }
276 
BN_mask_bits(BIGNUM * a,int n)277 int BN_mask_bits(BIGNUM *a, int n) {
278   if (n < 0) {
279     return 0;
280   }
281 
282   int w = n / BN_BITS2;
283   int b = n % BN_BITS2;
284   if (w >= a->width) {
285     return 1;
286   }
287   if (b == 0) {
288     a->width = w;
289   } else {
290     a->width = w + 1;
291     a->d[w] &= ~(BN_MASK2 << b);
292   }
293 
294   bn_set_minimal_width(a);
295   return 1;
296 }
297 
bn_count_low_zero_bits_word(BN_ULONG l)298 static int bn_count_low_zero_bits_word(BN_ULONG l) {
299   OPENSSL_STATIC_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
300                         "crypto_word_t is too small");
301   OPENSSL_STATIC_ASSERT(sizeof(int) <= sizeof(crypto_word_t),
302                         "crypto_word_t is too small");
303   OPENSSL_STATIC_ASSERT(BN_BITS2 == sizeof(BN_ULONG) * 8,
304                         "BN_ULONG has padding bits");
305   // C has very bizarre rules for types smaller than an int.
306   OPENSSL_STATIC_ASSERT(sizeof(BN_ULONG) >= sizeof(int),
307                         "BN_ULONG gets promoted to int");
308 
309   crypto_word_t mask;
310   int bits = 0;
311 
312 #if BN_BITS2 > 32
313   // Check if the lower half of |x| are all zero.
314   mask = constant_time_is_zero_w(l << (BN_BITS2 - 32));
315   // If the lower half is all zeros, it is included in the bit count and we
316   // count the upper half. Otherwise, we count the lower half.
317   bits += 32 & mask;
318   l = constant_time_select_w(mask, l >> 32, l);
319 #endif
320 
321   // The remaining blocks are analogous iterations at lower powers of two.
322   mask = constant_time_is_zero_w(l << (BN_BITS2 - 16));
323   bits += 16 & mask;
324   l = constant_time_select_w(mask, l >> 16, l);
325 
326   mask = constant_time_is_zero_w(l << (BN_BITS2 - 8));
327   bits += 8 & mask;
328   l = constant_time_select_w(mask, l >> 8, l);
329 
330   mask = constant_time_is_zero_w(l << (BN_BITS2 - 4));
331   bits += 4 & mask;
332   l = constant_time_select_w(mask, l >> 4, l);
333 
334   mask = constant_time_is_zero_w(l << (BN_BITS2 - 2));
335   bits += 2 & mask;
336   l = constant_time_select_w(mask, l >> 2, l);
337 
338   mask = constant_time_is_zero_w(l << (BN_BITS2 - 1));
339   bits += 1 & mask;
340 
341   return bits;
342 }
343 
BN_count_low_zero_bits(const BIGNUM * bn)344 int BN_count_low_zero_bits(const BIGNUM *bn) {
345   OPENSSL_STATIC_ASSERT(sizeof(BN_ULONG) <= sizeof(crypto_word_t),
346                         "crypto_word_t is too small");
347   OPENSSL_STATIC_ASSERT(sizeof(int) <= sizeof(crypto_word_t),
348                         "crypto_word_t is too small");
349 
350   int ret = 0;
351   crypto_word_t saw_nonzero = 0;
352   for (int i = 0; i < bn->width; i++) {
353     crypto_word_t nonzero = ~constant_time_is_zero_w(bn->d[i]);
354     crypto_word_t first_nonzero = ~saw_nonzero & nonzero;
355     saw_nonzero |= nonzero;
356 
357     int bits = bn_count_low_zero_bits_word(bn->d[i]);
358     ret |= first_nonzero & (i * BN_BITS2 + bits);
359   }
360 
361   // If got to the end of |bn| and saw no non-zero words, |bn| is zero. |ret|
362   // will then remain zero.
363   return ret;
364 }
365