1 /* $OpenBSD: bn_shift.c,v 1.22 2023/07/08 12:21:58 beck Exp $ */ 2 /* 3 * Copyright (c) 2022, 2023 Joel Sing <jsing@openbsd.org> 4 * 5 * Permission to use, copy, modify, and distribute this software for any 6 * purpose with or without fee is hereby granted, provided that the above 7 * copyright notice and this permission notice appear in all copies. 8 * 9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16 */ 17 18 #include <openssl/bn.h> 19 #include <openssl/err.h> 20 21 #include "bn_local.h" 22 23 static inline int 24 bn_lshift(BIGNUM *r, const BIGNUM *a, int n) 25 { 26 size_t count, shift_bits, shift_words; 27 size_t lshift, rshift; 28 ssize_t rstride; 29 BN_ULONG *dst, *src; 30 31 if (n < 0) { 32 BNerror(BN_R_INVALID_LENGTH); 33 return 0; 34 } 35 shift_bits = n; 36 37 /* 38 * Left bit shift, potentially across word boundaries. 39 * 40 * When shift is not an exact multiple of BN_BITS2, the bottom bits of 41 * the previous word need to be right shifted and combined with the left 42 * shifted bits using bitwise OR. If shift is an exact multiple of 43 * BN_BITS2, the source for the left and right shifts are the same 44 * and the shifts become zero bits (which is effectively a memmove). 45 */ 46 shift_words = shift_bits / BN_BITS2; 47 lshift = shift_bits % BN_BITS2; 48 rshift = (BN_BITS2 - lshift) % BN_BITS2; 49 rstride = 0 - (lshift + rshift) / BN_BITS2; 50 51 if (a->top < 1) { 52 BN_zero(r); 53 return 1; 54 } 55 56 count = a->top + shift_words + 1; 57 58 if (count < shift_words) 59 return 0; 60 61 if (!bn_wexpand(r, count)) 62 return 0; 63 64 src = a->d + a->top - 1; 65 dst = r->d + a->top + shift_words; 66 67 /* Handle right shift for top most word. */ 68 *dst = (*src >> rshift) & rstride; 69 dst--; 70 71 /* Handle left shift and right shift for remaining words. */ 72 while (src > a->d) { 73 *dst = *src << lshift | src[rstride] >> rshift; 74 src--; 75 dst--; 76 } 77 *dst = *src << lshift; 78 79 /* Zero any additional words resulting from the left shift. */ 80 while (dst > r->d) { 81 dst--; 82 *dst = 0; 83 } 84 85 r->top = count; 86 bn_correct_top(r); 87 88 BN_set_negative(r, a->neg); 89 90 return 1; 91 } 92 93 static inline int 94 bn_rshift(BIGNUM *r, const BIGNUM *a, int n) 95 { 96 size_t count, shift_bits, shift_words; 97 size_t lshift, rshift; 98 ssize_t lstride; 99 BN_ULONG *dst, *src; 100 size_t i; 101 102 if (n < 0) { 103 BNerror(BN_R_INVALID_LENGTH); 104 return 0; 105 } 106 shift_bits = n; 107 108 /* 109 * Right bit shift, potentially across word boundaries. 110 * 111 * When shift is not an exact multiple of BN_BITS2, the top bits of 112 * the next word need to be left shifted and combined with the right 113 * shifted bits using bitwise OR. If shift is an exact multiple of 114 * BN_BITS2, the source for the left and right shifts are the same 115 * and the shifts become zero (which is effectively a memmove). 116 */ 117 shift_words = shift_bits / BN_BITS2; 118 rshift = shift_bits % BN_BITS2; 119 lshift = (BN_BITS2 - rshift) % BN_BITS2; 120 lstride = (lshift + rshift) / BN_BITS2; 121 122 if (a->top <= shift_words) { 123 BN_zero(r); 124 return 1; 125 } 126 count = a->top - shift_words; 127 128 if (!bn_wexpand(r, count)) 129 return 0; 130 131 src = a->d + shift_words; 132 dst = r->d; 133 134 for (i = 1; i < count; i++) { 135 *dst = src[lstride] << lshift | *src >> rshift; 136 src++; 137 dst++; 138 } 139 *dst = *src >> rshift; 140 141 r->top = count; 142 bn_correct_top(r); 143 144 BN_set_negative(r, a->neg); 145 146 return 1; 147 } 148 149 int 150 BN_lshift1(BIGNUM *r, const BIGNUM *a) 151 { 152 return bn_lshift(r, a, 1); 153 } 154 LCRYPTO_ALIAS(BN_lshift1); 155 156 int 157 BN_lshift(BIGNUM *r, const BIGNUM *a, int n) 158 { 159 return bn_lshift(r, a, n); 160 } 161 LCRYPTO_ALIAS(BN_lshift); 162 163 int 164 BN_rshift1(BIGNUM *r, const BIGNUM *a) 165 { 166 return bn_rshift(r, a, 1); 167 } 168 LCRYPTO_ALIAS(BN_rshift1); 169 170 int 171 BN_rshift(BIGNUM *r, const BIGNUM *a, int n) 172 { 173 return bn_rshift(r, a, n); 174 } 175 LCRYPTO_ALIAS(BN_rshift); 176