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
bn_lshift(BIGNUM * r,const BIGNUM * a,int n)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
bn_rshift(BIGNUM * r,const BIGNUM * a,int n)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
BN_lshift1(BIGNUM * r,const BIGNUM * a)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
BN_lshift(BIGNUM * r,const BIGNUM * a,int n)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
BN_rshift1(BIGNUM * r,const BIGNUM * a)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
BN_rshift(BIGNUM * r,const BIGNUM * a,int n)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