1 /* 2 * Copyright 1995-2024 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 ERR_raise(ERR_LIB_BN, 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 ERR_raise(ERR_LIB_BN, BN_R_INVALID_SHIFT); 156 return 0; 157 } 158 159 bn_check_top(r); 160 bn_check_top(a); 161 162 ret = bn_rshift_fixed_top(r, a, n); 163 164 bn_correct_top(r); 165 bn_check_top(r); 166 167 return ret; 168 } 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 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