crypto/bn/bn_shift.c

   1 /*
   2  * Copyright 1995-2018 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         BNerr(BN_F_BN_LSHIFT, 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         BNerr(BN_F_BN_RSHIFT, BN_R_INVALID_SHIFT);
 156         return 0;
 157     }
 158
 159     ret = bn_rshift_fixed_top(r, a, n);
 160
 161     bn_correct_top(r);
 162     bn_check_top(r);
 163
 164     return ret;
 165 }
 166
 167 /*
 168  * In respect to shift factor the execution time is invariant of
 169  * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition
 170  * for constant-time-ness for sufficiently[!] zero-padded inputs is
 171  * |n < BN_BITS2| or |n / BN_BITS2| being non-secret.
 172  */
 173 int bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n)
 174 {
 175     int i, top, nw;
 176     unsigned int lb, rb;
 177     BN_ULONG *t, *f;
 178     BN_ULONG l, m, mask;
 179
 180     bn_check_top(r);
 181     bn_check_top(a);
 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 }