crypto/bn/bn_shift.c

   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 }