1 /* 2 * Copyright 1995-2018 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 <assert.h> 11 #include "internal/cryptlib.h" 12 #include "bn_lcl.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_TBIT) ? 1 : 0; 38 } 39 if (c) { 40 *rp = 1; 41 r->top++; 42 } 43 bn_check_top(r); 44 return 1; 45 } 46 47 int BN_rshift1(BIGNUM *r, const BIGNUM *a) 48 { 49 BN_ULONG *ap, *rp, t, c; 50 int i, j; 51 52 bn_check_top(r); 53 bn_check_top(a); 54 55 if (BN_is_zero(a)) { 56 BN_zero(r); 57 return 1; 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) 64 return 0; 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; 78 if (!r->top) 79 r->neg = 0; /* don't allow negative zero */ 80 bn_check_top(r); 81 return 1; 82 } 83 84 int BN_lshift(BIGNUM *r, const BIGNUM *a, int n) 85 { 86 int ret; 87 88 if (n < 0) { 89 BNerr(BN_F_BN_LSHIFT, BN_R_INVALID_SHIFT); 90 return 0; 91 } 92 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 119 nw = n / BN_BITS2; 120 if (bn_wexpand(r, a->top + nw + 1) == NULL) 121 return 0; 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; 137 } 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; 147 r->top = a->top + nw + 1; 148 r->flags |= BN_FLG_FIXED_TOP; 149 150 return 1; 151 } 152 153 int BN_rshift(BIGNUM *r, const BIGNUM *a, int n) 154 { 155 int i, j, nw, lb, rb; 156 BN_ULONG *t, *f; 157 BN_ULONG l, tmp; 158 159 bn_check_top(r); 160 bn_check_top(a); 161 162 if (n < 0) { 163 BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT); 164 return 0; 165 } 166 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); 172 return 1; 173 } 174 i = (BN_num_bits(a) - n + (BN_BITS2 - 1)) / BN_BITS2; 175 if (r != a) { 176 if (bn_wexpand(r, i) == NULL) 177 return 0; 178 r->neg = a->neg; 179 } else { 180 if (n == 0) 181 return 1; /* or the copying loop will go berserk */ 182 } 183 184 f = &(a->d[nw]); 185 t = r->d; 186 j = a->top - nw; 187 r->top = i; 188 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 } 202 if (!r->top) 203 r->neg = 0; /* don't allow negative zero */ 204 bn_check_top(r); 205 return 1; 206 } 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 } 258