]>
Commit | Line | Data |
---|---|---|
0f113f3e | 1 | /* |
4f22f405 | 2 | * Copyright 1998-2016 The OpenSSL Project Authors. All Rights Reserved. |
0f113f3e | 3 | * |
4f22f405 RS |
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 | |
535b9b57 BM |
8 | */ |
9 | ||
b39fc560 | 10 | #include "internal/cryptlib.h" |
535b9b57 BM |
11 | #include "bn_lcl.h" |
12 | ||
5acaa495 | 13 | int BN_nnmod(BIGNUM *r, const BIGNUM *m, const BIGNUM *d, BN_CTX *ctx) |
0f113f3e MC |
14 | { |
15 | /* | |
16 | * like BN_mod, but returns non-negative remainder (i.e., 0 <= r < |d| | |
17 | * always holds) | |
18 | */ | |
19 | ||
20 | if (!(BN_mod(r, m, d, ctx))) | |
21 | return 0; | |
22 | if (!r->neg) | |
23 | return 1; | |
24 | /* now -|d| < r < 0, so we have to set r := r + |d| */ | |
25 | return (d->neg ? BN_sub : BN_add) (r, r, d); | |
535b9b57 BM |
26 | } |
27 | ||
0f113f3e MC |
28 | int BN_mod_add(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
29 | BN_CTX *ctx) | |
30 | { | |
31 | if (!BN_add(r, a, b)) | |
32 | return 0; | |
33 | return BN_nnmod(r, r, m, ctx); | |
34 | } | |
535b9b57 | 35 | |
0f113f3e MC |
36 | /* |
37 | * BN_mod_add variant that may be used if both a and b are non-negative and | |
3fc7a9b9 AP |
38 | * less than m. The original algorithm was |
39 | * | |
40 | * if (!BN_uadd(r, a, b)) | |
41 | * return 0; | |
42 | * if (BN_ucmp(r, m) >= 0) | |
43 | * return BN_usub(r, r, m); | |
44 | * | |
45 | * which is replaced with addition, subtracting modulus, and conditional | |
46 | * move depending on whether or not subtraction borrowed. | |
0f113f3e | 47 | */ |
3fc7a9b9 AP |
48 | int bn_mod_add_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
49 | const BIGNUM *m) | |
0f113f3e | 50 | { |
3fc7a9b9 AP |
51 | size_t i, ai, bi, mtop = m->top; |
52 | BN_ULONG storage[1024 / BN_BITS2]; | |
53 | BN_ULONG carry, temp, mask, *rp, *tp = storage; | |
54 | const BN_ULONG *ap, *bp; | |
55 | ||
56 | if (bn_wexpand(r, mtop) == NULL) | |
0f113f3e | 57 | return 0; |
3fc7a9b9 AP |
58 | |
59 | if (mtop > sizeof(storage) / sizeof(storage[0]) | |
60 | && (tp = OPENSSL_malloc(mtop * sizeof(BN_ULONG))) == NULL) | |
fcc4ee09 | 61 | return 0; |
3fc7a9b9 AP |
62 | |
63 | ap = a->d != NULL ? a->d : tp; | |
64 | bp = b->d != NULL ? b->d : tp; | |
65 | ||
66 | for (i = 0, ai = 0, bi = 0, carry = 0; i < mtop;) { | |
67 | mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); | |
68 | temp = ((ap[ai] & mask) + carry) & BN_MASK2; | |
69 | carry = (temp < carry); | |
70 | ||
71 | mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); | |
72 | tp[i] = ((bp[bi] & mask) + temp) & BN_MASK2; | |
73 | carry += (tp[i] < temp); | |
74 | ||
75 | i++; | |
76 | ai += (i - a->dmax) >> (8 * sizeof(i) - 1); | |
77 | bi += (i - b->dmax) >> (8 * sizeof(i) - 1); | |
78 | } | |
79 | rp = r->d; | |
80 | carry -= bn_sub_words(rp, tp, m->d, mtop); | |
81 | for (i = 0; i < mtop; i++) { | |
82 | rp[i] = (carry & tp[i]) | (~carry & rp[i]); | |
83 | ((volatile BN_ULONG *)tp)[i] = 0; | |
84 | } | |
85 | r->top = mtop; | |
fcc4ee09 | 86 | r->flags |= BN_FLG_FIXED_TOP; |
70a579ae | 87 | r->neg = 0; |
3fc7a9b9 AP |
88 | |
89 | if (tp != storage) | |
90 | OPENSSL_free(tp); | |
91 | ||
0f113f3e MC |
92 | return 1; |
93 | } | |
5acaa495 | 94 | |
3fc7a9b9 AP |
95 | int BN_mod_add_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, |
96 | const BIGNUM *m) | |
97 | { | |
98 | int ret = bn_mod_add_fixed_top(r, a, b, m); | |
99 | ||
100 | if (ret) | |
101 | bn_correct_top(r); | |
102 | ||
103 | return ret; | |
104 | } | |
105 | ||
0f113f3e MC |
106 | int BN_mod_sub(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
107 | BN_CTX *ctx) | |
108 | { | |
109 | if (!BN_sub(r, a, b)) | |
110 | return 0; | |
111 | return BN_nnmod(r, r, m, ctx); | |
112 | } | |
535b9b57 | 113 | |
fcc4ee09 AP |
114 | /* |
115 | * BN_mod_sub variant that may be used if both a and b are non-negative, | |
116 | * a is less than m, while b is of same bit width as m. It's implemented | |
117 | * as subtraction followed by two conditional additions. | |
118 | * | |
119 | * 0 <= a < m | |
120 | * 0 <= b < 2^w < 2*m | |
121 | * | |
122 | * after subtraction | |
123 | * | |
124 | * -2*m < r = a - b < m | |
125 | * | |
126 | * Thus it takes up to two conditional additions to make |r| positive. | |
127 | */ | |
128 | int bn_mod_sub_fixed_top(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | |
129 | const BIGNUM *m) | |
130 | { | |
131 | size_t i, ai, bi, mtop = m->top; | |
132 | BN_ULONG borrow, carry, ta, tb, mask, *rp; | |
133 | const BN_ULONG *ap, *bp; | |
134 | ||
135 | if (bn_wexpand(r, mtop) == NULL) | |
136 | return 0; | |
137 | ||
138 | rp = r->d; | |
139 | ap = a->d != NULL ? a->d : rp; | |
140 | bp = b->d != NULL ? b->d : rp; | |
141 | ||
142 | for (i = 0, ai = 0, bi = 0, borrow = 0; i < mtop;) { | |
143 | mask = (BN_ULONG)0 - ((i - a->top) >> (8 * sizeof(i) - 1)); | |
144 | ta = ap[ai] & mask; | |
145 | ||
146 | mask = (BN_ULONG)0 - ((i - b->top) >> (8 * sizeof(i) - 1)); | |
147 | tb = bp[bi] & mask; | |
148 | rp[i] = ta - tb - borrow; | |
149 | if (ta != tb) | |
150 | borrow = (ta < tb); | |
151 | ||
152 | i++; | |
153 | ai += (i - a->dmax) >> (8 * sizeof(i) - 1); | |
154 | bi += (i - b->dmax) >> (8 * sizeof(i) - 1); | |
155 | } | |
156 | ap = m->d; | |
157 | for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) { | |
158 | ta = ((ap[i] & mask) + carry) & BN_MASK2; | |
159 | carry = (ta < carry); | |
160 | rp[i] = (rp[i] + ta) & BN_MASK2; | |
161 | carry += (rp[i] < ta); | |
162 | } | |
163 | borrow -= carry; | |
164 | for (i = 0, mask = 0 - borrow, carry = 0; i < mtop; i++) { | |
165 | ta = ((ap[i] & mask) + carry) & BN_MASK2; | |
166 | carry = (ta < carry); | |
167 | rp[i] = (rp[i] + ta) & BN_MASK2; | |
168 | carry += (rp[i] < ta); | |
169 | } | |
170 | ||
171 | r->top = mtop; | |
172 | r->flags |= BN_FLG_FIXED_TOP; | |
173 | r->neg = 0; | |
174 | ||
175 | return 1; | |
176 | } | |
177 | ||
0f113f3e MC |
178 | /* |
179 | * BN_mod_sub variant that may be used if both a and b are non-negative and | |
180 | * less than m | |
181 | */ | |
182 | int BN_mod_sub_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, | |
183 | const BIGNUM *m) | |
184 | { | |
185 | if (!BN_sub(r, a, b)) | |
186 | return 0; | |
187 | if (r->neg) | |
188 | return BN_add(r, r, m); | |
189 | return 1; | |
190 | } | |
535b9b57 BM |
191 | |
192 | /* slow but works */ | |
5acaa495 | 193 | int BN_mod_mul(BIGNUM *r, const BIGNUM *a, const BIGNUM *b, const BIGNUM *m, |
0f113f3e MC |
194 | BN_CTX *ctx) |
195 | { | |
196 | BIGNUM *t; | |
197 | int ret = 0; | |
198 | ||
199 | bn_check_top(a); | |
200 | bn_check_top(b); | |
201 | bn_check_top(m); | |
202 | ||
203 | BN_CTX_start(ctx); | |
204 | if ((t = BN_CTX_get(ctx)) == NULL) | |
205 | goto err; | |
206 | if (a == b) { | |
207 | if (!BN_sqr(t, a, ctx)) | |
208 | goto err; | |
209 | } else { | |
210 | if (!BN_mul(t, a, b, ctx)) | |
211 | goto err; | |
212 | } | |
213 | if (!BN_nnmod(r, t, m, ctx)) | |
214 | goto err; | |
215 | bn_check_top(r); | |
216 | ret = 1; | |
217 | err: | |
218 | BN_CTX_end(ctx); | |
26a7d938 | 219 | return ret; |
0f113f3e | 220 | } |
535b9b57 | 221 | |
5acaa495 | 222 | int BN_mod_sqr(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) |
0f113f3e MC |
223 | { |
224 | if (!BN_sqr(r, a, ctx)) | |
225 | return 0; | |
226 | /* r->neg == 0, thus we don't need BN_nnmod */ | |
227 | return BN_mod(r, r, m, ctx); | |
228 | } | |
5acaa495 BM |
229 | |
230 | int BN_mod_lshift1(BIGNUM *r, const BIGNUM *a, const BIGNUM *m, BN_CTX *ctx) | |
0f113f3e MC |
231 | { |
232 | if (!BN_lshift1(r, a)) | |
233 | return 0; | |
234 | bn_check_top(r); | |
235 | return BN_nnmod(r, r, m, ctx); | |
236 | } | |
5acaa495 | 237 | |
0f113f3e MC |
238 | /* |
239 | * BN_mod_lshift1 variant that may be used if a is non-negative and less than | |
240 | * m | |
241 | */ | |
5acaa495 | 242 | int BN_mod_lshift1_quick(BIGNUM *r, const BIGNUM *a, const BIGNUM *m) |
0f113f3e MC |
243 | { |
244 | if (!BN_lshift1(r, a)) | |
245 | return 0; | |
246 | bn_check_top(r); | |
247 | if (BN_cmp(r, m) >= 0) | |
248 | return BN_sub(r, r, m); | |
249 | return 1; | |
250 | } | |
5acaa495 | 251 | |
0f113f3e MC |
252 | int BN_mod_lshift(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m, |
253 | BN_CTX *ctx) | |
254 | { | |
255 | BIGNUM *abs_m = NULL; | |
256 | int ret; | |
5acaa495 | 257 | |
0f113f3e MC |
258 | if (!BN_nnmod(r, a, m, ctx)) |
259 | return 0; | |
5acaa495 | 260 | |
0f113f3e MC |
261 | if (m->neg) { |
262 | abs_m = BN_dup(m); | |
263 | if (abs_m == NULL) | |
264 | return 0; | |
265 | abs_m->neg = 0; | |
266 | } | |
5acaa495 | 267 | |
0f113f3e MC |
268 | ret = BN_mod_lshift_quick(r, r, n, (abs_m ? abs_m : m)); |
269 | bn_check_top(r); | |
5acaa495 | 270 | |
23a1d5e9 | 271 | BN_free(abs_m); |
0f113f3e MC |
272 | return ret; |
273 | } | |
5acaa495 | 274 | |
0f113f3e MC |
275 | /* |
276 | * BN_mod_lshift variant that may be used if a is non-negative and less than | |
277 | * m | |
278 | */ | |
5acaa495 | 279 | int BN_mod_lshift_quick(BIGNUM *r, const BIGNUM *a, int n, const BIGNUM *m) |
0f113f3e MC |
280 | { |
281 | if (r != a) { | |
282 | if (BN_copy(r, a) == NULL) | |
283 | return 0; | |
284 | } | |
285 | ||
286 | while (n > 0) { | |
287 | int max_shift; | |
288 | ||
289 | /* 0 < r < m */ | |
290 | max_shift = BN_num_bits(m) - BN_num_bits(r); | |
291 | /* max_shift >= 0 */ | |
292 | ||
293 | if (max_shift < 0) { | |
294 | BNerr(BN_F_BN_MOD_LSHIFT_QUICK, BN_R_INPUT_NOT_REDUCED); | |
295 | return 0; | |
296 | } | |
297 | ||
298 | if (max_shift > n) | |
299 | max_shift = n; | |
300 | ||
301 | if (max_shift) { | |
302 | if (!BN_lshift(r, r, max_shift)) | |
303 | return 0; | |
304 | n -= max_shift; | |
305 | } else { | |
306 | if (!BN_lshift1(r, r)) | |
307 | return 0; | |
308 | --n; | |
309 | } | |
310 | ||
311 | /* BN_num_bits(r) <= BN_num_bits(m) */ | |
312 | ||
313 | if (BN_cmp(r, m) >= 0) { | |
314 | if (!BN_sub(r, r, m)) | |
315 | return 0; | |
316 | } | |
317 | } | |
318 | bn_check_top(r); | |
319 | ||
320 | return 1; | |
321 | } |