1/* 2 * Copyright 1995-2016 The OpenSSL Project Authors. All Rights Reserved. 3 * 4 * Licensed under the OpenSSL license (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 <openssl/bn.h> 11 12#include <assert.h> 13#include <string.h> 14 15#include <openssl/err.h> 16 17#include "internal.h" 18 19 20int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) { 21 int i, nw, lb, rb; 22 BN_ULONG *t, *f; 23 BN_ULONG l; 24 25 if (n < 0) { 26 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); 27 return 0; 28 } 29 30 r->neg = a->neg; 31 nw = n / BN_BITS2; 32 if (!bn_wexpand(r, a->width + nw + 1)) { 33 return 0; 34 } 35 lb = n % BN_BITS2; 36 rb = BN_BITS2 - lb; 37 f = a->d; 38 t = r->d; 39 t[a->width + nw] = 0; 40 if (lb == 0) { 41 for (i = a->width - 1; i >= 0; i--) { 42 t[nw + i] = f[i]; 43 } 44 } else { 45 for (i = a->width - 1; i >= 0; i--) { 46 l = f[i]; 47 t[nw + i + 1] |= l >> rb; 48 t[nw + i] = l << lb; 49 } 50 } 51 OPENSSL_memset(t, 0, nw * sizeof(t[0])); 52 r->width = a->width + nw + 1; 53 bn_set_minimal_width(r); 54 55 return 1; 56} 57 58int BN_lshift1(BIGNUM *r, const BIGNUM *a) { 59 BN_ULONG *ap, *rp, t, c; 60 int i; 61 62 if (r != a) { 63 r->neg = a->neg; 64 if (!bn_wexpand(r, a->width + 1)) { 65 return 0; 66 } 67 r->width = a->width; 68 } else { 69 if (!bn_wexpand(r, a->width + 1)) { 70 return 0; 71 } 72 } 73 ap = a->d; 74 rp = r->d; 75 c = 0; 76 for (i = 0; i < a->width; i++) { 77 t = *(ap++); 78 *(rp++) = (t << 1) | c; 79 c = t >> (BN_BITS2 - 1); 80 } 81 if (c) { 82 *rp = 1; 83 r->width++; 84 } 85 86 return 1; 87} 88 89void bn_rshift_words(BN_ULONG *r, const BN_ULONG *a, unsigned shift, 90 size_t num) { 91 unsigned shift_bits = shift % BN_BITS2; 92 size_t shift_words = shift / BN_BITS2; 93 if (shift_words >= num) { 94 OPENSSL_memset(r, 0, num * sizeof(BN_ULONG)); 95 return; 96 } 97 if (shift_bits == 0) { 98 OPENSSL_memmove(r, a + shift_words, (num - shift_words) * sizeof(BN_ULONG)); 99 } else { 100 for (size_t i = shift_words; i < num - 1; i++) { 101 r[i - shift_words] = 102 (a[i] >> shift_bits) | (a[i + 1] << (BN_BITS2 - shift_bits)); 103 } 104 r[num - 1 - shift_words] = a[num - 1] >> shift_bits; 105 } 106 OPENSSL_memset(r + num - shift_words, 0, shift_words * sizeof(BN_ULONG)); 107} 108 109int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) { 110 if (n < 0) { 111 OPENSSL_PUT_ERROR(BN, BN_R_NEGATIVE_NUMBER); 112 return 0; 113 } 114 115 if (!bn_wexpand(r, a->width)) { 116 return 0; 117 } 118 bn_rshift_words(r->d, a->d, n, a->width); 119 r->neg = a->neg; 120 r->width = a->width; 121 bn_set_minimal_width(r); 122 return 1; 123} 124 125int bn_rshift_secret_shift(BIGNUM *r, const BIGNUM *a, unsigned n, 126 BN_CTX *ctx) { 127 int ret = 0; 128 BN_CTX_start(ctx); 129 BIGNUM *tmp = BN_CTX_get(ctx); 130 unsigned max_bits; 131 if (tmp == NULL || !BN_copy(r, a) || !bn_wexpand(tmp, r->width)) { 132 goto err; 133 } 134 135 // Shift conditionally by powers of two. 136 max_bits = BN_BITS2 * r->width; 137 for (unsigned i = 0; (max_bits >> i) != 0; i++) { 138 BN_ULONG mask = (n >> i) & 1; 139 mask = 0 - mask; 140 bn_rshift_words(tmp->d, r->d, 1u << i, r->width); 141 bn_select_words(r->d, mask, tmp->d /* apply shift */, 142 r->d /* ignore shift */, r->width); 143 } 144 145 ret = 1; 146 147err: 148 BN_CTX_end(ctx); 149 return ret; 150} 151 152void bn_rshift1_words(BN_ULONG *r, const BN_ULONG *a, size_t num) { 153 if (num == 0) { 154 return; 155 } 156 for (size_t i = 0; i < num - 1; i++) { 157 r[i] = (a[i] >> 1) | (a[i + 1] << (BN_BITS2 - 1)); 158 } 159 r[num - 1] = a[num - 1] >> 1; 160} 161 162int BN_rshift1(BIGNUM *r, const BIGNUM *a) { 163 if (!bn_wexpand(r, a->width)) { 164 return 0; 165 } 166 bn_rshift1_words(r->d, a->d, a->width); 167 r->width = a->width; 168 r->neg = a->neg; 169 bn_set_minimal_width(r); 170 return 1; 171} 172 173int BN_set_bit(BIGNUM *a, int n) { 174 if (n < 0) { 175 return 0; 176 } 177 178 int i = n / BN_BITS2; 179 int j = n % BN_BITS2; 180 if (a->width <= i) { 181 if (!bn_wexpand(a, i + 1)) { 182 return 0; 183 } 184 for (int k = a->width; k < i + 1; k++) { 185 a->d[k] = 0; 186 } 187 a->width = i + 1; 188 } 189 190 a->d[i] |= (((BN_ULONG)1) << j); 191 192 return 1; 193} 194 195int BN_clear_bit(BIGNUM *a, int n) { 196 int i, j; 197 198 if (n < 0) { 199 return 0; 200 } 201 202 i = n / BN_BITS2; 203 j = n % BN_BITS2; 204 if (a->width <= i) { 205 return 0; 206 } 207 208 a->d[i] &= (~(((BN_ULONG)1) << j)); 209 bn_set_minimal_width(a); 210 return 1; 211} 212 213int bn_is_bit_set_words(const BN_ULONG *a, size_t num, size_t bit) { 214 size_t i = bit / BN_BITS2; 215 size_t j = bit % BN_BITS2; 216 if (i >= num) { 217 return 0; 218 } 219 return (a[i] >> j) & 1; 220} 221 222int BN_is_bit_set(const BIGNUM *a, int n) { 223 if (n < 0) { 224 return 0; 225 } 226 return bn_is_bit_set_words(a->d, a->width, n); 227} 228 229int BN_mask_bits(BIGNUM *a, int n) { 230 if (n < 0) { 231 return 0; 232 } 233 234 int w = n / BN_BITS2; 235 int b = n % BN_BITS2; 236 if (w >= a->width) { 237 return 1; 238 } 239 if (b == 0) { 240 a->width = w; 241 } else { 242 a->width = w + 1; 243 a->d[w] &= ~(BN_MASK2 << b); 244 } 245 246 bn_set_minimal_width(a); 247 return 1; 248} 249 250static int bn_count_low_zero_bits_word(BN_ULONG l) { 251 static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), 252 "crypto_word_t is too small"); 253 static_assert(sizeof(int) <= sizeof(crypto_word_t), 254 "crypto_word_t is too small"); 255 static_assert(BN_BITS2 == sizeof(BN_ULONG) * 8, "BN_ULONG has padding bits"); 256 // C has very bizarre rules for types smaller than an int. 257 static_assert(sizeof(BN_ULONG) >= sizeof(int), 258 "BN_ULONG gets promoted to int"); 259 260 crypto_word_t mask; 261 int bits = 0; 262 263#if BN_BITS2 > 32 264 // Check if the lower half of |x| are all zero. 265 mask = constant_time_is_zero_w(l << (BN_BITS2 - 32)); 266 // If the lower half is all zeros, it is included in the bit count and we 267 // count the upper half. Otherwise, we count the lower half. 268 bits += 32 & mask; 269 l = constant_time_select_w(mask, l >> 32, l); 270#endif 271 272 // The remaining blocks are analogous iterations at lower powers of two. 273 mask = constant_time_is_zero_w(l << (BN_BITS2 - 16)); 274 bits += 16 & mask; 275 l = constant_time_select_w(mask, l >> 16, l); 276 277 mask = constant_time_is_zero_w(l << (BN_BITS2 - 8)); 278 bits += 8 & mask; 279 l = constant_time_select_w(mask, l >> 8, l); 280 281 mask = constant_time_is_zero_w(l << (BN_BITS2 - 4)); 282 bits += 4 & mask; 283 l = constant_time_select_w(mask, l >> 4, l); 284 285 mask = constant_time_is_zero_w(l << (BN_BITS2 - 2)); 286 bits += 2 & mask; 287 l = constant_time_select_w(mask, l >> 2, l); 288 289 mask = constant_time_is_zero_w(l << (BN_BITS2 - 1)); 290 bits += 1 & mask; 291 292 return bits; 293} 294 295int BN_count_low_zero_bits(const BIGNUM *bn) { 296 static_assert(sizeof(BN_ULONG) <= sizeof(crypto_word_t), 297 "crypto_word_t is too small"); 298 static_assert(sizeof(int) <= sizeof(crypto_word_t), 299 "crypto_word_t is too small"); 300 301 int ret = 0; 302 crypto_word_t saw_nonzero = 0; 303 for (int i = 0; i < bn->width; i++) { 304 crypto_word_t nonzero = ~constant_time_is_zero_w(bn->d[i]); 305 crypto_word_t first_nonzero = ~saw_nonzero & nonzero; 306 saw_nonzero |= nonzero; 307 308 int bits = bn_count_low_zero_bits_word(bn->d[i]); 309 ret |= first_nonzero & (i * BN_BITS2 + bits); 310 } 311 312 // If got to the end of |bn| and saw no non-zero words, |bn| is zero. |ret| 313 // will then remain zero. 314 return ret; 315} 316