1251881Speter/* 2251881Speter * Copyright 1995-2020 The OpenSSL Project Authors. All Rights Reserved. 3251881Speter * 4251881Speter * Licensed under the Apache License 2.0 (the "License"). You may not use 5251881Speter * this file except in compliance with the License. You can obtain a copy 6251881Speter * in the file LICENSE in the source distribution or at 7251881Speter * https://www.openssl.org/source/license.html 8251881Speter */ 9251881Speter 10251881Speter#include <assert.h> 11251881Speter#include "internal/cryptlib.h" 12251881Speter#include "bn_local.h" 13251881Speter 14251881Speterint BN_lshift1(BIGNUM *r, const BIGNUM *a) 15251881Speter{ 16251881Speter register BN_ULONG *ap, *rp, t, c; 17251881Speter int i; 18251881Speter 19251881Speter bn_check_top(r); 20251881Speter bn_check_top(a); 21251881Speter 22251881Speter if (r != a) { 23251881Speter r->neg = a->neg; 24299742Sdim if (bn_wexpand(r, a->top + 1) == NULL) 25251881Speter return 0; 26251881Speter r->top = a->top; 27251881Speter } else { 28251881Speter if (bn_wexpand(r, a->top + 1) == NULL) 29251881Speter return 0; 30251881Speter } 31251881Speter ap = a->d; 32251881Speter rp = r->d; 33251881Speter c = 0; 34299742Sdim for (i = 0; i < a->top; i++) { 35251881Speter t = *(ap++); 36299742Sdim *(rp++) = ((t << 1) | c) & BN_MASK2; 37299742Sdim c = t >> (BN_BITS2 - 1); 38251881Speter } 39251881Speter *rp = c; 40251881Speter r->top += c; 41251881Speter bn_check_top(r); 42251881Speter return 1; 43251881Speter} 44251881Speter 45299742Sdimint BN_rshift1(BIGNUM *r, const BIGNUM *a) 46299742Sdim{ 47299742Sdim BN_ULONG *ap, *rp, t, c; 48299742Sdim int i; 49299742Sdim 50299742Sdim bn_check_top(r); 51299742Sdim bn_check_top(a); 52299742Sdim 53299742Sdim if (BN_is_zero(a)) { 54299742Sdim BN_zero(r); 55299742Sdim return 1; 56299742Sdim } 57299742Sdim i = a->top; 58299742Sdim ap = a->d; 59299742Sdim if (a != r) { 60299742Sdim if (bn_wexpand(r, i) == NULL) 61299742Sdim return 0; 62299742Sdim r->neg = a->neg; 63299742Sdim } 64299742Sdim rp = r->d; 65299742Sdim r->top = i; 66299742Sdim t = ap[--i]; 67299742Sdim rp[i] = t >> 1; 68299742Sdim c = t << (BN_BITS2 - 1); 69299742Sdim r->top -= (t == 1); 70299742Sdim while (i > 0) { 71299742Sdim t = ap[--i]; 72299742Sdim rp[i] = ((t >> 1) & BN_MASK2) | c; 73299742Sdim c = t << (BN_BITS2 - 1); 74299742Sdim } 75299742Sdim if (!r->top) 76299742Sdim r->neg = 0; /* don't allow negative zero */ 77299742Sdim bn_check_top(r); 78299742Sdim return 1; 79299742Sdim} 80299742Sdim 81299742Sdimint BN_lshift(BIGNUM *r, const BIGNUM *a, int n) 82299742Sdim{ 83299742Sdim int ret; 84299742Sdim 85299742Sdim if (n < 0) { 86299742Sdim ERR_raise(ERR_LIB_BN, BN_R_INVALID_SHIFT); 87299742Sdim return 0; 88299742Sdim } 89299742Sdim 90299742Sdim ret = bn_lshift_fixed_top(r, a, n); 91251881Speter 92299742Sdim bn_correct_top(r); 93299742Sdim bn_check_top(r); 94251881Speter 95299742Sdim return ret; 96299742Sdim} 97251881Speter 98299742Sdim/* 99299742Sdim * In respect to shift factor the execution time is invariant of 100299742Sdim * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition 101299742Sdim * for constant-time-ness is |n < BN_BITS2| or |n / BN_BITS2| being 102299742Sdim * non-secret. 103299742Sdim */ 104299742Sdimint bn_lshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n) 105299742Sdim{ 106299742Sdim int i, nw; 107299742Sdim unsigned int lb, rb; 108299742Sdim BN_ULONG *t, *f; 109299742Sdim BN_ULONG l, m, rmask = 0; 110299742Sdim 111299742Sdim assert(n >= 0); 112299742Sdim 113299742Sdim bn_check_top(r); 114299742Sdim bn_check_top(a); 115299742Sdim 116299742Sdim nw = n / BN_BITS2; 117299742Sdim if (bn_wexpand(r, a->top + nw + 1) == NULL) 118299742Sdim return 0; 119299742Sdim 120299742Sdim if (a->top != 0) { 121299742Sdim lb = (unsigned int)n % BN_BITS2; 122299742Sdim rb = BN_BITS2 - lb; 123299742Sdim rb %= BN_BITS2; /* say no to undefined behaviour */ 124299742Sdim rmask = (BN_ULONG)0 - rb; /* rmask = 0 - (rb != 0) */ 125299742Sdim rmask |= rmask >> 8; 126299742Sdim f = &(a->d[0]); 127299742Sdim t = &(r->d[nw]); 128299742Sdim l = f[a->top - 1]; 129299742Sdim t[a->top] = (l >> rb) & rmask; 130299742Sdim for (i = a->top - 1; i > 0; i--) { 131299742Sdim m = l << lb; 132299742Sdim l = f[i - 1]; 133299742Sdim t[i] = (m | ((l >> rb) & rmask)) & BN_MASK2; 134299742Sdim } 135299742Sdim t[0] = (l << lb) & BN_MASK2; 136299742Sdim } else { 137299742Sdim /* shouldn't happen, but formally required */ 138299742Sdim r->d[nw] = 0; 139299742Sdim } 140299742Sdim if (nw != 0) 141299742Sdim memset(r->d, 0, sizeof(*t) * nw); 142299742Sdim 143299742Sdim r->neg = a->neg; 144299742Sdim r->top = a->top + nw + 1; 145299742Sdim r->flags |= BN_FLG_FIXED_TOP; 146299742Sdim 147299742Sdim return 1; 148299742Sdim} 149299742Sdim 150251881Speterint BN_rshift(BIGNUM *r, const BIGNUM *a, int n) 151251881Speter{ 152251881Speter int ret = 0; 153251881Speter 154251881Speter if (n < 0) { 155299742Sdim ERR_raise(ERR_LIB_BN, BN_R_INVALID_SHIFT); 156251881Speter return 0; 157251881Speter } 158251881Speter 159251881Speter ret = bn_rshift_fixed_top(r, a, n); 160251881Speter 161251881Speter bn_correct_top(r); 162251881Speter bn_check_top(r); 163251881Speter 164251881Speter return ret; 165251881Speter} 166251881Speter 167251881Speter/* 168251881Speter * In respect to shift factor the execution time is invariant of 169251881Speter * |n % BN_BITS2|, but not |n / BN_BITS2|. Or in other words pre-condition 170251881Speter * for constant-time-ness for sufficiently[!] zero-padded inputs is 171251881Speter * |n < BN_BITS2| or |n / BN_BITS2| being non-secret. 172251881Speter */ 173251881Speterint bn_rshift_fixed_top(BIGNUM *r, const BIGNUM *a, int n) 174251881Speter{ 175251881Speter int i, top, nw; 176299742Sdim unsigned int lb, rb; 177299742Sdim BN_ULONG *t, *f; 178299742Sdim BN_ULONG l, m, mask; 179251881Speter 180251881Speter bn_check_top(r); 181251881Speter bn_check_top(a); 182251881Speter 183251881Speter assert(n >= 0); 184299742Sdim 185251881Speter nw = n / BN_BITS2; 186251881Speter if (nw >= a->top) { 187251881Speter /* shouldn't happen, but formally required */ 188251881Speter BN_zero(r); 189251881Speter return 1; 190251881Speter } 191251881Speter 192251881Speter rb = (unsigned int)n % BN_BITS2; 193251881Speter lb = BN_BITS2 - rb; 194251881Speter lb %= BN_BITS2; /* say no to undefined behaviour */ 195251881Speter mask = (BN_ULONG)0 - lb; /* mask = 0 - (lb != 0) */ 196251881Speter mask |= mask >> 8; 197251881Speter top = a->top - nw; 198251881Speter if (r != a && bn_wexpand(r, top) == NULL) 199251881Speter return 0; 200251881Speter 201251881Speter t = &(r->d[0]); 202299742Sdim f = &(a->d[nw]); 203299742Sdim l = f[0]; 204299742Sdim for (i = 0; i < top - 1; i++) { 205251881Speter m = f[i + 1]; 206299742Sdim t[i] = (l >> rb) | ((m << lb) & mask); 207251881Speter l = m; 208251881Speter } 209251881Speter t[i] = l >> rb; 210251881Speter 211251881Speter r->neg = a->neg; 212251881Speter r->top = top; 213251881Speter r->flags |= BN_FLG_FIXED_TOP; 214251881Speter 215251881Speter return 1; 216251881Speter} 217251881Speter